Všechny proměnné, s kterými jsme až doposud pracovali, můžeme označit jako statické. Proměnná se vytvoří (vyhradí se pro ni místo v paměti) po spuštění aplikace při deklaraci a zaniká po skončení procedury, pokud je lokální, nebo po skončení aplikace, pokud je globální. Při deklaraci proměnných takto jednoznačně určujeme, jaké množství paměti využijeme pro uložení dat v programu.

Ukazatel je proměnná specielního typu. Každá proměnná typu ukazatel má tzv. doménový typ. Doménový typ ukazatele určuje, jaká dynamická proměnná bude vytvořena. Vytvoříme-li novou dynamickou proměnnou, vždy máme v nějaké proměnné typu ukazatel zapsáno místo v paměti, kde se nová dynamická proměnná nachází. K hodnotě dynamické proměnné pak přistupujeme právě pomocí ukazatele.

Deklarujeme proměnnou u, která je typu ukazatel. Za dvojtečkou zapíšeme znak šipka ^ a jméno doménového typu. Proměnná u tak bude ukazovat na dynamickou proměnnou typu integer. K vytváření dynamických proměnných použijeme proceduru New. Tato procedura má jeden parametr typu ukazatel. Po zavolání procedury New se v paměti vytvoří nová proměnná takového typu, který je doménovým typem parametru. S nově vytvořenou proměnnou pak můžeme pracovat prostřednictvím ukazatele, který jsme uvedli jako parametr procedury New.

Pokud chceme pracovat s hodnotou dynamické proměnné, pracujeme s ukazatelem na tuto dynamickou proměnnou. Uvedeme jméno proměnné typu ukazatel, která byla parametrem procedury New, a znak šipka. Tím získáme přístup k místu v paměti, kde se nachází nová dynamická proměnná a můžeme pracovat s její hodnotou. Pokud máme deklarovánu proměnnou u typu ukazatel s doménovým typem integer, můžeme takto vytvořit a použít novou dynamickou proměnnou typu integer:

Ukazatel u pak můžeme použít k vytvoření nové dynamické proměnné. Pokud nějaká proměnná typu ukazatel neukazuje na žádnou dynamickou proměnnou (před použitím New nebo po použití Dispose), její hodnota je nedefinovaná. Proměnné typu ukazatel můžeme přiřadit hodnotu nil. Tím dáme najevo, že ukazatel neurčuje žádnou dynamickou proměnnou. Je možné zapsat podmínku, kdy se ptáme, jestli má ukazatel hodnotu nil.

Po stisku tlačítka vytvořte dynamickou proměnnou typu integer. Dejte jí náhodnou hodnotu a vypište ji. (dynam.dpr)

Je pravda, že použití dynamické proměnné v předchozím příkladu je zbytečné. Mnohem lepší řešení by bylo se statickou proměnnou typu integer. Kdy má tedy použití dynamických proměnných smysl? Pokud předem víme, kolik proměnných budeme potřebovat, tak asi ne. Jestliže však množství hodnot, s kterými budeme pracovat, předem neznáme, můžeme si pro ně vytvářet proměnné dynamicky a jejich počet tedy přizpůsobovat počtu hodnot. K tomu ale potřebujeme vytvořit složitější datovou strukturu. Pokud by každá dynamická proměnná měla mít svůj ukazatel, který bychom deklarovali, nic tím nezískáme. Pro práci s  dynamickými datovými strukturami typicky využijme záznamy.

Vytvoříme záznam, který bude mít jednu z položek typu ukazatel, další položky pak mohou být různých jiných typů. Aby použití takového záznamu mělo smysl, položka záznamu typu ukazatel bude ukazovat na dynamickou proměnnou, která je také typu záznam (stejný záznam). Takové dynamické proměnné pak můžeme prostřednictvím položek typu ukazatel navzájem propojovat. V jednom záznamu máme ukazatel na další záznam atd.

Tento záznam má první položku s názvem hod typu integer. Tuto položku můžeme využít pro práci s hodnotou typu integer. Druhá položka dal je typu ukazatel. Typ pro tuto položku musí být definován dříve v unitě. Ještě před definicí typu záznam tedy definuji typ ukazatele na tento záznam. Takto definovaný typ je typem položky záznamu dal. V definici typu ukazatel tak vlastně jako doménový typ využívám typ dosud nedefinovaný. Toto je jediná výjimka v Pascalu, kdy mohu využít dosud nedefinovaný typ. Doménový typ pro ukazatel samozřejmě musím definovat později. V tomto konkrétním případě tedy definuji typ Uk, což je ukazatel na dynamickou proměnnou dosud neznámého typu Zaz. Tento typ definuji vzápětí. Je to záznam, jehož položka dal je typu Uk. Tato položka je tedy ukazatelem na dynamickou proměnnou typu Zaz.

Záznamy s touto strukturou se spojují do tzv. seznamů. Do seznamů můžeme přidávat prvky, rušit je, seznamy můžeme třídit apod. Typicky přitom používáme jednu proměnnou typu ukazatel na záznam, která ukazuje na první prvek seznamu. Takovou proměnnou obvykle nazýváme hlavou seznamu. Jedna z položek prvního prvku pak ukazuje na druhý prvek atd. Stačí tedy používat jednu proměnnou typu ukazatel a v seznamu může být uchováno velké množství hodnot. Pro každou je vytvořena dynamická proměnná.

Naprogramujte operace s jednosměrným seznamem. (seznam1.dpr)

V jednotlivých proměnných typu záznam budeme v položce hod uchovávat celé číslo a v položce dal ukazatel na další prvek seznamu. Tato struktura tedy vystihuje označení “jednosměrný”. V seznamu se můžeme pohybovat pouze jedním směrem, od hlavy ke konci. Na formuláři budeme zobrazovat vždy hodnotu aktuálního prvku a hodnotu jeho následníka. V memu pak vypíšeme všechny prvky seznamu. K práci se seznamem využijeme 2 globální proměnné typu ukazatel. Proměnná k bude ukazovat vždy na začátek seznamu, proměnná l na aktuální prvek. Umožníme přidávat prvky, procházet seznam prvek po prvku, rušit jednotlivé prvky a zrušit celý seznam.

Jako prvky seznamu použijeme celá čísla z intervalu 1..100, které budeme náhodně generovat. V reakci na událost OnCreate formuláře inicializujeme generátor náhodných čísel a hodnoty ukazatelů k,l nastavíme na nil. K výpisu prvků a celého seznamu připravíme procedury PisPrvek a PisSeznam. Obě procedury mají jako parametr ukazatel. Procedura PisPrvek dostává jako parametr ukazatel na aktuální prvek, do labelů vypisuje jeho hodnotu a hodnotu následníka:

Pokud má parametr hodnotu nil nebo neexistuje následník, je do příslušného labelu vypsán textový řetězec “nil”.

Pokud stiskneme tlačítko pro přidání prvku, prvek je přidáván vždy na začátek seznamu. Nastaví se také jako aktuální prvek a vypíše se. Současně se aktualizuje výpis celého seznamu:

procedure TForm1.BitBtn3Click(Sender: TObject);
var m:Uk;
begin
if l<>nil then //je co zrušit
  if l=k then //první prvek
    begin
    k:=l^.dal;
    Dispose(l);
    l:=k;
    end
  else
    if l^.dal=nil then //poslední prvek
      begin
      m:=k;
      while m^.dal<>l do
        m:=m^.dal;
      m^.dal:=nil;
      Dispose(l);
      l:=m;
      end
    else //prostřední prvek
      begin
      m:=l^.dal;
      l^.hod:=m^.hod;
      l^.dal:=m^.dal;
      Dispose(m);
      end;
PisPrvek(l);
PisSeznam(k);
end;

Protože vypouštíme prvek, musíme rušit příslušnou dynamickou proměnnou. V případě prvního prvku posuneme ukazatel k na následující prvek a zrušíme první prvek (stále na něj ukazuje l). Pak ještě posuneme l na nový první prvek.

V případě, že se jedná o poslední prvek, potřebujeme získat ukazatel na předposlední prvek. Použijeme pomocnou proměnnou m, která projde v cyklu prvky od prvního až k prvku, který má jako následníka poslední prvek. U předposledního prvku zapíšeme, že nemá následníka a pak můžeme zrušit poslední prvek a přesunout ukazatel l na bývalý předposlední prvek.

Ke zrušení prvku v prostředku seznamu se použije malý trik. Ve skutečnosti budeme rušit jeho následníka, ovšem zkopírujeme hodnotu a ukazatel z následníka do aktuálního prvku. Tím ze seznamu odstraníme rušenou hodnotu.

V případě, že se uživatel rozhodne ukončit aplikaci, zrušíme také celý seznam. Ve chvíli, kdy uživatel ukončí aplikaci, se vyvolává událost OnClose formuláře. My ještě můžeme na tuto událost reagovat a provést akce, které souvisejí s ukončením aplikace. Můžeme třeba i nepovolit ukončení aplikace. V proceduře FormClose tedy zrušíme vytvořený seznam zavoláním procedury Zrus. Paměť použitá pro dynamické proměnné tak bude uvolněna.

Naprogramujte operace s jednosměrným setříděným seznamem. (seznam2.dpr)

Jedná se pouze o malé rozšíření předchozího příkladu. Práce se seznamem, datové typy i zpracování je úplně stejné jako v předchozím příkladu. Jediný rozdíl je v proceduře pro přidávání nového prvku. Protože má být seznam setříděný, musíme pro nový prvek najít správnou pozici v seznamu. Musíme rozlišit případ, kdy je seznam prázdný a kdy jsou v seznamu prvky. Pokud už v seznamu nějaké prvky jsou, musíme pro novou hodnotu rozlišit případy, kdy patří na začátek seznamu, konec seznamu nebo doprostřed seznamu:

procedure TForm1.Button1Click(Sender: TObject);
var n:integer;
m:Uk;
begin
New(m);
n:=Random(100)+1;
if k<>nil then
  begin
  l:=k;
  while ((l^.hod<=n) and (l^.dal<>nil)) do
    l:=l^.dal;
  if l^.hod>n then //zatřidit
    if k=l then //na první misto
      begin
      m^.hod:=n;
      m^.dal:=k;
      k:=m;
      l:=k;
      end
    else //doprostřed
      begin
      m^.dal:=l^.dal;
      m^.hod:=l^.hod;
      l^.dal:=m;
      l^.hod:=n;
      end
  else //na konec
    begin
    l^.dal:=m;
    m^.hod:=n;
    m^.dal:=nil;
    l:=m;
    end
  end
else //první prvek
  begin
  m^.hod:=n;
  m^.dal:=nil;
  k:=m;
  l:=k;
  end;
PisPrvek(l);
PisSeznam(k);
end;

Patří-li hodnota doprostřed seznamu, použijeme kopii obsahu proměnné, na kterou ukazuje l, do nové dynamické proměnné. Novou hodnotu pak zapíšeme do prvku, kam ukazuje l.

Naprogramujte operace s obousměrným seznamem. (seznam3.dpr)

V záznamu přidáme položku pred, která je ukazatelem na předchozí prvek. Nové prvky obousměrného seznamu přidáváme na aktuální pozici v seznamu, není třeba si pamatovat ukazatel na začátek seznamu. V tomto příkladu tedy budeme pracovat s jediným globálním ukazatelem, který určuje aktuální prvek v seznamu. Tomu budeme muset přizpůsobit procedury PisSeznam, kde musíme začít výpis od začátku seznamu (musíme dojít na začátek) a dále proceduru Zrus, kdy musíme projít úsek nalevo i napravo od aktuálního prvku. V memu budeme opět vypisovat celý seznam, v labelech vypíšeme vždy hodnotu aktuálního prvku, jeho předchůdce a následníka.

Zásobníku se říká LIFO z anglického Last In First Out, tedy “poslední dovnitř, první ven”. Hodnoty, které se ukládají do zásobníku, se postupně uchovávají a pokud vybírám hodnotu ze zásobníku, vezmu hodnotu, která do zásobníku přibyla naposledy. Nová hodnota se tedy přidává na tzv. vrchol zásobníku, odkud se hodnota také vybírá. Při realizaci zásobníku pomocí seznamu si tedy stačí pamatovat ukazatel na začátek seznamu, který představuje vrchol zásobníku. Nové hodnoty se do seznamu přidávají na začátek, stejně tak ze začátku seznamu se hodnoty získávají. Výběr hodnoty ze zásobníku znamená zrušení příslušného prvku v seznamu.

Naprogramujte zásobník s použitím dynamických proměnných. (zasob.dpr)

Zásobník budeme reprezentovat jednosměrným seznamem prvků. Použijeme stejnou strukturu, jako u příkladů s jednosměrným seznamem. Jediný ukazatel, který si je třeba pamatovat, je ukazatel na vrchol zásobníku. Do zásobníku budeme vkládat náhodná čísla z intervalu 1..100. Vložení čísla do zásobníku zajistí procedura Pridej, která jako parametr dostane ukazatel na zásobník a přidávanou hodnotu. Vytvoří novou dynamickou proměnnou, kterou připojí na začátek seznamu a aktualizuje hodnotu ukazatele na vrchol zásobníku.

Výběr ze zásobníku realizujeme funkcí Vyber. Tato funkce dostane jako parametr ukazatel na vrchol zásobníku, zruší první prvek seznamu a vrátí jeho hodnotu. Využijeme toho, že pracujeme pouze s čísly z intervalu 1..100, a pokud budeme volat funkci Vyber a zásobník bude prázdný, návratová hodnota funkce bude nula.

Na formuláři jsou 2 tlačítka. První vkládá do zásobníku nové číslo a druhé číslo vybírá. Obsah zásobníku je graficky znázorněn. Vypisujeme na Canvas formuláře vždy maximálně 10 prvků ze zásobníku. Pro zjednodušení výpisu máme deklarovánu globální proměnnou Pocet, jejíž hodnota udává, kolik je v zásobníku čísel. Pokud počet čísel v zásobníku přesáhne 10, zobrazíme komponentu ScrollBar, která umožní procházet celý zásobník.

Komponenta ScrollBar (posuvná lišta), jejíž zástupce se nachází na liště Standard čtvrtý zprava, má podobně jako UpDown vlastnosti Min, Max a Position. Pozice (a současně hodnota vlastnosti Position) na ScrollBaru je indikována posuvným obdélníkem. Pokud počet čísel přesáhne 10, zobrazíme ScrollBar a v reakci na jeho událost OnScroll, která se vyvolává, pokud uživatel mění myší nebo klávesnicí pozici ScrollBaru, měníme zobrazená čísla ze zásobníku. Po každém přidání nebo ubrání čísla ze zásobníku rozhodujeme, zda bude ScrollBar zobrazen a aktualizujeme vlastnost Max ScrollBaru podle počtu čísel v zásobníku na hodnotu Pocet-10.

Výpis zásobníku realizuje procedura Zobraz, která dostává jako parametr ukazatel na vrchol zásobníku a pořadí čísla od dna zásobníku, které se má ve výstupu objevit nejvýše. Pokud je čísel 10 a méně, zobrazí se celý zásobník, je-li jich více, je začátek seznamu přeskočen. Procedura Zobraz je volána po kliknutí na tlačítka nebo po posunu ScrollBaru.

Procedury připravené pro práci se zásobníkem (Init, Pridej, Vyber) bychom mohli využívat opakovaně i pro práci s několika zásobníky najednou. Zásobník je určen vždy pouze ukazatelem, který předáváme jako parametr. Procedura zobraz je však závislá na hodnotě globální proměnné Pocet. Tuto hodnotu bychom však také mohli předávat jako parametr a zobecnit tak proceduru Zobraz pro práci s více zásobníky. Typicky však do zásobníku “není vidět” a používá se pouze vnitřně pro zpracování různých úloh.

Naprogramujte frontu s použitím dynamických proměnných. (fronta.dpr)

Proměnná, která bude určovat frontu, bude tedy typu záznam se dvěma složkami, ukazateli na začátek a konec fronty. Tato proměnná se využije jako parametr pro procedury Init, Pridej a Vyber, které realizují práci s frontou. Jejich zápis je přizpůsoben frontě, zápis reakcí na přidání a vybrání prvku prostřednictvím stisku tlačítek je však prakticky totožný s předchozím příkladem. Procedurám reagujícím na stisk tlačítek pro vložení a vybrání prvku je jedno, jak jsou prvky ukládány a vybírány, důležité je, že prvek může být uložen a vybrán.

Naprosto analogické je také zrušení zbylých prvků ve frontě při ukončení aplikace a volání inicializace fronty při spuštění aplikace.

Pokud bych nepřidával v těchto dvou programech grafický výstup, procedury reagující na přidání nebo vybrání prvku by byly zcela shodné. Pouze bych pracoval v případě zásobníku s proměnnou typu ukazatel, která ukazuje na vrchol zásobníku, a v případě fronty s proměnnou typu záznam, která určuje její začátek a konec. Bez použití seznamů můžeme zásobník a frontu realizovat staticky pomocí pole, počet prvků je však omezen rozsahem pole.

Binární vyhledávací strom je další datová struktura, která slouží k uchování hodnot a realizuje se typicky použitím dynamických proměnných. Strom je datová struktura, kde je jeden prvek tzv. kořen (v následujícím obrázku prvek s hodnotou 32). Kořen může mít následníky, tyto následníci další následníky atd. Vzniká tak struktura, kterou můžeme rozdělit do jednotlivých vrstev podle vzdálenosti prvků od kořenu. Pro binární strom platí, že každý prvek stromu má maximálně dva následníky (levého a pravého). Binární vyhledávací strom je pak specielním případem stromu, do kterého vkládáme hodnoty podle určitých pravidel. Pro každý prvek platí, že všichni jeho leví následníci mají menší hodnotu, všichni praví následníci mají hodnotu větší. Pro každý prvek, který chceme přidat do binárního vyhledávacího stromu, tak najdeme jednoznačné místo, kam ho uložit.

Všimněte si, že pokud bychom prošli prvky stromu zleva doprava, tak jak jsou zapsány na obrázku, jsou hodnoty setříděné od nejmenší do největší. Takový výpis je jednou z možných operací s binárním vyhledávacím stromem. Je to však náročnější operace, stejně jako vypouštění prvků ze stromu. Zpracujeme tedy pouze jednodušší operace.

Naprogramujte přidávání prvků do binárního vyhledávacího stromu. (strom1.dpr)

Pokud chceme přidat nový prvek, po kliknutí na tlačítko se generuje náhodně hodnota z intervalu 1..100 a najde se pro ní správné umístění ve stromu. Tlačítka s šipkami slouží pro zobrazení levého resp. pravého následníka. Tlačítko se čtvercem zobrazí kořen stromu. V memu se vypisují hodnoty v pořadí, jak byly vygenerovány. Výpis hodnot v memu nesouvisí s jejich uložením ve stromu. Po kliknutí na tlačítko pro rušení stromu je zrušen celý strom. Stejně tak se ruší celý strom při ukončení aplikace.

Pro práci se stromem definujeme typ záznam, který obsahuje hodnotu a ukazatele na levého a pravého následníka. Dále využijeme dvě proměnné typu ukazatel. Proměnná k ukazuje na kořen stromu, proměnna l na aktuální prvek. Procedura PisPrvek dostane jako parametr ukazatel na aktuální prvek a vypíše ho do labelu včetně hodnot jeho následníků.

Reakce na stisk tlačítek pro zobrazení následníků jsou velmi jednoduché. Pokud má zobrazený prvek následníka, posuneme se na něj a zobrazíme ho. Při přechodu do kořene stromu pouze nastavíme aktuální pozici na ukazatel na kořen stromu a prvek v kořeni vypíšeme.

Přidávání prvku je zajímavější. Vytvoříme novou dynamickou proměnnou m, jako její hodnotu zapíšeme vygenerované číslo n a levého i pravého následníka nastavíme na nil. Nová hodnota se stane tzv. listem stromu (nemá následníky). Použijeme pomocnou proměnnou p, ve které si pamatujeme předka pro novou dynamickou proměnnou. Strom procházíme od kořene vždy tím směrem, aby byla zachována vlastnost binárního vyhledávacího stromu. Tedy pokud je nová hodnota menší než hodnota v testovaném prvku, posuneme se doleva, jinak se posuneme doprava (tedy pokud se vyskytnou některé hodnoty vícekrát, umísťují se vpravo). Takto postupujeme tak dlouho, až najdeme prvek, ke kterému připojíme novou dynamickou proměnnou m jako následníka. Pokud zadáváme první prvek, vytvoří se kořen, jinak připojíme list.

Největší problémy způsobí zrušení této dynamické struktury. Pokud chceme zrušit strom, znamená to projít všechny jeho prvky a žádný nevynechat. Je nutné si uvědomit, že pokud přejdeme na následníka nějakého prvku, k původnímu prvku není možné se přímo vrátit. Jedna z variant by byla rozšířit datovou strukturu o ukazatel na předchůdce. Toto řešení se však nepoužívá. Lepší je pamatovat si dosud nezrušené prvky a vracet se k nim.

Naprogramujte přidávání prvků do binárního stromu. Strom rušte pomocí fronty. (strom2.dpr)

Na začátku těla procedury dám do fronty kořen stromu a v cyklu, který probíhá, dokud není fronta prázdná, vybírám prvek z fronty, zapisuji do fronty jeho následníky a vybraný prvek ruším:

Po výběru prvku z fronty opět ruším prvek fronty. Jakmile je fronta prázdná, je zrušen celý strom i všechny prvky fronty.

Naprogramujte přidávání prvků do binárního stromu. Strom rušte pomocí rekurzivní procedury. (strom3.dpr)

Celé zpracování příkladu zůstává stejné, změníme pouze opět způsob, jak rušit celý strom. Struktura binárního stromu je v podstatě rekurzivní strukturou. Část stromu má stejnou strukturu jako celý strom. Procedura Zrus bude tentokrát rekurzivní.

Pokud chceme rušit binární strom, znamená to zrušit kořen a zrušit oba podstromy. První podstrom má kořen v levém následníkovi, druhý podstrom má kořen v následníkovi pravém. Podstromy se pak zruší stejným způsobem. Procedura Zrus dostane jako parametr ukazatel na kořen stromu. Pokud má tento prvek stromu levého následníka, volá tato procedura sama sebe s ukazatelem na levého následníka jako s parametrem. Stejná situace je u pravého podstromu. Nakonec zrušíme prvek, na který ukazuje parametr.

V proceduře FormClose voláme proceduru Zrus pouze tehdy, je-li ve stromu alespoň jeden prvek (kořen). Toto řešení je velice jednoduché a není třeba využívat žádné další datové struktury. Je to varianta průchodu do hloubky, pořadí rušení prvků je však jiné, než při použití zásobníku. Při tomto zápisu je nejdříve rušen list zcela vlevo a postupně se zleva ruší nejmenší podstromy. Mírnou modifikací této procedury bychom získali proceduru, která vypíše prvky binárního vyhledávacího stromu od nejmenšího k největšímu, tedy setříděné.

Využití dynamických datových struktur je velmi výhodné ve chvíli, kdy nevíme s jakým množstvím dat budeme pracovat. Typicky využíváme záznamy, které obsahují hodnotu a ukazatele na další záznamy. Pro uložení jedné hodnoty tak potřebujeme více místa v paměti a toto řešení je tedy náročnější na paměť, než práce se statickými proměnnými. Pokud vytváříme nové dynamické proměnné, měli bychom je také rušit, když je už nepotřebujeme. I když Delphi po ukončení aplikace automaticky uvolňují veškerou použitou paměť, ve všech příkladech jsme před ukončením aplikace rušili vytvořené struktury. Použití dynamické datové struktury může být pouze jednou z částí větší aplikace a v dalších částech aplikace je pak možné uvolněnou paměť znovu využít (ve starších verzích Pascalu nebyla paměť po ukončení programu automaticky uvolňována a rušení použitých dynamických proměnných tedy bylo nutné).