2 Datové struktury
Pole Seznam Zásobník Fronty FIFO Haldy a prioritní fronty Stromy Hash tabulky Slovníky
25
2 Datové struktury
Pole
Datová struktura – kolekce elementů (hodnot či proměnných), identifikovaných jedním nebo více indexy, ze kterých je adresa každého elementu spočitatelná; počet indexů koresponduje s dimenzí pole (vektor, matice, tensor) předem stanovená velikost, prvky stejné velikosti přímý přístup na prvek pomocí indexu v konstatním čase vyhledání a zrušení prvku: O(n) - nutné projít (posunout) celé pole přidání/zrušení prvku na začátku a konci: O(1) nalezení nejmenšího a největšího prvku: O(n)
Setříděné pole
26
vyhledání prvku v O(log n) smazaní prvku v O(log n), pokud je implementováno jako označení prvku za neplatný (jinak v O(n) ) přidání prvku v O(n) nalezení nejmenšího v O(1) a největšího prvku v O(n)
2 Datové struktury
Spojový seznam
27
lineární spojový seznam - dynamická datová struktura, obsahující 1+ datových položek stejného typu, které jsou navzájem lineárně provázany vzájemnýmí odkazy pomocí ukazatelů nebo referencí. Aby byl seznam lineární, nesmí existovat cykly ve vzájemných odkazech. jednosměrný seznam - každá položka odkazuje na položku následující, v obousměrném seznamu odkazuje položka na následující i předcházející položky; konec (tail) a začátek (head) seznamu označují zarážky kruhový (cyklický) seznam – obsahuje cyklus, vytvořený navázáním konce a začátku seznamu Sekvenční přístup k prvkům vyhledání prvku: O(n) přidání/zrušení prvku: O(1)
2 Datové struktury
Zásobník
28
Abstraktní datový typ, charakterizován způsobem manipulace s daty – LIFO (Last In, First Out) pro manipulaci se udržuje tzv. ukazatel zásobníku, který udává tzv. vrchol zásobníku (poslední přidaná položka), a (minimálně) dvě operace – push a pop Typická časová složitost O(1) operací se snadno realizuje pomocí pole nebo lineárního (jednosměrného) spojového seznamu Typické užití zásobníku pro ukládání info a dat při volání zanořených procedur (bezpečnostní problém s buffer overflow)
2 Datové struktury
Fronty FIFO
abstraktní datový typ, charakterizován způsobem manipulace s daty- FIFO (First In, First Out). Typická časová složitost O(1) operací, realizuje se obvykle pomocí spojového seznamu Obvyklé operace:
29
bool empty() – příznak prázdná/neprázdná fronta T& front() – vrací referenci na položku v čele neprázdné fronty void dequeue() – odebere položku v čele neprázdné fronty void enqueue(const T& foo) – zařadí argument foo na konec fronty int size() – vrací počet položek ve frontě
2 Datové struktury
Halda
30
stromová datová struktura splňující vlastnost haldy: pokud je B potomek A, pak klíč(A) ≥ klíč(B). min-heap - v kořenu stromu je prvek s nejmenším klíčem, naopak max-heap.
2 Datové struktury
Halda
min-heap - v kořenu stromu je prvek s nejmenším klíčem, naopak max-heap. stromová datová struktura splňující vlastnost haldy: pokud je B potomek A, pak klíč(A) ≥ klíč(B). Obvyklé operace:
implementace v poli:
31
delete-max / delete-min: odstranění kořene z max-/min-heapu increase-key, decrease-key: aktualizace klíče v max-/min-heapu insert: vložení nového klíče merge: spojení dvou heapů do jednoho nového ki < k2i+1, ki < k2i+2
2 Datové struktury
Prioritní fronty
abstraktní datový typ, charakterizován způsobem manipulace s daty:
32
InsertWithPriority – vlož prvek s asociovanou prioritou GetNext: vyber prvek s nejvyšší prioritou PeekAtNext: ukaž prvek s nejvyšší prioritou, aniž by byl z fronty odstraněn
Implementace pomocí lineární struktury (pole, spojový seznam) – výběr z čela fronty O(1), vložení se zařazením O(n) Implementace pomocí binárního stromu(haldy) – maxheap, výběr O(log n), vložení O(log n)
2 Datové struktury
Stromy
zákl.pojmy - kořen stromu, (vnitřní) uzly či vrcholy, listy, předek (předchůdce) a následovník, rodič a potomek, podstrom stupeň (arita) uzlu = počet přímých následovníků vnitřního uzlu stupeň stromu = maximální stupeň mezi všemi uzly stromu cesta ve stromu: délka cesty = počet hran od kořene k danému uzlu (=hloubka uzlu) délka vnitřní cesty = součet délek cest jednotlivých uzlů průměrná délka vnitřní cesty: 1
PI =
n
∑ n .i i
i
33
kde ni je počet vrcholů na i-té úrovni hloubka uzlu - délka cesty od kořene k uzlu hloubka stromu / výška stromu - rovna hodnotě maximální hloubky uzlu (pro binární strom: n=2h+1–1, tedy hloubka h=floor(log2n) )
2 Datové struktury
Procházení stromem
Uspořádání – metody procházení:
34
R
Přímé (pre-order) uspořádání - R, A, B Vnitřní (in-order) uspořádání - A, R, B A B Inverzní (post-order) uspořádání - A, B, R Dokonale vyvážený strom – pro každý vrchol platí, že počet vrcholů v levém podstromu a pravém podstromu se liší nanejvýše o jedna. Vyhledávací - všechny klíče v levém podstromu jsou menší než a všechny klíče v pravém podstromu jsou větší než klíč v daném vrcholu.
do šířky – procházení po hladinách (vrstvách úrovní) prohledávání do šířky. do hloubky – procházení od kořene stromu na potomky daného vrcholu po jednotlivých větvích - prohledávání do hloubky.
2 Datové struktury
Binární strom
B-strom
35
Orientovaný graf s jedním kořenem, z něhož existuje cesta do všech vrcholů grafu; každý vrchol má max. dva následovníky a s výjimkou kořene právě jednoho předka. Kořen předka nemá. Reprezentace - pomocí dynamické struktury (hrany reprezentovány ukazateli), pomocí pole (viz halda). vícecestný m-ární strom, se stránkovou organizací; každá stránka (až na jednu) musí obsahovat n až 2n uzlů, kde n je zvolená konstanta (= řád B-stromu) B-strom je díky této vlastnosti vyvážený, operace přidání, vyjmutí i vyhledávání tedy probíhají v logaritmickém čase (výška B-stromu min. logm n, max logm/2 n). Typické užití – modifikace (B+) používají souborové systémy (NTFS, ReiserFS, XFS a JFS2) a relační databáze – ukládání indexů
2 Datové struktury seznam
binární strom
(min-) heap
insert
O(1)
O(log n)
O(log n)
findMin
O(n)
O(1)
O(1)
deleteMin
O(n)
O(log n)
O(log n)
decreaseKey
O(1)
O(log n)
O(log n)
delete
O(n)
O(log n)
O(log n)
merge
O(1)
O(m log(n+m))
O(m log(n+m))
36
2 Datové struktury
Skip List
37
Přeskakovací seznam - N-vrstvá struktura, popsána 1990 (William Pugh) jako jednodušší/rychlejší alternativa k vyváženým stromům Randomizovaná varianta setříděného spojového seznamu s dodatečnými paralelními vrstvami. Paralelní seznamy přeskakují více položek. Vyhledávání začíná na nejvyšší vrstvě a přechází do nižších vrstev pokud je aktuální položka větší/rovna vyhledávanému klíči. Je-li rovna, je nalezeno, je-li aktuální položka větší, procedura se opakuje po návratu o jeden krok a přechodu do nižší vrstvy.. Operace Insert, Search, Delete jsou prováděny v čase O(log n) za podmínky dostatečného počtu vrstev
2 Datové struktury
Hash (rozptylovací) tabulky
38
Datová struktura, která používá hashovací funkci H(key) pro efektivní mapování klíče k na celé číslo z intervalu <0, N-1> a ukládá položky (klíč, data) na vypočtené pozice H(key) Při mapování hašovací funkcí může docházet ke kolizím – řešení řetězené seznamy (rozptýlené tabulky), řetězené seznamy s oblastí přetečení, otevřená adresace (sekundární hashovací fce – lineární/kvadratické pokusy, double hash fce) Perfektní hashování: ke kolizím nedochází Vlastnosti: nejhorší případ - všechny klíče kolidují – složitost O(n) Při faktoru naplnění A = n/N (počet položek/velikost tab.) ≈ 0,7 je očekávaná složitost O(1) Příklad H(key) = Ordinal(key) mod N
2 Datové struktury Řešení kolizí 1. řetězené seznamy
tzv. rozptýlené tabulky.
2. oblast přetečení
řetězený seznam je vytvářen v oblasti přetečení
3. sekundární hashovací funkce -
umístění vkládaného prvku na jinou volnou pozici, kterou určíme sekundární hašovací funkcí.
metoda lineárních pokusů - sekvenčně prohledává tabulku, G(i)=i ; tj. h0 = H(k) hi = (h0 + i) mod L, i = 1,…, L-1 Prvky se shlukují kolem pozic primárních klíčů metoda kvadratických pokusů - rozptyluje prvky rovnoměrněji po celém poli, G(i)=ci2, tj. h0 = H(k) hi = (h0 + ci2) mod L, i > 0, c>0 metoda dvojího hashování h0 = H(k) hi = (h0 + j H’(k)) mod L, i > 0, c>0 L ... Neexistuje společný dělitel L a počet řádků (L je bezpečné), jinak se některé pozice obsazují a jiné vůbec
39
2 Datové struktury
Slovníky
Slovník je abstraktní datová struktura, skládající se z množiny unikátních klíčů a a množiny hodnot, kde každý klíč je asociován (mapován) s jednou hodnotou nebo s množinou hodnot. Základní operace: new, insert, find and delete.
40
new() vrací slovník D find(k, D) vrací hodnotu asociovanou s klíčem k ve slovníku D insert(k, v, D) asociuje ve slovníku D klíč k s hodnotou v delete(k, D) ruší klíč k ve slovníku D
Implementace – binární vyhledávací stromy (AVL), skiplisty, hash tabulky aj.
2 Datové struktury
Rekurze
rekurzivní algoritmus volá sám sebe dokud není dosažena ukončovací podmínka Iterativní algoritmus používá opakující se konstrukce (cykly) Příklad Tree (length, angle) { Draw(length, angle); Tree(length/2, angle+delta); Tree(length/2, angle-delta); }
Každý algoritmus využívající rekurzi lze přepsat do nerekurzivního tvaru (např. s použitím zásobníku) Rekurzivní datové struktury – definice dynamických datových struktur (seznamy, stromy): struct node { int n; // some data struct node *ptr_next; // pointer to another struct node }; // LIST is simply a synonym for struct node * typedef struct node *LIST;
41
