Dátové štruktúry: definícia, typy, príklady a použitie v programovaní

Pole

Najjednoduchším typom dátovej štruktúry je lineárne pole. Známa aj ako jednorozmerné pole. Pole obsahuje niekoľko hodnôt rovnakého typu (Integer, Floats, String atď.). Prístup k prvkom v rámci poľa je veľmi rýchly. Pole má zvyčajne pevnú veľkosť. Po definovaní veľkosti poľa na začiatku nemusí byť možné zväčšiť veľkosť poľa bez vytvorenia nového väčšieho poľa a skopírovania všetkých hodnôt do nového poľa. V informatike je dátová štruktúra typu pole alebo jednoducho pole dátová štruktúra pozostávajúca z kolekcie prvkov (hodnôt alebo premenných), z ktorých každý je identifikovaný aspoň jedným indexom alebo kľúčom poľa. Pole je uložené tak, že pozícia každého prvku sa dá vypočítať z jeho indexového súboru pomocou matematického vzorca.

Napríklad pole 10 celočíselných premenných s indexmi 0 až 9 môže byť uložené ako 10 slov na pamäťových adresách 2000, 2004, 2008, 2036, takže prvok s indexom i má adresu 2000 + 4 × i.

Keďže matematický koncept matice možno reprezentovať ako dvojrozmernú mriežku, dvojrozmerné polia sa niekedy nazývajú aj matice. V niektorých prípadoch sa vo výpočtovej technike na označenie matice používa pojem "vektor", hoci správnejším matematickým ekvivalentom sú skôr tuply ako vektory. Polia sa často používajú na implementáciu tabuliek, najmä vyhľadávacích tabuliek; slovo tabuľka sa niekedy používa ako synonymum pojmu pole.

Polia patria medzi najstaršie a najdôležitejšie dátové štruktúry a používajú sa takmer v každom programe. Možno ich použiť aj na implementáciu mnohých ďalších dátových štruktúr, ako sú zoznamy a reťazce. Efektívne využívajú adresnú logiku počítačov. Vo väčšine moderných počítačov a mnohých externých pamäťových zariadeniach je pamäť jednorozmerné pole slov, ktorých indexy sú ich adresy. Procesory, najmä vektorové, sú často optimalizované na operácie s poľom.

Polia sú užitočné, pretože indexy prvkov možno vypočítať počas behu. Táto vlastnosť okrem iného umožňuje jedným iteračným príkazom spracovať ľubovoľne veľa prvkov poľa. Z tohto dôvodu sa vyžaduje, aby prvky dátovej štruktúry poľa mali rovnakú veľkosť a mali by používať rovnakú dátovú reprezentáciu. Množina platných indexových kôpok a adresy prvkov (a teda aj vzorec na adresovanie prvkov) sú zvyčajne, ale nie vždy, počas používania poľa fixné.

Termín pole sa často používa na označenie dátového typu array, čo je druh dátového typu poskytovaného väčšinou vysokoúrovňových programovacích jazykov, ktorý pozostáva z kolekcie hodnôt alebo premenných, ktoré možno vybrať pomocou jedného alebo viacerých indexov vypočítaných v čase behu. Typy polí sú často implementované štruktúrami polí, v niektorých jazykoch však môžu byť implementované hashovacími tabuľkami, spájanými zoznamami, vyhľadávacími stromami alebo inými dátovými štruktúrami.

Prepojený zoznam

Prepojená dátová štruktúra je súbor informácií/údajov prepojených odkazmi. Údaje sa často nazývajú uzly. Odkazy sa často nazývajú odkazy alebo ukazovatele. Odteraz sa pre tieto pojmy budú používať slová uzol a ukazovateľ.

V prepojených dátových štruktúrach sa ukazovatele iba dereferencujú alebo porovnávajú na rovnosť. Preto sa prepojené dátové štruktúry líšia od polí, ktoré vyžadujú sčítanie a odčítanie ukazovateľov.

Prepojené zoznamy, vyhľadávacie stromy a stromy výrazov sú prepojené dátové štruktúry. Sú tiež dôležité v algoritmoch, ako je topologické triedenie a hľadanie množín.

Zásobník

Zásobník je základná dátová štruktúra, ktorú možno logicky považovať za lineárnu štruktúru reprezentovanú skutočným fyzickým zásobníkom alebo hromadou, štruktúrou, kde vkladanie a mazanie položiek prebieha na jednom konci nazývanom vrch zásobníka. Základný koncept možno znázorniť tak, že si množinu údajov predstavíte ako stoh tanierov alebo kníh, z ktorého môžete vybrať iba vrchnú položku, aby ste z neho mohli odstrániť veci. Táto štruktúra sa používa v celom programovaní.

Základná implementácia zásobníka sa nazýva aj štruktúra "Last In First Out", existujú však rôzne varianty implementácie zásobníka.

V zásade existujú tri operácie, ktoré možno vykonávať so zásobníkmi. Sú to:

• vkladanie ("posúvanie") položky do zásobníka
• vymazanie ("vyskočenie") položky zo zásobníka
• zobrazenie obsahu hornej položky zásobníka ("peeking")

Fronta

Fronta je abstraktný dátový typ alebo lineárna dátová štruktúra, do ktorej sa prvý prvok vkladá z jedného konca ("chvost") a odstránenie existujúceho prvku sa uskutočňuje z druhého konca ("hlava"). Fronta je štruktúra "First In First Out". "First In First Out" znamená, že prvky vložené do frontu ako prvé vyjdú prvé a prvky vložené do frontu ako posledné vyjdú posledné. Príkladom frontu sú rady čakajúcich ľudí. Prvá osoba v rade ide prvá a posledná osoba v rade ide posledná.

Proces pridania prvku do frontu sa nazýva "enqueuing" a proces odstránenia prvku z frontu sa nazýva "dequeuing".

Graf

Graf je abstraktný dátový typ, ktorý je určený na implementáciu konceptov grafov a hypergrafov z matematiky.

Dátová štruktúra grafu pozostáva z konečnej (a prípadne premenlivej) množiny usporiadaných dvojíc, nazývaných hrany alebo oblúky, určitých entít nazývaných uzly alebo vrcholy. Podobne ako v matematike sa hovorí, že hrana (x,y) smeruje alebo prechádza z x do y. Uzly môžu byť súčasťou štruktúry grafu alebo môžu byť externými entitami reprezentovanými celočíselnými indexmi alebo referenciami. Dátová štruktúra grafu môže tiež ku každej hrane priradiť nejakú hodnotu, napríklad symbolickú značku alebo číselný atribút.

Strom

Strom je jednou z najvýkonnejších pokročilých dátových štruktúr. Často sa objavuje v pokročilých predmetoch, ako je umelá inteligencia (AI) a dizajn. Prekvapivo je strom dôležitý aj v oveľa základnejšej aplikácii - pri vedení efektívneho indexu.

Pri použití stromu je vysoká pravdepodobnosť, že sa použije index. Najjednoduchším typom indexu je zoradený zoznam kľúčových polí. Strom má zvyčajne definovanú štruktúru. V prípade binárneho stromu môžete použiť binárne vyhľadávanie na vyhľadanie ľubovoľnej položky bez toho, aby ste museli prezerať každú položku.

Dátový typ strom je typ grafu, čo znamená, že mnohé algoritmy vytvorené na prechádzanie grafu pracujú aj so stromom, avšak algoritmy môžu byť veľmi podobné a musia mať vyhradený počiatočný uzol, teda uzol, na ktorý sa neviažu žiadne iné uzly.

Problém s jednoduchým usporiadaným zoznamom nastáva, keď začnete pridávať nové položky a musíte zoznam udržiavať zoradený - dá sa to urobiť pomerne efektívne, ale vyžaduje si to určité úpravy. Okrem toho lineárny index nie je ľahké zdieľať, pretože celý index sa musí "zamknúť", keď ho upravuje jeden používateľ, zatiaľ čo jednu "vetvu" stromu možno zamknúť, pričom ostatné vetvy zostanú upraviteľné pre ostatných používateľov (pretože ich nemožno ovplyvniť).

Tabuľka Hash

Hašovacia tabuľka je pole, v ktorom každý index ukazuje na prepojený zoznam založený na hašovacej hodnote. Hašovacia hodnota je hodnota určená hašovacou funkciou. Hašovacia funkcia určuje jedinečnú hodnotu na základe údajov, ktoré ukladá. To umožňuje prístup k údajom v konštantnom čase, pretože počítač vždy vie, kde ich má hľadať.