Menu

Úvod do dátových štruktúr v C ++

introduction data structures c

Vyskúšajte Náš Nástroj Na Odstránenie Problémov

Úvodný kurz o dátových štruktúrach v C ++.

„Dátovú štruktúru možno definovať ako organizovaný zber dát, ktorý pomáha programu efektívne a rýchlo pristupovať k dátam, aby mohol celý program efektívne fungovať. „

Vieme, že v programovacom svete sú dáta centrom a všetko sa točí okolo dát. Musíme robiť všetky dátové operácie vrátane ukladania, vyhľadávania, triedenia, organizovania a prístupu k dátam efektívne a až potom môže náš program uspieť.

=> Ak chcete preskúmať celý zoznam výukových programov C ++, prečítajte si tu.

Úvod do dátových štruktúr v C ++ (1)

Čo sa dozviete:

Prehľad

Musíme nájsť najefektívnejší spôsob ukladania údajov, ktorý nám môže pomôcť pri vytváraní dynamických riešení. Pri vytváraní takýchto riešení nám pomáha dátová štruktúra.

Pri organizovaní alebo usporiadaní údajov do štruktúr musíme zabezpečiť, aby usporiadanie predstavovalo takmer objekt zo skutočného sveta. Po druhé, toto usporiadanie by malo byť dostatočne jednoduché, aby k nemu mal ktokoľvek ľahký prístup a aby ho mohol kedykoľvek spracovať.

V tejto sérii sa dozvieme podrobne základné aj pokročilé dátové štruktúry. Dozvieme sa tiež podrobne o rôznych technikách vyhľadávania a triedenia, ktoré je možné vykonať na dátových štruktúrach.

Po osvojení tejto série cvičení by mal byť čitateľ oboznámený s každou dátovou štruktúrou a jej programovaním.

Prejdime si niektoré pojmy, ktoré používame pri práci s dátovými štruktúrami:

Napríklad,vziať konkrétneho študenta. Študent môže mať nasledujúce podrobnosti znázornené na obrázku.

Príklad - dátová štruktúra

  • Údaje: Je to elementárna hodnota. Na vyššie uvedenom obrázku môžu byť údajmi študenta.
  • Skupinová položka: Toto je údajová položka, ktorá má viac ako jednu podpoložku. Na vyššie uvedenom obrázku má Student_name krstné meno a priezvisko.
  • Záznam: Je to zbierka údajových položiek. V uvedenom príklade tvoria dátové položky, ako sú študentské priezvisko, meno, trieda, vek, známka atď., Záznam spolu.
  • Subjekt: Je to trieda záznamov. Na vyššie uvedenom diagrame je študent entita.
  • Atribút alebo pole: Vlastnosti entity sa nazývajú atribúty a každé pole predstavuje atribút.
  • Súbor: Súbor je zbierka záznamov. V uvedenom príklade môže mať študentská entita tisíce záznamov. Súbor teda bude obsahovať všetky tieto záznamy.

Čitateľ by si mal byť vedomý všetkých týchto pojmov, pretože ich tu a tam používame pri používaní rôznych dátových štruktúr.

Dátové štruktúry sú hlavným stavebným prvkom programu a ako programátori by sme si mali dávať pozor na to, ktorú dátovú štruktúru použiť. Presná dátová štruktúra, ktorá sa má použiť, je najťažším rozhodnutím, pokiaľ ide o programovanie.

Poďme diskutovať o potrebe dátovej štruktúry v programovaní.

Potreba dátovej štruktúry v programovaní

Pretože množstvo dát stále rastie, aplikácie sa stávajú čoraz zložitejšími, a preto je pre programátora ťažké spravovať tieto dáta aj softvér.

Aplikácia môže obvykle kedykoľvek čeliť týmto prekážkam:

# 1) Vyhľadávanie veľkého množstva údajov: Pretože sa spracúva a ukladá veľké množstvo údajov, môže byť kedykoľvek potrebné, aby náš program vyhľadal konkrétne údaje. Ak sú údaje príliš veľké a nie sú správne usporiadané, získanie potrebných údajov bude trvať veľa času.

Keď na ukladanie a organizáciu údajov používame dátové štruktúry, získavanie údajov sa stáva rýchlejším a ľahším.

# 2) Rýchlosť spracovania: Neusporiadané údaje môžu mať za následok nízku rýchlosť spracovania, pretože pri získavaní a prístupe k údajom bude zbytočne veľa času.

Ak pri ukladaní správne usporiadame údaje v dátovej štruktúre, nebudeme strácať čas aktivitami, ako je napríklad ich načítanie, a to vždy, keď ich usporiadame. Namiesto toho sa môžeme sústrediť na spracovanie údajov, aby sme dosiahli požadovaný výstup.

# 3) Viacero simultánnych požiadaviek: Mnoho aplikácií v dnešnej dobe vyžaduje súčasnú požiadavku na údaje. Tieto žiadosti by mali byť efektívne spracované, aby aplikácie bežali hladko.

Ak sú naše údaje uložené iba náhodne, potom nebudeme schopní spracovať všetky súbežné požiadavky súčasne. Je teda múdre rozhodnutie usporiadať údaje do správnej dátovej štruktúry, aby sa minimalizoval čas potrebný na vybavenie súbežných požiadaviek.

Klasifikácia dátovej štruktúry

Dátové štruktúry používané v C ++ je možné klasifikovať nasledovne.

Klasifikácia dátových štruktúr

Dátová štruktúra je spôsob organizácie údajov. Môžeme teda klasifikovať dátové štruktúry, ako je to znázornené, do primitívnych alebo štandardných dátových štruktúr a neprimitívnych alebo používateľom definovaných dátových štruktúr.

Videli sme všetky dátové typy podporované v C ++. Pretože toto je tiež spôsob organizácie dát, hovoríme, že ide o štandardnú dátovú štruktúru.

Ostatné dátové štruktúry nie sú primitívne a musí ich užívateľ definovať pred použitím v programe. Tieto užívateľom definované dátové štruktúry sa ďalej delia na lineárne a nelineárne dátové štruktúry.

Lineárna dátová štruktúra

Lineárne dátové štruktúry majú všetky svoje prvky usporiadané lineárne alebo sekvenčne. Každý prvok v lineárnej dátovej štruktúre má predchodcu (predchádzajúci prvok) a následníka (nasledujúci prvok)

Lineárne dátové štruktúry sa ďalej delia na statické a dynamické dátové štruktúry. Statické dátové štruktúry majú zvyčajne pevnú veľkosť a akonáhle je ich veľkosť deklarovaná v čase kompilácie, nemožno ju zmeniť. Dynamické dátové štruktúry môžu dynamicky meniť svoju veľkosť a prispôsobiť sa sami sebe.

Najobľúbenejším príkladom lineárnej statickej dátovej štruktúry je pole.

Pole

Pole je postupná zbierka prvkov rovnakého typu. Ku každému prvku poľa je možné získať prístup pomocou jeho polohy v poli, ktorá sa nazýva index alebo dolný index poľa. Názov poľa smeruje na prvý prvok v poli.

pole

Vyššie uvedené je pole „a“ n prvkov. Prvky sú očíslované od 0 do n-1. Veľkosť poľa (v tomto prípade n) sa nazýva aj rozmer poľa. Ako je znázornené na obrázku vyššie, názov poľa smeruje na prvý prvok poľa.

Pole je najjednoduchšou dátovou štruktúrou a je efektívne, pretože k prvkom je možné pristupovať priamo pomocou dolných indexov. Ak chceme získať prístup k tretiemu prvku v poli, musíme povedať iba (2).

Ale pridanie alebo odstránenie prvkov poľa je ťažké. Z tohto dôvodu používame polia iba v jednoduchých aplikáciách alebo v aplikáciách, kde sa nevyžaduje pridanie / vymazanie prvkov.

Populárne lineárne dynamické dátové štruktúry sú spojené zoznamom, zásobníkom a radom.

Prepojený zoznam

Prepojený zoznam je kolekcia uzlov. Každý uzol obsahuje dátový prvok a smerník na nasledujúci uzol. Uzly je možné pridávať a mazať dynamicky. Prepojený zoznam môže byť jednotlivo prepojený zoznam, v ktorom má každý uzol ukazovateľ iba na nasledujúci prvok. Pre posledný prvok je nasledujúci ukazovateľ nastavený na hodnotu null.

V zozname s dvojnásobným prepojením má každý uzol dva ukazovatele, jeden na predchádzajúci uzol a druhý na nasledujúci uzol. Pre prvý uzol je predchádzajúci ukazovateľ nulový a pre posledný uzol je nasledujúci ukazovateľ nulový.

Prepojený zoznam

Ako je znázornené na obrázku vyššie, začiatok zoznamu sa nazýva hlava, zatiaľ čo koniec prepojeného zoznamu sa nazýva koniec. Ako je uvedené vyššie, každý uzol má ukazovateľ na nasledujúci prvok. Prvky môžeme ľahko pridať alebo odstrániť zmenou ukazovateľa na ďalší uzol.

Stoh

Zásobník je lineárna dátová štruktúra, v ktorej je možné prvky pridávať alebo odstraňovať iba z jedného konca známeho ako „Vrch“ zásobníka. Týmto spôsobom zásobník vykazuje typ prístupu do pamäte typu LIFO (Last In, First Out).

Stoh

Ako je uvedené vyššie, prvky v zásobníku sa vždy pridávajú na jednom konci a tiež sa z rovnakého konca odstraňujú. Toto sa nazýva „Vrch“ zásobníka. Po pridaní prvku sa tento posunie nadol v zásobníku a horná časť zásobníka sa zvýši o jednu pozíciu.

Podobne, keď je prvok odstránený, horná časť stohu sa zníži. Keď je stoh prázdny, horná časť stohu je nastavená na -1. Na zásobníku sa vykonávajú dve hlavné operácie „Push“ a „Pop“.

Fronta

Fronta je ešte ďalšou lineárnou dátovou štruktúrou, v ktorej sú prvky pridávané na jednom konci zvanom „zozadu“ a vymazané z iného konca nazývaného „vpredu“. Fronta demonštruje FIFO (First In, First Out) typ metodiky prístupu do pamäte.

Fronta

Vyššie uvedený diagram zobrazuje rad so zadným a predným koncom. Ak je rad prázdny, zadný a predný ukazovateľ sa zhodujú.

Nelineárna dátová štruktúra

V nelineárnych dátových štruktúrach nie sú dáta usporiadané postupne, sú usporiadané nelineárne. Prvky sú navzájom spojené v nelineárnom usporiadaní.

Nelineárne dátové štruktúry sú stromy a grafy.

aké sú najlepšie aplikácie pre virtuálnu realitu

Stromy

Stromy sú nelineárne viacúrovňové dátové štruktúry, ktoré majú hierarchický vzťah medzi prvkami. Prvky stromu sa nazývajú Uzly.

Uzol v hornej časti sa nazýva koreň stromu. Koreň môže mať jeden alebo viac podradených uzlov. Nasledujúce uzly môžu mať tiež jeden alebo viac podradených uzlov. Uzly, ktoré nemajú podradené uzly, sa nazývajú listové uzly.

Stromy

Na vyššie uvedenom diagrame sme zobrazili strom so 6 uzlami. Z týchto troch uzlov sú listové uzly, jeden najvyšší uzol je koreň a ostatné sú podradené uzly. V závislosti od počtu uzlov, podradených uzlov atď. Alebo vzťahu medzi uzlami máme rôzne druhy stromov.

Grafy

Graf je sada uzlov tzv vrcholy navzájom prepojené pomocou volaných odkazov Hrany . Grafy môžu mať v sebe cyklus, t. J. Ten istý vrchol môže byť východiskovým aj koncovým bodom konkrétnej cesty. Stromy nikdy nemôžu mať cyklus.

Grafy

Vyššie uvedený diagram je neorientovaný graf. Môžeme mať aj usmernené grafy, kde pomocou smerových šípok reprezentujeme hrany.

Operácie s dátovou štruktúrou

Všetky dátové štruktúry vykonávajú na svojich prvkoch rôzne operácie.

Sú spoločné pre všetky dátové štruktúry a sú uvedené takto:

  • Vyhľadávanie: Táto operácia sa vykonáva na vyhľadanie konkrétneho prvku alebo kľúča. Najbežnejšími vyhľadávacími algoritmami sú sekvenčné / lineárne vyhľadávanie a binárne vyhľadávanie.
  • Triedenie: Operácia triedenia zahŕňa usporiadanie prvkov v dátovej štruktúre v konkrétnom poradí buď vzostupne, alebo zostupne. Pre dátové štruktúry sú k dispozícii rôzne triediace algoritmy. Najobľúbenejšie z nich sú Quicksort, Selection sort, Merge sort atď.
  • Vloženie: Operácia vloženia sa zaoberá pridaním prvku do dátovej štruktúry. Toto je najdôležitejšia operácia a v dôsledku pridania prvku sa zmení usporiadanie a musíme dbať na to, aby dátová štruktúra zostala nedotknutá.
  • Vymazanie: Operácia odstránenia odstráni prvok z dátovej štruktúry. Rovnaké podmienky, ktoré sa majú brať do úvahy pri vkladaní, musia byť splnené aj v prípade operácie vymazania.
  • Traverz: Hovoríme, že prechádzame dátovou štruktúrou, keď navštívime každý prvok v štruktúre. Na vykonanie určitých špecifických operácií v dátovej štruktúre je potrebný posuv.

V našich nasledujúcich témach sa najskôr naučíme rôzne techniky vyhľadávania a triedenia, ktoré sa majú vykonať na dátových štruktúrach.

Výhody dátovej štruktúry

  • Abstrakcia: Dátové štruktúry sa často implementujú ako abstraktné dátové typy. Používatelia pristupujú iba k jeho vonkajšiemu rozhraniu bez obáv o základnú implementáciu. Dátová štruktúra teda poskytuje vrstvu abstrakcie.
  • Účinnosť: Správna organizácia údajov vedie k efektívnemu prístupu k údajom, a tým k zefektívneniu programov. Po druhé, môžeme zvoliť správnu dátovú štruktúru v závislosti od našich požiadaviek.
  • Opätovná použiteľnosť: Môžeme znova použiť dátové štruktúry, ktoré sme navrhli. Môžu byť tiež zostavené do knižnice a distribuované klientovi.

Záver

Týmto uzatvárame tento návod na úvod do dátových štruktúr. Každú z dátových štruktúr sme v krátkosti predstavili v tomto výučbe.

V našich ďalších tutoriáloch preskúmame viac o dátových štruktúrach spolu s rôznymi technikami vyhľadávania a triedenia.

=> Kliknutím sem zobrazíte sériu školení Absolute C ++.

Odporúčané čítanie

^