Předchozí strana Obsah Další strana

6. DYNAMICKÉ DATOVÉ STRUKTURY


  1. Dynamické datové struktury a dynamické proměnné
  2. Datový typ Ukazatel
  3. Zásobník
  4. Fronta
  5. Seznam
  6. Stromy
  7. Třídění
    1. Bubble Sort
    2. Shaker Sort
    3. Insert Sort
    4. Select Sort
    5. Shell Sort
    6. Quick Sort
    7. Heap Sort
    8. Radix Sort
    9. Merge Sort
  8. Vyhledávání
    1. Vyhledávání v nesetříděné posloupnosti
    2. Vyhledávání v setříděné posloupnosti

6.1. DYNAMICKÉ DATOVÉ STRUKTURY A DYNAMICKÉ PROMĚNNÉ

Doposud jsme v předcházejících kapitolách pracovali s takovými strukturami, které během vykonávání programu nemění svůj rozsah. Například pole nemění svůj rozsah; velikost, která se uvádí při deklaraci proměnných, je stálá v celém programu a nedá se změnit. Také datová struktura záznam nemění během vykonávání programu svůj rozsah, který nadeklarujeme v části deklarace typů. Takovýmto strukturám říkáme statické datové struktury. Opakem těchto struktur jsou dynamické datové struktury, což jsou takové struktury, jejichž rozsah se může během vykonávání programu měnit. Představme si ze života takovou obyčejnou frontu nakupujících u pokladny v marketu. Náš běžící program je proces placení nakupujících. Během tohoto procesu fronta nakupujících ubývá (nakupující platí rychleji než další přicházejí k pokladně), nebo fronta narůstá (nakupující přicházejí k pokladně ve větším počtu něž kolik je jich u pokladny obslouženo), nebo fronta zůstává stejné délky (přichází k pokladně stejný počet nakupujících a stejný počet ve stejnou dobu zaplatí). Takto dynamicky se délka fronty mění během provádění procesu placení a takto si tedy můžeme představovat dynamickou datovou strukturu.

Nejen fronta se používá jako dynamická datová struktura, v jazyku Pascal se používají také zásobníky, seznamy a stromy (a možná i další).

Statické proměnné se v každém programu zavádějí deklarací, mají svá jména (identifikátory) a jsou statické ve smyslu statické datové struktury, jak jsme si ji uvedli výše. Naproti tomu stojí dynamické proměnné. Tyto se nezavádějí v programu deklarací, ale vzniknou v průběhu programu pomocí speciálního příkazu. Vzhledem k tomu, že dynamické proměnné se nezavádějí v programu deklarací, nemají také své jméno - identifikátor. K tomu, abychom se k těmto proměnným nějakým způsobem dostali, slouží nový datový typ Ukazatel, který ukazuje na proměnnou, uloženou v operační paměti.

 

6.2. DATOVÝ TYP UKAZATEL

Datový typ Ukazatel je základním stavebním kamenem dynamických datových struktur. Pomocí tohoto typu se konstruují další dynamické struktury.

Od standardních datových typů, které jsme si uváděli v kapitole 3. DATOVÉ TYPY, se liší hned v několika směrech. Jeden z rysů odlišnosti je ten, že se tento datový typ nezavádí deklarací v deklarační části programu, ale pomocí speciálního příkazu v těle programu. Další, podstatnou změnou oproti ostatním datovým typům je ten fakt, že ukazatel v sobě neuchovává konkrétní hodnotu nějakého prvku, ale uchovává v sobě adresu prvku v operační paměti počítače. Adresa, kterou ukazatel obsahuje, může ukazovat do libovolné části operační paměti.

Typ ukazatel není pouze jeden jediný, existují různé typy ukazatele, vždy podle datového typu dynamické proměnné, na kterou ukazatel ukazuje. Každý nový ukazatel tedy slouží jedné dynamické proměnné. Na příkladu si to ukážeme názorněji:

 type  
     veta = string[100];                      (1)
     ukazatelvety = ^veta;                  (2)
  
 var  
     V1, V2 : ukazatelvety;                 (3)

Na řádku s indexem (1) definujeme nový typ veta, což je řetězec s délkou 100 znaků. Na řádku s indexem (2) definujeme ukazatel na datový typ veta. Na řádku s indexem (3) pak deklarujeme proměnnou V1, která je datového typu ukazatel na datový typ veta, tzn. hodnotou této proměnné je pouze adresa na místo v operační paměti počítače, kde je uložena dynamická proměnná veta. Po této deklaraci nemá proměnná V1 ještě žádnou definovanou hodnotu.

Abychom mohli s proměnnou typu ukazatel v programu pracovat, musíme jí přidělit určitou část volné paměti a adresu na tuto část paměti uložit do proměnné typu ukazatel, tedy vzhledem k předchozímu příkladu, do proměnné V1. Toto provádíme pomocí procedury New:

 New(V1); 

Tímto příkazem se tedy vytvoří v paměti dynamická proměnná typu veta s nedefinovanou hodnotou a ukazatel (adresa) se uloží do proměnné V1.

Této proceduře podobná procedura GetMem provádí stejnou činnost jako New, pouze s tím rozdílem, že pomocí GetMem můžeme vyhradit místo v paměti o konkrétní velikosti, která nám bude dostačovat k naší práci:

GetMem(V1, 128);
GetMem(V1, length(V1) + 1

Příkladem může být uložení proměnné typu string, označme ji např. PR. Pokud na tuto proměnnou použijeme proceduru New, ta nám vyhradí místo v paměti o velikosti, která je deklarovaná pro typ string, tedy 256 byte. My ale použijeme proměnnou PR, do které uložíme např. slovo AUTOMOBIL. Využijeme tedy pouze 9 znaků a zbytek proměnné zůstane nevyužit. V tomto případě je vhodné použít místo procedury New proceduru GetMem, které můžeme přímo nařídit, kolik místa v paměti má pro novou proměnnou vyhradit. A kolik toho místa tedy má vyhradit, to můžeme proceduře GetMem říci např. udáním délky proměnné PR: length(PR) + 1. (Jedničku přičítáme kvůli nultému byte řetězce.)

Pokud chceme do dynamické proměnné něco uložit (což určitě chceme, na co by nám taková proměnná byla, kdybychom do ní nechtěli či nemohli nic uložit, že?), musíme k ní přes proměnnou typu ukazatel přistoupit. Toto se provádí pomocí operátoru nepřímé adresace ^. Tento operátor použijeme zároveň s příkazem přiřazení := :

 V1^ := 'Psat diplomovou praci je dosti narocne.'

Pomocí operátoru ^ přistoupíme přes proměnnou V1 typu ukazatel do dynamické proměnné v operační paměti, do které uložíme větu v apostrofech. Do jedné proměnné typu ukazatel můžeme také uložit hodnotu z jiné proměnné typu ukazatel. To se provede pouze příkazem přiřazení :

 V1 := V2

Takto se do proměnné V2 uloží adresa na tutéž proměnnou typu veta, na kterou již ukazuje proměnná V1 a která již obsahuje větu "Psat diplomovou praci je dosti narocne". Graficky to můžeme znázornit asi takto:

 ukazat1.gif (1791 bytes)

Pokud použijeme proceduru New nejen na proměnnou V1, ale také na proměnnou V2, můžeme příkaz přiřazení také provést mezi samotnými dynamickými proměnnými. Provedeme-li tuto sekvenci příkazů:

 New(V1); 
 New(V2); 
 V1^ := 'Psat diplomovou praci je dosti narocne'; 
 V2^ := V1^; 

potom graficky toto můžeme znázornit takto:

ukazat2.gif (2549 bytes)

Ke zrušení dynamické proměnné slouží procedury Dispose (nebo FreeMem):

 Dispose(V2); 

Tímto příkazem tedy uvolníme z paměti dynamickou proměnnou typu veta a smažeme ukazatel z proměnné V2.

Opakem procedury GetMem je procedura FreeMem, která, stejně jako Dispose, uvolňuje z paměti dynamickou proměnnou dané velikosti a smaže ukazatel na proměnnou:

FreeMem(V1, 128);
FreeMem(V1, length(V1) + 1

Proměnné typu ukazatel lze přiřadit také speciální hodnotu, která říká, že ukazatel nikam neukazuje, je to prázdný ukazatel, který neidentifikuje žádnou dynamickou proměnnou. Označujeme ho klíčovým slovem NIL.

 

6.3. ZÁSOBNÍK

zasobn1.gif (654 bytes)Zásobníkem rozumíme takovou dynamickou datovou strukturu, z níž se prvky vybírají v opačném pořadí než v jakém se do ní vkládají (takovým nejbližším přirovnáním může být obyčejná studna). Vybíráme tedy vždy poslední vložený prvek (podle toho se zásobníky také nazývají struktury LIFO - z anglického Last-In-First-Out). Pro zásobník můžeme definovat tyto základní operace:

Zásobník můžeme v Pascalu implementovat (vytvořit) buď pomocí pole, tedy jako statickou datovou strukturu, nebo pomocí ukazatele, tedy jako dynamickou datovou strukturu.

Implementace pomocí pole:

Při této implementaci jsme nuceni omezit maximální velikost zásobníku a překročení této velikosti musíme v programu ošetřit. Také musíme ošetřit opačný stav, kdy chceme ze zásobníku prvek odebrat, ale zásobník je již prázdný. Uvedeme si výpis programu se základními operacemi, obě výše popsané ošetření označím ve výpisu červeně:

 const Maxdelka = N;    {N je číslo omezující maximální délka zásobníku} 
  
 var zasobnik : array[1..Maxdelka] of datovytyp
          vrchol : 1..Maxdelka
  
 procedure Vytvor
 begin 
     vrchol := 0; 
 end
  
 procedure Vloz(X: datovytyp); 
 begin 
     if vrchol = Maxdelka then 
       begin          {ošetření překročení maximální velikosti}
         write('Pozor - zasobnik je plny.'); 
         Halt
       end
     else 
       begin 
         vrchol := vrchol + 1; 
         zasobnik[vrchol] := X
       end
 end
  
 procedure Odeber(var X: datovytyp); 
 begin 
     if vrchol = 0 then 
       begin         {ošetření prázdnosti zásobníku}
         write('Pozor - zasobnik je prazdny.'); 
         Halt
       end
     else 
       begin 
         X := zasobnik[vrchol]; 
         vrchol := vrchol - 1; 
       end
 end
  
 function Jeprazdny: boolean
 begin 
     if vrchol = 0 then Jeprazdny := true
     else Jeprazdny := false
 end

Implementace pomocí ukazatele:

Pokud budeme chtít implementovat zásobník pomocí ukazatele, nemusíme řešit maximální velikost zásobníku. Ta je dána velikostí operační paměti. Ta však také není nekonečná, proto je dobré dávat pozor na zápis procedur, které se zásobníkem budou pracovat a vkládat do něj prvky. Pokud se stane, že se procedura vkládání zacyklí, zásobník přeteče a program zhavaruje. Chyba může být nepatrná a tím více těžko odhalitelná. Výpis programu je následující (červený text opět označuje ošetření výběru prvku z prázdného zásobníku):

 type spoj = ^element 
        element = record 
                              hodnota: datovytyp
                              dalsi: spoj
                           end
 var zasobnik : spoj
  
 procedure Vytvor
 begin 
     zasobnik := nil
 end
  
 procedure Vloz(X: datovytyp); 
 var pom: spoj
 begin 
     new(pom); 
     with pom^ do  
       begin 
         hodnota := X
         dalsi := zasobnik
       end
     zasobnik := pom
 end
  
 procedure Odeber(var X: datovytyp); 
 var pom: spoj
 begin 
     if zasobnik = nil then 
       begin 
         write('Pozor - zasobnik je prazdny.'); 
         Halt
       end
     else 
       begin 
         X := zasobnik^.hodnota
         pom := zasobnik
         zasobnik := zasobnik^.dalsi
         dispose(pom); 
       end
 end
  
 function Jeprazdny: boolean
 begin 
     if zasobnik = nil then Jeprazdny := true
     else Jeprazdny := false
 end

 

6.4. FRONTA

fronta1.gif (1259 bytes)Fronta je dynamická datová struktura podobná zásobníku, rozdíl je pouze v tom, že prvky se z fronty odebírají v tom pořadí, v jakém se do fronty vkládají. Jako příklad si můžeme představit frontu nakupujících v obchodě. Podle toho se datový typ fronta také nazývá struktura FIFO - z anglického First-In-First-Out. Pro frontu můžeme definovat tyto operace:

Frontu stejně jako zásobník můžeme v Turbo Pascalu implementovat buď pomocí pole, nebo pomocí ukazatele.

Implementace pomocí pole:

Při této implementaci musíme neustále vědět, kde fronta začíná, kde končí a kolik má prvků. Také co se týče velikosti, musíme omezit maximální velikost fronty a překročení této velikosti musíme ošetřit.

Pokud budeme vkládat prvky do prázdné fronty, bude situace vypadat následovně:

fronta2.gif (1218 bytes)

Vidíme, že do fronty byly postupně vloženy hodnoty af. Pokud budeme s frontou pracovat tak, že staré prvky z ní budeme podle potřeby vybírat, nové do ní budeme vkládat, zjistíme, že pro nové vložení nám nemusí zbýt políčko ve frontě, zatímco po odebraných prvcích ze začátku fronty nám zbývají volná a nevyužitá políčka. Situace může tedy vypadat např. takto:

fronta3.gif (1418 bytes)

Takovýto problém můžeme vyřešit např. tím, že po každém výběru prvku ze začátku fronty můžeme celou frontu přesypat na začátek, neboli všechny prvky budeme přesunovat o jedno místo dopředu. Jednodušším řešením, které můžeme přirovnat k předchozímu řešení, je použití tzv. kruhové fronty. Za následníka posledního prvku považujeme u takovéto kruhové fronty první prvek. Tuto představu nám osvětlí následující obrázek:

fronta4.gif (2104 bytes)

Jak je vidět z obrázku, prvním prvkem je zde prvek s indexem 0 a poslední prvek má index N-1 vzhledem k tomu, že přidávání a odebírání prvků do a z fronty, resp. výpočet indexu prvku, budeme realizovat pomocí operace modulo N. V následujícím výpisu v Pascalu jsou realizovány procedury vytvoření prázdné fronty, přidání prvku do fronty, odebrání prvku z fronty a funkce testování prázdnosti fronty. Ošetření překročení maximální velikosti fronty a ošetření odebrání prvků z prázdné fronty je opět ve výpisu označeno červeně:

  const MaxDelka = N;    {N je číslo omezující délku fronty} 
             MaxIndex = N-1; 
  
 var fronta: array[1..MaxDelka] of datovytyp
       zacatek, konec: MaxIndex
       delka: MaxDelka;  
  
 procedure Vytvor
 begin 
     zacatek := 0; 
     konec := 0; 
     delka := 0; 
 end
  
 procedure Vloz(X: datovytyp); 
 begin 
     if delka = MaxDelka then 
       begin    {ošetření překročení maximální velikosti} 
         write('Pozor - fronta je plna.'); 
         Halt
       end
     else 
       begin 
         fronta[konec] := X
         konec := (konec + 1) mod MaxDelka
         delka := delka + 1; 
       end
 end
  
 procedure Odeber(var X: datovytyp); 
 begin 
     if delka = 0 then 
       begin    {ošetření prázdnosti fronty} 
         write('Pozor - fronta je prazdna.'); 
         Halt
       end
     else 
       begin 
         X := fronta[zacatek]; 
         zacatek := (zacatek + 1) mod MaxDelka
         delka := delka - 1; 
       end
 end
  
 function JePrazdna: boolean
 begin 
     if delka = 0 then JePrazdna := true 
     else JePrazdna := false
 end

Implementace pomocí ukazatele:

Pokud budeme řešit realizaci fronty pomocí ukazatele, opět, stejně jako u zásobníku, kontrola maximální velikosti fronty odpadá a maximální velikost fronty je dána velikosti dostupné paměti, ve které je fronta dynamicky vytvořena. Opět, pokud budeme programovat procedury a funkce, pracující s dynamickou frontou, musíme dávat velký důraz na správnou funkčnost procedur a funkcí. Zacyklená procedura vkládání nám může zhavarovat celý program a chyba bude těžko odhalitelná. Následuje výpis kódu.V proceduře Odeber je použita pomocná proměnná pom typu spoj, kterou využijeme k odstranění prvního prvku fronty.

 type spoj = ^element
          element = record 
                    hodnota: datovytyp
                    dalsi: spoj
              end
  
 var zacatek, konec: spoj
  
 procedure Vytvor
 begin 
     new(zacatek); 
     konec := zacatek
 end
  
 procedure Vloz(X: datovytyp); 
 begin 
     konec^.hodnota := X
     new(konec^.dalsi); 
     konec := konec^.dalsi
 end
  
 procedure Odeber(var X: datovytyp); 
 var pom: spoj
 begin 
     if zacatek = konec then 
       begin 
         write('Pozor - fronta je prazdna.'); 
         Halt
       end 
     else 
       begin 
         X := zacatek^.hodnota
         pom := zacatek
         zacatek := zacatek^.dalsi
         dispose(pom); 
       end
 end
  
 function JePrazdna: boolean
 begin 
     if zacatek = konec then JePrazdna := true 
     else JePrazdna := false
 end;

 

6.5. SEZNAM

Tato datová struktura je nejobecnější, co se trojice Zásobník - Fronta - Seznam týče. Seznam lze definovat následovně:

  1. logicky sousední prvky nejsou sousední fyzicky (tzn., že prvky, které v seznamu stojí vedle sebe, mohou být umístěny v operační paměti na libovolném místě a k prvkům se dostaneme pomocí ukazatelů na prvky)
  2. každý prvek v seznamu nese v sobě nejen informaci, pro kterou je seznam navržen, ale také ukazatel na sousední prvek (nejčastěji je sousedem následující prvek, ale existují i obousměrné seznamy), poslední prvek má místo ukazatele na následovníka hodnotu NIL, která označuje konec seznamu
  3. ke každému seznamu musí být zajištěn přístup pomocí ukazatele, který se nazývá hlavička seznamu

Zásobník i fronta jsou v podstatě speciální případy seznamu. Mají oproti seznamu podstatné omezení, a tím je možnost vkládání či výběru prvků pouze na stejných, předem definovaných místech (na začátku a na konci). Oproti tomu seznam má úplnou volnost ve výběru prvků, které se budou vybírat, či ve volbě pozice, na kterou se budou prvky vkládat. Tato volnost je umožněna značkou, která označuje místo v seznamu, kam budeme prvek vkládat či ze kterého budeme prvek vybírat nebo pouze číst jeho hodnotu.

Implementace pomocí ukazatele:

Graficky si lze seznam představit takto:

seznam.gif (1139 bytes)

Značku, vyobrazenou v obrázku, můžeme posouvat na začátek seznamu, na konec seznamu, můžeme ji posouvat vpravo i vlevo. Díky této značce přibudou v kódu programu nové funkce a procedury, které budou se značkou pracovat. Nyní si uvedeme celý výpis v Pascalu:

 type spoj = ^element
            element = record 
                   hodnota: datovytyp
                  dalsi: spoj
                 end
           seznam = record 
                  zacatek, konec, znacka: spoj
                end
  
 procedure Vytvor(var S: seznam); 
 begin 
    new(S.zacatek); 
    S.konec := S.zacatek
    S.znacka := S.zacatek
 end
  
 procedure Vloz(var S: seznam; X: datovytyp); 
 var pom: spoj
 begin 
    new(pom); 
    pom^.hodnota := X
    pom^.dalsi := S.znacka^.dalsi
    S.znacka := pom
    if S.konec = S.znacka then S.konec := pom
 end
  
 procedure Odeber(var S: seznam); 
 var pom: spoj
 begin 
    if S.zacatek = S.konec then CHYBA 
    else if S.znacka = S.konec then CHYBA 
    else  
      begin 
        pom := S.znacka^.dalsi
        if S.konec = pom then S.konec := S.znacka
        S.znacka^.dalsi := pom^.dalsi
        dispose(pom); 
      end
 end
  
 procedure Cti(S: seznam; var X: datovytyp); 
 begin 
    if S.znacka = S.konec then CHYBA 
    else X := S.znacka^.hodnota
 end
  
 procedure ZnackaNaZacatek(var S: seznam); 
 begin 
     S.znacka := S.zacatek
 end
  
 procedure ZnackaNaKonec(var S: seznam); 
 begin 
     S.znacka := S.konec
 end
  
 procedure ZnackaVpravo(var S: seznam); 
 begin 
     if S.znacka = S.konec then S.znacka := S.znacka^.dalsi
 end
  
 procedure ZnackaVlevo(var S: seznam); 
 var pom: seznam
 begin 
     if S.znacka <> S.zacatek then  
       begin 
         pom := S.zacatek
         while S.znacka <> pom^.dalsi do pom := pom^.dalsi
         S.znacka := pom
       end
 end
  
 function JePrazdny(var S: seznam): boolean
 begin 
     if S.zacatek = S.konec then JePrazdny := true 
     else JePrazdny := false
 end;  
  
 function JeNaZacatku(var S: seznam): boolean
 begin 
     if S.znacka = S.zacatek then JeNaZacatku := true 
     else JeNaZacatku := false
 end;  
  
 function JeNaKonci(var S: seznam): boolean
 begin 
     if S.znacka = S.konec then JeNaKonci := true 
     else JeNaKonci := false
 end;  

CHYBA, která se v předchozím výpisu vyskytuje celkem třikrát, řeší v prvním případě odebrání prvku z prázdného seznamu, ve druhém odebrání prvku z pozice značky, která je však na konci seznamu, a ve třetím případě řeší čtení hodnoty z prvku z pozice značky, která je na konci seznamu a je to sekvence příkazů, použitých výše ve výpisech fronty a zásobníku:

       begin 
         write('Chybove hlaseni  - nastala chyba !!!.'); 
         Halt
       end 

Implementace pomocí pole:

Implementace pomocí pole je náročnější, než implementace pomocí ukazatele a také využití implementace pomocí pole se zdá být méně pohodlné. Proto ji zde nebudeme uvádět. Můžeme ji však nalézt např. v knize [1].

 

6.6. STROMY

strom1.gif (1596 bytes)Stromem v tomto případě nemyslíme zástupce zemské flory, ale další dynamickou datovou strukturu, která se strom nazývá podle svého grafického vyjádření. I když spíše by to měl být obrácený strom, jehož listy rostou ne vzhůru, ale dolů. Pro představivost máme obrázek stromu vlevo.

Nejjednodušším případem této datové struktury je binární strom. Právě na obrázku je tento binární strom vyobrazen.

Definovat strukturu strom můžeme pomocí rekurze. Tento způsob definice je velice vhodný na pozdější převedení definice stromu do programovacího jazyka.

Definice: Strom můžeme definovat buď jako prázdný strom, nebo jako vrchol, k němuž jsou připojeny dvě další stromové struktury - podstromy.

Jinak řečeno: každý strom je tvořen dalšími stromy, pro které platí stejná definice. Tato rekurzivní definice se do programovacího jazyka převede velice lehce.

 type UVrchol = ^Vrchol 
          Vrchol = record 
                              hodnota: datovy_typ
                              levy, pravy : UVrchol
                          end

Jak je z předcházejícího výpisu vidět, podstromy levy a pravy jsou definovány opět jako typ ukazatel na strom. Zde je tedy využita ona rekurze.

Nejvyšší vrchol stromu se nazývá kořen stromu, prvky, které leží v nejnižší části stromu a nemají žádné následovníky, se nazývají listy stromu. Ostatní prvky jsou souhrnně nazývány vnitřní vrcholy.

Při realizaci určité funkce či procedury, která má být uskutečněna nad všemi vrcholy, je třeba celým stromem projít a všechny vrcholy navštívit. K průchodu stromem nám slouží tři rekurzivní metody, které se od sebe liší vzájemným pořadím provedení dané operace nad daným uzlem a průchodem oběma podstromy.

  1. Procedura preorder provádí nejprve danou operaci nad daným uzlem a poté prochází jednotlivé podstromy. Její programové řešení je následující:

     procedure Preorder(Strom : UVrchol); 
     begin 
       if Strom <> nil then  
       begin 
           ...                                        { operace nad daným uzlem } 
         Preorder(Strom^.Levy);    { průchod levým podstromem } 
         Preorder(Strom^.Pravy)    { průchod pravým podstromem }  
       end
     end

     

  2. Procedura inorder projde nejprve první z podstromů, poté provede danou operaci nad daným vrcholem a nakonec projde druhým z podstromů. Její programové řešení je následující:

     procedure Inorder(Strom : UVrchol); 
     begin 
       if Strom <> nil then  
       begin 
         Inorder(Strom^.Levy);     { průchod levým podstromem } 
           ...                                      { operace nad daným uzlem } 
         Inorder(Strom^.Pravy)    { průchod pravým podstromem }  
       end
     end

     

  3. Procedura postorder nejprve projde oběma podstromy poté provede danou operaci nad daným vrcholem. Její programové řešení je následující:

     procedure Postorder(Strom : UVrchol); 
     begin 
       if Strom <> nil then  
       begin 
         Postorder(Strom^.Levy);     { průchod levým podstromem } 
         Postorder(Strom^.Pravy)    { průchod pravým podstromem }  
           ...                                           { operace nad daným uzlem } 
       end
     end

Pokud tedy použijeme tyto při metody průchodu stromem na náš obrázek na začátku této kapitoly, můžeme získat tyto výsledky:

Nejvíce využitelné z celkové teorie stromů jsou dnes binární vyhledávací stromy a binární vyvážené stromy.

6.6.1. BINÁRNÍ VYHLEDÁVACÍ STROMY

strom3.gif (2269 bytes)Tyto typy binárních stromů jsou s výhodou používány v třídících a vyhledávacích algoritmech a mají tudíž specifické vlastnosti uzlů. Pro každý uzel platí, že žádný jeho následovník v levém podstromu, ať už přímý, nebo nepřímý, nemá hodnotu menší než je hodnota daného uzlu a žádný jeho následovník v pravém podstromu, ať už přímý, nebo nepřímý, nemá hodnotu větší než je hodnota daného uzlu. Nebo naopak. Příklad takového vyhledávacího stromu můžeme vidět na obrázku vlevo.

Pokud se takový strom využije ve vyhledávacím algoritmu, je časová složitost algoritmu závislá pouze na výšce stromu. Výškou stromu přitom myslíme počet hran, které obsahuje cesta od kořene stromu k jeho nejvzdálenějšímu listu. Pokud je strom vyvážený, tedy pokud se počty uzlů v podstromech každého uzlu stromu liší nejvýše o jeden, je jeho výška rovna pouze celé části logn, kde n je počet uzlů.

Jako příklad využití binárního vyhledávacího stromu si uvedeme třídicí algoritmus, který načítá vstupní hodnoty ze souboru a vytváří z nich binární vyhledávací strom. Po ukončení načítání a vytváření stromu jsou uspořádaná čísla vytištěna na obrazovku. Musíme ještě poznamenat, že čísla jsou ze stromu vypisována metodou inorder a rušení již prošlých uzlů je prováděno metodou postorder.

 program Trideni
  
 type UVrchol = ^Vrchol
      Vrchol = record 
                 hodnota : real
                 levy, pravy : Vrchol
               end
  
 var Strom : UVrchol
  
 procedure PridejVrchol(C : real; var podstrom : UVrchol); 
 begin 
   if podstrom = nil then 
   begin 
     new(podstrom); 
     with podstrom^ do 
     begin 
       hodnota := C
       levy := nil
       pravy := nil
     end
   end 
   else 
   with podstrom^ do 
     if (C < hodnota) then PridejVrchol(C, levy
                      else PridejVrchol(C, pravy); 
 end
  
 procedure Tisk(podstrom : UVrchol); 
 begin 
   if (podstrom <> nil) then 
   begin 
     with podstrom^ do 
     begin 
       Tisk(levy); 
       Writeln(hodnota); 
       Tisk(pravy); 
     end
     dispose(podstrom); 
   end
 end
  
 BEGIN 
   koren := nil
   while not(SeekEOF) do 
   begin 
     read(C); 
     PridejVrchol(C, koren); 
   end
   Tisk(koren); 
 END

Procedura PridejVrchol přidá prvek na konec větve stromu, pokud na větvi není následovník, jinak podle rozhodovací podmínky vybere podvětev dané větve a vloží prvek do ní.

strom4.gif (3294 bytes)Dalším příkladem využití těchto stromů je vytvoření programu na dekódování zprávy přijaté v Morseově abecedě. Hlavní strukturou zde budě opět binární vyhledávací strom, ve kterém budou uložena jednotlivá písmena a jejich vyjádření ve znacích tečka a čárka. Znázornění stromu vudíme na obrázku vlevo.

V kořenu je uložen speciální znak, označující mezeru. Při čtení řetězce stojíme v kořenu stromu. Znak tečka znamená přechod na levý podstrom, znak čárka znamená přechod na pravý podstrom. Při dalším přečtení znaku mezera se vytiskne celé dekódované slovo a pokračuje se novým slovem.

Celý program na dekódování Morseovy abecedy je uveden níže. Program nejprve vytvoří dekódovací strom a poté volá proceduru DEKODUJ. Pro jednoduchost předpokládáme, že všechny kódy písmen (dílčí posloupnosti teček a čárek) na vstupu jsou správné a jsou ukončeny alespoň jedním oddělovačem. Dekódování celého vstupního textu probíhá jako cyklus. Před načtením prvního znaku je nastaven pomocný ukazatel Smer na kořen stromu. V každém průchodu cyklem se pak přečte jeden znak kódu a podle jeho hodnoty (tečka, čárka nebo oddělovač) se buď provede přesun ukazatele Smer na levý podstrom aktuálního uzlu (tečka) nebo přesun ukazatele Smer na pravý podstrom aktuálního uzlu (čárka) nebo vytištění písmene v aktuálním uzlu a přesun ukazatele Smer zpět do kořene stromu. Tedy např. po zpracování kódu .-.. (vlevo, vpravo, vlevo, vlevo) bude vytištěno písmeno L.

 program Morse
  
 type UVrchol = ^Vrchol
      Vrchol = record 
                 znak : char
                 tecka, carka : UVrchol
               end;  
  
 var koren : UVrchol
  
 function VytvorUzel(z : char; t, c : UVrchol) : UVrchol
 var P : UVrchol;  
 begin 
   new(P); 
   with P^ do  
   begin 
     znak := z
     tecka := t
     carka := c
   end
   VytvorUzel := P 
 end
  
 procedure Dekoduj
 var smer : UVrchol
     symbol : char
 begin 
   smer := koren
   while not EOF do 
   begin 
     read(symbol); 
     case symbol of 
       '.' : smer := smer^.tecka
       '-' : smer := smer^.carka 
       else begin 
               write(smer^.znak); 
               smer := koren
             end
     end
   end;  
   writeln
 end
  
 BEGIN 
 koren := VytvorUzel(' ', 
            VytvorUzel('E', 
              VytvorUzel('I', 
                VytvorUzel('S', 
                  VytvorUzel('H', nil, nil), 
                   VytvorUzel('V', nil, nil)), 
                VytvorUzel('U', 
                  VytvorUzel('F', nil, nil), 
                nil)), 
              VytvorUzel('A', 
                 VytvorUzel('R', 
                   VytvorUzel('L', nil, nil), 
                nil), 
                 VytvorUzel('W', 
                   VytvorUzel('P', nil, nil), 
                  VytvorUzel('J', nil, nil)))), 
            VytvorUzel('T', 
              VytvorUzel('N', 
                 VytvorUzel('D', 
                   VytvorUzel('B', nil, nil), 
                   VytvorUzel('X', nil, nil)), 
                 VytvorUzel('K', 
                   VytvorUzel('C', nil, nil), 
                   VytvorUzel('Y', nil, nil))), 
              VytvorUzel('M', 
                VytvorUzel('G', 
                   VytvorUzel('Z', nil, nil), 
                   VytvorUzel('Q', nil, nil)), 
                VytvorUzel('O', nil, nil)))); 
  Dekoduj
 END

6.6.2. BINÁRNÍ VYVÁŽENÉ STROMY

strom2.gif (2140 bytes)Dokonale vyvážený binární strom je takový strom, ve kterém se počet vrcholů jeho levého podstromu liší od počtu vrcholů v jeho pravém podstromu maximálně o jeden. Pro takový strom s n vrcholy platí, že počet vrcholů v jeho levém podstromu je nl = n div 2 a pro počet vrcholů v jeho pravém podstromu platí np = n - nl - 1.

Vytvoření takového dokonale vyváženého binárního stromu uvádí následující výpis programu. Procedura strom je volána v programu pouze jednou, poté volá sama sebe k vytvoření celého stromu.

 type UVrchol = ^Vrchol 
      Vrchol = record 
                 hodnota: datovy_typ
                 levy, pravy : UVrchol
               end
  
 var pocet_vrcholu_stromu : integer
     koren_stromu : UVrchol
  
 function Strom(pocetvrcholu : integer) : UVrchol
 var novyvrchol : UVrchol
     nl, np : integer
     hodnotavrcholu : real
  
 begin 
   if pocetvrcholu = 0 then strom := nil 
   else begin 
     nl := pocetvrcholu div 2; 
     np := pocetvrcholu - nl - 1; 
     write('Vloz hodnotu do vrcholu stromu: '); 
     readln(hodnotavrcholu); 
     new(novyvrchol); 
     with novyvrchol^ do 
     begin 
       hodnota := hodnotavrcholu
       levy := Strom(nl); 
       pravy := Strom(np); 
     end
     Strom := novyvrchol
   end
 end
  
 procedure Vytvor_strom
   write('Vloz hodnotu udavajici pocet vrcholu stromu: '); 
   readln(pocet_vrcholu_stromu); 
   koren_stromu := Strom(pocet_vrcholu_stromu); 
 end

 

6.7. TŘÍDĚNÍ

I když tato kapitola zjevně nemá nic společného s dynamickými datovými strukturami, některé třídící metody, které si zde uvedeme, těchto struktur využívají. (My si zde uvedeme dvě konkrétní metody, metodu HeapSort a metodu RadixSort.) Proto je vhodné tuto kapitolu zařadit právě zde.

Třídících metod je určitě celá spousta a všechny si je zde uvést ani nemůžeme, rozebereme si zde pouze ty nejznámější a nejpoužívanější. Začneme těmi jednoduššími a pomalejších a postupně se dobereme metod náročných a rychlých.

Snad ještě hned na začátku bychom si měli vysvětlit pár pojmů, které budeme dále používat.

6.7.1. BUBBLE SORT - BUBLINKOVÉ TŘÍDĚNÍ

Tato třídící metoda je ze všech uvedených metod nejjednodušší, ale také nejpomalejší. Její princip spočívá v jednoduché záměně dvou sousedních prvků, pokud nevyhovují dané podmínce. Procedura obsahuje dva do sebe vnořené cykly, vnější zajišťuje zmenšování počtu prvků, které stále nejsou setříděny a vnitřní cyklus zajišťuje vlastní výměny dvou prvků v jednom průchodu posloupností.

 var pole : array[1..10]of integer
  
 procedure BubbleSort(maximum: integer); 
 var k, l, pom : integer
 begin 
   for k := 1 to maximum do 
   begin 
     for l := 1 to maximum-1 do 
     begin 
       if (pole[l] > pole[l+1]) then 
       begin 
         pom := pole[l]; 
         pole[l] := pole[l+1]; 
         pole[l+1] := pom
       end
     end
   end
 end

Existuje také vylepšená metoda Bubblesortu, ta ukončí průchod posloupností i celé procedury, pokud je již celá posloupnost uspořádaná, přestože oba cykly for stále neukončily činnost, neboli pokud nenastala při posledním průchodu posloupností žádná výměna prvků.

 var pole : array[1..10]of integer
  
  procedure BubbleSort(maximum: integer);  
  var k, l, pom : integer;  
         vymena: boolean;  
  begin  
    vymena := false;  
    for k := 1 to maximum do  
    begin  
      for l := 1 to maximum-1 do  
      begin  
        if (pole[l] > pole[l+1]) then  
        begin  
          vymena := true;  
          pom := pole[l];  
          pole[l] := pole[l+1];  
          pole[l+1] := pom;  
        end;  
      end;  
      if vymena = true then Halt;  
    end;  
  end;  

Metoda Bubblesortu je přirozená a stabilní. Nejrychlejší ze všech metod je pouze v tom případě. kdy chceme zjistit, zda je daná posloupnost setříděná či nikoliv. Jinak je metoda nejpomalejší. Její časová složitost (což je počet výměn,které je nutno provést k uspořádání posloupnosti) je O(N2), protože v nejhorším případě (kdy je posloupnost uspořádána přesně opačně než požadujeme) je nutno provést znacka2.gif (160 bytes) výměn prvků posloupnosti.

(Pozn.: Výraz znacka2.gif (160 bytes) patří do O(N2), protože nejvyšší mocnina vyskytující se ve výrazu, je N2.)

6.7.2. SHAKER SORT - TŔÍDĚNÍ PŘETŘÁSÁNÍM

Tato metoda třídění je vylepšená metoda BubbleSort. Její vylepšení se týká střídání směru průchodu posloupností. Zatímco metoda BubbleSort prochází danou posloupnost pouze jedním směrem (od prvního k poslednímu prvku), tato metoda střídá směr po každém průchodu posloupností za opačný.

 var pole : array[1..10]of integer
  
 procedure ShakerSort(max: integer); 
 var k, l, r, pom, i, j: integer
 begin 
   l := 2; 
   r := max
   k := max
   repeat 
     for j := r downto l do 
       if pole[j-1] > pole[j] then 
       begin 
         pom := pole[j-1]; 
         pole[j-1] := pole[j]; 
         pole[j] := pom
         k := j
       end
       l := k + 1; 
     for j := l to r do 
       if pole[j-1] > pole[j] then 
        begin 
         pom := pole[j-1]; 
         pole[j-1] := pole[j]; 
         pole[j] := pom
         k := j
       end
     r := k - 1; 
   until l > r;  
 end

Metoda je přirozená a stabilní. Časová složitost je O(N2).

6.7.3. INSERT SORT - TŘÍDĚNÍ VKLÁDÁNÍM

Tato metoda je založena na principu vkládání prvku na jeho správné místo v posloupnosti. Jak si můžete porovnat předchozí výpisy metod s výpisem této metody, používá pole o velikostí ne 10, ale 11 prvků, počínaje již nultým prvkem. Tento se v celé posloupnosti využívá jako pomocný prvek a samotná posloupnosti jej do sebe nezahrnuje.

 var pole : array[0..10]of integer
  
 procedure InsertSort(max: integer); 
 var i, j, pom:integer
 begin 
   for i:=2 to max do 
   begin 
     pom := pole[i]; 
     pole[0]:=pom
     j:=i-1; 
     while pom < pole[j] do  
     begin 
       pole[j+1] := pole[j]; 
       j:=j-1; 
     end
   pole[j+1] := pom
   end
 end

Metoda je přirozená a stabilní. Časová složitost je O(N2).

6.7.4. SELECT SORT - TŘÍDĚNÍ VÝBĚREM

Metoda pracuje na principu nalezení minimálního prvku v nesetříděné části posloupností a jeho zařazení na konec již setříděné posloupnosti. Metoda prochází celou nesetříděnou část posloupnosti a hledá nejmenší prvek. Až jej nalezne, vrátí se na konec již setříděné části posloupnosti a tento nejmenší prvek zde uloží. Tyto dvě činnosti vykonává do té doby, dokud neprojde celou posloupnost a nesetřídí ji.

 var pole : array[1..10]of integer
  
 procedure SelectSort(max: integer); 
 var i, j, min, pom : integer
 begin 
   for i := 1 to max - 1 do  
   begin  
     min := pole[i]; 
     for j := i + 1 to max do 
     begin 
       if min > pole[j] then 
       begin 
         min := pole[j]; 
         pom := j
       end
     end
     pole[pom] := pole[i]; 
     pole[i] := min
   end
 end

Metoda je nestabilní. Časová složitost je O(N2).

6.7.5. SHELL SORT - TŘÍDĚNÍ SE SNIŽUJÍCÍM SE PŘÍRÚSTKEM

Tuto metodu vytvořil jeden chytrý pán, po kterém je metoda pojmenována a tento pán ji poprvé publikoval v roce 1959. Metoda je velice podobná, co se její činnosti týče, metodě BubbleSort, ale je podstatně vylepšena, a proto také podstatně rychlejší. Pan Shell tři tvorbě této metody přišel na určité zákonitosti, jako např. na tuto, že každý prvek se v posloupnosti přesune ve průměrném případě o jednu třetinu celkové délky posloupnosti. Tohoto poznatku pan Shell využil a zmiňovanou metodu BubbleSort přepracoval v tom smyslu, že měnil v každém průchodu posloupností vzdálenost dvojic prvků, které se měly uspořádat.

Jinak řečeno: metoda pracuje tak, že neporovnává dva sousední prvky, ale prvky od sebe vzdálené o délku d. Tato délka se po každém průchodu posloupností zmenšuje na polovinu.

 const t = 4; 
  
 var i, j, k, s, x: integer
       m: 1..t
       h: array[1..t]of integer
       a: array[1..n] of integer
  
 begin 
   h[1] := 9;  
   h[2] := 5; 
   h[3] := 3; 
   h[4] := 1; 
   for m := 1 to t do 
   begin 
     k := h[m]; 
     s := -k;    {pozice zarážky} 
     for i := k+1 to n do 
     begin 
       x := a[i]; 
       j := i - k
       if s = 0 then s := -k
       s := s+1; 
       a[s] := x
       while x < a[j] do 
       begin 
         a[j+k] := a[j]; 
         j := j-k
       end
       a[j+k] := x
     end
   end
 end

Metoda není stabilní a také přirozenost metody není jednoznačná. Vztah pro přesnou časovou složitost nebyl odvozen; časová složitost, odvozená na základě experimentů, je O(N * (log2 N)2).

6.7.6. QUICK SORT - TŘÍDĚNÍ NA PRINCIPU ROZDĚLOVÁNÍ

Tato metoda třídění je původní, není odvozená z jiné metody a přišel s ní jistý pan C. A. R. Hoare v roce 1962. Obecný princip této metody spočívá v rozdělení původní posloupnosti do N podposloupností, pro které platí, že všechny prvky první podposloupnosti jsou menší než všechny prvky druhé podposloupnosti, atd. Poté se každá podposloupnost rozdělí opět na N' podpodposloupností, pro jejichž prvky platí opět podmínka rostoucí nerovnosti, atd., až nakonec rozdělování skončí, pokud jsou podposloupnosti prázdné.

Naše konkrétní realizace QuickSortu bude dělit vstupní posloupnost pouze na dvě části, a to podle prostředního prvku. Abychom docílili toho, že v levé podposloupnosti budou prvky menší než prostřední prvek a v pravé podposloupnosti budou prvky větší než prostřední prvek, musíme ty prvky, které jsou v levé části a patří do pravé (a naopak), přemístit. To provádíme pomocí dvou ukazovátek, které běží každé v jedné podposloupnosti proti sobě. Levé ukazovátko běží levou částí směrem k prostřednímu prvku tak dlouho, dokud nenalezne prvek větší než prostřední prvek. Pravé ukazovátko pro změnu běží pravou částí směrem k prostřednímu prvku tak dlouho, dokud nenarazí na prvek, který je menší než prostřední prvek. Až obě ukazovátka takové prvky naleznou, zamění je mezi sebou a prohledávání pokračuje. Prohledávání obou částí je poté ukončeno, pokud dojde k překřížení obou ukazovátek.

Princip metody si ukážeme na následujícím vývojovém diagramu:

quicksort.gif (3072 bytes)

Tato metoda je pěkným příkladem ukázky rekurzivního řešení problému, i když metoda QuickSort se dá řešit i nerekurzivně.

 procedure QuickSort(l, r: integer); 
 var i, j, pom, pom2: integer
  
 procedure ROZDEL
 begin 
   i := l
   j := r
   pom :=pole[(i + j) div 2]; 
   repeat 
     while pole[i] < pom do i := i + 1; 
     while pole[j] > pom do j := j - 1; 
     if i <= j then 
     begin 
       pom2 := pole[i]; 
       pole[i] := pole[j]; 
       pole[j] := pom2
       i := i + 1; 
       j := j - 1; 
     end
   until i > j
 end
  
 begin 
   ROZDEL
   if l < j then QuickSort(l,j); 
   if i < r then QuickSort(i,r); 
 end

Metoda není ani přirozená, ani stabilní, ale je jedna z nejúspěšnějších metod třídění. Časová složitost je O(N * log2 N).

6.7.7. HEAP SORT - TŘÍDĚNÍ POMOCÍ STROMOVÉ STRUKTURY

Tato třídící metoda využívá ke své činnosti právě dynamickou datovou strukturu, a tou je halda. Popíšeme si ji přesněji.

Halda, někdy nazývána také hromada, je binární strom, jehož vrcholy jsou ohodnoceny celými čísly a má následující vlastnosti:

  1. každý vrchol, který neleží na předposlední nebo poslední úrovni stromu, má dva následníky; na předposlední úrovni stromu následují zleva doprava vrcholy se dvěma následníky, poté vrcholy, mající pouze levého následníka a nakonec vrcholy bez následníků;
  2. ohodnocení libovolného vrcholu není větší než ohodnocení libovolného jeho následníka.

Předvést si to mužeme na následujícím grafu:

halda.gif (1338 bytes)

Této datové stuktury se využívá k tomu, aby se do ní uspořádaly prvky vstupní posloupnosti přesně podle pravidel, které jsme si k haldě uvedli výše. Poté se z haldy vybírají prvky do výstupní posloupností, počínaje minimálním (tedy nejvyšším) prvkem. Následuje výpis v Pascalu:

 Procedure HeapSort
 var l, r, pom: integer
  
     Procedure Vytvorhaldu
     Label 13; 
     Var i, j:integer
     Begin 
       i := l
       j := 2*i
       Pom := pole[i]; 
       While j <= r do 
       Begin 
         If j < r then  
           if pole[j] < pole[j+1] then j := j+1; 
           if pom >= pole[j] then goto 13; 
           pole[i] := pole[j]; 
           i := j
           j := 2*i
       End
     13: pole[i] := pom
     End
  
 Begin 
   l := (n div 2) + 1; 
   r := n
   While l > 1 do 
   Begin 
     l := l - 1; 
     Vytvorhaldu
   end
   While r > 1 do 
   Begin 
     Pom := pole[1]; 
     Pole[1] := pole[r]; 
     Pole[r] := pom
     r := r - 1; 
     Vytvorhaldu
   end
 end;  

6.7.8. RADIX SORT - TŘÍDĚNÍ GRUPOVÁNÍM

Tato metoda třídí posloupnost K-místných čísel délky N a pracuje na principu přihrádkového řazení. Zavádí se zde deset přihrádek pomocí datové struktury fronta pro každou číslici z intervalu 0 až 9. Vlastní tříděiní probíhá takto: v prvním průchodu vstupní posloupností čísla zařazujeme do vzniklých přihrádek podle jejich poslední číslice (jednotky), poté čísla spojíme z přihrádek do nové posloupnosti; v dalším průchodu čísla z této nové posloupnosti zařazujeme do vzniklých přihrádek podle jejich předposlední číslice (desítky), poté čísla spojíme do další nové posloupnosti; takto provádíme rozdělování a spojování po jednotlivých řádech číslic až do řádu K. Duležitá poznámka: čísla z přihrádek vybíráme do nové posloupnosti v takovém pořadí, v jakém jsme je do přihrádek vložili - proto využíváme datovou strukturu fronta.

Celý postup si mužeme předvést na následujícím obrázku. Zde budeme třídit dvojciferná čísla:

radixsort.gif (3785 bytes)

I když jsou na obrázku přihrádky zobrazeny spíše jako zásobníky, můsím opět zopakovat, že je zde využita datová struktura fronta. Následuje výpis: Poíkazy Pridej, Odeber a JePrazdna jsou volání procedur a funkcí fronty tak, jak jsme si tuto datovou strukturu nadefinovali v kapitole výše, která se frontou zabývá.

 var pole : array[1..10]of integer
  
 procedure RadixSort(N, K: integer); 
 var i, j, rad, C: integer
 begin 
   rad := 10; 
   for C := 0 to 9 do  
     Vytvor(Prihradka[C]); 
   for i := K downto 1 do 
   begin 
     for j := 1 to N do 
       Pridej(Prihradka[pole[j] mod rad], pole[j]); 
     j := 1; 
     for C := 0 to 9 do 
       while (not (JePrazdna(Prihradka[C])))do 
       begin 
         Odeber(Prihradka[C], pole[j]); 
         j := j + 1; 
       end
   rad := rad * 10; 
   end
 end

Časová složitost metody je O(N) (protože zpracováváme posloupnost délky N a to právě tolikrát, kolik je počet cifer největšího čísla v posloupnosti). Metoda je rychlejší než metoda QuickSort, avšak je podstatně paměťově náročná

6.7.9. MERGE SORT - ŘAZENÍ NA PRINCIPU SETŘIĎOVÁNÍ (SLUČOVÁNÍ)

Metoda pracuje na principu sekvenčního setřídění dvou seřazených posloupnosti do jedné seřazené posloupnosti. Používá se pro setřídění záznamů z dvou čí několika souborů a používá se tehdy, pokud se záznamy k setřídění nevejdou do pracovní paměti počítače.

 begin 
   i := 1; 
   j := 1; 
   k := 1; 
   while (i <= m) and (j <= n) do 
   begin 
     if A[i] < B[i] then  
     begin 
       C[k] := A[i]; 
       i := i + 1; 
     end 
     else begin  
       C[k] := B[j]; 
       j := j + 1; 
     end 
     k := k + 1; 
   end
   while i <= m do  
   begin  
     C[k] := A[i]; 
     i := i + 1; 
     k := k + 1; 
   end
   while j <= n do  
   begin  
     C[k] := B[j]; 
     j := j + 1; 
     k := k + 1; 
   end
 end

Metoda není stabilní a nechová se přirozeně. Její časová složitost je O(N * log2 N).

 

6.8. VYHLEDÁVÁNÍ

Tato kapitola by správně měla být umístěna v kapitole, zabývající se strukturovaným programováním, ale poněvadž je v literatuře téměř vždy spjata s předchozí kapitolou o třídění, umístil jsem tuto kapitolu zde také.

Vyhledávacích metod jistě existuje mnoho a jsou založeny na mnoha datových strukturách, my si zde však pro názornost uvedeme metodu vyhledávání v nesetříděném a setříděném poli.

Metody vyhledávání např. pomocí vyhledávacích tabulek lze nalézt v [1].

6.8.1. VYHLEDÁVÁNÍ V NESETŘÍDĚNÉ POSLOUPNOSTI

Pokud budeme vyhledávat určitou hodnotu v nesetříděné posloupnosti, můžeme hledat dvěma způsoby:

  1. hledáme první výskyt hledané hodnoty; v tomto případě pokud vyhledávací algoritmus nalezne hledanou hodnotu, ukončíme jej.
    Algoritmus hledá hodnotu sekvenčně - prochází posloupnost od prvního prvku směrem ke konci posloupnosti.
     var pole : array[1..20] of integer
         i, find : integer
         nalezeno : boolean
      
     begin 
       for i := 1 to 20 do 
       begin 
         write('Vlozte hodnotu posloupnosti: '); 
         readln(pole[i]); 
       end
       write('Vlozte hodnotu, kterou chcete najit: '); 
       readln(find); 
       i := 0; 
       repeat 
         Inc(i); 
         nalezeno := (pole[i] = find); 
       until nalezeno or (i = 20); 
       if nalezeno then writeln('Hodnota byla nalezena na ',i,'-te pozici.') 
         else writeln('Hodnota nebyla nalezena.'); 
     end
  2. hledáme všechny výskyty hledané hodnoty; v tomto případě vyhledávací algoritmust projde celou posloupnost a při nalezení hledané hodnoty vypíše pozici hledané hodnoty v posloupnosti.
     var pole : array[1..20] of integer
         i, find : integer
         pom, nalezeno : boolean
      
     begin 
       for i := 1 to 20 do 
       begin 
         write('Vlozte hodnotu posloupnosti: '); 
         readln(pole[i]); 
       end
       write('Vlozte hodnotu, kterou chcete najit: '); 
       readln(find); 
       i := 0; 
       repeat 
         Inc(i); 
         nalezeno := (pole[i] = find); 
         if nalezeno then 
         begin 
           pom := nalezeno
           writeln('Hodnota byla nalezena na ',i,'-te pozici.'); 
         end
       until (i = 20); 
       if not(pom) then writeln('Hodnota nebyla nalezena.'); 
     end

6.8.2. VYHLEDÁVÁNÍ V SETŘÍDĚNÉ POSLOUPNOSTI

Vyhledávání v setříděné posloupnosti je rychlejší než v posloupnosti neuspořádané, nemusíme totiž prohledávat celé pole, ale jen jeho část.

Opět si zde uvedeme dvě metody:

  1. Vyhledávání se zarážkou je v podstatě identické s vyhledáváním v nesetříděné posloupnosti, kdy hledáme pouze první výskyt hledané hodnoty.
     procedure Vyhlzarazka(var pole: array of integer;  
                           hodn: integer; var poz: integer;  
                           var exist: boolean); 
     begin 
       exist := FALSE
       i := 1; 
       j := 50; 
       while ((i < j) and not(exist)) do 
       begin 
         if (pole[i] = hodn) then 
         begin 
           exist := TRUE
           poz := i
         end 
         else inc(i); 
       end
     end
  2. Vyhledávání půlením intervalu je metoda zcela jiná než předchozí. Tato metoda využívá ve velké míře právě uspořádání posloupnosti, např. od nejmenšího prvku po největší. Metoda totiž rozpůlí tuto posloupnost na dvě poloviny a zjišťuje, zda hledaná hodnota leží v polovině s menšími čísly či v polovině s většími čísly. Podle výsledku výběru poloviny posloupnosti se právě vybraná polovina opět rozpůlí na dvě poloviny a celý cyklus se opakuje do té doby, dokud není hledaná hodnota nalezena nebo dokud nezůstane dělená posloupnost prázdná
     procedure Vyhlpuleni(var pole: array of integer;  
                          hodn: integer; var poz: integer;  
                          var exist: boolean); 
     begin 
       exist := FALSE
       i := 1; 
       j := 50; 
       repeat 
         k := trunc((i + j) div 2); 
         if (pole[k] = hodn) then 
         begin 
           poz := k
           exist := TRUE
         end
         if (pole[k] < hodn) then i := k + 1 
         else j := k - 1; 
       until ((pole[k] = hodn) or (i > j)) 
     end

Předchozí strana Obsah Další strana