Dátové štruktúry
Počítač dokáže uchovávať a spracovávať veľké množstvo údajov. Formálne dátové štruktúry umožňujú štruktúrovať tento priestor na logické celky. Dátová štruktúra je spôsob ako uchovávať a organizovať dáta tak, aby boli ľahko prístupné a modifikovateľné.
^ TOPPoužitie
Žiadna dátová štruktúra sa nehodí na všetky možné aplikácie, a preto je dôležité poznať možnosti a obmedzenia viacerých z nich.
Niekedy používame dátové štruktúry, aby nám umožnili robiť viac, napríklad uskutočňovať rýchle
vyhľadávanie alebo triedenie.
Inokedy zase potrebujeme, aby dátová štruktúra bola presne špecializovaná a aby nám v konečnom dôsledku dovoľovala menej.
Napríklad zásobník je limitovanou formou všeobecnejšej dátovej štruktúry.
Tieto obmedzenia dovoľujú nezaťažovať sa podrobnosťami pri písaní algoritmov.
Voľba správnej dátovej štruktúry 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.
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á.
Pojem dátový typ
Zaužívaná konvencia je, že každá konštanta, premenná, výraz alebo funkcia sú určitého typu. Tento typ určuje množinu hodnôt,
do ktorej daná konštanta prináleží, alebo ktoré môže daná premenná, či výraz nadobudnúť, alebo ktoré možno danou funkciou vypočítať.
Zvyčajne je typ konštanty, premennej alebo funkcie explicitne stanovený v rámci deklarácie príslušného objektu. Objekt musí byť vždy
deklarovaný skôr ako je použitý, lebo kompilátor musí zvoliť reprezentáciu príslušného objektu v pamäti počítača.
Podstatné vlastnosti pojmu dátový typ teda sú:
- Typ údajov určuje množinu hodnôt, do ktorej daná konštanta prináleží, alebo ktoré môže daná premenná či výraz nadobudnúť, alebo ktoré môže daným operátorom alebo funkciou vypočítať.
- Typ hodnoty konštanty, premennej alebo výrazu sa dá určiť z ich deklarácie alebo zápisu bez nevyhnutnosti uskutočniť vlastný výpočtový proces programu.
- Každý operátor alebo funkcia predpokladá argumenty presne definovaných typov a poskytuje výsledok tiež presne definovaného typu. V prípade, že operátor pripúšťa argumenty rôznych typov (napríklad ak sa operátor "+" používa na ščítanie celých i reálnych čísel), dá sa typ výsledku určiť podľa špecifických pravidiel príslušného programovacieho jazyka.
Abstraktný dátový typ
Pretože sú dátové štruktúry vyššou úrovňou abstrakcie, umožňujú operácie na množine dát, ako sú napríklad pridávanie položky do zoznamu,
alebo nájdenie prvku s najväčšou prioritou vo fronte. Takáto dátová štruktúra, ktorá umožňuje operácie, sa volá
abstraktný dátový typ
(abstract data type). Abstraktný dátový typ dokáže minimalizovať závislosti v kóde, čo je dôležité pri častých zmenách. Jednotlivé
implementačné detaily sú skryté a to dovoľuje nahrádzať už raz zvolené špeciálne dátové štruktúry za také, ktoré zdieľajú spoločné vlastnosti
na vyššej úrovni.
Programovacie jazyky prinášajú množinu vstavaných typov, napríklad celočíselný typ (integer), alebo čísla s desatinnou čiarkou
(floating-point numbers). Tieto dátové typy sú abstrakciami, lebo skrývajú detaily o tom, ako procesor jednotlivé operácie na nich vykonáva.