Údajová štruktúra

Binárny strom – jednoduchý typ rozvetvenej štruktúry súvisiacich údajov

Údajová štruktúra alebo dátová štruktúra je údajový typ alebo zostrojenie oblasti hodnôt z elementárnych oblastí hodnôt pomocou konštruktorov. Je to najmä spôsob ukladania údajov v počítači za účelom efektívneho použitia.

Údajová štruktúra je časť údajovej základne. Ak by údajovou základňou bola napr. KARTOTÉKA, tak údajovou štruktúrou by mohla byť ZÁSUVKA (z počítačového hľadiska SÚBOR – FILE), KARTA V ZÁSUVKE alebo FORMULÁR (z počítačového hľadiska ZÁZNAM – RECORD), ÚDAJ NA FORMULÁRI (z počítačového hľadiska POLE – ARRAY, TEXT, CELÉ ČISLO – INTEGER).

Údajová štruktúra je to isté, čo údajový typ alebo zostrojenie oblasti hodnôt z elementárnych oblastí hodnôt pomocou konštruktorov. Elementárnymi oblasťami hodnôt sú celé čísla Z (integer), reálne čísla R (real), množina pravdivostných hodnôt (boolean), množina znakov (char), používateľom definované konečné množiny (skalárne typy) a ich podobory. Konštruktory slúžia na určenie štruktúry oblasti hodnôt a zloženia, resp. rozkladu ich prvkov. Obyčajne máme nasledujúcich päť konštruktorov: agregácia, zovšeobecnenie, rekurzia, vytvorenie množiny všetkých podmnožín, vytvorenie priestoru funkcií.

Často sa stáva, že vhodne zvolená údajová štruktúra umožní pri počítačoch použitie efektívneho algoritmu. Voľba údajovej štruktúry začína voľbou abstraktnej údajovej štruktúry. Dobre navrhnutá údajová štruktúra umožňuje vykonávanie kritických operácií za použitia minima zdrojov – podľa možnosti výpočtového času a operačnej pamäte.

Rôzne druhy údajových štruktúr sa hodia na rôzne aplikácie. Niektoré sú vysoko špecializované na určitú úlohu. Napríklad B-stromy sú obzvlášť vhodné na implementáciu databáz, kým fungovanie smerovacích tabuliek je podmienené použitím v sieti počítačov.

Pri návrhu mnohých typov programov je voľba údajových štruktúr primárnou úlohou. Skúsenosti z budovania veľkých systémov ukázali, že zložitosť implementácie, kvalita a výkonnosť konečného výsledku závisí do veľkej miery na voľbe najvhodnejších údajových štruktúr. Potom ako sú zvolené údajové štruktúry je voľba algoritmov pomerne zjavná. Niekedy to funguje aj opačne – údajová štruktúra sa zvolí, pretože na riešenie úlohy existuje algoritmus, ktorý najlepšie pracuje s istou údajovou štruktúrou. V každom prípade je voľba údajovej štruktúry kritická.

Vznikli formalizované metódy a programovacie jazyky, kde sú kľúčovým organizačným faktorom údajové štruktúry a nie algoritmy. Väčšina jazykov má nejaký systém modulov umožňujúci znovupoužitie údajových štruktúr v rôznych aplikáciách tak, že sa za navrhnuté rozhrania skryjú implementačné detaily. Objektovo orientované jazyky ako C++ a Java na to používajú objekty.

Keďže údajové štruktúry sú v profesionálnych programoch kriticky dôležité, mnohé z nich sú vyčerpávajúco podporované v štandardných knižniciach moderných programovacích jazykov ako napr. Knižnica štandardných šablón (STL) v C++, Java API alebo Microsoft .NET framework.

Fundamentálnymi stavebnými prvkami údajových štruktúr sú polia, záznamy, uniony a ukazovatele. Napríklad nulovateľný pointer je pointer, ktorý môže nadobúdať nulovú hodnotu je kombináciou ukazovateľov a unionov a na jeho základe je možné zostrojiť najjednoduchšiu spojovú údajovú štruktúru – spájaný zoznam.

Existuje diskusia o tom, či údajové štruktúry reprezentujú implementácie alebo rozhrania. Záleží na uhle pohľadu – na údajovú štruktúru sa môžeme pozerať ako na rozhranie medzi dvomi funkciami alebo ako implementáciu metód prístupu k úložnému priestoru, ktorý je organizovaný podľa príslušného údajového typu.

Zoznam údajových štruktúr

• bunka s využitím smerníka
• pole (array, dimension)
• dátum a čas (date, time, datetime)
• množina (set)
• slovník (dictionary)
• trieda (class)
• zoznam (list)
• spájaný zoznam (linked list)
• zásobník (stack)
• front (queue)
• vektor (vector)
• strom (tree)
• graf
• halda (heap)
• zobrazenie (map)

Pozri aj

• Perzistentná údajová štruktúra

Externé odkazy

• Výučbový systém pre údajove typy a štruktúry (DP) Archivované 2007-05-04 na Wayback Machine
• Opisy zo Slovníka algoritmov a údajových štruktúr (en).
• Odkazy z C/C++ User’s Group Page (en)