Jurdič Radim ABSTRAKTNÍ DATOVÉ TYPY Veškeré hodnoty, s nimiž v programech pracujeme, můžeme rozdělit do několika skupin zvaných datové typy. Každý datový typ představuje množinu hodnot, nad kterými můžeme provádět společné operace a které mají společnou vnitřní reprezentaci. Datové typy jsou například string, byte, char, boolean Zásobník Zásobník je dynamická datová struktura, která umožňuje postupné vkládání prvků a jejich odstraňování, ovšem v takovém pořadí, že naposledy vložený prvek můžeme odstranit jako první (last in - first out, LIFO – pro zjednodušenou představu si představme zásobník pistole). Nad zásobníkem můžeme provádět následující operace: • • • •
push:vložení hodnoty na vrchol zásobníku, pop:odstranění hodnoty z vrcholu zásobníku, top:čtení hodnoty z vrcholu zásobníku a empty:testování, zda je zásobník prázdný.
Reprezentace zásobníku pomocí statického pole V případě, že se rozhodneme využít jako prostoru pro uložení hodnot v zásobníku datový typ pole, musíme při inicializace stanovit jeho velikost. Pole bude mít jako parametr číslo označující maximální počet prvků, které budeme schopni do zásobníku uložit.
Reprezentace zásobníku pomocí dynamického pole Pokud nám nevyhovuje to, že musíme předem určit maximální velikost zásobníku a chtěli bychom velikost zásobníku přizpůsobit podle potřeby, můžeme při přetečení zásobníku automaticky zvětšit velikost pole, do něhož ukládáme hodnoty. Asi není příliš praktické toto zvětšování provádět při vkládání každého prvku, neboť každé zvětšení vyžaduje přidělení paměti pro nové pole a kopírování obsahu pole původního. Můžeme tedy na začátku vytvořit pole určité počáteční velikosti a v případě, že jeho velikost nebude stačit, zvětšíme ho o určitý přírůstek velikosti. Obě tyto hodnoty zadáme v konstruktoru zásobníku.
Reprezentace zásobníku pomocí vázaného seznamu Jinou možností jak dosáhnout automatického přizpůsobování velikosti zásobníku je jeho reprezentace vázaným seznamem položek nesoucích jednotlivé hodnoty. Vázaný seznam je tvořen položkami obsahujícími kromě samotné datové hodnoty také odkaz na následující prvek seznamu.
Fronta Fronta (queue) je datová struktura obdobná zásobníku, ovšem s tím, že se z ní prvky odstraňují v tom pořadí, v jakém byly do fronty vloženy (first in - first out, FIFO). Typ fronta nabízí následující základní operace: • • • •
append: vložení hodnoty na konec fronty, serve: odstranění hodnoty ze začátku fronty, front: čtení hodnoty na začátku fronty a empty: testování, zda je fronta prázdná.
Fronta pomocí cyklického pole Pokud se chceme vyhnout nutnosti přesouvat prvky pole , můžeme využít variantu založenou na cyklickém přidělování prvků statického pole. Zkuste si představit pole, do něhož budeme ukládat hodnoty, jako proužek papíru rozdělený na jednotlivé buňky a na koncích slepený tak, že za posledním prvkem pole následuje opět první prvek. Jednotlivé hodnoty pak budeme mít uložené v souvislé řadě kdekoliv v tomto poli, přičemž si budeme pamatovat pouze index, od kterého budeme prvky vybírat, a index, za který budeme prvky vkládat. Pokud by se stalo, že se oba indexy někde „potkají,“ znamená to, že došlo k zaplnění celého pole. - prázdny seznam – začátek je před koncem fronty, - 1.prvkový seznam – začátek a konec ukazují na stejné políčko, - plný seznam – začátek je o jedno políčko před koncem. Fronta pomocí vázaného seznamu V případě implementace pomocí vázaného seznamu si můžeme udržovat odkaz na první prvek, takže pro odebrání prvku ze začátku fronty nemusíme zbývající prvky přesunovat, ale postačí jen přesměrování odkazu z prvního prvku na druhý. Složitost této operace je tedy konstantní. Pro připojení prvku na konec fronty potřebujeme vyhledat poslední prvek. Pokud budeme postupovat od začátku fronty a přesouvat se směrem vpřed až k poslednímu prvku, bude tato operace vyžadovat počet kroků úměrný délce fronty, takže časová složitost operace vkládání bude lineární. Ovšem opět postačí si pamatovat odkaz na poslední prvek a ten pak připojit jednoduchým přesměrováním odkazů. Tato operace má již složitost konstantní.
Seznam Seznam (list) je datová struktura, která umožňuje kromě základních operací nad obecnou kolekcí také přistupovat k libovolnému prvku na základě pořadového čísla (indexu) a vkládat a rušit prvky na libovolné pozici. Představuje vlastně nejobecnější kolekci, pomocí které můžeme implementovat kolekce další včetně zásobníku a fronty. Každý seznam si udržuje informaci o aktuálním prvku. K tomuto aktuálnímu prvku se vztahuje řada operací. Platí, že k aktuálnímu prvku nějak doiterujeme, nelze si tedy najednou říct: "aktuální prvek bude tenhle" a ukázat někam doprostřed seznamu. Aktuální prvek je jakási vnitřní proměnná seznamu, jejíž hodnotu nám může na žádost seznam poskytnout. Abychom mohli po seznamu iterovat (a tedy prohlížet jeho prvky) musíme mít nějaký záchytný bod. Tento záchytný bod nastaví funkce: • • • • • • • • •
end first insert locate retrieve delete next previous create
Po zavolání těchto funkcí, se nastavuje vnitřní proměnná aktuálního prvku na čelo respektive ocas seznamu. Funkce vrací zda se to povedlo. Metody, jakými můžeme realizovat vyhledání prvku, záleží na konkrétní implementaci kolekce, ale všechny musí řešit jeden společný problém, a to jak definovat rovnost objektů.. Hlavní používané metody implementace seznamu jsou následující: • • • •
seznam implementovaný polem, jednosměrně vázaný seznam, obousměrně vázaný seznam. pomocí indexů
Implementace seznamu pomocí pole Při implementaci seznamu pomocí pole můžeme podobně jako v případě zásobníku využít statického pole, jehož velikost je dána předem, případně dynamického pole, jehož velikost se
upravuje podle potřeby. V případě statického pole musíme předem rozhodnout, jaký nejvyšší počet prvků může být v seznamu současně uložen. Pokud tento počet známe již při implementaci aplikace, může být řešení využívající statického pole velmi efektivní. Je možné také na začátku činnosti aplikace zjistit požadovanou velikost (např. z konfiguračních údajů nebo parametrů spuštění programu), pole o této velikosti vytvořit a dále s ním pracovat již podobně jako se statickým polem. Z hlediska časové složitosti jsou kritickými operacemi vkládání a rušení prvku uvnitř seznamu. Pro přidání nebo zrušení prvku na konci seznamu totiž stačí pouze aktualizovat informaci o délce seznamu, zatímco na ostatních pozicích je třeba všechny následující prvky přesunout a vytvořit tak místo pro nový prvek, případně naopak zaplnit mezeru po odstraněném prvku. Tento přesun má obecně lineární časovou složitost. Naopak velmi efektivní je v případě reprezentace seznamu polem operace čtení prvku z libovolné pozice. Operaci indexOf() zajišťující vyhledání prvku v seznamu můžeme realizovat nejjednodušší metodou lineárního vyhledávání, kdy postupně projdeme všechny prvky v seznamu a porovnáváme je s hledaným klíčem. Složitost této operace je lineární, v nejhorším případě musíme provést tolik kroků porovnání, jaká je délka seznamu. Jednosměrně vázaný seznam S jednosměrně vázaným seznamem jsme se vlastně setkali již při implementaci zásobníku a fronty. V obou případech jsme použili položky nesoucí data a odkaz na následující prvek. Pokud budeme chtít s touto datovou strukturou pracovat jako s obecným seznamem, je třeba se opět zamyslet nad složitostí jednotlivých operací.
Při vkládání na konkrétní pozici jednosměrně vázaného seznamu musíme nejprve vyhledat požadovanou pozici, na což potřebujeme čas úměrný délce seznamu. Samotné vložení, případně odstranění prvku je již proveditelné v konstantním čase, neboť vyžaduje pouze přesměrování odkazů. Máme-li však již k dispozici referenci na konkrétní prvek seznamu (např. po úspěšném vyhledávání), jsme schopni za něj vložit nový prvek v konstantním čase. Vložení prvku před tuto pozici nebo odstranění aktuálního prvku je ale podstatně složitější, neboť potřebujeme nejprve vyhledat předcházející prvek, abychom mohli aktualizovat jeho odkaz na následníka. K vyhledání tohoto prvku však potřebujeme opět lineární čas.Ale jak tuto operaci urychlit? Řešením je zřejmě rozšíření položky seznamu o odkaz na předcházející prvek. To nám umožní jednak provést vkládání nebo rušení na aktuální pozici i před ní, jednak se můžeme v seznamu lehce pohybovat nejen směrem vpřed, ale i zpět.
Oboustranně vázaný seznam Položka obousměrně vázaného seznamu tedy obsahuje odkaz na předcházející i následující prvek seznamu. První prvek seznamu má odkaz na předcházející prvek nastaven na null(nil), poslední prvek seznamu má podobně nastaven odkaz na následující prvek na null(nil)
V takto realizovaném seznamu jsme schopni velmi jednoduše vkládat, číst a rušit prvky na začátku i na konci seznamu (v konstantním čase) a máme-li k dispozici referenci na libovolný prvek seznamu, jsme schopní opět v konstantním čase za něj nebo před něj vložit nový prvek, případně tento prvek nebo některého jeho souseda ze seznamu odstranit. Strom Strom můžeme chápat jako zobecněný seznam, ve kterém může mít každý prvek více následníků. První prvek této struktury se nazývá kořen stromu, prvky bez následníků se označují jako listy. Uzlům, které nejsou listy, obvykle říkáme vnitřní uzly stromu. Stromy z pohledu matematiků a informatiků jsou poněkud zvláštní v tom, že se nejčastěji kreslí kořenem nahoru.Kořenem je uzel 1, vnitřními uzly stromu jsou 1, 3 a 4 a listy jsou uzly 2, 5, 6 a 7.
Strom patří do skupiny rekurzivních datových typů, neboť jeho definici lze popsat následujícími dvěma pravidly: 1. Samostatný uzel bez následníků je strom. 2. Uzel s alespoň jedním následníkem, který je stromem, je rovněž strom.
Binární strom V praxi se často setkáváme s binárními stromy, jejichž uzly mají nejvýše dva následníky. Tento typ stromu se používá například pro vyhledávání, reprezentaci zanořených seznamových struktur nebo jako vnitřní struktura pro rozhodovací systémy. Průchod stromem Při průchodu stromem začínáme kořenem stromu a postupně procházíme v určitém stanoveném pořadí jeho uzly a v každém provedeme nějakou akci. V principu můžeme u binárního stromu definovat tři typy průchodů v závislosti na tom, ve kterém okamžiku stanovenou akci provedeme: • • •
preorder - akci provedeme před vstupem do levého podstromu, inorder - akci provedeme po zpracování levého podstromu, ale ještě před vstupem do pravého podstromu a postorder - akci provedeme až po zpracování levého a pravého podstromu.
Volba typu průchodu vždy závisí na konkrétním algoritmu. Pokud nám nezáleží na pořadí, ve kterém se budou uzly stromu zpracovávat, můžeme v podstatě zvolit libovolný typ průchodu např. pokud bychom chtěli pouze zjistit počet uzlů stromu, určit jeho výšku nebo sečíst hodnoty ve všech uzlech.
Binární vyhledávací strom Pojmem binární vyhledávací strom označujeme binární strom, jehož uzly obsahují vzájemně porovnatelné klíče a jenž je uspořádaný takovým způsobem, že klíče všech uzlů levého podstromu jsou menší nebo rovny klíči aktuálního uzlu a klíče všech uzlů pravého podstromu jsou větší než klíč aktuálního uzlu Pokud nepřipouštíme vícenásobný výskyt klíčů, pak na obou stranách bude mezi klíči platit ostrá nerovnost.
Vyhledávání v binárním vyhledávacím stromu je založeno na již představeném principu binárního vyhledávání. Zde se množina hodnot, v nichž vyhledáváme, rozděluje na dvě části dané levým a pravým podstromem aktuálního uzlu. Je-li vyhledávaná hodnota menší než je klíč aktuálního uzlu, pak pokračujeme levým podstromem, je-li větší, pokračujeme pravým podstromem. Složitosti binárního vyhledáván je logaritmická, ovšem za předpokladu, že množinu vyhledávaných hodnot rozdělíme vždy přesně na polovinu. Jenže u binárního vyhledávacího stromu tato podmínka platit nemusí, stačí si představit strom, jehož každý vnitřní uzel má levý podstrom tvořený pouze jediným listem. Binární strom vlastně degraduje na obyčejný seznam a složitost vyhledávání vzroste na lineární.
V ideálním případě má každý vnitřní uzel vyhledávacího stromu právě dva následníky. Takovému stromu se pak říká absolutně vyvážený strom a u něj je logaritmická složitost zaručena. Stromy s neomezeným větvením Není-li omezen počet následníků uzlu stromu, pak hovoříme o stromu s neomezeným větvením. Tuto datovou strukturu můžeme realizovat přirozeně tak, že každý uzel stromu bude obsahovat seznam následníků Jinou variantou je propojení každého uzlu s jeho nejlevějším následníkem a pravým sousedem. Tato varianta je výhodná například tam, kde potřebujeme zajistit statické přidělení paměti pro uzel stromu (např. v poli) - dynamický seznam následníků je nahrazen právě uvedenými dvěma ukazateli. Podle konkrétní potřeby můžeme strukturu uzlu rozšířit ještě o ukazatel na nadřazený uzel; naopak lze prakticky využít i takové stromy, ve kterých každý uzel zná pouze svůj nadřazený uzel a další vazby neudržujeme.
Reprezentace výrazu jako obecného stromu Předchozí část byla věnována homogenní stromové struktuře, kdy všechny typy uzlů stromu byly shodné. V praxi však mohou nastat i situace, kdy například typ listu je jiný než typ vnitřních uzlů, nebo kdy je strom tvořen různými typy uzlů, jejichž větvení je pak dáno konkrétním typem uzlu. pickým příkladem použití obecného stromu je reprezentace aritmetického výrazu. Každý aritmetický výraz můžeme znázornit stromovou strukturou, ve které vnitřní uzly představují operátory (počet následníků je pak dán aritou operace) a listy představují operandy. Například výraz 2 + 3 * 6 můžeme reprezentovat tímto stromem:
Pro lepší reprezentaci výrazu, je lepší použít tuto stromovou strukturu:
Základem reprezentace výrazu je abstraktní třída Expr, která představuje libovolný výraz. Tento výraz můžeme specializovat na výraz tvořený unárním operátorem (UnaryExpr) a výraz tvořený binárním operátorem (BinaryExpr). Budeme-li pro jednoduchost uvažovat pouze výrazy tvořené celočíselnými operandy a operátory pro změnu znaménka, sčítání a násobení, získáme čtyři listové třídy ConstExpr, NegExpr, AddExpr a MulExpr. Takto definovaná struktura tříd umožní rozšiřování o další druhy operandů a operátorů, aniž by bylo třeba přepisovat existující definice. Třídy reprezentující konkrétní operandy a operátory také implementují metodu toString(), aby bylo možné výraz v čitelné podobě zobrazit.
