Meni

Uvod u strukture podataka na C ++

introduction data structures c

Isprobajte Naš Instrument Za Uklanjanje Problema

Uvodni vodič o strukturama podataka na C ++.

„Struktura podataka može se definirati kao organizirana zbirka podataka koja pomaže programu da pristupi podacima učinkovito i brzo, tako da cijeli program može funkcionirati na učinkovit način. “

Znamo da su u programskom svijetu podaci središte i da se sve vrti oko podataka. Moramo izvršiti sve podatkovne operacije, uključujući pohranu, pretraživanje, sortiranje, organiziranje i pristup podacima, i samo tada naš program može uspjeti.

=> Pogledajte ovdje kako biste istražili cjeloviti popis vodiča za C ++.

Uvod u strukture podataka na C ++ (1)

Što ćete naučiti:

Pregled

Moramo pronaći najučinkovitiji način pohrane podataka koji nam može pomoći u izgradnji dinamičkih rješenja. Struktura podataka pomaže nam u izgradnji takvih rješenja.

Tijekom organiziranja ili raspoređivanja podataka u strukture, moramo osigurati da raspored predstavlja gotovo stvarni objekt. Kao drugo, ovaj aranžman trebao bi biti dovoljno jednostavan da mu svatko može lako pristupiti i obraditi ga kad god je potrebno.

U ovoj ćemo seriji detaljno naučiti o osnovnoj, kao i naprednoj strukturi podataka. Također ćemo detaljno naučiti o raznim tehnikama pretraživanja i sortiranja koje se mogu izvoditi na strukturama podataka.

Nakon što je naučio ovu lekciju, čitatelj bi se trebao dobro upoznati sa svakom strukturom podataka i njihovim programiranjem.

Prođimo kroz neke izraze koje koristimo dok se bavimo strukturama podataka:

Na primjer,uzeti određenog učenika. Učenik može imati sljedeće detalje predstavljene slikovito.

Primjer - struktura podataka

  • Podaci: To je elementarna vrijednost. Na gornjoj slici, podaci o broju učenika mogu biti podaci.
  • Stavka grupe: Ovo je podatkovna stavka koja ima više od jedne podstavke. Na gornjoj slici, Student_name ima Ime i Prezime.
  • Snimiti: To je zbirka podataka. U gornjem primjeru, stavke podataka poput broja učenika, imena, razreda, dobi, ocjene itd. Zajedno tvore zapis.
  • Entitet: To je klasa zapisa. U gornjem dijagramu učenik je entitet.
  • Atribut ili polje: Svojstva entiteta nazivaju se atributima i svako polje predstavlja atribut.
  • Datoteka: Datoteka je zbirka zapisa. U gornjem primjeru učenički entitet može imati tisuće zapisa. Tako će datoteka sadržavati sve ove zapise.

Čitatelj bi trebao biti svjestan svih ovih izraza jer ih svako malo koristimo kada koristimo razne strukture podataka.

Strukture podataka glavni su blok programa i kao programeri, trebali bismo biti oprezni koju strukturu podataka koristiti. Točna struktura podataka koja će se koristiti je najteža odluka što se tiče programiranja.

Razmotrimo potrebu za strukturom podataka u Programiranju.

Potreba za strukturom podataka u programiranju

Kako količina podataka i dalje raste, aplikacije postaju sve složenije, pa programeru postaje teško upravljati tim podacima kao i softverom.

Tipično, u bilo kojem trenutku aplikacija se može suočiti sa sljedećim preprekama:

# 1) Pretraživanje velikih količina podataka: S velikom količinom podataka koja se obrađuje i pohranjuje, u bilo kojem trenutku naš će program možda trebati pretražiti određene podatke. Ako su podaci preveliki i nisu pravilno organizirani, trebat će vam puno vremena da biste dobili potrebne podatke.

Kada za pohranu i organizaciju podataka koristimo podatkovne strukture, dohvat podataka postaje brži i lakši.

# 2) Brzina obrade: Neorganizirani podaci mogu rezultirati sporom brzinom obrade jer će se puno vremena gubiti na dohvaćanje i pristup podacima.

Ako podatke pravilno organiziramo u strukturu podataka tijekom spremanja, tada nećemo gubiti vrijeme na aktivnosti poput dohvaćanja, svaki puta organizirajući ih. Umjesto toga, možemo se koncentrirati na obradu podataka kako bismo proizveli željeni rezultat.

# 3) Više istodobnih zahtjeva: Mnoge aplikacije danas trebaju istodobno zatražiti podatke. Te bi zahtjeve trebalo učinkovito obraditi kako bi se aplikacije mogle nesmetano pokretati.

Ako su naši podaci pohranjeni samo nasumično, tada nećemo moći istovremeno obrađivati ​​sve istodobne zahtjeve. Stoga je mudra odluka urediti podatke u odgovarajućoj strukturi podataka kako bi se minimaliziralo vrijeme izvršavanja istodobnih zahtjeva.

Klasifikacija strukture podataka

Strukture podataka korištene u C ++-u mogu se klasificirati kako slijedi.

Klasifikacija struktura podataka

Struktura podataka je način organizacije podataka. Tako možemo klasificirati podatkovne strukture kako su prikazane u primitivne ili standardne podatkovne strukture i neprimitivne ili korisnički definirane podatkovne strukture.

Vidjeli smo sve vrste podataka podržane u C ++. Budući da je ovo također način organizacije podataka, kažemo da je to standardna struktura podataka.

Ostale podatkovne strukture nisu primitivne i korisnik ih mora definirati prije nego što ih koristi u programu. Te korisnički definirane strukture podataka dalje se klasificiraju u linearne i nelinearne strukture podataka.

Linearna struktura podataka

Linearne strukture podataka imaju sve elemente poredane linearno ili u slijedu. Svaki element u linearnoj strukturi podataka ima prethodnika (prethodni element) i nasljednika (sljedeći element)

Linearne strukture podataka nadalje se dijele na statičke i dinamičke strukture podataka. Statičke strukture podataka obično imaju fiksnu veličinu i nakon što se njihova veličina deklarira u vrijeme sastavljanja, ne može se mijenjati. Dinamičke strukture podataka mogu dinamički mijenjati svoju veličinu i prilagoditi se sebi.

Najpopularniji primjer linearne statičke strukture podataka je niz.

Polje

Niz je sekvencijalna zbirka elemenata iste vrste. Svakom elementu niza može se pristupiti pomoću njegove pozicije u nizu koja se naziva indeksom ili indeksom niza. Ime niza pokazuje na prvi element u nizu.

niz

Gore prikazano je polje 'a' od n elemenata. Elementi su numerirani od 0 do n-1. Veličina niza (u ovom slučaju n) naziva se i dimenzija niza. Kao što je prikazano na gornjoj slici, ime niza pokazuje na prvi element niza.

Niz je najjednostavnija struktura podataka i učinkovit je jer se elementima može pristupiti izravno s pretplatama. Ako želimo pristupiti trećem elementu niza, tada moramo reći a (2).

Ali dodavanje ili brisanje elemenata niza je teško. Stoga nizove koristimo samo u jednostavnim aplikacijama ili u aplikacijama u kojima nije potrebno dodavanje / brisanje elemenata.

Popularne linearne dinamičke strukture podataka povezani su popis, stog i red čekanja.

Povezani popis

Povezani popis zbirka je čvorova. Svaki čvor sadrži element podataka i pokazivač na sljedeći čvor. Čvorovi se mogu dinamički dodavati i brisati. Povezani popis može biti pojedinačno povezan popis u kojem svaki čvor ima pokazivač samo na sljedeći element. Za posljednji je element sljedeći pokazivač postavljen na nulu.

Na dvostruko povezanom popisu svaki čvor ima dva pokazivača, jedan na prethodni, a drugi na sljedeći čvor. Za prvi čvor prethodni je pokazivač null, a za zadnji čvor sljedeći je nula.

Povezani popis

Kao što je prikazano na gornjoj slici, početak popisa naziva se glava, dok se kraj povezanog popisa naziva rep. Kao što je gore prikazano, svaki čvor ima pokazivač na sljedeći element. Promjenom pokazivača na sljedeći čvor možemo lako dodati ili izbrisati elemente.

Stog

Stog je linearna struktura podataka u kojoj se elementi mogu dodavati ili uklanjati samo s jednog kraja poznatog kao 'Vrh' stoga. Na taj način, stog prikazuje LIFO (zadnji ulaz, prvi izlaz) pristup memoriji.

Stog

Kao što je gore prikazano, elementi u stogu uvijek se dodaju na jedan kraj i također uklanjaju s istog kraja. To se naziva 'Vrh' stoga. Kada se doda element, on se gurne prema dolje, a vrh stopa se poveća za jedan položaj.

Slično tome, kada se ukloni element, vrh steka se smanjuje. Kad je stog prazan, vrh stoga postavlja se na -1. Postoje dvije glavne operacije 'Push' i 'Pop' koje se izvode na stogu.

Red

Red je još jedna linearna struktura podataka u kojoj se elementi dodaju na jednom kraju koji se naziva 'stražnji' i brišu s drugog kraja koji se naziva 'prednji'. Red čekanja pokazuje FIFO (First In, First Out) vrstu metodologije pristupa memoriji.

Red

Gornji dijagram prikazuje red sa stražnjim i prednjim krajevima. Kad je red prazan, stražnji i prednji pokazivači međusobno se podudaraju.

Nelinearna struktura podataka

U nelinearnim strukturama podataka podaci se ne slažu sekvencijalno, već se raspoređuju na nelinearan način. Elementi su međusobno povezani u nelinearnom rasporedu.

Nelinearne strukture podataka su Drveće i Grafovi.

kako otvoriti bin datoteku na androidu

Drveće

Stabla su nelinearne višerazinske podatkovne strukture koje imaju hijerarhijski odnos između elemenata. Elementi stabla nazivaju se Čvorovi.

Čvor na vrhu naziva se korijen stabla. Korijen može imati jedan ili više podređenih čvorova. Naredni čvorovi također mogu imati jedan ili više podređenih čvorova. Čvorovi koji nemaju podređene čvorove nazivaju se čvorovi listova.

Drveće

U gornjem dijagramu prikazali smo stablo sa 6 čvorova. Od ova tri čvora su čvorići lista, jedan najviši čvor je korijen, a ostali su podređeni čvorovi. Ovisno o broju čvorova, podređenih čvorova itd. Ili o odnosu između čvorova, imamo različite vrste stabala.

Grafikoni

Grafikon je skup čvorova koji se nazivaju vrhovi međusobno povezani pomoću nazvanih veza Rubovi . Grafovi mogu imati ciklus unutar sebe, tj. Isti vrh može biti početna točka kao i završna točka određene staze. Drveće nikada ne može imati ciklus.

Grafikoni

Gornji dijagram je neusmjereni graf. Također možemo imati usmjerene grafikone na kojima predstavljamo rubove pomoću usmjerenih strelica.

Operacije na strukturi podataka

Sve strukture podataka izvode razne operacije na svojim elementima.

Oni su zajednički svim strukturama podataka i navedeni su kako slijedi:

  • Pretraživanje: Ova se operacija izvodi za traženje određenog elementa ili ključa. Najčešći algoritmi pretraživanja su sekvencijalno / linearno i binarno pretraživanje.
  • Sortiranje: Operacija sortiranja uključuje slaganje elemenata u strukturi podataka u određenom redoslijedu uzlazno ili silazno. Postoje različiti algoritmi za sortiranje koji su dostupni za strukture podataka. Najpopularniji među njima su Quicksort, Selection sort, Merge sort itd.
  • Umetanje: Operacija umetanja bavi se dodavanjem elementa u strukturu podataka. Ovo je najvažnija operacija i kao rezultat dodavanja elementa, raspored se mijenja i moramo voditi računa da struktura podataka ostane netaknuta.
  • Brisanje: Operacija brisanja uklanja element iz strukture podataka. Isti uvjeti koje treba uzeti u obzir za umetanje moraju biti ispunjeni i u slučaju postupka brisanja.
  • Putovanje: Kažemo da prelazimo strukturu podataka kada posjetimo svaki element u strukturi. Prelazak je potreban za obavljanje određenih specifičnih operacija na strukturi podataka.

U sljedećim temama prvo ćemo naučiti razne tehnike pretraživanja i sortiranja koje će se izvoditi na strukturama podataka.

Prednosti strukture podataka

  • Apstrakcija: Strukture podataka često se provode kao apstraktni tipovi podataka. Korisnici pristupaju samo njegovom vanjskom sučelju bez brige o temeljnoj implementaciji. Tako struktura podataka pruža sloj apstrakcije.
  • Učinkovitost: Pravilna organizacija podataka rezultira učinkovitim pristupom podacima, čime programi postaju učinkovitiji. Drugo, možemo odabrati pravilnu strukturu podataka ovisno o našim zahtjevima.
  • Mogućnost ponovne upotrebe: Možemo ponovno koristiti strukture podataka koje smo dizajnirali. Mogu se kompilirati u knjižnicu i distribuirati klijentu.

Zaključak

Ovim završavamo ovaj vodič o uvodu u strukture podataka. Ukratko smo predstavili svaku strukturu podataka u ovom vodiču.

U našim sljedećim vodičima istražit ćemo više o strukturama podataka zajedno s raznim tehnikama pretraživanja i sortiranja.

=> Kliknite ovdje za apsolutnu C ++ seriju treninga.

Preporučena literatura

^