16. Základní datové struktury
Základní abstraktní datové struktury
Související operace a jejich složitost
Implementace
pojmy
zásobník
fronta
množina
prioritní fronta
seznam
hašovací tabulka
příklady použití
implementace zásobníku/fronty
implementace
duplicity OK
operace na seznamu
prvky lineárně
abstraktní dynam. dat. strukt.
pomocí lineárního (1stranného) spoj. seznamu
pomocí oboustranného spoj. seznamu
pomocí dynam. pole
nemusíme znát předem počet prvků
+ rychlý přístup k prvkům O(1) - náhodný přístup na index i
v případě potřeby se pole realokuje na dvojnásebek
- pomalé odebírání a vkládání doprostřed/na začátek - O(n)
základ - záznam obsahující uloženou hodnotu + ukazatel na následující prvek
ukazatel posledního prvku je prázdný
pokud navážeme konec na začátek - kruhový
ukazatelé prvního a poslendího prvku jsou prázdné
procházení oběma směry - v paměti ale 2krát tolik ukazatelů
navíc ukazatel na předchozí prvek
pokud navážeme konec na začátek - kruhový (sentiel - hlídka - první i poslední prvek)
přidání prvku
smazání k-tého prvku
vytvoření prázdného O(1)
vložení před/za k-tý prvek
setřízení seznamu
vyhledávání v seznamu
test, zda je seznam prázdný O(1)
první prvek - head O(1)
seznam bez prvního prvku - tail (...)
implementace
operace
log. složitost O(log n)
negarantuje pořadí, každý prvek max jednou
abstraktní dynam. dat. strukt.
pomocí hašovací tabulky
pomocí vyhledávacího stromu
pomocí seznamu
neefektivní (vyhledávání - projít celou)
nejjednoduší
ignoruje pořadí a při vkládání se kontroluje přítomnost stejného prvku
téměř konstantní přístup k prvkům - vhodné pro časté vkládání
př.: Java
vhodné pro setřízené množiny
dotaz na prvek x
je množina prázdná
přidání/odebrání prvku
počet prvků (...)
vytvoření
použití: prohledávání do hloubky (!), přerušení, skoky do podprogramů, volání procedur, fcí,...
nejjednodušší typ seznamu
vrchol - přidání/odebrání, LIFO
realizace: programově/obvody
abstr. dynam. dat. str.
implementace
operace
pomocí pole a proměnné
pomocí lineárně spoj. seznamu (ukazatelé)
první prvek - dno
proměnná - index vrcholu
1směrný seznam
první prvek - vrchol --> použiju operaci tail
odebrání O(1)
ověření prázdnosti O(1)
přidání O(1)
prvek na vrcholu zás. O(1)
vytvoření prázdného O(1)
implementace
další typy
prohledávání do šířky
operace
zachovává pořadí, FIFO
abstr. dynam. dat. strukt.
pole + 2 proměnné
lineárně spoj. seznam
časté vkládání a odebírání - zvyš. indexů - řešení
vhodná - 3. prom. - počet prvků
pokud známe max. možnou délku
proměnné - index prvního a posledního prvku
posun, pokud nutné (pak celé)
kruhové pole (slož.)
posouvat prvku o 1 níže (neefektivní)
1směrný - začátek fronty na začátku a konec na konci
každý uzel - ukazatel na následníka
obousměrná (odebírat/vkládat na obou koncích)
prioritní
ověření práznosti O(1)
přidání prvku na konec O(1)
vytvoření O(1)
fronta bez 1. prvku O(1)
první prvek O(1)
seznam, udpořádán podle priorit (ne příchodu)
reprez. seznamem méně efekt. --> bin. halda
kolize
operace
hašovací fce
konzistentně vrací pro stejné objekty stejné adresy
kombinace výhod vyhl. pomocí indexu (O(1)) a procházení seznamu (nízká paměť)
ukládání dvojic klíč - hodnota
nezaručuje vrácení různé adresy pro různé objekty
celý prostor adres se stejnou prstí
výpočet adresy - rychle
modulární aritmetika
využití - rychlé hledání položky v poli/jiném homogennímt typu
při pokusu uložení více objektů na = adresu
haš. fce nezaručuje jinou adresu pro jiné obj.
řešení
zřetězením
otevřenou adresací
hodnoty do spoj. seznamů (kolize - na konec)
velké zaplnění - degradace výkonu
hodnoty do pole
vyhledávání
obvykle
kolize
lineární zkoušení
druhotné hašování
- obsazená - o 1 místo dál
nevýhoda - shlukování - nutné sekvenčně procházet
- spočítáme adresu
dvojce hašov. fcí
- inic. adresa
- pokud obsazeno - vypočte posun - opět posun...
abstr. dat. strukt.
abstr. proměnná
dynam. dat. strukt.
abstr. pole
prvky nejsou indexovány (ukazatelé) - konkr. - projití celého
časová slož. - vkládání/mazání uprostřed - O(n) - lineární vyhledávání
neumožňuje náhodný přístup
pokud neznáme dopředu velikost
data na začátek
využití: fronty zpráv, roura, heapsort
využití: řazení - heapsort, Dijkstr, Jarník
odstranění O(n)
vložení O(n)
vyhledávání prvku O(n), prům. O(1)
mazání - nutné nahradit volná místa hlídkami
pro získání hodnoty z klíče - adresace