Maturitní otázka č. 18 - lineární datové struktury

Charakterizujte frontu a zásobník a naznačte jejich programovou realizaci s polem pevné velikosti

Obojí jsou datové struktury, které umožňují dvě základní operace: push(x) a pop(). Funkce push vloží zadaný prvek do datové struktury, funkce pop jeden prvek ze struktury vyndá a navrátí jej. Použít pro jejich vnitřní ukládání dat pole pevné velikosti je velmi rozumné, ale šlo by to i jinak. Když chceme vkládat do zcela plné datové struktury nebo odebírat ze zcela prázdné, musí se nějakým civilizovaným způsobem vyhlásit chyba.

Zásobník čili stack navrací prvky v opačném pořadí, než v jakém je vkládáme; také se mu říká last-in-first-out struktura čili LIFO. Anglické označení stack je přiléhavé: připomíná například stoh papírů, kdy další papíry pokládáme navrch a odebíráme také vždy ten horní.

Naprogramovat jej s polem je jednoduché: krom pole samotného si budeme pamatovat počet prvků, které v zásobníku jsou. To nám zároveň určuje index prvku v poli, kam bychom vkládali nový prvek při zavolání funkce push; odebírat při volání pop tedy budeme prvek předcházející. Po každém vkládání prvku počet zvýšíme, po každém odebrání snížíme.

Před odebíráním musíme ověřit, že v zásobníku nějaké prvky jsou - pokud ne, vyhlásíme chybu. Naopak, před přidáním ověříme, že počet prvků v zásobníku je menší než velikost pole, jinak vyhlásíme chybu.

Fronta navrací prvky ve stejném pořadí, v jakém je vkládáme; nikdo nepředbíhá. Anglicky se to řekne queue nebo first-in-first-out, FIFO.

Při programování fronty v poli nám už jedna proměnná navíc nestačí. Prvky budeme odebírat ze začátku a rozhodně si nemůžeme dovolit po každém odebraném prvku posouvat celý obsah pole zpátky doleva. Kromě počtu prvků uvnitř si tedy musíme pamatovat také polohu začátku a po každém volání pop ji posunout doprava. Díky tomu můžou ostatní prvky zůstat, kde jsou. Nové prvky pak budeme přidávat do pole na pozici danou součtem začátku fronty a počtu prvků ve frontě.

Takhle přímočaré řešení naráží na zásadní problém: až se po několika odebráních začátek fronty výrazně posune, nezbude nám do konce pole už moc místa a kapacita fronty by se tím zmenšila. Přitom ale před začátkem fronty zůstalo v poli volné místo po odebraných prvcích; bylo by škoda ho nevyužít. Představíme si tedy, že je pole spojené do kruhu a po překročení jeho konce pokračujeme zase od začátku. Zbývá si jen rozmyslet, že k výpočtu skutečné pozice stačí použít dělení velikostí pole se zbytkem. Pro přidávání nepoužijeme výše zmíněný součet, ale jeho zbytek po dělení. Zrovna tak po posunutí začátku jeho hodnotu nahradíme zbytkem po dělení.

Když se fronta napíše takhle, hlásí chybu ve stejných situacích jako zásobník: při odebírání z fronty s nulovým počtem prvků a přidávání do fronty s počtem rovným velikosti pole.

Výjimky (výjimečná odbočka)

Ještě stručně, co to znamená hlásit chybu (maturitní otázky se to netýká, ale je dobré to vědět). Většina moderních jazyků podporuje výjimky neboli exceptions, přehledný způsob, jak zbytku programu ohlásit, že je něco špatně. Část programu volající určitou funkci může obsahovat kód, který se má vykonat, když nastane výjimka; navíc je možné rozlišovat výjimky různých druhů pro všechny možné druhy chyb. Když takový kód zrovna není určený, výjimka zůstane neošetřená a přenese se na vyšší úroveň programu anebo program sletí. Podrobnosti záleží na konkrétním jazyce.

Výjimku v C++, Javě a Ruby vyvoláte příkazem throw. Volání funkce, která výjimku může způsobit, zabalíte do bloku kódu try { ... } a hned za ním následuje blok catch (nazev_vyjimky) { ... }, který ji případně ošetří. Podrobnosti si kdyžtak vyzkoušejte sami.

Popište základní operace pro práci s lineárním spojovým seznamem. Popište, v čem spočívají výhody a nevíhody složitějších variant spojového seznamu.

Spojový seznam (linked list) se skládá ze spousty samostatných prvků rozházených libovolně po paměti, v každém prvku jsou uložená (mimo jiné) nějaká data. Abychom se k nim vůbec nějak dostali, odkazují prvky na sebe navzájem: v nejjednodušší variantě vždy každý na ten následující. Když chceme seznam projít, začneme prvním prvkem, z něj zjistíme adresu druhého a tak pokračujeme, než se dostaneme k hledanému prvku. Často se vyplatí použít dvousměrnou variantu (doubly-linked list), kdy každý prvek odkazuje i na předcházející - pak můžeme snadno procházet seznamem v obou směrech.

Někde si musíme zvlášť pamatovat ukazatel na první prvek seznamu; velmi praktické je pamatovat si i ten poslední, abychom mohli rychle přidávat na konec. Za výhodu spojového seznamu se dá považovat, že všechny ostatní informace jsou uloženy přímo v prvcích a jeho délku můžeme měnit zcela libovolně. Pro pohodlné procházení si zavedeme, že poslední prvek odkazuje na NULL a zrovna tak první v dvousměrném seznamu.

Nevýhodou spojových seznamů (oproti obyčejnému poli) je, že vyhledání n-tého prvku vždycky zabere lineárně dlouho vzhledem k n. Zásadní výhodou je, že můžeme velmi rychle (nezávisle na délce seznamu) vložit nový prvek nebo celý další seznam na libovolné místo. Když je seznam dvousměrný, můžeme také prvky takhle rychle odebírat. Zdá se trochu podivné, k čemu umět rychle odebírat (nebo přidávat), když neumíme příslušný prvek rychle najít; může se stát, že prvek seznamu získáme odjinud, a pak to má smysl.

Spojové seznamy jsou pomalé i z vidláckého hlediska: průchod seznamem, přidání prvku na konec a odebrání z konce trvá prostě několikrát déle než v poli (ačkoliv složitost je v těchhle případech stejná). Počítač musí provést mnohem víc operací - přečíst z paměti spoustu adres a některé přepsat. Navíc, procesory jsou velmi dobře uzpůsobené na procházení pole (automaticky načítají další prvky), ale spojový seznam jim v jakémkoli zrychlování brání.