PPA2 shrnutí přednášky 2 „letem světem“

M. Prantl

Spojové datové struktury I.

• Do teď – pole

• Od teď – pole + spojové struktury

– Tzn. pole rozhodně neopouštíme

• Proč ?

– Snadné mazání a vkládání prvků mezi existující

– Práce s většími seznamy než v případě polí

• Pole potřebují volnou sekvenční paměť o velikosti N

• Spojové struktury „hledají“ místo kdekoliv v paměti

Spojové datové struktury II.

• Spojový seznam

– Nejzákladnější struktura (viz. dále)

– Jednosměrný, obousměrný, kruhový

• Stromy

• Hashovací tabulky

• Fronta

• Grafy

Spojové datové struktury III.

• Je potřeba ukazatel na další prvek !

– Popř. další ukazatele na jiné prvky (předchozí…)

=> Větší paměťové nároky

Spojové datové struktury IV.

• Snadné mazání

• A obdobně také vkládání

Spojové datové struktury V.

• Projití všech prvků – O(n)

Item tmp = head;

while (tmp != null)

{

//do something with tmp

tmp = tmp.next;

}

Spojové datové struktury VI.

• Přidání prvku – head – první prvek – last – poslední prvek

Item tmp = new Item(…)

if (head == null)

{

head = tmp;

}

else

{

last.next = tmp;

}

last = tmp;

Složitost I.

• Více typů

• Přesné počítání složitosti – naprosto k ničemu

• Podstatné vědět základní – Logaritmická složitost O(log n) – Mocniny n O(n2).... – Lineární O(n) – Konstantní O(1) – Jiné se moc nepoužívají

• Nejčastěji u alg. třídění (n2 vs n log n)

Složitost II.

• Vysoká složitost a její důsledky

Složitost III.

Složitost IV.

Zdroj: wikipedia

Děkuji za pozornost

Otázky ?