- jedna sa o abstrakciu od fyzickej a implementacnej vrstvy, je to vlastne konceptualna uroven
- zdoraznuju co sa s typmi vykonava, ake operacie s datmi vykonavaju
- je to mnozina druhu a dat a prislusnych operacii, ktore su presne specifikovane, nezavisle na implementacii
- tvorene signaturou a semantikou
- signatura = syntax - deklaracia druhov (obor hodnot), deklaracia operacii (mena operacii, druhy a poradie argumentov, druh vysledku)
- semantika = axiomy = popis vlastnosti operacii
samotna datova struktura je realizaciou ADT
ADT
- staticke - pocet a usporiadenie zloziek sa nemeni
- dynamicke - pocet a usporiadanie zloziek sa meni
- homogenne - vsetky komponenty rovnakeho druhu
- heterogenne - rozneho typu
- linearne - bezprostredny naslednik existuje (pole, zoznam)
- nelinearne - bezporostredny naslednik neexistuje (strom, tabulka)
sekvencne ADT - pole, zoznam, zasobnik, fronta
asociativne ADT - tabulka, mnozina
Pole
- postupnost prvkov, ktorym je priradeny index
- homogenne
- staticke - pokial je znamy pocet prvkov vopred
- dynamicke - pokial nie je znamy pocet prvkov
- linearne
- pristup pomocou mapovacej funkcie, ktore hovori, co kam bude ulozene, napriklad urci offset od base address
operacie: init, upper, lower, set, get
Tabulka
- homogenna
- dynamicka
- nelinearna
- polozky su jednoznacne urcene klucom
- operacie: init, insert, delete, search, read
- tabulka je implementovana v poli
- pre male mnozstvo klucov - sekvencne vyhladavanie
- pre vacsie - hash table
Zoznam
- homogenny
- linearny
- dynamicky
- mame ukazovatko a pracujeme nad prvkom, na ktory ukazujeme
- init, insert, delete, beginning?, end?, read, first, last, next, prev, length, empty?, full?, insertBeg, insertEnd, mark
- implementovane v poli
- implementovane ako zasobniky v poli
- v dynamickej pamati - linked list, double linked list, circular linked list
- vzdy mame tri pointre - head, tail, point
- po vlozeni vkladam vpred a ukazovatko nemenim
- po mazani ukazovatko posuniem na dalsiu poziciu
Mnozina
- s aj bez opakovania prvkov
- heterogenna
operacia
- ins, del, in, card
Strom
- strom je acyklicky suvisly graf
- ak ma koren, tak potom to je korenovy strom - koren je vzdy spojeny so vsetkymi uzlami orientovanou cestou
- binarny, usporiadany binarny ...
- empty, leaf?,set left, set right, set info, null
Fronta
FIFO - first in first out (pipe)
- implementovana v poli, linearne, kruhovo
- v dynamickej pamati, ako spojovy zoznam
LIFO - last in first out (buffer)
- pristup len na top
- vkladanie len na top
- implementuje sa v poli, alebo dynamickej pamati, ako spojovy zoznam
