Z´ akladn´ı datov´ e struktury Martin Trneˇcka
Katedra informatiky, Pˇr´ırodovˇ edeck´ a fakulta Univerzita Palack´ eho v Olomouci
4. listopadu 2013
Martin Trneˇ cka (UPOL)
Algoritmick´ a matematika 1
4. listopadu 2013
1 / 27
Datov´a struktura Volnˇe ˇreˇceno, zp˚ usob uloˇzen´ı dat v poˇc´ıtaˇci a zp˚ usob jak´ym s tˇemito daty m˚ uˇzeme pracovat.
Martin Trneˇ cka (UPOL)
Algoritmick´ a matematika 1
4. listopadu 2013
2 / 27
Abstraktn´ı datov´a struktura Neform´aln´ı definice: Datov´a struktura, kter´a nen´ı z´avisl´a na vlastn´ı implementaci a kter´a je definov´ana pomoc´ı povolen´ych operac´ı na t´eto struktuˇre. Form´alnˇe lze definovat jako matematick´y model (nepˇr´ım´a definice pomoc´ı operac´ı neˇr´ık´ame co to je, ale co s t´ım lze dˇelat). Nezaj´ım´a n´as konkr´etn´ı implementace, ale rozhran´ı, kter´e struktura poskytuje. Implementace je ale tak´e d˚ uleˇzit´a (uk´aˇzeme pozdˇeji). Konkr´etn´ı implementace je oznaˇcov´ana pojmem datov´a struktura“. ” Motivace: Zjednoduˇsuj´ı n´avrh algoritm˚ u a pˇrin´aˇsej´ı abstrakci do programov´an´ı.
Martin Trneˇ cka (UPOL)
Algoritmick´ a matematika 1
4. listopadu 2013
3 / 27
Abstraktn´ı promˇenn´a Nejz´akladnˇejˇs´ı, netrivi´aln´ı abstraktn´ı datov´a struktura. Operace definovan´e nad promˇenou: zaps´an´ı, smaz´an´ı, modifikace promˇenn´e ˇcten´ı obsahu promˇenn´e Pozor! Promˇ enn´ a v jazyce C je element jazyka. To nen´ı tot´ eˇ z jako abstraktn´ı datov´ a struktura promˇ enn´ a.
Martin Trneˇ cka (UPOL)
Algoritmick´ a matematika 1
4. listopadu 2013
4 / 27
Abstraktn´ı pole Z´akladn´ı abstraktn´ı datov´a struktura. Reprezentuje kolekci, kter´a obsahuje prvky. Ty jsou sloˇzeny z p´ar˚ u ve tvaru (kl´ıˇc, hodnota). Operace definovan´e nad polem: pˇrid´an´ı p´aru ke kolekci odstranˇen´ı p´aru z kolekce modifikace p´aru v kolekci pˇr´ıstup k hodnotˇe spojen´e s konkr´etn´ım kl´ıˇcem Pozor! Pole v jazyce C je datov´ y typ. To nen´ı tot´ eˇ z jako abstraktn´ı datov´ a struktura pole.
Martin Trneˇ cka (UPOL)
Algoritmick´ a matematika 1
4. listopadu 2013
5 / 27
Seznam (anglicky list) Nejobecnˇejˇs´ı abstraktn´ı datov´a struktura. Mnoˇzina (kolekce) n ≥ 0 prvk˚ u, pˇriˇcemˇz tyto prvky jsou uloˇzeny line´arnˇe za sebou (k-t´y prvek seznamu je pˇred k − 1 prvkem seznamu). Operace definovan´e na seznamu: pˇr´ıstup, modifikace k-t´eho prvku smaz´an´ı k-t´eho prvku vloˇzen´ı pˇred, za k-t´y prvek spojen´ı, rozdˇelen´ı seznamu setˇr´ızen´ı seznamu vyhled´an´ı v seznamu
Martin Trneˇ cka (UPOL)
Algoritmick´ a matematika 1
4. listopadu 2013
6 / 27
Seznam - pˇr´ıklad
Martin Trneˇ cka (UPOL)
Algoritmick´ a matematika 1
4. listopadu 2013
7 / 27
Z´asobn´ık (anglicky stack) Princip pr´ace s daty: Data, kter´a jsou uloˇzena jako posledn´ı jsou ˇctena jako prvn´ı. Lze si j´ı pˇredstavit jako obyˇcejn´y z´asobn´ık do pistole. Abstraktn´ı datov´a struktura typu LIFO (Last In – First Out). Kl´ıˇcov´y prvek je vrchol z´asobn´ıku, kter´y pˇredstavuje posledn´ı uloˇzen´y prvek. Operace definovan´e na z´asobn´ıku: push - uloˇzen´ı prvku na vrchol z´asobn´ıku pop - odebr´an´ı prvku z vrcholu z´asobn´ıku top - vrac´ı prvek na vrcholu z´asobn´ıku (neodebere jej) is empty - predik´at pr´azdnosti z´asobn´ıku
Martin Trneˇ cka (UPOL)
Algoritmick´ a matematika 1
4. listopadu 2013
8 / 27
Z´asobn´ık - pˇr´ıklad
Martin Trneˇ cka (UPOL)
Algoritmick´ a matematika 1
4. listopadu 2013
9 / 27
Fronta (anglicky queue) Princip pr´ace s daty: Data, kter´a jsou uloˇzena jako prvn´ı jsou ˇctena jako prvn´ı. Lze si j´ı pˇredstavit jako obyˇcejnou frontu v obchodˇe. Abstraktn´ı datov´a struktura typu FIFO (First In – First Out). Kl´ıˇcov´e prvky jsou zaˇc´atek a konec fronty. Operace definovan´e na frontˇe: push - uloˇzen´ı prvku na konec fronty pop - odebr´an´ı prvku ze zaˇc´atku fronty is full - predik´at plnosti fronty is empty - predik´at pr´azdnosti fronty
Martin Trneˇ cka (UPOL)
Algoritmick´ a matematika 1
4. listopadu 2013
10 / 27
Fronta - pˇr´ıklad
Martin Trneˇ cka (UPOL)
Algoritmick´ a matematika 1
4. listopadu 2013
11 / 27
Varianty fronty Obousmˇern´a fronta (anglicky double-ended queue), modifikace jednosmˇern´e fronty. Data lze pˇrid´avat a odeb´ırat z konce i ze zaˇc´atku fronty. Fronta s prioritami (prvky mohou pˇredb´ıhat).
Martin Trneˇ cka (UPOL)
Algoritmick´ a matematika 1
4. listopadu 2013
12 / 27
Dalˇs´ı abstraktn´ı datov´e struktury Strom Graf Mnoˇzina Kontejner Slovn´ık dalˇs´ı
Martin Trneˇ cka (UPOL)
Algoritmick´ a matematika 1
4. listopadu 2013
13 / 27
Druh´a strana - implementace Implementace je z pohledu abstraktn´ıch datov´ych struktur nepodstatn´a“. ” Z pohledu jejich pouˇz´ıv´an´ı (programov´an´ı) je vˇsak kruci´aln´ı a to zejm´ena efektivita implementace jednotliv´ych operac´ı nad datovou strukturou. Je velice obt´ıˇzn´e vytvoˇrit implementaci, kde by vˇsechny operace byly efektivn´ı.
Martin Trneˇ cka (UPOL)
Algoritmick´ a matematika 1
4. listopadu 2013
14 / 27
Seznam - implementace Z´akladn´ı dynamick´a datov´a struktura, kter´e je pamˇet’ pˇridˇelov´ana dynamicky. Jedn´a se o konkr´etn´ı implementaci. Prvky seznamu jsou tvoˇreny uzly (pomocnou datovou strukturou), kter´e obsahuj´ı kromˇe samotn´eho prvku, ukazatele na dalˇs´ı uzel. Pro pr´aci se seznamem je kl´ıˇcov´y zaˇc´atek (head) seznamu a v nˇekter´ych pˇr´ıpadech i konec (tail) seznamu. Typy seznam˚ u: jednosmˇern´y seznam obousmˇern´y seznam cyklick´y seznam
Martin Trneˇ cka (UPOL)
Algoritmick´ a matematika 1
4. listopadu 2013
15 / 27
Seznam - pˇr´ıklady
Martin Trneˇ cka (UPOL)
Algoritmick´ a matematika 1
4. listopadu 2013
16 / 27
Seznam vs. pole Na rozd´ıl od pole prvky v seznamu nemus´ı b´yt v pamˇeti uloˇzeny line´arnˇe za sebou. Pr´ace se seznamem, nevyˇzaduje dodateˇcnou pr´aci s pamˇet´ı (nevyˇzaduje realokaci pamˇeti pˇri pˇrid´av´an´ı a odeb´ır´an´ı prvk˚ u). Vyhled´av´an´ı, vkl´ad´an´ı a maz´an´ı je pomalejˇs´ı neˇz u pole (proˇc?).
Martin Trneˇ cka (UPOL)
Algoritmick´ a matematika 1
4. listopadu 2013
17 / 27
Z´asobn´ık - implementace Pomoc´ı pole (statick´a struktura). Pomoc´ı seznamu (dynamick´a struktura, vyuˇz´ıv´a pointry). Ve vˇetˇsinˇe jazyk˚ u jiˇz existuje.
Martin Trneˇ cka (UPOL)
Algoritmick´ a matematika 1
4. listopadu 2013
18 / 27
Z´asobn´ık - implementace polem I. int zasobnik[5]; void push(int x, int zasobnik) { int pocet_prvku = sizeof(zasobnik) / sizeof(int); if(pocet_prvku == 5) { printf("Zasobnik je plny"); exit(); } else zasobnik[++pocet_prvku] = x; return; }
Martin Trneˇ cka (UPOL)
Algoritmick´ a matematika 1
4. listopadu 2013
19 / 27
Z´asobn´ık - implementace polem II. int pop(int zasobnik) { int pocet_prvku = sizeof(zasobnik) / sizeof(int); if(pocet_prvku == 0) { printf("Zasobnik je prazdny"); exit(); } else return zasobnik[pocet_prvku--]; }
Martin Trneˇ cka (UPOL)
Algoritmick´ a matematika 1
4. listopadu 2013
20 / 27
Z´asobn´ık - implementace seznamem
Martin Trneˇ cka (UPOL)
Algoritmick´ a matematika 1
4. listopadu 2013
21 / 27
Fronta - implementace Pomoc´ı pole (podobna jako z´asobn´ık, nav´ıc ukazatel na zaˇc´atek). Pomoc´ı seznamu. Ve vˇetˇsinˇe jazyk˚ u jiˇz existuje. V´ybˇer struktury urˇcuje sloˇzitost operac´ı.
Martin Trneˇ cka (UPOL)
Algoritmick´ a matematika 1
4. listopadu 2013
22 / 27
Fronta - implementace seznamem I. struct fronta { int hodnota; struct fronta* dalsi; };
Martin Trneˇ cka (UPOL)
Algoritmick´ a matematika 1
4. listopadu 2013
23 / 27
Fronta - implementace seznamem II. void push(int hodnota, struct fronta* f) { struct fronta* novy = (struct fronta*) malloc(sizeof(struct fronta)); struct fronta* pomocna = f; novy->hodnota = hodnota; novy->dalsi = NULL; while(pomocna->dalsi) { pomocna = pomocna->dalsi; } pomocna->dalsi = novy; }
Martin Trneˇ cka (UPOL)
Algoritmick´ a matematika 1
4. listopadu 2013
24 / 27
Fronta - implementace seznamem III. int pop(struct fronta* f) { int hodnota = f->hodnota; *f = *f->dalsi; return hodnota; }
Martin Trneˇ cka (UPOL)
Algoritmick´ a matematika 1
4. listopadu 2013
25 / 27
Fronta - implementace seznamem IV. int main(int argc, char* argv[]) { struct fronta *f = (struct fronta*) malloc(sizeof(struct fronta)); f->hodnota = 10; f->dalsi = NULL; push(11, f); push(12, f); push(13, f); printf("%d\n", pop(f)); printf("%d\n", pop(f)); printf("%d\n", pop(f)); return 0; } Martin Trneˇ cka (UPOL)
Algoritmick´ a matematika 1
4. listopadu 2013
26 / 27
Fronta - implementace polem
Martin Trneˇ cka (UPOL)
Algoritmick´ a matematika 1
4. listopadu 2013
27 / 27
