Programování v příkladech

Následuje několik jednoduchých úloh.

U úloh tohoto typu si vždy kreslete obrázky, na kterých bude znázorněno, co je propojeno ukazately, odkud kam ukazatele vedou a jak se ukazatele mění, když provádíme nějakou operaci. Nejdůležitější pro řešení těchto úloh není klávesnice a monitor, ale tužka a guma (guma proto, že propojení ukazately se při operacích často mění).

Příklady z této podkapitoly řešte tak, že do následujícího souboru doplníte implementace zadaných funkcí. Rozhodně si ale tento zdrojový kód nejprve projděte a ujistěte se, že mu zcela rozumíte.

type
    UkPrvek = ^Prvek;

    (*
     * Zakladni stavebni jednotka spojoveho seznamu.
     * Zapouzdruje: hodnotu jednoho prvku seznamu a ukazatel na dalsi prvek.
     *)
    Prvek =
        record
            info: Integer;
            dalsi: UkPrvek;
        end;


(*
 * Prida prvek na zacatek seznamu.
 * parametry:
 *     prvniPrvek - ukazatel na prvni prvek seznamu
 *     vkladanaHodnota - hodnota, ktera se ma do seznamu vlozit
 *)
procedure pridej(var prvniPrvek: UkPrvek; vkladanaHodnota: Integer);
var
    {Prvek, ktery bude zapouzdrovat nove pridavanou hodnotu}
    novyPrvek: UkPrvek;
begin
        {vytvorime novy prvek a pripojime ho na zacatek}
        new (novyPrvek);
        novyPrvek^.info := vkladanaHodnota;
        novyPrvek^.dalsi := prvniPrvek;
        prvniPrvek := novyPrvek;
end;

(*
 * Vypise vsechny prvky spojoveho seznamu, oddeluje je mezerou.
 * parametry:
 *     prvniPrvek - ukazatel na prvni prvek seznamu.
 *)
procedure vypisSeznam(var prvniPrvek: UkPrvek);
var
    {ukazatel na prvek, ktery zapouzdruje prave vypisovanou hodnotu}
    aktualniPrvek: UkPrvek;
begin
    aktualniPrvek := prvniPrvek;
    while (aktualniPrvek <> nil) do begin
        write(aktualniPrvek^.info, ' ');
        aktualniPrvek := aktualniPrvek^.dalsi;
    end;
end;


(*
 * Test spojoveho seznamu. Seznam je naplnen cisly 1 az 50 a pote vypsan.
 *)
var
    seznam: UkPrvek;
    vkladanaHodnota: Integer;
begin
    seznam := nil;    

    for vkladanaHodnota := 1 to 50 do begin
        writeln('Vkladam hodnotu ', vkladanaHodnota);
        pridej(seznam, vkladanaHodnota);
    end;

    writeln('OBSAH SEZNAMU:');
    vypisSeznam(seznam);
    writeln;
end.

Příkaz dispose slouží k uvolnění paměti, kterou si program alokoval (tj. „zamluvil“) pomocí příkazu new. Alokovanou paměť je třeba uvolňovat, jinak by paměť dříve nebo později došla. Příkaz dispose se pro uvolnění daného bloku paměti volá vždy jen jedenkrát a jako parametr se mu předá ukazatel na blok, který se má uvolnit. Po provedení dispose ukazaje tento ukazatel na stejné místo v paměti jako před provedením. Protože uvolněný blok již program nebude používat, je většinou třeba všechny ukazatele, které na ten blok ukazují, nastavit na nil. Příklad:

var ukazatel1, ukazatel2, ukazatel3: UkPrvek;
begin
        {tady neco alokujeme, budou na to ukazovat tri ukazatele}
        new (ukazatel1);
        ukazatel2 := ukazatel1;
        ukazatel3 := ukazatel1;

        {ted to zrusime - treba pres ukazatel2, ale to je jedno,
         stejne tak by se mohlo napsat dispose (ukazatel1)
         nebo dispose (ukazatel3), protoze rusime to, na co ten
         ukazatel ukazuje, ne ten ukazatel samotny, a vsechny tri
         ukazatele ukazuji na totez misto v pameti}
        dispose(ukazatel2);

        {a nakonec ukazatele nastavime na nil, aby neukazovaly
         na uvolnenou pamet}
        ukazatel1 := nil;
        ukazatel2 := nil;
        ukazatel3 := nil;

function pocetPrvku(var prvniPrvek: UkPrvek): Integer;
var
    pocet: Integer;
    aktualniPrvek:UkPrvek;
begin
    pocet := 0;
    aktualniPrvek := prvniPrvek;
    while (aktualniPrvek <> nil) do
    begin
        inc(pocet);
        aktualniPrvek := aktualniPrvek^.dalsi;
    end;
    pocetPrvku := pocet;
end;

function posledniHodnota(var prvniPrvek: UkPrvek): Integer;
var
    aktualniPrvek:UkPrvek;
begin
    aktualniPrvek := prvniPrvek;
    if aktualniPrvek = nil then
        posledniHodnota := 0
    else begin
        while (aktualniPrvek^.dalsi <> nil) do
            aktualniPrvek := aktualniPrvek^.dalsi;
        posledniHodnota := aktualniPrvek^.info;
    end;
end;

procedure odstranPosledni(var prvniPrvek: UkPrvek);
var
    predchudce, aktualni: UkPrvek;
begin
    if prvniPrvek = nil then exit;
    if prvniPrvek^.dalsi = nil then begin
        dispose(prvniPrvek);
        prvniPrvek := nil;
    end else begin
        aktualni := prvniPrvek;
        while aktualni^.dalsi <> nil do begin
            predchudce := aktualni;
            aktualni := aktualni^.dalsi;
        end;
        dispose (predchudce^.dalsi);
        predchudce^.dalsi := nil;
    end;
end;

function otocNedestruktivne(var prvniPrvek: UkPrvek): UkPrvek;
var
    aktualni, novy: UkPrvek;
    hodnota: Integer;
begin
    aktualni := prvniPrvek;
    novy := nil;
    while (aktualni <> nil) do begin
        hodnota := aktualni^.info;
        aktualni := aktualni^.dalsi;
        pridej(novy,hodnota);
    end;
    otocNedestruktivne := novy;
end;

procedure otocDestruktivne(var prvniPrvek: UkPrvek);
var
    {prvni z dvojice prvku, mezi kterymi se zmeni "smer sipky"}
    prvniProhazovany,
    {druhy z dvojice prvku, mezi kterymi se zmeni "smer sipky"}
    druhyProhazovany,
    {pomocny ukazatel na naslednika druheho prohazovaneho,
     abychom na nej neztratili odkaz}
    naslednikDruhehoProhazovaneho:
        UkPrvek;
begin
    if (prvniPrvek = nil) then
        exit;
    prvniProhazovany := prvniPrvek;
    druhyProhazovany := prvniPrvek^.dalsi;
    prvniProhazovany^.dalsi := nil;
    while (druhyProhazovany <> nil) do begin
        naslednikDruhehoProhazovaneho := druhyProhazovany^.dalsi;
        druhyProhazovany^.dalsi := prvniProhazovany;
        prvniProhazovany := druhyProhazovany;
        druhyProhazovany := naslednikDruhehoProhazovaneho;
    end;
    prvniPrvek := prvniProhazovany;
end;

Příklady z této podkapitoly řešte tak, že do následujícího souboru doplníte implementace zadaných funkcí. Rozhodně si ale tento zdrojový kód nejprve projděte a ujistěte se, že mu zcela rozumíte.

type
    UKprvek = ^Prvek;

    (*
     * Zakladni stavebni jednotka spojoveho seznamu.
     * Zapouzdruje: hodnotu jednoho prvku seznamu a ukazatel na dalsi prvek.
     *)
    prvek =
        record
            info: Integer;
            dalsi: UkPrvek;
        end;

    (*
     * Seznam je tvoren ukazatelem na svuj prvni a posledni prvek.
     *)
    Seznam =
        record
            zacatek: UKprvek;
            konec: UKprvek;
        end;


(*
 * Inicializace seznamu.
 * Prazdny seznam neobsahuje zadne prvky,
 * takze ukazatele na prvni a posledni prvek budou nil.
 *)
procedure init(var s: Seznam);
begin
    s.zacatek := nil;
    s.konec := nil;
end;

(*
 * Prida prvek na konec seznamu.
 * parametry:
 *     s - seznam, do nejz chceme prvek vlozit
 *     hodnota - vkladana hodnota
 *)
procedure pridejNaKonec(var s: Seznam; hodnota: Integer);
var
    novy: UkPrvek;
begin
    new (novy);
    novy^.info := hodnota;
    novy^.dalsi := nil;
    if (s.konec <> nil) then
        s.konec^.dalsi := novy;
    if (s.zacatek = nil) then
        s.zacatek := novy;
    s.konec := novy;
end;

(*
 * Na zacetek seznamu vlozi zadany prvek.
 *)
procedure pridejNaZacatek(var s: Seznam; var prvek: UkPrvek);
begin
    prvek^.dalsi := s.zacatek;
    s.zacatek := prvek;
    if (s.konec = nil) then
        s.konec := s.zacatek;
end;

(*
 * Na standardni vystup vypise vsechny prvky seznamu s od prvniho po posledni.
 *)
procedure vypisSeznam (var s:seznam);
var
    aktualni: UkPrvek;
begin
    aktualni := s.zacatek;
    while aktualni <> nil do begin
        write(' ', aktualni^.info);
        aktualni := aktualni^.dalsi;
    end;
end;

(*
 * Na konec seznamu pripoji usek z jineho seznamu.
 * parametry:
 *     kam - cilovy seznam (k nemu se bude pripojovat usek)
 *     zacatek - prvni prvek useku ve zdrojovem seznamu
 *     konec - prvni prvek ve zdrojovem seznamu, ktery jiz neni soucasti useku
 *             je-li nil, pak se kopiruji prvky az po konec zdrojoveho seznamu
 *)
procedure kopiruj(var kam: Seznam; zacatek, konec: UkPrvek);
var
    akt: UkPrvek;
begin
    akt := zacatek;
    while (akt <> konec) do begin
        pridejNaKonec(kam, akt^.info);
        akt := akt^.dalsi;
    end;
end;

(*
 * Smaze vsechny prvky seznamu s.
 *)
procedure zrus(var s: Seznam);
var
    akt, tmp: UkPrvek;
begin
    akt := s.zacatek;
    while (akt <> nil) do begin
        tmp := akt;
        akt := akt^.dalsi;
        dispose (tmp);
    end;
    s.zacatek := nil;
    s.konec := nil;
end;


var
    s, s_bez_kraju: Seznam;
begin
    init(s);
    pridejNaKonec(s, 8); pridejNaKonec(s, 5); pridejNaKonec(s, 7);
    pridejNaKonec(s, 6); pridejNaKonec(s, 13); pridejNaKonec(s, 7);
    pridejNaKonec(s, 21); pridejNaKonec(s, 1); pridejNaKonec(s, 4);
    vypisSeznam(s);
    writeln;

    init(s_bez_kraju);
    kopiruj(s_bez_kraju, s.zacatek^.dalsi, s.konec);
    vypisSeznam(s_bez_kraju);
    writeln;

    zrus(s);
    vypisSeznam(s);
    writeln;
    
    zrus(s_bez_kraju);
    vypisSeznam(s_bez_kraju);
    writeln;
end.

Základní myšlenka je jednoduchá. Procedura požívá dva ukazatele, akt1 a akt2. Dokud ukazatel akt2 není nil, platí, že ukazuje-li akt1 na k-tý prvek seznamu, pak akt2 ukazuje na 2k-tý prvek seznamu. Toho je docíleno tak, že na začátku ukazuje akt1 na první prvek seznamu a akt2 na druhý prvek seznamu. Pak se v každém kroku posuneme ukazatelem akt1 o jeden prvek vpřed, zatímco ukazatelem akt2 se posumene o dva prvky vpřed (jde-li to). Tento krok opakujeme tak dlouho, dokud není akt2 na konci seznamu, tj. dokud nemá hodnotu nil. Pak ukazatel akt1 ukazuje na prostřední prvek seznamu. Prvky od začátku seznamu až po prostřední prvek zkopírujeme do seznamu s1, zbylé prvky do seznamu s2.

procedure split(var s, s1, s2: Seznam);
var
    akt1, akt2: UkPrvek;
begin
    if (s.zacatek = nil) then exit;
    akt1 := s.zacatek;
    akt2 := s.zacatek^.dalsi;
    while akt2 <> nil do begin
        akt2 := akt2^.dalsi;
        if (akt2 <> nil) then begin
            akt2 := akt2^.dalsi;
            akt1 := akt1^.dalsi;
        end;
    end;
    kopiruj(s1, s.zacatek, akt1^.dalsi);
    kopiruj(s2, akt1^.dalsi, nil);
end;

Sjednocení uspořádaných seznamů s1 a s2 je uspořádaný seznam s takový, že množina všech jeho prvků je sjednocením množiny všech prvků prvního seznamu a všech prvků druhého seznamu. Destruktivním sjednocením se rozumí taková implementace, ve které se nikde neobjeví prikaz new, pouze se přepojují ukazatele. Naopak nedestruktivní je takové, které new hojně využívá, a co je důležité, sjednocované seznamy zůstanou nedotčeny. Destruktivní sjednocení by tedy mohlo vypadat třeba tak, že do prvního seznamu se vmíchají prvky z druhého seznamu. Druhý seznam bude tedy po provedení procedury prázdny, zatímco první bude obsahovat uspořádané sjednocení původnich seznamů.

procedure sjednoceni(var s1, s2, s: Seznam);
var
    {ukazatel na aktualni prvek s1}
    prvni,          
    {ukazatel na aktualni prvek s2}
    druhy: UkPrvek;  
begin
    prvni := s1.zacatek;
    druhy := s2.zacatek;
    if (prvni=nil) and (druhy=nil) then exit;

    while (prvni<>nil) and (druhy<>nil) do begin
        if prvni^.info <= druhy^.info then begin
            pridejNaKonec(S, prvni^.info);
            prvni := prvni^.dalsi;
        end else begin
            pridejNaKonec(S, druhy^.info);
            druhy := druhy^.dalsi;
        end;
    end;

    if prvni <> nil then kopiruj(S, prvni, nil);
    if druhy <> nil then kopiruj(S, druhy, nil);
end;

Když navrhujete jakoukoliv rekurzivní proceduru, je vhodné rozmyslet si tzv. kontrakt. To slovo znamená doslova závazek. Tedy, co daná procedura musí dělat a co nesmí dělat. V případě mergesortu by kontrakt mohl znít takto:Procedura bere odkazy na dva inicializované seznamy. Druhý z těchto seznamů musí být prázdný. Procedura do druhého seznamu uloží všechny prvky prvního seznamu vzestupne setříděně, první seznam nechá nezměněný.

Skoro každá rekurzivní procedura vypadá takto:

if (vstup_maly) then
    jednoduse_spocitej_vystup
else begin
    uprav_vstup;
    zavolej_se_rekurzivne;
    uprav_vystup;
end;

Je zde velmi úzká souvislost s principem důkazu matematickou indukcí. Ostatně, korektnost rekurzivních algoritmů se obvykle indukcí dokazuje. Kontrakt je vlastně tvrzení, které je třeba dokázat.

Toto je kostra mergesortu:

if ("nesetrideno" je jednoprvkovy nebo prazdny) then begin
    kopiruj "nesetrideno" do "setrideno";
end else begin
    vytvor pomocne seznamy s1, s2, s_s1 a s_s2;
    inicializuj je;
    rozdel "nesetrideno" na 2 casti, vysledek do s1 a s2;
    setrid rekurzivne s1, vysledek do s_s1;
    setrid rekurzivne s2, vysledek do s_s2;
    sjednot s_s1 a s_s2, vysledek do "setrideno";
    zrus pomocne seznamy;
end; 

Zkusme dokázat korektnost takto definované procedury.

Pro prázdný a jednoprvkový vstupní seznam procedura vrátí kopii vstupního seznamu a ta bude (triviálně) setříděná.

Nechť má seznam n prvků, kde n > 1. Rozdělíme-li seznam na dvě poloviny s1 a s2, pak sjednocení kolekcí prvků s1 a s2 bude rovno kolekci prvků vstupního seznamu. Pokud už víme, že procedura správně třídí seznamy délky kratší než n, rekurzivním zavoláním procedury dostaneme uspořádané seznamy s_s1 a s_s2 a sjednocení kolekcí jejich prvků bude opět rovno kolekci všech prvků vstupního seznamu. Slitím s_s1 a s_s2 dostaneme uspořádaný seznam. Kolekce jeho prvků bude rovna kolekci prvků vstupního seznamu. Algoritmus je tedy korektní.

Pro úplnost uveďme ještě kompletní zdrojový kód procedury mergesort.

procedure mergesort (var nesetrideno, setrideno: Seznam);
var
    s1, s2, s_s1, s_s2: Seznam;
begin
    if (nesetrideno.zacatek = nesetrideno.konec) then begin
        kopiruj(setrideno, nesetrideno.zacatek, nil);
    end else begin
        init(s1);
        init(s2);
        init(s_s1);
        init(s_s2);

        split(nesetrideno, s1, s2);
        mergesort(s1, s_s1);
        mergesort(s2, s_s2);
        sjednoceni(s_s1, s_s2, setrideno);

        zrus(s_s2);
        zrus(s_s1);
        zrus(s2);
        zrus(s1);
    end;
end;

(*
 * Provede destruktivni sjednoceni ponechavajici duplicitni klice.
 * parametry:
 *     s1 - ukazatel na zacatek prvniho seznamu a vysledneho sjednoceni
 *     s2 - ukazatel na zacatek druheho seznamu, po provedeni bude nil
 *)
procedure sjednoceni (var s1, s2: Seznam);
var
    {ukazatel na prvky prvniho seznamua jeho predchudce}
    akt1,pred,    
    {ukazatel na prvky druheho seznamu}
    akt2,       
    {pomocny ukazatel pri prepojovani} 
    pom: UkPrvek; 
begin
    akt1 := s1.zacatek;
    akt2 := s2.zacatek;
    if (akt1 = nil) and (akt2 = nil) then
        exit;
    if akt1 = nil then begin
        s1.zacatek := s2.zacatek;
        s1.konec := s2.konec;
        s2.zacatek := nil;
        s2.konec := nil;
        exit;
    end else if akt2 = nil then
        exit;

    while (akt1 <> nil) and (akt2 <> nil) do begin
    {seznamy jsou neprazdne}
        if akt1^.info <= akt2^.info then begin
            {mensi hodnota v s1}
            pred := akt1;
            akt1 := akt1^.dalsi;
        end else begin     
            {mensi hodnota v s2}               
            pom := akt2;
            akt2 := akt2^.dalsi; 
            s2.zacatek := akt2;

            if akt1 = s1.zacatek then begin
                {novy zacatek s1}
                pridejNaZacatek(s1, pom);
                pred := s1.zacatek;
            end else begin
                {vkladame mezi pred a akt1}
                pred^.dalsi := pom;
                pom^.dalsi := akt1;
                pred := pom;
            end;
        end;
    end;
    if akt1 = nil then begin       
        {pripojeni zbytku s2 => s2 musime vyprazdnit}                   
        pred^.dalsi:=akt2;
        akt1 := akt2;
        s1.konec := s2.konec;
        s2.konec := nil;
        s2.zacatek := s2.konec;
    end else
        s2.konec := akt2;
end;

Nyní byste již měli mít dostatek zkušeností, abyste si sami mohli implementovat jednoduchou knihovnu pracující s obousměrnými spojovými seznamy. Připomeňme, že obousměrný spojový seznam je seznam, ve kterém každý prvek obsahuje nejen ukazatel na následníka, ale i na předchůdce. Ukazatel na předchůdce prvního prvku má hodnotu nil, stejně tak ukazatel na následníka posledního prvku.

Tato sekce pojednává o ne příliš používané, zato u zkoušky se občas vyskytující datové struktuře - lineárním spojovém seznamu s hlavou.

Lineární spojový seznam s hlavou je, stejně jako základní varianta spojových seznamů, řetízek prvků, v němž každý prvek má dva atributy - hodnotu a ukazatel na další prvek. První prvek v tomto řetízku však nenese žádnou informaci, jeho hodnota může být libovolná. Reprezentuje-li seznam s hlavou posloupnost [a₁, a₂,... a_n], potom hodnoty prvků v řetízku jsou po řadě x, a₁, a₂,... a_n, kde x může být naprosto libovolné.

Pro spojové seznamy platí jeden velmi důležitý invariant: první prvek vždy existuje (tj. ukazatel na první prvek nemá nikdy hodnotu nil). A navíc, žádná operace nemusí první prvek nijak využívat ani měnit. Proto spousta algoritmů pracujících se seznamy s hlavou nemusí rozlišovat, zda pracuje s prázdným nebo neprázdným seznamem. A navíc, nemusí rozlišovat ani to, zda požadovaná operace ovlivní první prvek seznamu nebo jiný než první prvek seznamu.

Ukažme si dvě varianty přidávání hodnoty do uspořádaného lineárního spojového seznamu. První varianta algoritmu bude přidávat prvek do obyčejného uspořádaného seznamu, druhá varianta do uspořádaného seznamu s hlavou.

procedure pridejDoUsporadaneho(var seznam: UkPrvek; hodnota: Integer);
var
    aktualni, novy: UkPrvek;
begin
    new (novy);
    novy^.info := hodnota;

    {budeme pridavat na zacatek seznamu}
    if (seznam = nil) or (seznam^.info > hodnota) then begin
        novy^.dalsi := seznam;
        seznam := novy;

    {budeme pridavat jinam nez na zacatek seznamu}
    end else begin
        aktualni := seznam;
        while (aktualni^.dalsi <> nil) and (aktualni^.dalsi^.info < hodnota) do
            aktualni := aktualni^.dalsi;

        novy^.dalsi := aktualni^.dalsi;
        aktualni^.dalsi := novy;
    end;
end;

A nyní druhá varianta.

procedure pridejDoUsporadaneho(seznam: UkPrvek; hodnota: Integer);
var
    aktualni, novy: UkPrvek;
begin
    new (novy);
    novy^.info := hodnota;

    aktualni := seznam;
    while (aktualni^.dalsi <> nil) and (aktualni^.dalsi^.info < hodnota) do
        aktualni := aktualni^.dalsi;

    novy^.dalsi := aktualni^.dalsi;
    aktualni^.dalsi := novy;
end;

U druhé varianty jsme se nemuseli zabývat případem, kdy přidáváme prvek na začátek seznamu, a to z toho prostého důvodu, že na začátek seznamu prvek nikdy nepřidáváme. Na začátku seznamu se totiž vždy nachází hlava, jejíž hodnota nehraje žádnou roli (nevztahuje se na ni tedy pravidlo, že prvky seznamu jsou uspořádány). Hlava navíc vždy existuje, takže se nemusíme zabývat případem, kdy je seznam prázdný.

Obrázek 1.1. Reprezentace polynomu pomocí cyklického seznamu s hlavou.

Tato reprezentace se obzvlášť hodí pro řídké polynomy, tedy polynomy tvaru a₀ + a₁x +a₂x² ... + a_nxⁿ takové, že pro většinu m < n je a_m = 0. Reprezentace seznamem místo polem přinese efektivněkší využití paměti Díky kruhovému seznamu s hlavou zase snáze detekujeme konec polynomu. Nulový polynom nebudeme reprezentovat ukazatelem s hodnotou nil, nýbrž seznamem obsahujícím jediný prvek - hlavu.

Následuje několik příkladů, ve kterých bude vašim úkolem odhalit chybu v uvedeném zdrojovém kódu, případně najít protipříklad, na kterém uvedená procedura nebo funkce selže.

Procedura má datovou strukturu nastavit tak, aby reprezentovala prázdný spoják. Prázdný spoják = spoják bez žádných prvků = spoják, který nemá první ani poslední prvek = spoják, kde s.zac = nil a s.kon = nil. Tedy tělo procedury by mělo vypadat takto:

s.zac := nil;
s.kon := nil;

Procedura je chybná, neboť provádí chybnou dereferenci, a to na prvních dvou řádcích. Tak napřiklad u přikazu s.zac^.pred := nil je s.zac před provedením initu neinicializovaná, tj. míří na náhodné místo v paměti, takže dereference s.zac^.pred může způsobit zhroucení programu (ve FreePascalu se to tak stane takřka s jistotou, Borland Pascal si nechá líbit i chybnou dereferenci).

Pokud pomocí této procedury přidáváme prvek do prázdného seznamu, pak s.zac má hodnotu nil (za předpokladu, že se správně provede init, v opačném připadě nějakou náhodnou hodnotu), takže dereference s.zac^.pred := novy v proceduře pridejNaZacatek je chybná.

Protipříkladem může být třeba řetězec HAHHAHA a hledaný podřetězec HAHA. Funkce srovnává řetězec a podřetězec znak po znaku. Jakmile zjistí, že se v nějakém znaku liší, vrátí se v podřetězci na první znak a v řetězci poskočí o znak vpřed. Jak se bude funkce chovat u našeho protipříkladu? Srovná první znak řetězce a první znak podřetězce. Rovnají se, takže přejde u řetězce i podřetězce na druhý znak. Ty se taktéž rovnají. Přechází tedy na třetí znaky, i ty se rovnají. Ve čtvrtém znaku se však řetězec a podřetězec liší (v řetězci je čtvrtým znakem H, zatímco v podřetězci A). Proto se algoritmus posune v podřetězci na první znak a v řetězci na následující (tj. pátý znak) a začne zjišťovat, zda se podřetězec HAHA nenachází někde za pátým znakem v řetězci HAHHAHA . To je ale kámen úrazu, neboť jak je vidět, podřetězec HAHA se v řetězci HAHHAHA nachází již za čtvrtým znakem, takže funkce podřetězec v řetězci už nikdy neobjeví.

Nechť je řetězec XYXYXW a hledaný podřetězec XYXW. Zde nám nepomůže se po zjištění, že se čtvrté znaky liší, v řetězci neposunout na pátý znak a zůstat na čtvrtém, neboť podřetězec XYXW začíná na třetím znaku řetězce XYXYXW.

První chyba je v podmínce cyklu:

while (aktualni^.info = aktualni_vpodret^.info)
          and (aktualni <> nil) do begin

Tady autor (správně) předpokládá, že aktualni může mít hodnotu nil (například tehdy, když uživatel zadá prázdný řetězec). Potom však výraz aktualni^.info způsobí chybnou dereferenci!

Navíc, může se tady stát i to, že aktualni_vpodret bude mít hodnotu nil (například tehdy, když uživatel zadá prázdný podřetězec). A pak pro změnu výraz aktualni_vpodret^.info způsobí chybnou dereferenci.

Jak to opravit? Pokud vám něco říká termín „neúplné vyhodnocování logického výrazu“, pak by to pro vás měla být hračka (v Borland Pascalu i Free Pascalu by mělo být implicitně zapnuté). Kdyby ne, prostě mi napište, vysvětlím, o co jde.

Tento příklad testuje, jak se dokážete poučit z rad uvedených v této knížce. Před tímto příkladem se píše, že největší problém při testu správnosti procedury je umět odhalit, ověřit a otestovat okrajové podmínky. Zde mám konkrétně na mysli případ, kdy se odstraňovaný prvek nachází hned na začátku nebo na konci spojového seznamu. Pokud se odstraňovaný prvek nachází na začátku seznamu, pak příkaz aktualni^.pred^.nasl na řádku 26 způsobí chybnou dereferenci (neboť prvek, na nějž ukazuje ukazatel aktualni je prvním prvkem seznamu a nemá tedy předchůdce, tj. aktualni^.pred má hodnotu nil). Pokud se odstraňovaný prvek nachází na konci seznamu, dojde k obdobné situaci, a to sice na řádku 27.

První příkaz alokuje blok paměti a adresu tohoto bloku uloží do proměnné uzel. Druhý příkaz hodnotu této proměnné nastaví na nil. Tím ztratíme odkaz na alokovaný blok paměti, takže jej už nikdy nebudeme moci použít. Nepůjde jej ani odalokovat pomocí dispose. Blok bude v paměi pouze zabírat místo, dokud náš program neskončí. Nejen, že je první příkaz zbytečný, ale po provedení této dvojice příkazů zůstane v paměti smetí.

Nikoliv. Podívejme se na řádky 11 až 13. Nechť seznam obsahuje jediný prvek a ten prvek má hodnotu 6. Nechť chceme z tohoto seznamu vymazat všechny prvky s hodnotou 2. Potom

pred := PrvniPrvek;              {pred bude ukazovat na prvek s hodnotou 6}
aktualni := prvniPrvek^.dalsi;   {aktualni bude ukazovat na nil}
while (aktualni^.info <> krit)   {...a tady to sebou rízne - dereference nil}

Navíc je procedura zbytečně složitá. Posloupnost příkazů na řádcích 11 až 19 by se totiž dala nahradit jedním jediným rekurzivním voláním. Zkuste přijít na to, jak bude toto volání vypadat.

Příklady z této kapitoly řešte tak, že do následujícího zdrojového kódu doplníte implementace zadaných procedur. V této kostře je implementovaná i procedura, která strom vykreslí, aby se to dalo dobře ladit (odflákl jsem ji, není napsaná moc elegantně, tj. není to příklad hodný následování).

const
    {pocet radek platna}
    ROWS = 20;
    {pocet znaku na radku platna}
    COLUMNS = 80;


type
    {ukazatel na uzel stromu}
    UKUzel = ^Uzel;
    
    {usel stromu obsahuje zapouzdrenou hodnotu a ukazatele na prave a leve dite}
    Uzel =
        record
            info: Integer;
            left: UKUzel;
            right: UKUzel;
        end;

    {vyuzivano pri vykreslovani stromu}
    TPlatno = array[1..ROWS, 1..COLUMNS] of char;

(*
 * Vlozi do stromu novy prvek.
 * parametry:
 *     koren - ukazatel na koren stromu
 *     hodnota - hodnota, ktera se ma do stromu vlozit
 *)
procedure vloz(var koren: UKUzel; hodnota: Integer);
begin
    if (koren = nil) then begin
        new (koren);
        koren^.info := hodnota;
        koren^.left := nil;
        koren^.right := nil;
    end else if (hodnota < koren^.info) then begin
        vloz(koren^.left, hodnota);
    end else if (hodnota > koren^.info) then begin
        vloz(koren^.right, hodnota);
    end;
end;


(*
 * Pomocna procedura, do platna zakresli na zadanou pozici schematicky strom.
 * parametry:
 *     koren - koren vykreslovaneho stromu
 *     platno - platno, na nejz se bude kreslit
 *     radek - radek platna, na nejz se zakresli koren;
 *             ostatni casti stromu se zakresli niz
 *     zacatek - index nejlevejsiho sloupce platna, kam muze byt zakreslen strom
 *     sirka - maximalni pocet sloupcu,
 *             ktere muze vykresleny strom na platne zabirat
 *)
procedure nakresli(
    var koren: UKUzel; var platno: TPlatno; radek, zacatek, sirka: Integer);
var
    i: Integer;
    novaSirka, novyZacatek, novyProstredek, prostredek: Integer;
begin
    prostredek := zacatek + sirka div 2 + 1;
    platno[radek, prostredek - 1] := chr(ord('0') + koren^.info div 100);
    platno[radek, prostredek] := chr(ord('0') + (koren^.info mod 100) div 10);
    platno[radek, prostredek + 1] := chr( ord('0') + koren^.info mod 10);
    novaSirka := sirka div 2;
    if (koren^.left <> nil) then begin
        novyZacatek := zacatek;
        novyProstredek := novyZacatek + novaSirka div 2 + 1;
        for i := novyProstredek to prostredek do platno[radek + 1, i] := '-';
        platno[radek + 2, novyProstredek] := '|';
        nakresli(koren^.left, platno, radek + 3, novyZacatek, novaSirka)
    end;
    if (koren^.right <> nil) then begin
        novyZacatek := zacatek + novaSirka;
        novyProstredek := novyZacatek + novaSirka div 2 + 1;
        for i := prostredek to novyProstredek do platno[radek + 1, i] := '-';
        platno[radek + 2, novyProstredek] := '|';
        nakresli(koren^.right, platno, radek + 3, novyZacatek, novaSirka)
    end;
end;


(*
 * Schematicky nakresli strom, kresli na standardni vystup.
 * parametry:
 *     koren - ukazatel na koren vykreslovaneho stromu
 *)
procedure nakresliStrom(var koren: UKUzel);
var
    platno: TPlatno;
    i, j: Integer;
begin
    for i := 1 to ROWS do begin
        for j := 1 to COLUMNS do begin
            platno[i, j] := ' ';
        end;
    end;
    nakresli(koren, platno, 1, 0, COLUMNS);
    for i := 1 to ROWS do begin
        for j := 1 to COLUMNS do begin
            write(platno[i, j]);
        end;
        writeln;
    end;
end;


var
    strom: UKUzel;
begin
    strom := nil;
    vloz(strom, 50);

    vloz(strom, 25);
    vloz(strom, 75);

    vloz(strom, 12);
    vloz(strom, 30);
    vloz(strom, 60);
    vloz(strom, 80);

    vloz(strom, 11);
    vloz(strom, 13);
    vloz(strom, 26);
    vloz(strom, 32);

    vloz(strom, 51);
    vloz(strom, 61);
    vloz(strom, 79);
    vloz(strom, 81);

    nakresliStrom(strom);
    
end.

Ukážeme si například pravou rotaci. Levá rotace by se provedla analogicky, lze též napsat obecnější funkci, které se směr předá jako parametr (Kryl ukazoval na přednášce).

procedure rotujDoprava(var koren: UkUzel);
var
    {novy koren}
    Nkoren: UkUzel;
begin
    if koren = nil or koren^.left = nil then
        exit;
    Nkoren := koren^.left;
    koren^.left := Nkoren^.right;
    Nkoren^.right := koren;
    koren := Nkoren;
end;

function jeTam(var koren: UkUzel; hodnota:Integer): boolean;
begin
    if koren = nil then begin
        jeTam := false;
    end else if koren^.info > hodnota then begin
        jeTam := jeTam(koren^.left, hodnota);
    end else if koren^.info < hodnota then begin
        jeTam := jeTam(koren^.right, hodnota);
    end else begin
        jeTam := true;
    end;
end;

procedure vypisPrvkyVzestupne (var koren: UkUzel);
begin if koren <> nil then begin 
    vypisPrvkyVzestupne(koren^.left);
    write(' ', koren^.info);
    vypisPrvkyVzestupne(koren^.right);
    end; 
end;

Zkuste nejprve sami přijít na nějaké řešení. Teprve kdybyste dlouhou dobu na nic nepřicházeli, podívejte se na toto řešení. Obrázky po zdrojovým kódem ilustrují vkládání hodnoty 15 do kořene stromu, v jehož kořeni je momentálně hodnota 20.

procedure vlozDoKorene(var koren: UkUzel; hodnota: Integer);
begin
    if koren = nil then
        vloz(koren, hodnota)
    else if hodnota < koren^.info then begin
        vlozDoKorene(koren^.left, hodnota);
        rotujDoprava(koren);
    end else if hodnota > koren^.infobegin
        vlozDoKorene(koren^.right, hodnota);
        rotujDoleva(koren);
    end;
end;

Obrázek 2.1. Před rekurzivním vložením čísla 15

Obrázek 2.2. Po rekurzivním vložení čísla 15

Obrázek 2.3. Po pravé rotaci kořeme

function odeberNejpravejsi(var koren: UkUzel): Integer;
var
    tmp: UkUzel;
begin
    if (koren^.right <> nil) then begin
        {existuji prvky vpravo od korene ==> rekurzivne volame na pravy podstrom}
        odeberNejpravejsi := odeberNejpravejsi(koren^.right);
    end else begin
        {vpravo od korene se uz zadny prvek nenachazi, proto vypustime koren}
        tmp := koren;
        koren := koren^.left;
        odeberNejpravejsi := tmp^.info;
        dispose (tmp);
    end;
end;

Všimněte si použití parametrů předávaných referencí. To, že je procedura takto napsaná, nám umožní ji zavolat například takto: odeberNejpravejsi(uzel^.left). Ani v případě, že by nejpravějším prvem v levém podstromě uzlu uzel byl přímo prvek, na nějž ukazuje ukazatel uzel^.left, se volající nemusí starat o aktualizaci ukazatele uzel^.left, to zařídí přímo procedura odeberNejpravejsi.

procedure odstranKoren(var koren: UkUzel);
var
    tmp: UkUzel;
begin
    if (koren^.left = nil) and (koren^.right = nil) then begin
        {koren nema deti}
        dispose (koren);
        koren := nil;
    end else if (koren^.right = nil) then begin
        {koren ma jen leveho syna, ten se stane novym korenem}
        tmp := koren;
        koren := koren^.left;
        dispose (tmp);
    end else if (koren^.left = nil) then begin
        {koren ma jen praveho syna, ten se stane novym korenem}
        tmp := koren;
        koren := koren^.right;
        dispose (tmp);
    end else begin
        {koren ma dve deti, hodnotu korene nahradime jeho naslednikem
         v in-order usporadani a naslednika vypustime}
        koren^.info := odeberNejpravejsi(koren^.left);
    end;
end;

procedure odstran(var koren: UkUzel; hodnota: Integer);
begin
    {pokud takova hodnota ve strome neni, pozadavek ignorujeme}
    if (koren = nil) then
        exit;
    
    {hondta je v koreni, vyuzijeme jiz existujici proceduru}
    if (hodnota = koren^.info) then begin
        odstranKoren(koren);
    {hodnota v levem podstrome, rekurzivne volame na levy podstrom}
    end else if (hodnota < koren^.info) then begin
        odstran(koren^.left, hodnota);
    {hodnota v pravem podstrome, rekurzivne volame na pravy podstrom}
    end else if (hodnota > koren^.info) then begin
        odstran(koren^.right, hodnota);
    end;
end;

V Absurdistánu jsou řádově desítky tisíc měst. Mezi dvěma městy může vést libovolný počet přímých silnic. Všechny silnice jsou šotolinové. Konaly se volby, které vyhrála strana A, která slíbila vyasfaltovat všechny silnice. Načež strana B se rozhodla, že jí úkol ztíží, a prosadila následující legislativní úpravu:

Vládní strana A proto zadala softwarové firmě, aby problém vyřešila. SW firma jste vy. Pro která vstupní data má úloha řešení? Jde-li to, vytvořte harmonogram prací.

Nabízí se použití grafů. Vrcholy grafu budou města, hranami pak přímé silnice vedoucí mezi dvěma městy. Jediná potíž je v tom, že mezi dvěma městy může vést více než jedna přímá silnice. V grafu se pak mezi dvěma vrcholy může objevit více než jedna hrana. I s takovým grafem se dá pracovat. Odborně se mu říká multigraf.

Zkusme otázku přeformulovat. Stačí nám umět řešit tuto úlohy pro souvislé grafy, abychom ji jednoduše vyřešili i pro nesouvislé grafy? Odpověď zni ano. Uvědomte si totiž jednoduchou vlastnost: graf lze vyasfaltovat, právě když lze vyasfaltovat každou jeho komponentu souvislosti. Důkaz je triviální. Pokud umíme vyasfaltovat celý graf, pak snadno vyasfaltujeme i každou jeho komponentu souvislosti. Naopak, jestliže umíme vyasfaltovat každou komponentu souvislosti, vyasfaltujeme celý graf komponentu po komponentě.

Proto nás stačí, když umíme úlohu vyřešit jen pro souvislé grafy. Nesouvislý graf vyasfaltujeme tak, že algoritmus asfaltování rekurzivně pustíme na všechny komponenty souvislosti.

Z pravidel uvedených v legislativní úpravě plyně, že každý den lze vyasfaltovat právě dvě nevyasfaltované silnice. Celkový počet asfaltovaných silnic tedy musí být sudé číslo. Kdyby měl graf lichý počet hran, pak by jej určitě nebylo možné vyasfaltovat. A co víc, v předchozím úkolu jsme si řekli, že graf je vyasfaltovatelný, právě když je každá jeho komponenta souvislosti vyasfaltovatelná. Obecná charakteristika grafů, které nelze vyasfaltovat, by tedy mohla znít třeba takto: „Graf nelze vyasfaltovat, jestliže některá z jeho komponent souvislosti má lichý počet hran.“

Obvykle se v důkazech podobných tvrzení postupuje tak, že se nejprve problém rozdělí na několik možných případů. A rozumné bývá rozlišit dva případy:

Toho se budeme držet i v našem případě.

Dále, uvědomte si, že tvrzení se nám bude krásně dokazovat pomocí matematické indukce. Je-li totiž dán souvislý graf se sudým počtem hran, pak se můžeme pokusit z něj dvě na sebe navazující hrany odtrhnout (tj. označit za vyasfaltované) a dostaneme opět graf se sudým počtem hran. Jen se při odebrání těchto dvou hran graf nesmí rozpadnout na více komponent, z nichž aspoň jedna by měla lichý počet hran.

Strom má sudý nenulový počet hran, má tedy aspoň dvě hrany. Z toho plyne, že musí mít aspoň tři vrcholy. A známé trvrzení říká, že každý strom s alepoň dvěma vrcholy má alespoň dva listy. Ve stromě tedy musí existovat list.

Označme libovolný list stromu písmenem v. Označme jeho bezprostředního souseda písmenem w. Označme k₁, k₂,... k_n komponenty, na které by se graf rozpadl, kdybychom odstranili vrchol w. Nechť bez újmy na obecnosti je k₁ komponenta, kterou tvoří jediný vrchol, a to vrchol v. Kdyby měly všechny komponenty k₂,... k_n lichý počet hran, pak by měl i celý graf lichý počet hran (pokud ke každé z těchto komponent přidáme i hranu, která ji spojuje s vrcholem w, bude mít každá z těchto komponent sudý počet hran, a protože v grafu se nachází ještě hrana (v, w), bude mít graf celkově lichý počet hran). Proto aspoň jedna z komponent k₂,... k_n má sudý počet hran, nechť je to bez újmy na obecnosti k₂. Odstraňme z grafu hranu (v, w) a hranu spojující vrchol w s komponentou k₂. Tím jsme odstranili dvě na sebe navazující hrany, aniž by se nám graf rozpadl na více komponent, z nichž by některá měla lichý počet hran.

Obrázek 3.1. Odtrhávání dvojice hran ze stromu