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í

  1. obsazená - o 1 místo dál

nevýhoda - shlukování - nutné sekvenčně procházet

  1. spočítáme adresu

dvojce hašov. fcí

  1. inic. adresa
  1. 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