117

Texty k Programování na VŠFS Petr Kučera

29. května 2006

Petr Kučera ()

Texty k Programování na VŠFS

29. května 2006

1 / 117

Obsah

Základní informace k předmětu Dynamicky alokovaná paměť Jednoduché dynamicky alokované datové struktury Stromy Grafy Vstup a výstup do souboru Rekurze Třídící algoritmy

Petr Kučera ()


29. května 2006

2 / 117

Základní informace k předmětu

e-mail: www: Zápočet: Zkouška: Literatura:

Petr Kučera ()

[email protected] http://kti.ms.mff.cuni.cz/˜kucerap/vsfs/programovani Dostatečná účast (chybět nejvýš čtyři vyučovací hodiny), nebo zápočtový program (postup jako minulý semestr.) Praktická, naprogramování zadané úlohy nebo úloh. Töpferová Dana, Töpfer Pavel Sbírka úloh z programování, Grada 1992 Töpfer Pavel Algoritmy a programovací techniky, Prometheus 1995


29. května 2006

3 / 117

Část I Dynamicky alokovaná paměť

Petr Kučera ()


29. května 2006

4 / 117

Typ ukazatel Proměnná typu ukazatel na typ obsahuje adresu dat daného typu. Deklarace: var p:^typ; type typ ukazatele = ^typ; Například: var p: ^string[32]; type pstr32 = ^string[32]; type ppstr32 = ^pstr32; Porovnání ukazatelů: =, <> Hodnota nil, má-li ukazatel hodnotu nil, znamená to, že nikam neodkazuje. Vždy testovat. Dereferenční operátor ^ (ukazatel^), použití například: writeln (pˆ);

Petr Kučera ()


29. května 2006

5 / 117

Dynamická alokace paměti – new

Někdy je užitečné říct si o paměť až za běhu programu, například, když na začátku nevíme, kolik jí budeme potřebovat, nebo chceme prostě šetřit pamětí. Alokace, procedura new (ukazatel). Například: new (p); Velikost paměti, která se alokuje, je daná typem ukazatele. Pokud se nepodaří paměť alokovat, program skončí s chybou.

Petr Kučera ()


29. května 2006

6 / 117

Uvolnění paměti – dispose

Dealokace, uvolnění paměti, procedura dispose (ukazatel). Například: dispose (p); Po dispose má ukazatel nedefinovanou hodnotu. Okamžitě přiřadit nil. Pokud p a q jsou ukazatelé ukazující na stejný objekt a zavoláme dispose (p);, hodnota q se nemění. Pokud je p=nil, dojde po dispose (p); k chybě a ukončení programu. Testovat! Pokud paměť neuvolníte a ztratíte na ni ukazatel, zůstane zabraná až do konce programu.

Petr Kučera ()


29. května 2006

7 / 117

Poznámky k paměti V pascalu je paměť běžícího programu organizována ve čtyřech segmentech: Code segment, v němž je uložen kód programu. Data segment, v němž jsou uložena staticky alokovaná data (tj. na začátku programu). Stack segment, v němž jsou uloženy aktivační záznamy při volání procedur a funkcí (tj. kam se vrátit po jejich ukončení, kam vrátit hodnotu apod.) a hlavně lokální proměnné v procedurách a funkcích. Heap segment, čili halda, zde se přiděluje dynamicky alokovaná paměť. Velikosti jednotlivých segmentů mohou být omezeny.

Petr Kučera ()


29. května 2006

8 / 117

Příklad program ukazatel (input, output); var p: ^string[32]; type pstring32 = ^string[32]; begin new (p); p^ := ’Ahoj světe!’; writeln (p^); dispose (p); p := nil; end.

Petr Kučera ()


29. května 2006

9 / 117

Lineární spojový seznam

Lineární spojový seznam je posloupnost záznamů stejného typu seřazených za sebe a spojených pomocí ukazatelů. Každý uzel seznamu obsahuje nějaká data a odkaz na následníka. Data

Data

Data

Data NIL

Petr Kučera ()


29. května 2006

10 / 117

Lineární seznam v Pascalu

Typ ukazatel na záznam R může být deklarován před deklarací typu R, ale v rámci jednoho bloku type. (Jinak by nešlo realizovat.) Deklarace typu spojového seznamu (data jsou například jedno číslo): type PLSeznam = ^TLSeznam; TLSeznam = record data : integer; dalsi : PLSeznam; end;

Petr Kučera ()


29. května 2006

11 / 117

Manipulace s lineárním spojovým seznamem (cvičení) I 1

function vytvor(N: integer): PLSeznam; Funkce vytvoří seznam s N prvky a vrátí odkaz na první prvek z tohoto seznamu (nil, pokud N <= 0). V položkách data budou uložena čísla 1 . . . N vzestupně od začátku do konce.

2

function najdi(s: PLSeznam; d: integer): PLSeznam; Funkce najde prvek v seznamu, který má položku data shodnou s d a vrátí odkaz na něj, nebo nil, pokud prvek v seznamu není.

3

function najdiPredchudce(s, p: PLSeznam): PLSeznam; Funkce najde předchůdce prvku p v seznamu s a vrátí na něj odkaz. Pokud se p v seznamu nevyskytuje, vrátí nil, je-li p první, vrátí p.

4

function konec(s: PLSeznam): PLSeznam; Vrátí odkaz na poslední prvek seznamu.

5

procedure vypis(s: PLSeznam); Vypíše na obrazovku čísla v pořadí, v jakém jsou v seznamu. Petr Kučera ()


29. května 2006

12 / 117

Manipulace s lineárním spojovým seznamem (cvičení) II 1

procedure vlozZaPrvek(p, q: PLSeznam); Vloží prvek q za prvek p.

2

procedure pridejNaZacatek(var s: PLSeznam; p: PLSeznam); Vloží prvek p na začátek seznamu s.

3

procedure pridejNaKonec(var s: PLSeznam; p: PLSeznam); Vloží prvek p na konec seznamu s.

4

function smaz(var s: PLSeznam; p: PLSeznam): PLSeznam; Smaže prvek p ze seznamu s. Buď si nejprve vymění data s následníkem, nebo nejprve najde předchůdce. Vrací odkaz na smazaný prvek, v položce dalsi bude mít nil. Pokud jej nebudete už používat, nezapomeňte po smaz na dispose.

5

procedure zrus(var s: PLSeznam); Projde seznam a pomocí dispose zruší jeho prvky, s bude po ukončení obsahovat nil. Petr Kučera ()


29. května 2006

13 / 117

Část II Jednoduché dynamicky alokované datové struktury

Petr Kučera ()


29. května 2006

14 / 117

Jednoduché datové struktury

Lineární spojový seznam. Obousměrný spojový seznam Seznam s hlavou

Petr Kučera ()


29. května 2006

15 / 117

Obousměrný spojový seznam

Obousměrný spojový seznam je lineární seznam, v němž má každý prvek odkaz nejen na následníka, ale i na předchůdce.

Data

Data

Data

NIL

Petr Kučera ()

Data NIL


29. května 2006

16 / 117

Obousměrný seznam v Pascalu type POSeznam = ^TOSeznam; TOSeznam = record data : integer; dalsi : POSeznam; pred : POSeznam; end;

Funkce a procedury přistupující k obousměrnému seznamu jsou implementované podobně jako pro lineární seznam. Něco je jednodušší, například vkládání, mazání, protože máme odkaz na předchůdce. Ale musíme hlídat i odkazy na předchůdce, proto je implementace poněkud pracnější. Petr Kučera ()


29. května 2006

17 / 117

Seznam s hlavou Seznam libovolného typu si reprezentujeme hlavou, což je struktura, která teprve odkazuje na skutečný seznam. Hlava může obsahovat i jiné položky, například odkaz na konec, počet prvků a podobně. Příklad čtyřprvkového lineárního seznamu s hlavou: 4

Data

Hlava

Data

Data

Data NIL

Petr Kučera ()


29. května 2006

18 / 117

Seznam s hlavou v Pascalu Příklad pro lineární seznam s hlavou s odkazy na začátek a počtem prvků: type THLSeznam = record pocet : integer; zac : PLSeznam; kon : PLSeznam; end; Manipulace je shodná s manipulací s lineárním seznamem, ale musíme upravovat počet a oba odkazy v hlavě. Hlava může být alokovaná staticky.

Petr Kučera ()


29. května 2006

19 / 117

Zásobník Datová struktura řídící se pravidlem: Poslední dovnitř, první ven. (Anglicky Last In First Out, zkráceně LIFO.) Dno

Vrchol

Přistupujeme k němu obvykle pomocí těchto procedur a funkcí: I I I

top – Vrací prvek na vrcholu zásobníku. push – Uloží prvek na vrchol zásobníku. pop – Smaže prvek z vrcholu zásobníku a vrátí jej.

Petr Kučera ()


29. května 2006

20 / 117

Zásobník pomocí pole Například zásobník celých čísel: const MAX_ZAS_VEL = 100; type TZasobnikA = record zasobnik : array [1..MAX_ZAS_VEL] of integer; vrchol : integer; end; procedure function procedure function

ZAInit ZATop ZAPush ZAPop

Petr Kučera ()

(var (var (var (var

z z z z

: : : :

TZasobnikA); {Inicializace} TZasobnikA) : integer; TZasobnikA; cis : integer); TZasobnikA) : integer;


29. května 2006

21 / 117

Zásobník pomocí pole (poznámky)

Položka vrchol vlastně vždy obsahuje počet prvků v zásobníku. Přístupové procedury a funkce pouze aktualizují hodnotu položky vrchol a přistupují jen k zasobnik [vrchol]. Pozor na přetečení nebo podtečení (nutno kontrolovat). ZATop zásobník nemění, předání odkazem použito, aby se nekopírovalo celé pole. Výhodou implementace pomocí pole je rychlost. Nevýhodou je, že musíme dopředu dobře odhadnout maximální velikost zásobníku a to, že zásobník zabírá stále stejně paměti, i když obsahuje jen jeden či dva prvky.

Petr Kučera ()


29. května 2006

22 / 117

Zásobník pomocí seznamu s hlavou Přidáváme i odebíráme ze začátku seznamu. Výhody a nevýhody opačně než u implementace pomocí pole. Opět zásobník celých čísel: type TZasobnikLS = record zac : PLSeznam; end; procedure function procedure function

Petr Kučera ()

ZLSInit ZLSTop ZLSPush ZLSPop

(var (var (var (var

z z z z

: : : :

TZasobnikLS); {Inicializace} TZasobnikLS) : integer; TZasobnikLS; cis : integer); TZasobnikLS) : integer;


29. května 2006

23 / 117

Fronta

Datová struktura řídící se pravidlem: První dovnitř, první ven. (Anglicky First In First Out, zkráceně FIFO.) Vstup

Výstup

Přistupujeme k němu obvykle pomocí těchto procedur a funkcí: I I I

first – Vrací první prvek fronty. put – Uloží prvek na konec fronty. get – Smaže prvek ze začátku fronty a vrátí jej.

Petr Kučera ()


29. května 2006

24 / 117

Fronta pomocí pole Například fronta celých čísel: const MAX_FR_VEL = 100; type TFrontaA = record fronta : array [1..MAX_FR_VEL] of integer; zac, kon : integer; pocet : integer; end; procedure function procedure function

FAInit FAFirst FAPut FAGet

Petr Kučera ()

(var (var (var (var

z z z z

: : : :

TFrontaA); {Inicializace} TFrontaA) : integer; TFrontaA; cis : integer); TFrontaA) : integer;


29. května 2006

25 / 117

Fronta pomocí pole (poznámky)

Při posunu indexů zac a kon počítáme modulo MAX VELIKOST FRONTY, jako by bylo pole do kolečka. Vyhneme se tím přesunu prvků, kdybychom došli na konec pole. Abychom poznali přetečení a podtečení, musíme si pamatovat počet prvků (a kontrolovat jej). Výhody a nevýhody jako u zásobníku pomocí pole.

Petr Kučera ()


29. května 2006

26 / 117

Fronta pomocí seznamu s hlavou Přidáváme na konec seznamu, odebíráme ze začátku. Výhody a nevýhody jako u zásobníku pomocí seznamu. Fronta celých čísel: type TFrontaLS = record zac, kon : PLSeznam; end; procedure function procedure function

Petr Kučera ()

FLSInit FLSTop FLSPush FLSPop

(var (var (var (var

z z z z

: : : :

TFrontaLS); {Inicializace} TFrontaLS) : integer; TFrontaLS; cis : integer); TFrontaLS) : integer;


29. května 2006

27 / 117

Varianty fronty

Oboustraná fronta Přidávání i odebírání z obou konců, implementace nejsnáze pomocí obousměrně vázaného seznamu. Prioritní fronta Prvky jsou odebírány podle priorit (pokud mají stejnou prioritu, bere se jako normální fronta). Pokud je různých priorit málo, třeba d, můžeme implementovat pomocí d různých seznamů nebo polí. Pokud je priorit hodně, bývá implementace pomocí pole nebo seznamu pomalá (kvůli třídění), lepší je halda (o té možná jindy).

Petr Kučera ()


29. května 2006

28 / 117

Cvičení

1

2

3

4

Implementujte zásobník celých čísel pomocí pole i dynamicky pomocí seznamu. Implementujte frontu celých čísel pomocí pole i dynamicky pomocí seznamu. Implementujte prioritní frontu celých čísel, která upřednostňuje sudá čísla před lichými. Implementujte oboustranou frontu.

Petr Kučera ()


29. května 2006

29 / 117

Část III Stromy

Petr Kučera ()


29. května 2006

30 / 117

Stromy

6

Co je to strom

7

Reprezentace stromu

8

Binární vyhledávací stromy

9

Cvičení

Petr Kučera ()


29. května 2006

31 / 117

Co je to strom. . . Formálně: Acyklický graf. Neformálně: I I I I

Struktura skládající se z vrcholů (uzlů). Jeden je význačný, nazývá se kořen, ten reprezentuje přístup ke stromu. Kořen má několik následníků neboli synů. Každý z nich je kořenem menšího stromu, tj. má další syny atd.

V binárním stromě má každý vrchol nejvýš dva syny (levého a pravého). Strom

Petr Kučera ()

Binární strom


29. května 2006

32 / 117

Reprezentace binárního stromu

S vrcholem mohou být asociována data (v příkladu celé číslo). Ve vrcholu se občas hodí mít kromě odkazu na syny i odkaz na otce (v příkladu chybí).

type PBinVrchol = ^TBinVrchol; TBinVrchol = record levy, pravy : PBinVrchol; data : integer; end;

Petr Kučera ()


29. května 2006

33 / 117

Reprezentace obecného stromu I

Je-li maximální počet synů omezený a ne příliš velký, můžeme odkazy na ně uchovávat v poli.

const MAX_POCET_SYNU = 20; type PVrchol = ^TVrchol; TVrchol = record syn : array [1..MAX_POCET_SYNU] of PVrchol; data : integer; end;

Petr Kučera ()


29. května 2006

34 / 117

Reprezentace obecného stromu II Jinou možností je uchovávat odkazy na syny ve spojovém seznamu.

type PSeznamSynu = ^TSeznamSynu; PVrchol = ^TVrchol; TSeznamSynu = record syn : PVrchol; dalsi : PSeznamSynu; end; TVrchol = record syn : PSeznamSynu; data : integer; end; Petr Kučera ()


29. května 2006

35 / 117

Reprezentace obecného stromu III Dalším způsobem je pamatovat si jen odkaz na prvního syna a svého dalšího bratra. Chceme-li se dozvědět všechny syny, přejdeme do prvního a projdeme postupně všechny jeho bratry. Obecný strom jsme vlastně nahradili binárním.

type PVrchol TVrchol syn, data end;

Petr Kučera ()

= ^TVrchol; = record bratr : PVrchol; : integer;


29. května 2006

36 / 117

Binární vyhledávací strom (BVS) je binární strom, v němž navíc asociujeme s každým vrcholem tzv. klíč (například číslo). Navíc pro každý vrchol v platí, že I

I

všechny prvky v podstromu levého syna (není-li nil) mají klíč menší než klíč v a všechny prvky v podstromu pravého syna (není-li nil) mají klíč větší než klíč v .

50 51

23 6 1

Petr Kučera ()

43 11

27

67 62


89 29. května 2006

37 / 117

Reprezentace BVS

Binární strom, liší se jen položkou klíč. Položka „dataÿ pro jednoduchost vynechána.

type PBVSVrchol = ^TBVSVrchol; TBVSVrchol = record levy, pravy : PBVSVrchol; klic : integer; end;

Petr Kučera ()


29. května 2006

38 / 117

Vyhledávání v BVS function najdi (PBVSVrchol : koren; x : integer):PBVSVrchol Hledáme prvek s klíčem x. Začínáme v kořeni Porovnáme hodnotu x s klíčem aktuálního vrcholu, I I I

je-li x stejný jako klíč, končíme, je-li x větší, změníme aktuální klíč na pravého syna, je-li x menší, změníme aktuální klíč na levého syna. 50

x=43 23

51

6 1

Petr Kučera ()

43 11

27

67 62


89

29. května 2006

39 / 117

Vkládání do BVS procedure vloz (var PBVSVrchol : koren; x : integer) Nejprve postupujeme stejně jako ve funkci najdi, dokud nenarazíme na nil. (Pokud prvek najdeme, tak ohlásíme chybu.) Tím jsme našli místo, kde by vrchol byl, kdyby byl ve stromě. Vytvoříme nový vrchol se zadaným klíčem a přidáme jej na nalezené místo. 50

x=46 23

51

6 1

Petr Kučera ()

43 11

27

67 46

62


89

29. května 2006

40 / 117

Mazání z BVS procedure smaz (var PBVSVrchol : koren; x : integer) Nejprve stejně jako ve funkci najdi nenajdeme prvek v , při hledání v najdeme rovnou i jeho otce o. Nemá-li vrchol v syna, prostě v , s využitím odkazu na o, odstraníme. Má-li vrchol v jediného syna s, smažeme v a s připojíme jako syna o (toho, kterým byl v ). Pokud má vrchol v dva syny, . . . viz následující slide. 50

x=46 23

51

6 1

43 o 11

27 v

Petr Kučera ()

50

x=43 23 o 6

67 46

62

51

89

1

v 11


s

27

43

67 62 29. května 2006

89 41 / 117

Mazání z BVS (dokončení) Má-li v dva syny l a r , najdeme nejbližší menší prvek w , což je největší prvek z levého podstromu. Ten najdeme tak, že jdeme z l stále doprava, všimněte si, že w nikdy nemá pravého syna. Vyměníme datové a klíčové položky w a v . Poté w smažeme tak, jak bylo popsáno. Analogicky lze použít nejbližší větší prvek. x=23 23 6 1

50

27

Petr Kučera ()

67

43 46

62

50 o

11 v

51 r

w

x=23

v

l 11

o

6 89

1

l 23


51 r

w

27

67

43 46

62

29. května 2006

89 42 / 117

Cvičení

Implementujte funkce a procedury pro vyhledávání, vkládání a mazání v binárním vyhledávacím stromě. Implementujte funkce, které najdou největší a nejmenší prvek z binárního vyhledávacího stromu. Implementujte funkci, která vypíše prvky uložené v binárním vyhledávacím stromě od nejmenšího do největšího, nepoužívejte přitom rekurzi, o které si řekneme později. Jako nápověda může sloužit, že se zde využije zásobník.

Petr Kučera ()


29. května 2006

43 / 117

Část IV Grafy

Petr Kučera ()


29. května 2006

44 / 117

Grafy 10

Co je to graf

11

Reprezentace grafu

12

Průchod stromu a grafu

13

Průchod stromu do hloubky

14

Průchod stromu do šířky

15

Průchod grafu do hloubky

16

Průchod grafu do šířky

17

Cvičení

Petr Kučera ()


29. května 2006

45 / 117

Co je to graf . . . Graf je struktura skládající se z vrcholů a hran mezi těmito vrcholy. (Například silniční síť.) Orientovaný graf hrany jsou orientované, tj. u každé je dáno, že vede z jednoho vrcholu do jiného a ne naopak. Neorientovaný graf hrany nejsou orientované, tj. každá vede jakoby oběma směry. Sousedi či následníci vrcholy jsou ty vrcholy, do nichž z něj vede hrana. Cesta je posloupnost vrcholů v1 , . . . , vk , že mezi dvěma následujícími vždy vede hrana a žádný vrchol se neopakuje. Cyklus je „cestaÿ, která začíná i končí ve stejném vrcholu.

Petr Kučera ()


29. května 2006

46 / 117

Co je to graf . . . Neorientovaný graf

Orientovaný graf h

f b

d c

a

h

f

b

d c

g

e

a

g

e

Cesta a, b, c, d, e

Petr Kučera ()


29. května 2006

47 / 117

Matice sousednosti Matice sousednosti grafu s n vrcholy je matice A velikosti n × n booleovských hodnot. Deklarace: var A: array [1..N, 1..N] of boolean; A[i, j] = true, právě když je v grafu hrana z vrcholu i do vrcholu j.

h

f

b

d c

a

Petr Kučera ()

g

e

a a 0 b 1 c 0 d 0 e 0 f 0 g 0 h 0


b 1 0 0 0 0 0 0 0

c 0 1 0 0 0 0 0 0

d 0 0 1 0 0 0 0 0

e 0 0 0 1 0 0 0 0

f 0 1 0 0 0 1 0 0

g 1 0 1 0 0 0 0 0

29. května 2006

h 0 0 0 0 0 1 1 0

48 / 117

Matice incidence Matice incidence grafu s n vrcholy a m hranami je matice I velikosti m × n booleovských hodnot. Deklarace: var I: array [1..M, 1..N] of boolean; I [i, j] = true, právě když vrchol j je prvkem hrany i.

h

f

b

d c g

a

Petr Kučera ()

e

1 a 1 b 1 c 0 d 0 e 0 f 0 g 0 h 0

2 1 0 0 0 0 0 1 0

3 0 1 1 0 0 0 0 0


4 0 1 0 0 0 1 0 0

5 0 0 1 1 0 0 0 0

6 0 0 1 0 0 1 0 0

7 0 0 1 0 0 0 1 0

8 0 0 0 1 1 0 0 0

9 10 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1

29. května 2006

49 / 117

Seznam sousedů Seznam sousedů grafu s n vrcholy a m hranami se skládá z pole V délky n, v němž si ke každému vrcholu i pamatujeme odkaz na seznam vrcholů, do nichž z i vede hrana. Seznamy buď dynamicky pomocí lineárního spojového seznamu. Hodí se pokud se často mění struktura grafu. Nebo pomocí druhého pole E délky m. V [i] pak obsahuje index v poli E , na němž začíná seznam sousedů vrcholu i, seznam končí na V [i + 1] − 1. Pro jednoduchost přidáme vrchol N + 1, abychom mohli k vrcholům přistupovat jednotným způsobem. Z téhož důvodu i M + 1 v jako rozsah v deklaraci V . Deklarace: var V: array [1..N+1] of 1..M+1; E: array [1..M] of 1..N; Petr Kučera ()


29. května 2006

50 / 117

Seznam sousedů – příklad h

f

b

d c g

a

e

V

a b c d e f g h ? 1 3 6 8 9 9 11 12 12

E

1 2 3 4 5 6 b g a c f d

Petr Kučera ()

7 g

8 e


9 c

10 11 h h 29. května 2006

51 / 117

Průchod stromu nebo grafu

Chceme navštívit všechny vrcholy a něco s nimi udělat. Navíc máme požadavky na pořadí, v jakém je navštívíme. Například chceme vypsat uzly binárního vyhledávacího stromu uspořádané podle klíčů. Nebo chceme v grafu pro daný počáteční vrchol spočítat délku nejkratší cesty (co do počtu hran) do ostatních vrcholů.

Petr Kučera ()


29. května 2006

52 / 117

Průchod stromu do hloubky

Konkrétní úloha: Vypsat uzly binárního vyhledávacího stromu uspořádané podle klíčů. Postupujeme tak, že v daném vrcholu v nejprve vypíšeme všechny uzly v podstromu levého syna, potom vrchol v , potom všechny uzly v podstromu pravého syna. Uzly v obou podstromech zpracováváme analogicky. Realizace buď pomocí rekurze (později), nebo pomocí zásobníku.

Petr Kučera ()


29. května 2006

53 / 117

Průchod stromu do hloubky – algoritmus 1

Z ← prázdný zásobník

2

v ← kořen stromu

3 4

zeZasobniku ← false Dokud není v nil, opakuj následující kroky: 1

Má-li v levého syna l a zeZasobniku = false 1 2 3 4

2 3

vypiš v Má-li v pravého syna r 1 2 3

4 5

push(Z , v ) v ←l zeZasobniku ← false pokračuj další smyčkou cyklu

v ←r zeZasobniku ← false pokračuj další smyčkou cyklu

v ← pop(Z ) zeZasobniku ← true

Petr Kučera ()


29. května 2006

54 / 117

Průchod stromu do hloubky – varianty Podle pořadí zpracovávaných vrcholů rozeznáváme tři varianty průchodu do hloubky. preorder Zpracuj vrchol v , zpracuj levý podstrom vrcholu v , zpracuj pravý podstrom vrcholu v . inorder Zpracuj levý podstrom vrcholu v , zpracuj vrchol v , zpracuj pravý podstrom vrcholu v . postorder Zpracuj levý podstrom vrcholu v , zpracuj pravý podstrom vrcholu v , zpracuj vrchol v . Předešlý algoritmus zařídí výpis v pořadí inorder. Ostatní varianty lze provést snadnou modifikací, my si je ukážeme později v části o rekurzi.

Petr Kučera ()


29. května 2006

55 / 117

Průchod stromu do šířky

Konkrétní úloha: Vypsat uzly binárního stromu v pořadí podle jejich hloubky. Realizace pomocí fronty (tady nejde rekurzi moc dobře použít).

Petr Kučera ()


29. května 2006

56 / 117

Průchod stromu do šířky – algoritmus

1 2 3

F ← prázdná fronta put(F , kořen stromu) Dokud není F prázdná, opakuj následující kroky: 1 2 3 4

v ← get(F ) vypiš v Má-li v levého syna l, put(F , l). Má-li v pravého syna r , put(F , r ).

Petr Kučera ()


29. května 2006

57 / 117

Průchod grafu do hloubky

Chceme navštívit každý vrchol grafu právě jednou a to tak, že jsme-li ve vrcholu v , který má následníky u1 , . . . , uk , chceme nejprve navštívit všechny vrcholy, do nichž vede cesta z u 1 , potom všechny vrcholy, do nichž vede cesta z u2 atd. Stejně jako při průchodu stromem, použijeme zásobník. Například chceme zjistit komponenty souvislosti grafu (komponenta souvislosti je množina vrcholů, které jsou všechny spojené cestami. Navíc už je maximální, nejde k ní tedy nic přidat.)

Petr Kučera ()


29. května 2006

58 / 117

Průchod grafu do hloubky Tento algoritmus označí (nastaví K [i] na 1) všechny vrcholy, do nichž vede cesta z vrcholu s. N označuje počet vrcholů. 1

Z ← prázdný zásobník

2

push(Z , počáteční vrchol s)

3

K : array [1. .N] of integer

4

K [i] ← 0 pro i = 1 . . . N.

5 6

K [s] ← 1 Dokud není Z prázdný, opakuj následující kroky: 1 2

v ← pop(Z ) Pro každého následníka u vrcholu v , pro nějž K [u] = 0, proveď: 1 2

push(Z , u). K [u] ← 1

Petr Kučera ()


29. května 2006

59 / 117

Průchod grafu do hloubky – poznámky

Graf je vhodné reprezentovat pomocí seznamu následníků. Pokud chceme najít všechny komponenty, voláme tento algoritmus, dokud je pro nějaký vrchol K [v ] = 0 s tím, že jako počáteční vrchol použijeme vrchol v . Číslo komponenty postupně zvyšujeme, v algoritmu bylo 1.

Petr Kučera ()


29. května 2006

60 / 117

Průchod grafu do šířky

Chceme navštívit každý vrchol grafu právě jednou a to tak, že jsme-li ve vrcholu v , který má následníky u1 , . . . , uk , chceme nejprve navštívit vrcholy u1 , . . . , uk a pak teprve jejich následníky atd. Stejně jako při průchodu stromem, použijeme frontu. Například vycházíme z vrcholu s a chceme najít pro každý vrchol v délku nejkratší cesty (co do počtu hran) z s do v . Případně i tuto cestu.

Petr Kučera ()


29. května 2006

61 / 117

Průchod grafu do šířky – algoritmus Tento algoritmus spočítá pro každý vrchol délku nejkratší cesty (počet hran) z vrcholu s. Délku uloží do pole D, předchůdce na této cestě do P. 1

F ← prázdná fronta

2

put(F , počáteční vrchol s)

3

D, P: array [1. .N] of integer

4

D[i] ← N + 1, P[i] ← N + 1 pro i = 1 . . . N.

5 6

D[s] ← 0 Dokud není F prázdná, opakuj následující kroky: 1 2

v ← get(F ) Pro každého následníka u vrcholu v , pro nějž D[u] = N + 1, proveď: 1 2 3

put(F , u). D[u] ← D[v ] + 1 P[u] ← v

Petr Kučera ()


29. května 2006

62 / 117

Průchod grafu do šířky – poznámky

Vhodnou reprezentací grafu je opět seznam sousedů. Cestu do vrcholu zrekonstruujeme pomocí předchůdců.

Petr Kučera ()


29. května 2006

63 / 117

Cvičení

1

2 3

4

5

Implementujte algoritmus pro vypsání uzlů binárního vyhledávacího stromu uspořádané podle klíče. Implementujte průchod stromem do šířky. Implementujte průchod grafem do hloubky a hledání komponent souvislosti grafu. Implementujte průchod grafem do šířky a počítání nejkratších cest ze zadaného vrcholu (co do počtu hran). Implementujte průchod stromem v pořadí preorder, inorder, postorder.

Petr Kučera ()


29. května 2006

64 / 117

Část V Vstup a výstup do souboru

Petr Kučera ()


29. května 2006

65 / 117

Vstup a výstup do souboru 18

Typy souborů

19

Otevření a uzavření souboru

20

Pohyb v souboru

21

Textové soubory

22

Netextové soubory

23

Cvičení

Petr Kučera ()


29. května 2006

66 / 117

Typy souborů Soubor s udaným typem, např.: var f1: file of integer; Soubor bez udaného typu, základní položkou je byte, např.: var f2: file; Textový soubor, čte se obvykle po znacích nebo po řádcích, např.: var f3: text; Standardní vstup, obvykle jde o vstup z klávesnice, je to textový soubor jen pro čtení, který je vždy otevřený po spuštění programu. Čte z něj pomocí funkcí read, readln a podobných, u nichž se nespecifikuje soubor parametrem. Standardní výstup, obvykle jde o výstup na obrazovku, je to textový soubor jen pro zápis, který je vždy otevřený po spuštění programu. Zapisuje se do něj pomocí funkcí write, writeln a podobných.

Petr Kučera ()


29. května 2006

67 / 117

Otevření a uzavření souboru Nejprve je nutné asociovat soubor se jménem: assign (f1, "cisla"); Poté je možné soubor otevřít: I

I

I

reset – soubor musí existovat, textové soubory jsou otevřeny pouze pro čtení. rewrite – pokud soubor existoval, smaže nejprve jeho obsah, pokud neexistoval, vytvoří jej. append – otevírá textový soubor pro zápis, soubor musí existovat a zapisovaný text bude přidáván na konec souboru.

Například: reset (f1); rewrite (f2); append (f3); Nakonec je slušné soubor zavřít. close (f1); Další manipulace se soubory a adresáři viz. nápověda a dokumentace.

Petr Kučera ()


29. května 2006

68 / 117

Pohyb v souboru

V každý okamžik je program v souboru na určité pozici, tj. za nějakým znakem, či složkou daného typu. Funkce eof vrací true, pokud je tato pozice na konci souboru, false jinak. Pohyb je vykonáván jednak přirozeně čtením a zápisem, jednak pomocí dalších funkcí, které se liší podle typu souboru.

Petr Kučera ()


29. května 2006

69 / 117

Pohyb v textovém souboru

U všech funkcí pro textové soubory, pokud není udán soubor, míní se standardní vstup případně výstup. eoln vrací true, pokud je pozice souboru na znaku konce řádku, jinak false. seekeof má stejný význam jako eof, ale ignoruje všechny mezery, tabelátory a znaky konce řádku. Změní pozici na první znak za těmito znaky a pak vrátí, co by vrátilo eof. seekeoln má stejný význam jako eoln, ale ignoruje všechny mezery a tabelátory. Změní pozici na první pozici za těmito znaky a pak vrátí, co by vrátilo eoln

Petr Kučera ()


29. května 2006

70 / 117

Čtení z textového souboru

Procedury read, readln. Prvním parametrem může být textový soubor, jinak se bere standardní vstup. Další parametry mohou být typu char, celočíselného, reálného nebo string, ze souboru se přečte příslušná hodnota (znak, reprezentace čísla nebo řetězec příslušné délky) a načte se do daného parametru. readln se liší jen tím, že nakonec přejde na nový řádek.

Petr Kučera ()


29. května 2006

71 / 117

Zápis do textového souboru Procedury write, writeln Prvním parametrem může být opět textový soubor, jinak se míní standardní výstup. Další parametry mohou být stejného typu jako u read. Parametry je možné zadat pomocí: Potom: I I

hodnota [ : minšířka [ : početmíst]]

minšířka specifikuje, na kolik pozic se má výstup zarovnat. početmíst specifikuje počet desetinných míst je za desetinnou tečkou (jen reálné parametry ).

writeln se liší jen tím, že na konec přidá znak konce řádku.

Petr Kučera ()


29. května 2006

72 / 117

Buffery

Všechny operace se bufferují. Velikost bufferu je možné změnit pomocí settextbuf. flush vyprázdní buffer a přitom zapíše dosud nezapsané znaky na disk.

Petr Kučera ()


29. května 2006

73 / 117

Příklad práce s textovým souborem (začátek) program textsoub; var vstup: text; vystup: text; soucet: integer; scitanec: integer; begin assign (vstup, ’vstup.txt’); assign (vystup, ’vystup.txt’); reset (vstup); rewrite (vystup);

Petr Kučera ()


29. května 2006

74 / 117

Příklad práce s textovým souborem (dokončení) while not seekeof (vstup) do begin soucet := 0; while not seekeoln (vstup) do begin read (vstup, scitanec); soucet := soucet + scitanec; end; writeln (vystup, soucet:10); readln (vstup); end; close (vstup); close (vystup); end.

Petr Kučera ()


29. května 2006

75 / 117

Pohyb v netextových souborech

V textových souborech sice nelze používat funkce a procedury popsané v následující části, ale lze je použít na file of char, který je skoro jako textový. filepos vrací současnou pozici v souboru, tj. pořadové číslo právě zpracovávané položky souboru. filesize vrací celkový počet položek v souboru. seek nastaví současnou pozici na hodnotu specifikovanou parametrem. Číslo první položky je 0, číslo poslední je filesize - 1 .

Petr Kučera ()


29. května 2006

76 / 117

Čtení a zápis do netextového souboru

Opět pomocí procedur read a write. Tentokrát se připouštějí jen dva parametry, soubor a proměnná, do které se načte jedna, následující položka. Blokové čtení a zápis (po více položkách) pomocí procedur blockread a blockwrite, viz nápověda a dokumentace. truncate smaže všechny položky od současné do konce souboru.

Petr Kučera ()


29. května 2006

77 / 117

Cvičení I

Napište program, který se zeptá uživatele na název textového souboru a slovo, poté vypíše čísla řádků u přímo ty řádky, které obsahují dané slovo. Napište program, který porovnává dva vstupní soubory znak po znaku, nakonec vypíše, v kolika znacích se soubory lišily.

Petr Kučera ()


29. května 2006

78 / 117

cvičení II Napište program, který z jednoho souboru načte graf zadaný seznamem sousedů a vypíše jeho matici sousednosti do jiného souboru. I

I

Předpokládejte, že vstup má následující formát: Na první řádce je číslo s počtem vrcholů n, vrcholy jsou potom číslovány od jedné n. Každá následující řádka obsahuje vždy číslo vrcholu, dvojtečku a za ní mezerami oddělená čísla sousedních vrcholů. Kolem dvojtečky mohou být mezery. Řádky s vrcholy jsou uspořádané vzestupně podle čísla vrcholu. Na první řádce výstupu by měl být opět počet vrcholů, na dalších řádkách vypsaná matice z nul a jedniček, které budou na každém řádku oddělené mezerami.

Napište program, který bude dělat opak předešlého, tj. bude převádět matici sousednosti na seznam sousedů.

Petr Kučera ()


29. května 2006

79 / 117

Část VI Rekurze

Petr Kučera ()


29. května 2006

80 / 117

Rekurze 24

Co je to rekurze?

25

Průchod stromem do hloubky

26

Průchod grafem do hloubky

27

Varovný příklad – Fibonacciho čísla

28

Zpracování aritmetického výrazu

29

Cvičení

Petr Kučera ()


29. května 2006

81 / 117

Co je to rekurze?

Rekurzí nazýváme volání funkce nebo procedury v rámci jejího těla. Může jít o volání někde „hloubějiÿ, například funkce a volá funkci b, funkce b volá funkci a a podobně. Za rekurzí je vždy schován zásobník a lze ji pomocí zásobníku odstranit, rozdíl je jen v tom, jestli ten zásobník spravujete vy (nerekurzivně) nebo překladač a systém (rekurzivně). Ukážeme si na příkladech. . .

Petr Kučera ()


29. května 2006

82 / 117

Průchod binárním stromem do hloubky (preorder ) Průchod do hloubky lze vyřešit snadno, průchod do šířky je nutné řešit pomocí fronty, pomocí rekurze nelze. procedure projdi (PBinVrchol koren) begin if koren <> nil then begin akce (koren); if koren^.levy <> nil then projdi (koren^.levy); if koren^.pravy <> nil then projdi (koren^.pravy); end; end;

Petr Kučera ()


29. května 2006

83 / 117

Průchod binárním stromem do hloubky (inorder )

procedure projdi (PBinVrchol koren) begin if koren <> nil then begin if koren^.levy <> nil then projdi (koren^.levy); akce (koren); if koren^.pravy <> nil then projdi (koren^.pravy); end; end;

Petr Kučera ()


29. května 2006

84 / 117

Průchod binárním stromem do hloubky (postorder )

procedure projdi (PBinVrchol koren) begin if koren <> nil then begin if koren^.levy <> nil then projdi (koren^.levy); if koren^.pravy <> nil then projdi (koren^.pravy); akce (koren); end; end;

Petr Kučera ()


29. května 2006

85 / 117

Průchod grafem do hloubky Hledání komponent grafu.

var K: array [1..N] of integer; V: array [1..N+1] of 1..M+1; E: array [1..M] of 1..N; procedure projdiVrchol (vrchol: integer, komp: integer) var soused: 1..M; begin K[vrchol]:=komp; for soused:=V[vrchol] to V[vrchol+1]-1 do begin if K[E[soused]] = 0 then projdiVrchol (E[soused], komp); end end; Petr Kučera ()


29. května 2006

86 / 117

Průchod grafem do hloubky Dokončení

procedure projdiGraf; var v: 1..N; var c: 1..N; begin c:=0; for v:=1 to N do if K[v] = 0 then begin c:=c+1; projdiVrchol (v, c); end; end;

Petr Kučera ()


29. května 2006

87 / 117

Fibonacciho čísla

Posloupnost Fibonnaciho čísel je definována následujícím předpisem: F0 = 0 F1 = 1 Fn = Fn−1 + Fn−2

pro n > 1

Naším úkolem je napsat funkci, která co nejrychleji spočítá n-té Fibonacciho číslo.

Petr Kučera ()


29. května 2006

88 / 117

Fibonacciho čísla rekurzivně function FibRec (n: integer): integer; begin if (n = 0) or (n = 1) then FibRec := n else FibRec := FibRec (n-1) + FibRec (n-2); end;

Co je špatně? Například pro spočítání 10. čísla je nutné znát 9. a 8., ale pro 9. je také nutné znát 8. Příliš mnoho výpočtů se tak opakuje a celkově bude tato funkce počítat exponenciálně dlouho vzhledem k n. Petr Kučera ()


29. května 2006

89 / 117

Strom volání funkce FibRec(10) 10 9

8

8 7

7 6

Petr Kučera ()

6

7 5

6


6 5

5

29. května 2006

4

90 / 117

Fibonacciho čísla rychleji

Jak z toho ven? Buď přidat pomocné pole, do nějž se budou ukládat už spočítané hodnoty Fibonacciho čísel. Ve volání funkce se pak nejprve testuje, jestli už není příslušná hodnota spočítaná. Druhou možností je jednoduché nerekurzivní řešení, stačí si totiž vždy pamatovat tři poslední Fibonacciho čísla.

Petr Kučera ()


29. května 2006

91 / 117

Fibonacciho čísla nerekurzivně function FibNerek (n: integer) : integer; var a, b, c, i: integer; begin if (n = 0) or (n = 1) then FibNerek := n else begin a := 0; b := 1; c := 1; for i := 3 to n do begin a := b; b := c; c := a + b; end FibNerek := c; end; end; Petr Kučera ()


29. května 2006

92 / 117

Reprezentace aritmetického výrazu Nejběžnější je infixový zápis, např.: (32 + 3) ∗ 6 − (12 + 7)/4 V prefixovém zápisu píšeme nejprve operátor, za ním následují operandy. Např.: − ∗ + 32 3 6 / + 12 7 4 V postfixovém zápisu naopak píšeme nejprve operandy, za nimi teprve operátor. Např.: 32 3 + 6 ∗ 12 7 + 4 / − Prefixový a postfixový zápis se hodí pro zpracování v programu. Pořadí číselných konstant je ve všech zápisech stejné, liší se jen umístění operátorů a použití závorek. Petr Kučera ()


29. května 2006

93 / 117

Reprezentace výrazu binárním stromem I Aritmetický výraz se často reprezentuje binárním stromem. Kořen je tvořen prvním operátorem s nejnižší prioritou, jeho synové jsou stromové reprezentace operandů. Listy jsou ohodnoceny číselnými konstantami. Například:

/

*

32

Petr Kučera ()

+

6

+ 3

12

4 7


29. května 2006

94 / 117

Reprezentace výrazu binárním stromem II Infixový, prefixový nebo postfixový zápis výrazu dostaneme průchodem do hloubky odpovídajícím způsobem, tj. inorder, preorder nebo postorder. Vyhodnocení výrazu daného binárním stromem opět triviálně průchodem do hloubky (lze i přímo analogickým postupem). Reprezentace v Pascalu: type PVyraz = ^TVyraz; TVyraz = record hodnota : integer; operator : char; levy, pravy : PVyraz; end;

Petr Kučera ()


29. května 2006

95 / 117

Vytvoření stromu výrazu

Chceme vytvořit binární strom reprezentující výraz zadaný řetězcem v infixovém zápisu. Nejsnažší je rekurzivní postup metodou rozděl a panuj. Budeme předpokládat, že výraz obsahuje jen číselné konstanty, operátory *, /, +, - a závorky. Následuje pouze idea, konkrétní realizaci je možné nalézt v doporučené literatuře.

Petr Kučera ()


29. května 2006

96 / 117

Převod výrazu v infixovém zápisu na strom Vytvoříme následující funkce, které mezi sebou používají nepřímou rekurzi: Prvek(var hodnota: integer; var znak: char) : boolean Tato funkce přečte ze vstupu/řetězce následující prvek výrazu, buď číselnou konstantu, nebo znak operátoru či závorky, přečte-li číslo, bude znak=’$’. Vrací true, pokud uspěl, false při nějaké chybě, nebo když už ve vstupu nic není. Faktor : PVyraz Faktorem (činitelem, dělitelem, dělencem) je číselná konstanta, nebo výraz uzavřený do závorek. Tato funkce tedy buď vrátí list reprezentující příslušné číslo, nebo strom reprezentující výraz v závorkách, rekurzivně vytvořený voláním funkce Vyraz.

Petr Kučera ()


29. května 2006

97 / 117

Převod výrazu v infixovém zápisu na strom Dokončení

Clen : PVyraz Členem (sčítancem, menšitelem, menšencem) je součin či podíl více faktorů. Tato funkce vrátí strom vystavěný z jednotlivých podstromů, které nám vrátí postupná volání funkce faktor, funkce skončí ve chvíli, kdy přečteným znakem je ’+’, ’-’, nebo ’)’, případně narazí na konec vstupu/řetězce. Vyraz : PVyraz Výraz je součtem či rozdílem více členů. Tato funkce vytvoří strom vystavěný z jednotlivých členů, jejichž stromové reprezentace nám vrátí postupná volání funkce clen. Funkce končí ve chvíli, kdy narazí na konec výrazu či na ’)’.

Petr Kučera ()


29. května 2006

98 / 117

Výrazy, závěrečné poznámky

Výraz zapsaný infixově, lze celkem jednoduše převést do postfixového zápisu jedním průchodem s použitím zásobníku (viz literatura). Vyhodnocení či vytvoření stromu z výrazu v postfixovém či prefixovém zápisu je jednodušší (viz cvičení a literatura). Analogickým postupem jako vytváření stromu, lze rovnou výraz vyhodnocovat, místo stromové reprezentace prostě vždy vracíme výsledné číslo.

Petr Kučera ()


29. května 2006

99 / 117

Cvičení Vyzkoušejte si průchody do hloubky grafem či stromem pomocí rekurze. Vyzkoušejte si výpočet Fibonacciho čísla pomocí rekurze i bez rekurze a porovnejte rychlost obou řešení. Vyzkoušejte si napsat funkce a procedury, které umožní vytvořit z výrazu na vstupu, zadaného infixovým zápisem, binární strom, který jej reprezentuje. Vyzkoušejte si napsat funkce a procedury, které umožní vyhodnotit výraz na vstupu, který je zadaný v infixovém zápisu. Předešlé dva body zkuste i pro postfixový a prefixový zápis. Naprogramujte převod mezi jednotlivými způsoby zápisu výrazu.

Petr Kučera ()


29. května 2006

100 / 117

Část VII Třídící algoritmy

Petr Kučera ()


29. května 2006

101 / 117

Třídící algoritmy

30

Třídění obecně

31

Bublinkové třídění

32

Quicksort

33

Mergesort

34

Vnější třídění

Petr Kučera ()


29. května 2006

102 / 117

Třídění Úlohou je setřídit data podle nějakých klíčů. Vnitřní třídění – data jsou uložena v poli s přímým přístupem. Vnější třídění – data jsou uložena v souboru se sekvenčním přístupem, obvykle jsou tak velká, že se nevejdou do paměti. Třídění založené na porovnávání nutně spotřebuje čas Ω(n · log n). Rozumné algoritmy třídí v tomto čase. Pomalejší třídí v kvadratickém čase a hodí se jen pro malá data. Přihrádkové třídění, radixsort – třídí v lineárním čase, ale jen v případě, že hodnoty klíčů patří do malého omezeného rozsahu. Dále popsané algoritmy většinou předpokládají, že čísla v posloupnosti jsou po dvou různá, třebaže se dají upravit, aby pro ně toto omezení neplatilo. Předpokládáme deklaraci type TPole = array [1..N] of integer; Petr Kučera ()


29. května 2006

103 / 117

Bublinkové třídění

Jde o kvadratický algoritmus ⇒ na větší data nepoužívat! Předpokládejme, že data jsou uložena v poli A s n prvky. Postup je následovný, projdeme n-krát pole A a při každém průchodu, pokud narazíme na dvojici A[i] < A[i + 1], tak příslušné prvky vyměníme. Dá se to urychlit tím, že poprvé sice projdeme pole celé, ale poté již vždy polem procházíme jen do místa, kde byla naposledy provedena výměna.

Petr Kučera ()


29. května 2006

104 / 117

Quicksort Třídění metodou rozděl a panuj. Postup je velice jednoduchý: I I

I I

Vyber pivota b (nějaký prvek pole A). Jedním průchodem vytvoř pole A1 prvků menších než pivot, A2 prvků větších než pivot. Rekurzivně setřiď A1 a A2 . Vrať pole složené z A1 , b, A2 .

V nejhorším případě může být čas kvadratický. Pokud je za pivota zvolený medián (tj. |A 1 | = |A2 |), je čas vždy O(n · log n). Při jistých požadavcích na náhodnost vstupu je quicksort průměrně O(n · log n), za pivota je možné zvolit cokoli, třeba A[1].

Petr Kučera ()


29. května 2006

105 / 117

Implementace quicksortu procedure qsort (var A: TPole; l, r: integer); var b, i, j, c: integer; begin if (l b do j:=j-1; c:=A[i]; A[i]:=A[j]; A[j]:=c; end; qsort(A, l, i-1); qsort(A, i+1, r); end; end; Petr Kučera ()


29. května 2006

106 / 117

Quicksort Poznámky

Implementace je popsána tak, abychom nevytvářeli zbytečná odkládací pole. Lze samozřejmě implementovat i nerekurzivně se zásobníkem. Medián lze nalézt v lineárním čase, proto je možné quicksort implementovat tak, že má zaručenou složitost O(n · log n), ale ve skutečnosti je to potom pomalejší. Stejným postupem lze hledat k-tý nejmenší/největší prvek. Pouze místo dvou rekurzivních volání, voláme rekurzivně vyhledávání jen na tu půlku, kde se prvek nachází, což zjistíme podle toho, kolik je v jednotlivých půlkách prvků. Musíme samozřejmě příslušně upravit k.

Petr Kučera ()


29. května 2006

107 / 117

Mergesort Mergesort, čili třídění sléváním, má zaručenou složitost O(n · log n). Postupujeme v podstatě opačně, než v quicksortu: I I I

Rozděl pole A na dvě poloviny A1 , A2 stejné velikosti. Rekurzivně setřiď obě poloviny A1 a A2 . Slij pole A1 a A2 do výsledného pole.

Popíšeme proceduru slij(A, l, r, m), která slije dvě setříděná pole, z nichž první je uloženo v prvcích A[l..m], druhé v prvcích A[m + 1..r ]. S jejím využitím popíšeme proceduru msort(A, l, r), která setřídí pole složené z prvků A[l..r ]. Pomocné pole B je možné mít pouze jedno a předávat s dalšími parametry odkaz na ně, a to z důvodu šetření pamětí.

Petr Kučera ()


29. května 2006

108 / 117

Slévání procedure slij (var A: TPole; l, r, m: integer); var B: array [1..N] of integer; i, j, k: integer; begin i:=l; j:=m+1; k:=l; while (i<=m) and (j<=r) do begin if (A[i] <= A[j]) then begin B[k]:=A[i]; i:=i+1; end else begin B[k]:=A[j]; j:=j+1; end; k:=k+1; end; while (i<=m) do begin B[k]:=A[i]; i:=i+1; k:=k+1; end; while (j<=r) do begin B[k]:=A[j]; j:=j+1; k:=k+1; end; for k:=l to r do A[k]:=B[k]; end; Petr Kučera ()


29. května 2006

109 / 117

Implementace mergesortu

procedure msort (var A: TPole; l, r:integer); var m: integer; begin if (l
Petr Kučera ()


29. května 2006

110 / 117

Nerekurzivní implementace mergesortu

Rozmyslíme-li si, jak mergesort pracuje, můžeme se jednoduše obejít bez rekurze. Jednoprvkové pole je vždy setříděné. V prvním kroku slijeme vždy dvě následující jednoprvková pole, a tak vzniknou utříděná pole délky 2. V dalším kroku slijeme vždy dvě následující dvouprvková pole, a vytvoříme tak utříděná pole délky 4. Pokračujeme dál stejně, až dokud nesetřídíme celé pole. Tomuto postupu se říká přímé slučování, lze jej použít i jako vnější třídění na soubory.

Petr Kučera ()


29. května 2006

111 / 117

Nerekurzivní implementace mergesortu procedure msort2 (var A: TPole); var krok, i, j: integer; begin krok:=1; while krok < N do begin i:=1; j:=2*krok; if (j > N) then j:=N; while i < N do begin if (i+krok-1 N) then j:=N; end; krok := krok * 2; end; end; Petr Kučera ()


29. května 2006

112 / 117

Vnější třídění Přirozené slučování

Princip přímého slučování lze zobecnit. Pro nás není podstatné to, že na začátku jsou setříděné posloupnosti jednoprvkové, ale to, že jsou setříděné. Postup bude tedy takový, že budeme postupně slučovat setříděné úseky, až nakonec vznikne jeden velký úsek se všemi prvky. Ukážeme si jako vnější třídění, tj. předpokládáme, že data jsou uložena v nějakém souboru DATA, do kterého chceme nakonec uložit i setříděný výsledek.

Petr Kučera ()


29. května 2006

113 / 117

Přirozené slučování Postup tedy bude následovný: 1

Rozdělíme setříděné podposloupnosti z DATA do dvou souborů A1 a B1.

2

Sloučíme první posloupnost z A1 s první z B1 do A2.

3

Sloučíme druhou posloupnost z A1 s druhou z B1 do B2.

4

5

6

Stejně pro další posloupnosti, na konci jsou vzniklé delší podposloupnosti rovnou uložené v A2, B2. Pokud při slučování vznikla pouze jedna posloupnost, rovnou skončíme, výsledek je v A1 (resp A2, záleží na následujícím kroku). Vyměníme role A1, B1 a A2, B2 a pokračujeme opět krokem 2.

Konkrétní implementace viz doporučená literatura.

Petr Kučera ()


29. května 2006

114 / 117

Závěrečné poznámky

Metody vnějšího a vnitřního třídění lze kombinovat, tj. při vnějším třídění můžeme nejprve předtřídit bloky takové velikosti, která se nám vejde do paměti. Tento postup nám může ušetřit počáteční čtení a zápisy do souborů.

Petr Kučera ()


29. května 2006

115 / 117

Cvičení

1 2

Implementujte uvedené algoritmy a zkuste je spustit. Rozmyslete si hledání k-tého nejvyššího či nejmenšího prvku postupem rozděl a panuj (jak bylo naznačeno u quicksortu).

Petr Kučera ()


29. května 2006

116 / 117

Konec

Teď už opravdu. . .

Petr Kučera ()


29. května 2006

117 / 117

117

Recommend Documents