Praktická cvičení algoritmů

{posouv me levě index, dokud

neni na prvku vetsim nez pivot}

while pole[j]>P do dec(j);

{posouvame pravy index,

dokud neni na prvku mensim nez pivot}

if i<j then {pokud se indexy neprekrizily a nejsou shodne} begin pom:=pole[i]; {vymenime nalezene prvky} pole[i]:=pole[j]; pole[j]:=pom; inc(i); dec(j); {a posuneme indexy na dalsi prvky} end else if i=j then {pokud se indexy sesly (ukazuji na pivota)} begin inc(i); {posunume je jeste dale, aby vymezovaly roztridene

poloviny pole}

dec(j); {a doslo k prekrizeni, coz vede k ukonceni cyklu} end until i>j; {opakujeme, dokud nejsou obeti casti pole roztrideny podle pivota} {Pole [Zac,Kon] je rozdeleno na 2 useky [Zac,j] a [i,Kon], ktere zpracujeme rekurzivne (opet touto procedurou)}

if Zac<j then QuickSort(pole,Zac,j);

{ma smysl tridit

nejmene dva prvky}

if i
31

Řešený příklad 5:

Základní problém - nalezení dělící hodnoty: Hodnotu není možné určit algoritmicky - hledání by znehodnotilo celou metodu. Proto se "uhodne" jako hodnota prvku ležícího uprostřed řazené části. V nejhorším případě se pole rozdělí na jeden prvek a zbytek.

2.6. Výhody a nevýhody Je zřejmé, že algoritmy probrané v prvních třech podkapitolách (BubbleSort, Select-Sort, Insert-Sort) patří k méně efektivním a pro profesionální využití nevhodným algoritmům. Jejich časová složitost principiálně kvadratická – o(n2). To znamená, že v průměrném případě stoupá čas potřebný k seřazení pole kvadraticky vzhledem k počtu prvků. Jde tedy sice o postupy poměrně efektivní (v informatice je mnoho problémů, které neumíme řešit v polynomiálním čase, např. optimalizační problémy), ale přesto není tato kvadratická složitost tím nejlepším možným. Přesto existují i případy, kdy tyto postupy mohou být relativně zajímavé pro využití v praxi. Shrňme je nyní pro každý algoritmus zvlášť. Bubble-Sort:

32

-

velmi dobrá efektivita pro téměř seřazené vstupní posloupnosti

-

díky přesunům mezi sousedními prvky je velmi vhodný pro použití u dynamických datových struktur jako jsou spojové seznamy

-

jednoduchá implementace a možnost přidat dodatečné modifikace pro speciální typy vstupních polí

Insert-Sort: - vhodný pro dynamické datové struktury (vkládání mezi prvky), odpadá časově náročné přesouvání celého zbytku pole – u statických struktur je to náročná operace

Select-Sort: -

dává nejstabilnější časové výsledky – provádí se vždy (u libovolného pole stejné velikosti) přesně stejný postup

Samozřejmě pro profesionální využití jsou použitelné dvě poslední metody (Quick-Sort a Heap-Sort). Více používanou metodou je Quick-Sort, který v průměrném případě má o něco lepší složitost. Přesto je složitost obou o((log n)*n) – tedy logaritmicko-lineární. Pokud si dokážete představit graf takovéto funkce, je jasné, že složitost této metody je výrazně lepší než u třech metod triviálních. I v řádech tisíců řazených prvků bude metoda hotova velmi rychle narozdíl od kvadraticky rostoucí funkce. Problém QuickSortu je možná jeho rekurzivní založení a pak také, že pronejhorší případ může degradovat až na kvadratickou složitost. Tuto nevýhodu nemá právě Heap-Sort, který pro všechny případy logaritmicko-lineární, avšak v průměrném případě má o něco horší koeficienty dané funkce. Nejdůležitější probrané pojmy: -

triviální algoritmy třídění – Bubble-Sort, Insert-Sort, Select-Sort efektivní algoritmy třídění – Quick-Sort, Heap-Sort

Úkoly a otázky k textu: 1. Vyčíslete přesný počet operací, které vám nad vámi zvoleným polem prvků provedou postupně všechny uvedené algoritmy řazení.

33

3. Implementace řadících algoritmů v Javě Cíl: Seznámíte se: • se způsobem práce se soubory v jazyce JAVA • možnostmi rozdělení úlohy do více knihoven • způsobem implementace jednoduchého textového menu • způsobem odečítání času a dalších speciálních technik • generování náhodných dat V předchozí kapitole jsme se seznámili s tím nejdůležitějším algoritmickým vybavením, které pro zpracování první úlohy budete potřebovat. Algoritmy jsme ukázali na příkladech a kódech (původně Pascal – ovšem ten je velmi podobný pseudokódu), ovšem pouze na konceptuální úrovni. Nyní je potřeba vás připravit na implementační problémy. A jak již bylo řečeno v úvodu, nyní je preferovaným jazykem implementace JAVA. Chci zdůraznit, že toto v žádném případě není kurz programování v Javě. To by vyžadovalo solidně vás nejprve uvést do problematiky objektově-orientovaného programování, což není účelem kurzu a ani by to dost dobře nešlo skloubit s výukou základní algoritmizace. Java je samozřejmě objektový jazyk, i když v rámci metod programujete spíše procedurálně a právě tento moment se pokusíme využít. Je to poněkud těžkopádné, protože vás tím vlastně ochuzuji o podstatu jazyka JAVA, ale je to nezbytné, abych jste mohli zpracovat daný úkol. Vychází to z obecného konceptu výuky na Ostravské Univerzitě a i přestože by pro vás asi byla vhodnější implementace v neobjektovém jazyce, musíme se držet této stanovené linie. Předpokládám, že po absolvování kurzu Algoritmy a datové struktury již 3.1. Práce se soubory Nezbytnou součástí snad každé profesionální aplikace je vstupně-výstupní práce se soubory. Účelem informačních systémů je nějakým způsobem zpracovávat data a ty jsou většinou uloženy v externích souborech a rovněž se do souborů ukládají. Je tedy potřeba, co nejvhodnějším způsobem načíst data (např. čísla) do datových struktur v operační paměti. V jazyce Pascal jsme neměli příliš na výběr, jakou datovou strukturu použít. V objektové hierarchii jazyka JAVA existuje však mnoho objektů, pomocí kterých lze načíst daná data do datových struktur. Následující ukázka se jeví pro naše účely jako poměrně nejpohodlnější. Java má mnoho možností jak načítat u ukládat data do souborů. V zásadě můžete využívat buď zcela základních objektů typů Stream, které ovšem nebudou schopny přímo načítat různé typy dat (čísla, řetězce atd..), ale jsou určeny spíše pro primitivní práci s byty, maximálně

34

nekonvertovanými řetězci. Je možno tedy doporučit cestu nejmenšího odporu a použití objektu typu Scanner. Ten umožňuje otevřít textový soubor, definovat si dokonce regulární výrazy jako oddělovače a jednotlivá celá čísla ze vstupního souboru načítat pohodlně například metodou nextInt (následující číslo). Rovněž lze velice elegantně testovat, zda jste již na konci souboru prostým zavoláním metody hasNextInt, která sama otestuje, zda je v souboru ještě nějaké číslo. Lze si prohlédnout v dokumentaci JDK celou třídu typu Scanner, uvidíte, že je tam obrovské množství velice komfortních funkcí pro programátory, které by jinak zabraly velké úsilí. Navíc ve Streamech není k dispozici test konce souboru, tak jak ho známe třeba z Pascalu a tudíž je nutné provést otestování vzniku výjimky na konec souboru, což u Scanneru není. Proto silně doporučuji Scanner pro práci se soubory (textovými). Následující zdrojový kód vám načte připravený soubor test.txt (musíte si ho vytvořit) do pole, ve kterém jsou mezerami oddělená celá čísla. Zároveň vám uchová počet prvků ve stejnojmenné proměnné. Pole je deklarováno jako statické s pevným počtem prvků (10tis.). Řešený příklad 6: import java.io.*; import java.util.*; public class souborVstup { public static void main (String[] args) { int pole[] = new int[10000]; int pocetPrvku = 0; try { Scanner sc = new Scanner(new File("test.txt")); while (sc.hasNextInt()) pole[pocetPrvku++] = sc.nextInt();

sc.close(); } catch (IOException e) { System.out.println("Chyba pri cteni souboru!");

} for (int i = 0;i<pocetPrvku;i++){ System.out.print("pole["); System.out.print(i); System.out.print("]="); System.out.print(pole[i]); System.out.println(""); } }

}

Výstupy do textového souboru s pole lze nejjednodušeji provést pomocí připraveného komfortního objektu Typu PrintWriter. Ten lze opět vytvořit přímo jako diskový soubor. V cyklu se pak jednotlivá čísla v poli uloží pomocí metody print.

35

Třída Scanner

3.2. Tvorba náhodného pole čísel a odečet času V Javě lze odečíst čas pomocí vytvoření objektu typu Date (aktuální čas). Ten má metodu getTime, která vám přímo vrátí čas v milisekundách (od 1.1.1970). Stačí pak odečíst čas ještě jednou do nové proměnné po skončení měřených činností a jednoduše je odečíst. Níže uvedený kód vám tedy vytvoří pole náhodných čísel typu Int mezi 0...1000, dále jej uloží do souboru testout.txt a navíc přitom dvakrát odečte čas, který se vypíše (rozdíl dt1 a dt2). Date je samozřejmě opět mnohem složitější objekt, opět pro podrobnosti se doporučuje nahlédnout do Doc JDK. Řešený příklad 7: import java.io.*; import java.util.*; import java.lang.*; public class souborVystup{ public static void main (String[] args) { long time1, time2; Date dt1, dt2; dt1 = new Date(); time1 = dt1.getTime(); int pole[] = new int [100000]; int pocetPrvku = 100000; for (int i=0; i<pocetPrvku;i++){ pole[i] = (int)((Math.random())*1000); } try { PrintWriter outFile = new PrintWriter("testout.txt"); for (int i=0; i<pocetPrvku;i++){ outFile.print(pole[i]); outFile.print(" "); } outFile.close(); } catch (IOException e) { System.out.println("Chyba pri cteni souboru!"); } dt2 = new Date(); time2 = dt2.getTime(); System.out.print("Cele to trvalo ms:"); System.out.println(time2-time1); } }

V přiloženém zdrojovém kódu je rovněž obsaženo vygenerování pole 100tis. Pseudonáhodných čísel. K tomu se použije metoda random třídy Math. Problém je, že vrací reálné číslo mezi 0 a 1, což nechceme. Proto je hodnota vrácená touto metodou násobená stem a pak násilně přetypována

36

na typ Int. Násilné přetypování z reálného čísla mezi 0..1000 udělá jeho celou část (provádí se pomocí cílového typu v závorce před přetypovávaným výrazem).

3.3. Jednoduché textové menu Další nutnou součástí zadání je vytvoření menu s možností volby dané akce (např. načtení pole ke třídění nebo výpis tabulky s porovnáním efektivity). Následující kód ukazuje možný příklad takovéhoto programu. Řešený příklad 8: public static void main(String args[]) { int volbaMenu; System.out.println("Porovnani efektivity radicich algoritmu"); System.out.println("======================================="); do { System.out.println(" ----------------------------------"); System.out.println(" Menu programu:"); System.out.println(" ----------------------------------"); System.out.println(" 1 - Nacteni pole ze souboru"); System.out.println(" 2 - Ulozeni pole do souboru"); System.out.println(" ----------------------------------"); System.out.println(" 3 - Generovani pole"); System.out.println(" ----------------------------------"); System.out.println(" 4 - Setrideni pole - SelectSort"); System.out.println(" 5 - Setrideni pole - InsertSort"); System.out.println(" 6 - Setrideni pole - BubbleSort"); System.out.println(" 7 - Setrideni pole - QuickSort"); System.out.println(" 8 - Setrideni pole - HeapSort"); System.out.println(" ----------------------------------"); System.out.println(" 9 - Porovnani efektivity algoritmu"); System.out.println(" ----------------------------------"); System.out.println(" 0 - Konec programu"); System.out.println(" ----------------------------------"); volbaMenu=VstupVystup.ctiInt("Vase volba: "); switch (volbaMenu) { case 1:Global.pocetPrvku = VstupVystup.nactiPole(Global.pole,"",true);break; case 2: VstupVystup.ulozPole(Global.pole,Global.pocetPrvku,"",true); break; case 3:Global.generujPole(0,true);break; case 4: MetodyTrideni.selectSort(Global.pole,Global.pocetPrvku,true); break; case 5: MetodyTrideni.insertSort(Global.pole,Global.pocetPrvku,true); break; case 6: MetodyTrideni.bubbleSort(Global.pole,Global.pocetPrvku,true); break; case 7: MetodyTrideni.quickSort(Global.pole,0,Global.pocetPrvku1,true); break; case 8: MetodyTrideni.heapSort(Global.pole,Global.pocetPrvku,true); break;

37

case 9:Efektivita.porovnani();break; case 0:System.out.println("KONEC PROGRAMU"); } try {Thread.sleep(800);} catch(InterruptedException e) {}; System.out.println("\n"); } while (volbaMenu != 0); }

Nabídka je realizována pomocí dvou složek. Jednak je pomocí metody println na standardní výstup vypsána tabulka možných voleb. Pak se ve větvení typu switch (v Pascalu case) po stisku klávesy provede daná volba. Např. se setřídí pomocí metody selectSort třídy MetodyTrideni setřídí dané pole prvků o zadané velikosti. (pozor! Pokud pracujete se statickým polem, musíte vždy znát velikost obsazené části pole – pole je deklarováno na určitou maximální velikost, ale využita může být jen část.) 3.4. Dělení do knihoven

Knihovny

Při vytváření rozsáhlejších projektů jako je tento je potřeba rozdělit celou aplikaci do logických bloků (knihoven), z nichž každá obsahuje třídy a metody podle určité logické funkce. V Pascalu jsme hovořili o tzv. unitách. Pro náš příklad použití řadících algoritmů, se nabízí například rozdělení na: - hlavní ovládací program (menu) - vstupy a výstupy do souborů - vlastní algoritmy pro setřídění pole čísel - integrující knihovna pro vygenerování tabulky porovnání časové efektivity Knihovna pro vstup a výstup. Řešený příklad 9: import java.io.*; import java.util.*; public class VstupVystup { private static BufferedReader vstup = new BufferedReader(new InputStreamReader(System.in)); public static int ctiInt(String text) { boolean chyba; int i = 0; do { chyba = false; System.out.print(text); try { i = Integer.valueOf(vstup.readLine()); } catch (Exception e) {chyba = true;} } while (chyba); return i; } ....

38

Knihovna třídících metod Řešený příklad 10: import java.util.*; public class MetodyTrideni { static long selectSort(int[] pole, int pocetPrvku, boolean hlaska) { Date c1 = new Date(); int n = pocetPrvku-1; int max = pole[0]; int k; for (int j = n; j >= 1; j--) { max = pole[j]; k = j; for (int i = 0; i <= j; i++) { if (pole[i] > max) { max = pole[i]; k = i; } } pole[k] = pole[j]; pole[j] = max; } if (hlaska) System.out.println("Setrideno " + pocetPrvku + " prvku pomoci SelectSort."); Date c2 = new Date(); return c2.getTime()-c1.getTime(); } ...

Porovnání efektivity: Řešený příklad 11: public class Efektivita { static void porovnani() { long[][] casy = new long[4][5]; System.out.print("provadeji se testy... "); for (int i = 0; i < 4; i++) { Global.generujPole((int)Math.pow(10,i+1),false); VstupVystup.ulozPole(Global.pole,Global.pocetPrvku,"srovnani ",false); casy[i][0] = MetodyTrideni.selectSort(Global.pole,Global.pocetPrvku,false); VstupVystup.nactiPole(Global.pole,"srovnani",false); casy[i][1] = MetodyTrideni.insertSort(Global.pole,Global.pocetPrvku,false); VstupVystup.nactiPole(Global.pole,"srovnani",false); casy[i][2] = MetodyTrideni.bubbleSort(Global.pole,Global.pocetPrvku,false);

39

VstupVystup.nactiPole(Global.pole,"srovnani",false); casy[i][3] = MetodyTrideni.quickSort(Global.pole,0,Global.pocetPrvku-1,false); VstupVystup.nactiPole(Global.pole,"srovnani",false); casy[i][4] = MetodyTrideni.heapSort(Global.pole,Global.pocetPrvku,false); }

Globální deklarace pole: import java.util.*; public class Global { public static int[] pole = new int[10000]; public static int pocetPrvku = 0;

... Jelikož v rámci všech unit budete využívat jisté globální deklarace (např. strukturu pole), je nutné ji deklarovat ve zvláštní knihovně. Nejdůležitější probrané pojmy: -

Vstupy a výstupy v Javě knihovny vlastních tříd a metod

Úkoly a otázky k textu: 1. Prozkoumejte další možností vstupně-výstupních metod a napište pro ně ukázkové kódy.

40

4. Dynamické datové struktury Cíl: Seznámíte se: • s pojmem dynamické datové struktury • implementací datové struktury typu spojový seznam Při vytváření programových kódů v různých programovacích jazycích potřebujeme často, aby prvky různých datových typů spolu nějakým způsobem souviseli. Říkáme, že potřebujeme prvky zřetězit. Toto může být zapříčiněno mnoha důvody: • například chceme, aby prvky byli nějakým způsobem seřazeny •

potřebujeme pracovat s celou množinou prvků kvůli tomu, že v této množině vyhledáváme nějakou hodnotu (nejmenší, největší atd.)

• zjišťujeme počet výskytů daného prvku v množině prvků Důvodů můžeme nalézt mnoho. Cílem tohoto textu je seznámit čtenáře s datovými strukturami, které umožňují vytváření řetězců různých datových typů a taky manipulaci s těmito datovými strukturami (vkládání, odebírání, vyhledávání prvků atd.). Při popisování tvorby těchto datových struktur je použito jednoduchého programovacího jazyka Pascal, který byl zaveden společností Borland. Některé části jsou pak porovnávány s programovacím jazykem C, který má společné rysy s programovacími jazyky C++, C# nebo Java. 4.1. Datový typ ukazatel a dynamická proměnná Proměnná datového typu ukazatel je statická proměnná. Tato proměnná se na rozdíl od ostatních statických proměnných nepoužívá k uchovávání konkrétní hodnoty, ale jen k uložení adresy. Tím, že lze pomocí statické proměnné odkazovat na konkrétní místo v paměti, lze s touto pamětí dynamicky pracovat. V programovacích jazycích proměnná datového typu UKAZATEL slouží k vytváření dynamických proměnných. Používání dynamických proměnných je velmi efektivní z hlediska využívání paměti. Nezávisle na datovém typu, na který UKAZATEL ukazuje, zabírá tento datový typ v paměti 4B. Tento datový typ se podobně jako ostatní statické proměnné deklaruje v deklarační části programového kódu. Je znám pod anglickým názvem POINTER. Pokud se nepodaří vytvořit dynamickou proměnnou (například z důvodu malé dostupné paměti) obsahuje proměnná datového typu UKAZATEL hodnotu NIL, což znamená, že neukazuje na žádnou proměnnou. Tato

41

Ukazatel

hodnota by této proměnné měla být přiřazena také po zániku dynamické proměnné. Dovolené operace s proměnnou datového typu UKAZATEL: • přiřazení - na levé i pravé straně přiřazovacího příkazu musí být proměnná datového typu UKAZATEL • relační operace - obvykle jsou dovoleny jen operace rovnosti = a nerovnosti <> • získání hodnoty a vytvoření dynamické proměnné - v jazyku Pascal může ukazatel získat adresu s hodnotou, na kterou bude odkazovat třemi způsoby: a) použití adresního operátora @ b) použitím standardní procedury NEW c) použitím standardní procedury GetMem • odebrání hodnoty a zrušení dynamické proměnné - v jazyku Pascal může být ukazateli odebrána hodnota dvěma způsoby: a) použitím standardní procedury DISPOSE b) použitím standardní procedury FreeMem Po zrušení dynamické proměnné je dobré také zrušit adresu v paměti, na kterou ukazatel odkazuje. V takovém případě se ukazateli přiřazuje tzv. prázdná hodnota. V Pascalu se nazývá NIL. V jazyce JAVA existuje trochu odlišný způsob práce s ukazateli. Není potřeba jako v Pascalu nebo C rušit dynamickou proměnnou. O to se stará tzv. Garbage Collector, který má za úkol rušit všechny porměnné, na které se již neodkazuje žádný ukazatel. Používání dynamické proměnné v programovacích jazycích vede k efektivnějšímu využívání operační paměti. Každá instance datového typu nebo objektu vytvořená jako dynamická proměnná má určité specifické vlastnosti: • Dynamická proměnná vzniká za běhu programu, tedy ne při překladu do strojového kódu jako statická proměnná. • Za běhu programu může být taktéž odstraněna. Tím se nepotřebné proměnné můžeme zbavit a uvolnit místo v paměti pro vytvoření další proměnné. • Jelikož vzniká a zaniká za běhu programu nemůže být uvedena v deklarační části programu a proto nemá žádný identifikátor(jméno). • Dynamickou proměnnou může vytvořit pouze statická proměnná, která je datového typu UKAZATEL (pointer). • Proměnná datového typu ukazatel neobsahuje žádnou konkrétní hodnotu, ale pouze adresu na které je uložena dynamická proměnná. Umožňuje tedy přístup k hodnotě dynamické proměnné.

42

•

•

Nevýhodou dynamické proměnné je, že pokud není dostatek paměti pro její vytvoření, tak se ukončí běh programu. Vyvolá se tzv. výjimka za běhu programu. Proto při vytváření dynamických proměnných je důležité testovat dostupnou paměť. Po ukončení práce s dynamickou proměnnou bývá dobré tuto proměnnou zrušit. U dnešních velkých operačních pamětí používaných u osobních počítačů není tento požadavek, tak naléhavý jako dříve. Ovšem pracujeme-li s programovacím jazykem, který je objektově orientovaný (např. C++) a pomocí něj zavedeme objekt, který má velké paměťové nároky, můžeme rychle vyčerpat i velkou paměť. Proto postup kde se využívá uvolňování paměti je vždy doporučován.

Každá dynamická proměnná určená pro dynamickou datovou strukturu musí být vždy definovaná jako záznam (v Pascalu datový typ RECORD, v C datový typ STRUCT). Je to proto, že každá takováto proměnná musí být tvořena minimálně dvěma položkami. Počet položek se liší podle toho, do jakého typu struktury bude tato dynamická proměnná zařazována: 1. Dynamická proměnná zařazovaná do lineárních jednosměrně zřetězených struktur - jako je zásobník, fronta, jednosměrný seznam bude složena ze dvou položek: • PRVNÍ POLOŽKA tvoří hodnotovou část. • DRUHÁ POLOŽKA tvoří adresní část, je to ukazatel na adresu dalšího prvku v pořadí. Prostřednictvím této druhé položky vzniká propojení mezi jednotlivými dynamickými proměnnými v jednom směru a tím vzniká požadované zřetězení dynamické datové struktury. Podle toho, že vzniká propojení pouze v jednom směru mluvíme o těchto strukturách jako o jednosměrně zřetězených.

2. Dynamická proměnná zařazovaná do lineárních obousměrně zřetězených struktur - jako jsou například obousměrné seznamy bude složena ze tří položek: • PRVNÍ POLOŽKA tvoří hodnotovou část. • DRUHÁ POLOŽKA tvoří adresní část, je to ukazatel na adresu dalšího prvku v pořadí. Prostřednictvím této druhé položky vzniká propojení mezi jednotlivými dynamickými proměnnými v jednom

43

Dynamická proměnná

•

směru a tím vzniká požadované zřetězení dynamické datové struktury. TŘETÍ POLOŽKA je opět adresní část, ukazatel na adresu předešlého prvku. Prostřednictví této třetí položky vzniká propojení v opačném směru. Tím, že jsou prvky propojené (zřetězené) v obou směrech nazýváme tyto struktury obousměrně zřetězené.

3. Dynamická proměnná zařazovaná do nelineárních zřetězených struktur - jako jsou binární stromy bude složena opět ze tří položek: • PRVNÍ POLOŽKA tvoří hodnotovou část. • DRUHÁ POLOŽKA tvoří adresní část odkazující na následníka napravo. • TŘETÍ POLOŽKA tvoří adresní část odkazující na následníka nalevo.

Vznik dynamické proměnné předchází alokace (vyhrazení) paměti pro tuto proměnnou a uložení odkazu na tuto proměnnou do proměnné typu UKAZATEL. Alokovat paměť lze v Pascalu dvěma způsoby: 1. Standardní procedura NEW - v C a C++ má stejný název. Tato procedura zabírá souvislou oblast v paměti a ukládá adresu této paměti do proměnné typu UKAZATEL. Parametr, který se této proceduře předává může být jen proměnná typu UKAZATEL. Velikost alokované paměti závisí na datovém typu uvedeném při deklaraci proměnné typu ukazatel. 2. Standardní procedura GetMem - zabírá souvislou oblast v paměti a ukládá adresu této oblasti do proměnné typu UKAZATEL. Tato proměnná má dva parametry - proměnnou typu UKAZATEL a

44

hodnotu udávající velikost potřebné paměti. Velikost alokované paměti tedy závisí na parametru udávajícím požadovanou velikost. Při práci s dynamickou proměnou je nutno používat speciálního operátoru, který bude označovat, že se jedná o ukazatel. V Pascalu je to operátor^ (v C a C++ se nazývá dereferenční operátor *), který se vždy píše za název proměnné typu UKAZATEL (v C a C++ se píše před název proměnné typu UKAZATEL). Tím se zpřístupní místo v paměti, jehož adresa je uložená právě v proměnné typu UKAZATEL. Obecně platí, že s dynamickou proměnnou lze provádět ty operace, které jsou dovoleny pro datový typ, který je uveden při deklaraci proměnné typu UKAZATEL, který tuto dynamickou proměnnou vytváří. Příklady operace s dynamickou proměnnou a proměnnou datového typu UKAZATEL: 1. deklarování dvou ukazatelů

var P, Q : ^ integer;

2. vytvoření dynamické proměnné - po vytvoření má dynamická proměnná prázdnou hodnotu, která se značí NIL new( P )

3. přiřazení hodnoty do dynamické proměnné P^ := 10;

4. přiřazení jedné proměnné typu ukazatel do druhé téhož datového typu - obě budou ukazovat na tu samou dyn. proměnnou Q := P;

5. přiřazení hodnoty jedné dynamické proměnné do druhé dynamické proměnné new (P);

45

new (Q); Q^ := P^;

Po těchto příkazech vzniknou dvě různé dynamické proměnné se stejnými hodnotami.

Po ukončení práce s dynamickou proměnnou je nutné tuto proměnnou odstranit z paměti a uvolnit tak paměť pro další použití. Pro uvolnění paměti existují v Pascalu opět dvě možnosti: 1. Standardní procedura DISPOSE - v C a C++ nahrazuje tuto proceduru standardní procedura DELETE. Parametrem procedury DISPOSE je proměnná typu UKAZATEL, která ukazuje na rušenou dynamickou proměnnou. Obvykle se používá, když byla dynamická proměnná vytvořena procedurou NEW. Příklad: dispose (ukaz); 2. Standardní procedura FreeMem - která má opět dva parametry proměnnou typu UKAZATEL a hodnotu udávající velikost rušené paměti. Velikost rušené paměti tedy závisí na parametru udávajícím požadovanou velikost. FreeMem se obvykle používá, když byla proměnná vytvořena procedurou GetMem. Příklad: FreeMem (p : pointer; velikost : word); Po zrušení dynamické proměnné je dobré také zrušit adresu v paměti, na kterou ukazatel odkazuje. V takovém případě se ukazateli přiřazuje tvz. prázdná hodnota. V Pascalu se nazývá NIL. 4.2. Dynamické datové struktury Dynamické datové struktury slouží k ukládání dat v operační paměti pro jejich pozdější zpracování. Při jejich použití nemusíme dopředu znát množství ukládaných hodnot. Takže velikost pro ně alokované paměti není známa během překladu programového kódu. Velikost těchto datových struktur se mění podle potřeby za běhu programu. Dynamické datové struktury jsou tvořeny dynamickými proměnnými. Rozdělení dynamických datových struktur: 1. Lineární dynamická struktura - je tvořena lineárně uspořádanou množinou prvků. To znamená, že ke každému prvku s výjimkou posledního, existuje jeden následník a ke každému prvku s výjimkou

46

prvního existuje jeden předchůdce. Tyto lineární dynamické struktury mohou být dvojího druhu: a) jednosměrně zřetězené - každý prvek v této struktuře obsahuje kromě hodnotové části, také část odkazující na svého následníka - zásobník - fronta - jednosměrný seznam b) obousměrně zřetězené - každý prvek struktury obsahuje hodnotovou část, část odkazující na následníka a část odkazující na předchůdce - obousměrný seznam Podmínku lineární uspořádanosti splňuje také kruhový spojový seznam Ten je uspořádán tak, že následníkem posledního prvku je prvek první a naopak předchůdcem prvního prvku je prvek poslední. 2. Nelineární dynamická struktura - je tvořena množinou prvků, kdy každý prvek má jeden nebo více následníků. O této struktuře pak mluvíme jako o stromové struktuře. Prvek, který nemá žádného předchůdce (stojí na vrcholu stromu) nazýváme kořen. Prvky, které nemají žádné následníky (stojí ne nejnižší úrovni) nazýváme listy stromu. Patří sem především binární stromy, které se mohou vyskztovat v několika podobách: a) binární vyhledávací strom b) degenerovaný a vyvážený strom

4.3. Zásobník Zásobník lze charakterizovat jako spojový seznam u něhož jeden konec je vrchol a ten slouží k ukládání a odebírání prvků. Kdykoli tedy chceme odebrat prvek z tohoto zásobníku, bude to vždy ten, který byl vložen jako poslední. Podle této vlastnosti se zásobník také nazývá pamětí typu LIFO (Last In First Out). Zásobník si můžeme představit jako na sobě naskládané knihy, kde může být jako první odebrána vždy jen ta kniha, která byla na hromadu přidána jako poslední. Grafické znázornění zásobníku obsahujícího tři prvky:

47

Zásobník

Proměnná datového typu UKAZATEL (zde má název UKAZ) musí vždy odkazovat na adresu dynamické proměnné, která zrovna tvoří vrchol zásobníku. (poznámka autora: šipka vždy odkazuje na celý prvek (proměnnou), ne jen na jednu z položek prvku) Pracovat se pak dá pouze s tímto vrcholem. Tento ukazatel je deklarován v hlavním programu. Hodnota, která byla do zásobníku přidána jako první (tzn. že se nachází úplně vespod zásobníku) neodkazuje na žádný další prvek, proto musí mít v adresní části hodnotu NIL. V podprogramech se pak využívá druhý pomocný ukazatel, kterým budeme vytvářet nebo odebírat prvky (na dalších obrázcích má označení P). Při vlastní práci se zásobníkem je tedy vhodné využívat podprogramy. Příklady podprogramů pro práci se zásobníkem: 1. Deklarace vlastního zásobníku: Deklarace zásobníku musí být vždy v hlavním programu. • Zásobník je dynamická datová struktura, proto jednotlivé prvky musí být dynamické proměnné. • Abychom mohli tyto prvky zřetězit musí mít každá dynamická proměnná kromě hodnotové části, také část adresní. • Zde je deklarována dynamická proměnná s názvem Objekt, která má hodnotovou část s názvem HODNOTA a adresní část s názvem DALŠÍ. • Na tuto proměnnou odkazuje proměnná Spoj, která je datového typu UKAZATEL. Tímto je tedy zaveden nový datový typ s názvem Spoj. • Pokud budeme chtít pracovat s datovou strukturou ZÁSOBNÍK, musíme vytvořit proměnnou datového typu Spoj. Zde máme deklarovanou proměnnou s názvem UKAZ. type Spoj = ^Objekt; Objekt = record HODNOTA : integer; DALSI

: Spoj;

48

end; var UKAZ: Spoj;

2. Vytvoření prázdného zásobníku: • Zásobník se inicializuje tak, že se v podprogramu (nebo také v hlavním programu) do proměnné datového typu Spoj (o tomto typu víme, že to je vlastně ukazatel), přiřadí prázdná hodnota NIL. procedure Vytvorit (var UKAZ: Spoj); begin UKAZ := NIL; end;

3. Vložení nového prvku na vrchol zásobníku: • Při vkládání nového prvku do zásobníku je podprogramu předán odkaz na vrchol zásobníku (UKAZ) a hodnota, která se má uložit (X). Proměnná UKAZ se musí umět vrátit do hlavního programu (proto je před touto proměnnou klíčové slovo var), jinak by už nešlo se zásobníkem pracovat. • V podprogramu se musí využít další proměnná typu Spoj (o kterém už víme že je datového typu UKAZATEL), která bude sloužit jen pro vytvoření nové dynamické proměnné. • Nová dynamická proměnná se vytvoří pomocí procedury new, které předáme ukazatel (zde je to ukazatel P). • Této proměnné je do hodnotové části předána hodnota X, a do adresní části odkaz na dosavadní vrchol zásobníku UKAZ. • Celý tento ukazatel P je pak přiřazen ukazateli UKAZ, čímž vznikne nový vrchol. procedure Vlozit (var UKAZ: Spoj; X: integer); var P: Spoj; begin new (P); P^.HODNOTA := X; P^.DALSI := UKAZ;

49

UKAZ := P; end;

4. Odebrání prvku z vrcholu zásobníku: • Podprogramu se musí předat odkaz na vrchol zásobníku, tento odkaz se musí vrátit zpět do hlavního programu. Hlavnímu programu může být také předána hodnotová část odebíraného prvku (např. z důvodu jeho výpisu). V proceduře Odebrat je do hlavního programu vrácena proměnná X. • Opět je nutno zavést pomocnou proměnou datového typu Spoj, tentokrát kvůli odstranění prvku. • Před odebráním prvku ze zásobníku je nutné vždy testovat, zda je zásobník prázdný. Odebírání prvků z prázdného zásobníku vyvolá chybu za běhu programu, která vede k ukončení celého programu. Zda je zásobník prázdný poznáme podle ukazatele odkazujícího na prázdnou hodnotu NIL. Toto testování lze přenechat vhodně napsanému podprogramu (v pozdějším příkladu je použita funkce s názvem JePrazdny). • Ukazatel odkazující na stávající vrchol musí být předán do pomocného ukazatele. • Nový vrchol musí být následníkem stávajícího. • Starý vrchol, na který odkazuje ukazatel P se odstraní pomocí procedury Dispose, čímž se zároveň uvolní paměť od tohoto prvku. • Do ukazatele P se přiřadí prázdná hodnota. procedure Odebrat (var UKAZ: Spoj; var X: integer); var P: Spoj; begin if UKAZ = NIL then writeln (' Zásobník je prázdný, nelze odebírat !') else begin P := UKAZ; X := UKAZ^.HODNOTA; UKAZ := UKAZ^.DALSI;

50

dispose(P); P := NIL; end; end;

5. Testování prázdnosti zásobníku: • Pokud by se zásobník netestoval na prázdnost mohla by být, při odebírání prvku z prázdného zásobníku, vyvolána chyba za běhu programu, která by vedla k ukončení programu. • Jestli je zásobník prázdný zjistíme podle ukazatele na vrchol (UKAZ), který odkazuje na prázdnou hodnotu NIL. function JePrazdny (UKAZ: Spoj) boolean; begin JePrazdny := (UKAZ = NIL); end;

4.4. Fronta Datová struktura s označením fronta pracuje s jednotlivými datovými prvky způsobem, který je podobný čekání lidí ve frontě. Každý nový příchozí do fronty se zařadí na konec, takže ten kdo přijde nejdříve bude obsloužen jako první a jako první taky z fronty odejde. Stejným způsobem pracuje datová struktura fronta, kde na jednom konci jsou prvky vkládány a z druhého konce jsou odebírány. Podle této vlastnosti frontu nazýváme pamětí typu FIFO (First In First Out). Grafické znázornění fronty obsahujícího tři prvky:

51

Fronta

Při realizaci fronty je vhodné využít dvou proměnných datového typu UKAZATEL. Kde první odkazuje na prvek, který byl do fronty vložen jako první (zde má název ČELO) a druhý odkazuje na prvek, který byl vložen jako poslední (zde KONEC). Tento naposled vložený prvek musí mít v adresní části hodnotu NIL. Tyto dva ukazatele jsou používány v hlavním programu. Prvky fronty jsou opět dynamické proměnné. Při vlastní práci s frontou (přidávání a odebírání prvků) je nutné ještě vytvořit jeden ukazatel, pomocí kterého se budou prvky do fronty vkládat a odebírat. 1. Deklarace vlastní fronty: • Deklarace fronty musí být vždy v hlavním programu. • Fronta je dynamická datová struktura, proto jednotlivé prvky musí být dynamické proměnné. • Abychom mohli tyto prvky zřetězit musí mít každá dynamická proměnná kromě hodnotové části, také část adresní. • Zde je deklarována dynamická proměnná s názvem Objekt, která má hodnotovou část s názvem HODNOTA a adresní část s názvem DALŠÍ. • Na tuto proměnnou odkazuje proměnná Spoj, která je datového typu UKAZATEL. Tímto je tedy zaveden nový datový typ s názvem Spoj. • Pokud budeme chtít pracovat s datovou strukturou FRONTA, musíme zavést dvě proměnné a deklarovat je jako datový typ Spoj. Zde máme deklarované proměnné s názvem ČELO, což je ukazatel na první prvek fronty a KONEC, což je ukazatel na poslední prvek fronty. type Spoj = ^Objekt; Objekt = record HODNOTA : integer; DALSI : Spoj; end; var CELO, KONEC: Spoj;

2. Vytvoření prázdné fronty: • Fronta se inicializuje tak, že se v podprogramu (nebo také v hlavním programu) do proměnné datového typu Spoj (o tomto typu

52

víme, že je to vlastně ukazatel) odkazující na první prvek, přiřadí prázdná hodnota NIL. procedure Vytvorit (var CELO: Spoj); begin CELO := NIL; end;

3. Vložení nového prvku na konec fronty: • Při vkládání nového prvku do fronty je podprogramu předán odkaz na první prvek fronty (ČELO) a poslední prvek fronty (KONEC), a dále pak hodnota, která se má uložit (X). Proměnné ČELO a KONEC se musí umět vrátit do hlavního programu (proto je před touto proměnnou klíčové slovo var), jinak by už nešlo s frontou pracovat. • V podprogramu se musí využít další proměnná typu Spoj (o kterém už víme že je datového typu UKAZATEL), která bude sloužit jen pro vytvoření nové dynamické proměnné (zde je to P). • Nová dynamická proměnná se vytvoří pomocí procedury new, které se předá ukazatel. • Této proměnné je do hodnotové části předána hodnota X. • Do adresní části se přiřadí odkaz na prázdnou hodnotu NIL. • Při přiřazování tohoto pomocného ukazatele P, je nutno testovat zda je fronta prázdná. Toto se pozná podle toho, že ukazatel ČELO odkazuje na prázdnou hodnotu NIL. Pomocný ukazatel se pak přiřadí jednak do ukazatele ČELO a jednak do ukazatele KONEC. Takže ukazatele ČELO i KONEC odkazují na ten sám první (a zároveň poslední) prvek. • Nebyla-li při testování fronta prázdná (byl tam alespoň jeden prvek), přiřadí se pomocný ukazatel za dosavadní poslední prvek tak, že se přiřadí do adresní části tohoto posledního prvku. Pomocný ukazatel pak musí být ještě přiřazen do ukazatele KONEC, čímž tento ukazatel bude odkazovat na nový konečný prvek. procedure Vlozit (var CELO, KONEC: Spoj; X: integer); var

53

P: Spoj; begin new (P); P^.HODNOTA := X; P^.DALSI := NIL; if CELO = NIL then CELO := P else KONEC^.DALSI := P; KONEC := P; end;

4. Odebrání prvku z čela fronty: • Podprogramu se musí předat odkaz na první prvek fronty (ČELO), odkaz na poslední prvek se předávat nemusí. Odkaz na první prvek se musí vrátit zpět do hlavního programu. Hlavnímu programu může být také předána hodnotová část odebíraného prvku (např. z důvodu jeho výpisu). V proceduře Odebrat je do hlavního programu vrácena proměnná X. • Opět je nutno zavést pomocnou proměnou, tentokrát kvůli odstranění prvku. • Před odebíráním je nutné vždy testovat zda už fronta není prázdná. Odebírání z prázdné fronty vyvolá chybu za běhu programu a program se ukončí. Toto testování je výhodné přenechat podprogramu (v příkladu se o toto stará funkce JePrazdna) • Pokud ve frontě zbývá nějaký prvek odebere se (příkazy by měly být uzavřeny do bloku) • Ukazatel odkazující na stávající první prvek musí být předán do pomocného ukazatele. • Hodnotová část prvního prvku je předána do proměnné, která tuto hodnotu vrací do hlavního programu. • Nový první prvek musí být následníkem stávajícího. • Starý první prvek, na který odkazuje ukazatel P se odstraní pomocí procedury Dispose, čímž se zároveň uvolní paměť od tohoto prvku. • Pomocný ukazatel P se nastaví na hodnotu NIL.

54

procedure Odebrat (var CELO: Spoj; var X: integer); var P: Spoj; begin if CELO = NIL then writeln (' Z fronty nelze odebirat, fronta je prazdna !') else begin P := CELO; X := CELO^.HODNOTA; CELO := CELO^.DALSI; dispose(P); P := NIL; end; end;

5. Testování prázdnosti fronty: • Pokud by se fronta netestovala na prázdnost mohla by být, při odebírání prvku z prázdné fronty, vyvolána chyba za běhu programu, která by vedla k ukončení programu. • Jestli je fronta prázdná zjistíme podle ukazatele na první prvek (ČELO), který odkazuje na prázdnou hodnotu NIL. fuction JePrazdny (CELO: Spoj) boolean; begin JePrazdny := (CELO = NIL); end;

6. Výpis seznamu: • Podprogramu je předán odkaz na první prvek seznamu. Tento odkaz se nesmí vracet zpět do hlavního programu.. procedure Vypis(CELO: Spoj); var begin

55

while CELO<> NIL do begin write(CELO^.HODNOTA : 4); CELO := CELO^.DALSI; end; end;

7. Uvolnění paměti: • Po ukončení práce s dynamickou datovou strukturou je nutné vyčistit paměťod dynamických proměnných tvořící tuto strukturu paměť. • Tento algoritmus je podobný výpisu prvku. Někdy mohou být oba tyto algoritmy v jedné proceduře. procedure UvolniPamet(CELO: Spoj); var P: Spoj; begin while CELO<> NIL do begin P := CELO; CELO := CELO^.DALSI; dispose(P); end; end;

4.5. Jednosměrný spojový seznam Jednosměrný spojový seznam je podobný datové struktuře fronta, na rozdíl od fronty lze do tohoto seznamu vkládat a odebírat prvky na libovolné místo. Tedy vkládat lze nejen na konec struktury , ale také do prostřed a na začátek. A taktéž odebírat lze libovolný prvek uprostřed struktury, na konci, a jako u fronty na začátku. Datové struktury zásobník a fronta jsou považovány za speciální případy jednosměrných spojových seznamů. Grafické znázornění jednosměrného spojového seznamu obsahujícího tři prvky:

56

Při porovnání fronty a této struktury nelze najít žádný rozdíl. Opět zde jsou zavedeny dvě proměnné datového typu UKAZATEL (obvykle bývají deklarovány v hlavním programu), odkazující na první a poslední prvek ve struktuře. Poslední prvek ve struktuře musí ve své adresní části odkazovat na prázdnou hodnotu NIL. Rozdíl oproti frontě, že tento poslední prvek nemusí být nutně ten, který byl vložen jako poslední. V podprogramech se pak mohou využívat další pomocné ukazatele pro přidávání a odebírání prvků ze struktury. 1. Deklarace jednosměrného spojového seznamu: • Deklarace jednosměrného spojového seznamu je naprosto stejná jako u fronty. Musí být vždy v hlavním programu. • Abychom mohli tyto prvky zřetězit musí mít každá dynamická proměnná kromě hodnotové části, také část adresní. • Zde je deklarována dynamická proměnná s názvem Objekt, která má hodnotovou část s názvem HODNOTA a adresní část s názvem DALŠÍ. • Na tuto proměnnou odkazuje proměnná Spoj, která je datového typu UKAZATEL. Tímto je tedy zaveden nový datový typ s názvem Spoj. • Pokud budeme chtít pracovat s touto datovou strukturou, musíme zavést dvě proměnné a deklarovat je jako datový typ Spoj. Zde máme deklarované proměnné s názvem ČELO, což je ukazatel na první prvek a KONEC, což je ukazatel na poslední prvek . type Spoj = ^Objekt; Objekt = record HODNOTA : integer; DALSI : Spoj; end;

var CELO, KONEC: Spoj;

2. Vytvoření prázdného seznamu: • Jednosměrný seznam se inicializuje tak, že se v podprogramu (nebo také v hlavním programu) do proměnné datového typu Spoj (o tomto typu víme, že je to vlastně ukazatel) odkazující na první prvek, přiřadí prázdná hodnota NIL. Takže opět stejný proces jako u fronty. procedure Vytvorit (var CELO: Spoj); begin CELO := NIL; end;

57

Jednosměrný spojový seznam

3. Vložení nového prvku do jednosměrného seznamu (naplnění seznamu prvky): • Může se dít v podprogramu, kterému je předán odkaz na první prvek (ČELO) a poslední prvek (KONEC), a dále pak hodnota, která se má uložit (X). Proměnné ČELO a KONEC se musí umět vrátit do hlavního programu (proto je před touto proměnnou klíčové slovo var). • V podprogramu se využívá další proměnná typu Spoj (o kterém už víme že je datového typu UKAZATEL), která bude sloužit jen pro vytvoření nové dynamické proměnné (zde je to P). • Nová dynamická proměnná se vytvoří pomocí procedury new, které se předá ukazatel. • Této proměnné je do hodnotové části předána hodnota X. • Do adresní části se přiřadí odkaz na prázdnou hodnotu NIL. • Při přiřazování tohoto pomocného ukazatele P, je nutno testovat zda je seznam prázdný. Toto se pozná podle toho, že ukazatel ČELO odkazuje na prázdnou hodnotu NIL. Pomocný ukazatel se pak přiřadí jednak do ukazatele ČELO a jednak do ukazatele KONEC. Takže ukazatele ČELO i KONEC odkazují na ten sám první (a zároveň poslední) prvek. • Nebyl-li při testování seznam prázdný (byl-li tam alespoň jeden prvek), přiřadí se pomocný ukazatel za dosavadní poslední prvek tak, že se přiřadí do adresní části tohoto posledního prvku. Pomocný ukazatel pak musí být ještě přiřazen do ukazatele KONEC, čímž tento ukazatel bude odkazovat na nový konečný prvek. procedure Vlozit (var CELO, KONEC: Spoj; X: integer); var P: Spoj; begin new (P); P^.HODNOTA := X; P^.DALSI := NIL; if CELO = NIL then CELO := P else KONEC^.DALSI := P; KONEC := P; end;

58

V dalším textu se předpokládá, že jednosměrný seznam obsahuje několik prvků. 4. Vložení prvku na konec jednosměrného seznamu:

procedure VlozitNaKonec(var KONEC: Spoj; X: integer); var P: Spoj; begin new (P); P^.HODNOTA := X; P^.DALSI := NIL; KONEC^.DALSI := P; KONEC := P; end;

5. Vložení prvku na začátek jednosměrného seznamu:

procedure VlozitNaZacatek(var CELO: Spoj; X: integer); var P: Spoj; begin new (P); P^.HODNOTA := X; P^.DALSI := CELO; CELO := P; end;

59

6. Vkládání prvku na libovolné místo uprostřed seznamu: • Při vkládání prvku na libovolné místo uprostřed seznamu, lze využít dva způsoby. Oba vyžadují, aby byla zavedena pomocné proměnná datového typu UKAZATEL. Tato proměnná bývá obvykle deklarována v hlavním programu. • Důležité je na začátku prohledávání přiřadit ukazatel na první prvek (ČELO) do pomocného ukazatele (POM). Protože s ukazatelem na první prvek se nesmí hýbat pokud nejde o přidávání nebo odebíráni prvního prvku. a) přidávání nového prvku ZA prvek, na který ukazuje ukazatel POM: •

Logika vyhledávání prvku, za který nový prvek vložit, je přenechána hlavnímu programu. Do podprogramu přichází ukazatel POM už odkazující na takovýto prvek.

procedure VlozitZaPom(var POM: Spoj; X: integer); var P:Spoj; begin new(P); P^.HODNOTA := X; P^.DALSI := POM^.DALSI; POM^.DALSI := P; end;

60

b) přidávání prvku PŘED prvek, na který ukazuje ukazatel POM: •

Logika vyhledávání vhodného prvku před který postavit nový prvek je opět ponechána na hlavním programu. Podprogramu je ukazatel POM předán už nastaven na tento prvek. Kromě toho také ukazatel na první prvek (tedy ČELO)

•

V podprogramu musí být nadeklarován další pomocný ukazatel (zde je to PŘEDPOM), který odkazuje právě na prvek, stojící před ukazatelem POM.

procedure VlozitPredPom(var CELO, POM: Spoj; X: integer); var P, PREDPOM:Spoj; begin PREDPOM := CELO; while PREDPOM^.DALSI <> POM do PREDPOM := PREDPOM^.DALSI; new(P); P^.HODNOTA := X; P^.DALSI := POM; PREDPOM^.DALSI := P; end;

61

7. Odstranění prvku na začátku seznamu: •

Při odebírání prvků z dynamické datové struktury by mělo být vždy testováno zda se neodebírá ze struktury, ve které už žádný prvek není.

•

Podprogramu stačí předat odkaz na první prvek (tedy ČELO).

•

Ukazatel na první prvek se musí vracet do hlavního programu z důvodu další funkčnosti seznamu. Kromě toho lze vracet do hlavního programu také hodnotu odebíraného prvku.

procedure OdebratZeZacatku(var CELO: Spoj; var X: integer); var P:Spoj; begin if CELO = NIL then writeln('Ze zasobniku nelze odebirat, je prazdny') else begin P := CELO; X := CELO^.HODNOTA; CELO := CELO^.DALSI; dispose(P); p := NIL; end; end;

62

8. Odstranění prvku z konce seznamu •

Opět by mělo být testováno zda se neodebírá ze struktury, ve které už žádný prvek není.

•

Podprogramu se tentokrát musí předat odkaz na první prvek (tedy ČELO) a poslední prvek (KONEC). Oba se vrací zpět.

•

Kromě toho se může vracet také hodnota odebíraného prvku (výpis této hodnoty).

•

V podprogramu je deklarována pomocná proměnná datového typu UKAZATEL, která prochází celý seznam až narazí na předposlední prvek.

•

Poslední se odstraní a z tohoto předposledního vznikne nový konec.

procedure OdebratZKonce(var CELO, KONEC: Spoj; var X: integer); var P, PREDKON:Spoj; begin if CELO = NIL then writeln('Ze zasobniku nelze odebirat, je prazdny') else begin PREDKON := CELO; while PREDKON^.DALSI <> KONEC do PREDKON := PREDKON^.DALSI; P := KONEC; X := KONEC^.HODNOTA; KONEC := PREDKON; KONEC^.DALSI := NIL; dispose(P); P := NIL; PREDKON := NIL; end; end;

63

9. Odstranění prvku z prostřed seznamu: • Nejdříve je nutné v hlavním programu vyhledat prvek, který se má odstranit a odkázat na něj pomocí nějakého ukazatele (zde POM). • Podprogramu předat spolu s tímto ukazatelem, ukazatele odkazujícího na první prvek (ČELO). • V podprogramu deklarovat třetí ukazatel použitý u tohoto procesu a to ukazatel odkazující na předchůdce odebíraného prvku (zde PRED). • Opět můžeme (ale nemusíme) vracet hodnotu odebíraného prvku do hlavního programu (pomocí klíčového slova var). procedure OdebratPom(var CELO: Spoj; var X: integer); var P,PRED:Spoj; begin PRED := CELO; while PRED^.DALSI <> POM do PRED := PRED^.DALSI; PRED^.DALSI := POM^.DALSI; X := POM^.HODNOTA; dispose(POM); P := NIL; end;

64

10. Výpis seznamu: •

Podprogramu je předán odkaz na první prvek seznamu. Tento odkaz se nesmí vracet zpět do hlavního programu. Je to z toho důvodu, že se tento ukazatel posouvá až na poslední prvek a vypisuje hodnoty jednotlivých prvků. V hlavním programu je potřeba, aby stále odkazoval na první prvek.

procedure Vypis(CELO: Spoj); var begin while CELO<> NIL do begin write(CELO^.HODNOTA : 4); CELO := CELO^.DALSI; end; end;

11. Uvolnění paměti: •

Po ukončení práce s dynamickou datovou strukturou je nutné vyčistit od dynamických proměnných tvořící tuto strukturu paměť.

•

Tento algoritmus je podobný výpisu prvku. Někdy mohou být oba tyto algoritmy v jedné proceduře.

procedure UvolniPamet(CELO: Spoj); var P: Spoj; begin while CELO<> NIL do begin P := CELO; CELO := CELO^.DALSI; dispose(P); end; end;

4.6. Dvousměrný spojový seznam Rozdíl proti jednosměrně zřetězenému spojovému seznamu, u kterého každý prvek zná adresu svého následníka je v tom, že tento druh seznamu tvoří takové prvky které znají adresu nejen svého následníka, ale také předchůdce. Takováto dynamická struktura zvyšuje nároky na dostupnou paměť, protože každý prvek tvoří tři položky. První položka je hodnotová část, druhá položka je adresní část ukazující na následující prvek a třetí část je opět adresní část ukazující na adresu předchůdce. Velkou výhodu takto definovaných prvků struktury poznáme v případě vkládání a odebírání prvků na libovolné místo v seznamu. Například u jednosměrného seznamu bylo při odebírání posledního prvku potřeba

65

jednoznačně identifikovat předposlední prvek, který se po odebrání posledního stal novým posledním prvkem. Tento předposlední prvek se dal nalézt jen za pomoci dalšího pomocného ukazatele, který procházel strukturu tak dlouho až našel prvek, který měl ve své adresní části adresu posledního prvku. Tento zdlouhavý postup u obousměrně zřetězeného seznamu odpadá, protože zde obsahuje poslední prvek odkaz na předposlední prvek. Grafické znázornění jednosměrného spojového seznamu obsahujícího tři prvky:

U obousměrného spojového seznamu jsou deklarovány dva ukazatele. První odkazuje na počáteční prvek ve struktuře, druhý pak na poslední prvek ve struktuře. První prvek v seznamu má v adresní části odkazující na předchůdce prázdnou hodnotu NIL, poslední prvek v seznamu má přiřazenu hodnotu NIL zase v adresní části odkazující na následníka. V hlavím programu musí být deklarován pomocný ukazatel v případě vkládání prvků na určité místo, nebo při odebírání prvků z určitého místa popřípadě při odebírání podle určité hodnoty. 1. Deklarace obousměrného spojového seznamu: •

Obousměrný spojový seznam.

•

•

•

type

Abychom mohli prvky zřetězit musí mít každá dynamická proměnná kromě hodnotové části, také část adresní odkazující na následníka a předchůdce. Dynamická proměnná má hodnotovou část s názvem HODNOTA, adresní část odkazující na následníka s názvem DALŠÍ a adresní část odkazující na předchůdce s názvem PŘED. Na tuto proměnnou odkazuje proměnná Spoj, která je datového typu UKAZATEL. Tímto je tedy zaveden nový datový typ s názvem Spoj. Pokud budeme chtít pracovat s touto datovou strukturou, musíme zavést dvě proměnné a deklarovat je jako datový typ Spoj. Zde máme deklarované proměnné s názvem PRVNÍ, což je ukazatel na první prvek a POSLEDNÍ, což je ukazatel na poslední prvek . Spoj = ^Objekt; Objekt = record HODNOTA : integer; DALSI, PRED : Spoj;

66

end; var PRVNI, POSLEDNI: Spoj;

2. Vložení prvního prvku do seznamu: • •

• • • •

Tuto proceduru je možné využít zároveň pro inicializaci seznamu Podprogramu je předán odkaz na první prvek (PRVNÍ) a poslední prvek (POSLEDNÍ), a dále pak hodnota, která se má uložit (X). Proměnné PRVNÍ a POSLEDNÍ se musí umět vrátit do hlavního programu (proto je před touto proměnnou klíčové slovo var). V podprogramu se využívá další proměnná typu Spoj, která bude sloužit jen pro vytvoření nové dynamické proměnné (zde je to P). Nová dynamická proměnná se vytvoří pomocí procedury new, které se předá ukazatel. Této proměnné je do hodnotové části předána hodnota X. Do adresní části odkazující na následníka a předchůdce se přiřadí odkaz na prázdnou hodnotu NIL.

• Procedure VlozitPrvni(var PRVNI, POSLEDNI: Spoj; X: integer); var P: Spoj; begin new(P); P^.HODNOTA := X; P^.DALSI := NIL; P^.PRED := NIL; PRVNI := P; POSLEDNI := P; end;

3. Vložení nového prvku na začátek seznamu: • Zde je nutné nově vytvořený prvek připojit k prvku prvnímu, tak aby se z původně prvního prvku stal prvek druhý. • Toto se provede tak, že do adresní části odkazující na následníka nově vytvořeného prvku se vloží adresa prvního prvku. • Nakonec se musí ukazatel PRVNÍ přesunout na nově vytvořený prvek.

67

Procedure VlozitNaZacatek(var PRVNI: Spoj; X: integer); var P: Spoj; begin new(P); P^.HODNOTA := X; P^.DALSI := PRVNI; P^.PRED := NIL; PRVNI^.PRED := P; PRVNI := P; end;

4. Vložení nového prvku na konec seznamu: • Nově vytvořený prvek se musí připojit k poslednímu tak, že se připojí do adresní části odkazující na následníka. • Na tento nový poslední prvek se musí přesunout ukazatel POSLEDNÍ. procedure VlozitNaKonec(var POSLEDNI: Spoj; X: integer); var P: spoj; begin new(P); P^.HODNOTA := X; P^.DALSI := NIL; P^.PRED := POSLEDNI; POSLEDNI^.DALSI := P; POSLEDNI := P; end;

68

5. Vložení nového prvku PŘED prvek, na který odkazuje ukazatel POM: • V hlavním programu procházet seznam tak dlouho až se nalezne pozice nebo prvek s hodnotou před kterou je nutné vložit nový prvek. • Na prvek na této pozici nebo na prvek s touto hodnotou nastavit pomocný ukazatel (zde POM) a předat ho podprogramu. • Ukazatel POM se nemusí vracet do hlavního programu, protože slouží jen pro vyhledání vhodného prvku. Není důležitý pro identifikaci prvního a posledního prvku. procedure VlozitPredPom(POM: Spoj; X: integer); var P: Spoj; begin new(P); P^.HODNOTA := X; P^.DALSI := POM; P^.PRED := POM^.PRED; POM^.PRED^.DALSI := P; POM^.PRED := P; end;

6. Vložení nového prvku ZA prvek, na který odkazuje ukazatel POM: • •

V hlavním programu procházet seznam tak dlouho až se nalezne pozice nebo prvek s hodnotou za kterou je nutné vložit nový prvek. Na prvek na této pozici nebo na prvek s touto hodnotou nastavit pomocný ukazatel (zde POM) a předat ho podprogramu. Ukazatel POM se opět nevrací do hlavního programu.

• procedure VlozitZaPom(POM: Spoj; X: integer); var

69

P: Spoj; begin new(P); P^.HODNOTA := X; P^.PRED := POM; P^.DALSI := POM^.DALSI; POM^.DALSI^.PRED := P; POM^.DALSI := P; end;

7. Odstranění prvku na začátku seznamu: •

Kontrola prázdnosti seznamu je přenechána hlavnímu programu.

•

Ukazatel PRVNÍ je důležitý pro fungování celé struktury proto se musí vracet zpět do hlavního programu

•

Proměnná X se může vracet do hlavního programu.

•

Tato operace má dvě možnosti provedení. V tomto příkladu byla vybrána ta verze, že se nejdříve posune ukazatel PRVNÍ na další prvek v pořadí a pak se ukazatel na předchůdce nastaví na NIL. Druhá verze pak je, že se nejdříve nastaví předchůdce (samozřejmě opět na NIL) a pak se posune ukazatel PRVNÍ

•

ÚKOL: Vytvořte druhou verzi odstraňování prvku ze začátku.

•

Po zrušení prvku se ukazatel musí nastavit na NIL.

procedure OdebratZeZacatku(var PRVNI: Spoj; var X: integer); var P: Spoj; begin P := PRVNI;

70

X := PRVNI^.HODNOTA; PRVNI := PRVNI^.DALSI; PRVNI^.PRED := NIL; dispose(P); P := NIL; end;

8. Odstranění prvku z konce seznamu: •

Kontrola prázdnosti seznamu je přenechána hlavnímu programu.

•

Ukazatel POSLEDNÍ je důležitý pro fungování celé struktury proto se musí vracet zpět do hlavního programu

•

Proměnná X se může vracet do hlavního programu.

•

Tato operace má opět dvě možnosti provedení. V tomto příkladu byla vybrána verze, ve které se nejdříve nastaví následník (na NIL) a pak se posune ukazatel POSLEDNÍ na předcházející prvek v pořadí. Druhá verze je zase opačná.

•

ÚKOL: Vytvořte druhou verzi odstraňování prvku z konce.

•

Po zrušení prvku se ukazatel musí nastavit na NIL.

procedure OdebratZKonce(var POSLEDNI: Spoj; var X: integer); var P: Spoj; begin P := POSLEDNI; X := POSLEDNI^.HODNOTA; POSLEDNI^.PRED^.DALSI := NIL; POSLEDNI := POSLEDNI^.PRED; dispose(P); P := NIL; end;

71

9. Odstranění prvku z prostřed seznamu: •

Z hlavního programu je předán odkaz na prvek, který má být odebrán v podobě ukazatele POM. Tento ukazatel se nevrací zpět

•

Po zrušení prvku se tento ukazatel musí nastavit na NIL.

procedure OdebratPom(POM: spoj); begin POM^.PRED^.DALSI := POM^.DALSI; POM^.DALSI^.PRED := POM^.PRED; dispose(POM); POM := NIL; end;

10. Výpis seznamu: •

Vypisovat obsah seznamu se dá dvěma způsoby. První způsob je předat podprogramu odkaz na první prvek a vypisovat seznam od tohoto prvku.

•

Druhý způsob je vypisovat seznam od konce.

•

Ukazatele předané této proceduře se nesmí vracet zpět do hlavního programu, proto nejsou deklarovány jako var.

72

•

V této proceduře se bude obsah seznamu vypisovat na jeden řádek a pro výpis každé hodnoty jsou k dispozici čtyři místa.

procedure VypisOdPredu(PRVNI: Spoj); begin while PRVNI <> NIL do begin write (PRVNI^.HODNOTA : 4); PRVNI := PRVNI^.DALSI; end; end;

11. Uvolnění paměti: •

Po ukončení práce s dynamickou datovou strukturou je nutné vyčistit od dynamických proměnných tvořící tuto strukturu paměť. Protože po ukončení programu zaniknou ukazatele na tyto proměnné a struktura se stává nedostupná.

•

Tento algoritmus je podobný výpisu prvku. Někdy mohou být oba tyto algoritmy v jedné proceduře.

•

Opět lze z důvodu obousměrného zřetězení uvolňovat paměť dvěma způsoby.

•

Zde se uvolňuje paměť od prvního prvku.

procedure UvolniPamet(CELO: Spoj); var P: Spoj; begin while CELO<> NIL do begin P := CELO; CELO := CELO^.DALSI; dispose(P); end; end;

Nejdůležitější probrané pojmy: -

Ukazatel a dynamická proměnná Dynamické datové struktury – spojový seznam, zásobník, fronta, jednosměrné a obousměrné seznamy

Úkoly a otázky k textu: 1. Vytvořte jednoduchou ukázku struktury typu strom.

73

5. Implementace fronty s prioritou Cíl: Seznámíte se: • Způsobem práce s dynamickými datovými strukturami v Javě • Simulace procesu jednoduchými metodami 5.1. Hlavní program pro simulaci letiště Vlastní simulace provozu na letišti má probíhat zcela automatizovaně a vybírat a zařazovat přitom letadla, která v danou chvíli přiletěla. Dále musí obsloužit frontu – tedy nechat přistát letadlo. To lze realizovat opět pomocí odečítání systémového času. Uděláme jednoduše smyčku, která vždy čeká na novou sekundu (celá část systémového času se změní) a pak provede všechny potřebné akce s frontou. To se provádí stále ve smyčce, dokud už není žádná aktivita nad letištěm možná. Řešený příklad 12:

Automatizované vykonání akcí

... Prilety.init(); //otevreni souboru se vstupnimi daty Fronta fronta = new Fronta(); //vytvoreni nove fronty VstupVystup.otevriLog(); veVzduchuVsechny = !Prilety.nactiDalsiLetadlo(); startCas = new Date().getTime(); do { minulyCas = new Date().getTime(); aktualniCas = (int)(minulyCas - startCas)/1000; // Odebere se vsem letadlum ve fronte cast paliva // a nechaji se popadat ty bez paliva fronta.odeberPalivo(-1, aktualniCas); // Necha pristat jedno letadlo z fronty fronta.pristaniLetadla(aktualniCas); // Zaradi do fronty letadla co prave priletla while (!veVzduchuVsechny && (Prilety.dalsiPrilet <= aktualniCas)) { fronta.zaradLetadlo(Prilety.dalsiPrilet, Prilety.dalsiSpolecnost, Prilety.dalsiPalivo); veVzduchuVsechny = !Prilety.nactiDalsiLetadlo(); }; // pocka se 1 sekunda while (((new Date().getTime())) - minulyCas <= 1000); } while(!(veVzduchuVsechny && fronta.pocetLetadel() == 0)); VstupVystup.zavriLog(); System.out.println("\nKONEC PROGRAMU"); ....

74

5.2. Fronta a operace Vlastní implementace fronty s prioritou vyžaduje kromě již probraných obecných principů také vkládání do fronty podle priority daného letadla. Prioritou je pro nás množství paliva = čím méně, tím vyšší je priorita. Řešený příklad 13: public class Fronta { //prvek fronty private class Letadlo { int prilet; String spolecnost; int palivo; Letadlo dalsi; Letadlo predchozi; // konstruktor letadla Letadlo (int pri, String spo, int pal, Letadlo pre, Letadlo dal) { prilet = pri; spolecnost = spo; palivo = pal; predchozi = pre; dalsi = dal; } } // konstruktor fronty Fronta () { zacatekFronty = null; konecFronty = null; pocet = 0; } private Letadlo zacatekFronty; private Letadlo konecFronty; private int pocet; public palivo) {

void

zaradLetadlo(int

Letadlo a = konecFronty; while (a != null &&

cas,

String

a.palivo

spolecnost, >

palivo)

int a

=

a.predchozi; if (konecFronty == null) { konecFronty = new Letadlo(cas, spolecnost, palivo, null, null); zacatekFronty = konecFronty; } else { if (a == null) { Letadlo n = zacatekFronty; zacatekFronty = new Letadlo(cas, spolecnost, palivo, null, n); n.predchozi = zacatekFronty; } else { Letadlo n = new Letadlo(cas, spolecnost, palivo, a, a.dalsi); if (n.dalsi != null) n.dalsi.predchozi = n; a.dalsi = n; } } pocet++; VstupVystup.zapisLog("\t"+cas+"\t priletlo: "+spolecnost+"\t(zbyva paliva: "+palivo+")");

75

} ...

5.3. Vstupy a výstupy Podobně jako u úlohy s řazením prvků pole, je nutné i zde realizovat vstup ze souborů obsahujících informace o letadlech. Dále se pak musí do výstupních souborů zaznamenat údaje o proběhlých činnostech na letišti (protokol o simulaci). Řešený příklad 14: public class Prilety { private static Scanner sc; private static boolean konecSouboru; public static int dalsiPrilet; public static String dalsiSpolecnost; public static int dalsiPalivo; public static void init() { try { sc = new Scanner(new File("vstup.txt")); konecSouboru = false; } catch (IOException e) { System.out.println("Chyba pri cteni vstupniho souboru!"); konecSouboru = true; } } ...

Nejdůležitější probrané pojmy: -

Dynamické proměnné v Javě

Úkoly a otázky k textu: 1. Prozkoumejte v Javě možnosti již připravených tříd typu Seznam, Fronta.

76

Literatura

1. TRETEROVÁ, E.: Algoritmy a datové struktury1. Ostrava: Učební text PřF OU Ostrava, 2003. 135s. 2. TRETEROVÁ, E.: Algoritmy a datové struktury2. Ostrava: Učební text PřF OU Ostrava, 2003. 127s. 3. KVOCH, M.: Programování v Turbo Pascalu 7.0. České Budějovice: Kopp, 1993. 237s. 4. ĎURÁKOVÁ, D., Dvorský J., Ochodková E.: Základy algoritmizace : Učební text FEI VŠB Ostrava, dostupné na: http//www.cs.vsb.cz/ochodkova/course/za/algor_dist.zip, 2004 5. BRŮHA, L.: Java – Hotová řešení. Brno: Computer Press. 2003. 325s. 6. ECKEL, B.: Myslíme v jazyce C++. Praha: Grada Publishing. 2000. 554s. 7. Algoritmy a programování. stránky dostupné na adrese: http://www.sweb.cz/david.padrta/pascal/alg_prog.html

77