(následující stručný text nenahrazuje výklad, je jen podkladem pro cvičení)
Pokud potřebujeme pracovat s maticí dat, nadeklarujeme si ji jako pole.
a : array[1..100] of integer;
V poli se pohybujeme pomocí indexu. Často používáme klasický cyklys for - do. Pokud ovšem potřebujeme proměnnou velikost pole, máme na výběr dvě možnosti.
Nadeklarujeme největší předpokládanou délku. Někde si pak pamatujeme aktuální počet prvků. Pokud by počet prvků po přidání dalšího mohl překročit deklarovanou velikost, ohlásíme chybu a operaci odmítneme.
Použijeme jako mez pole konstantu. Velikost pole pak ale můžeme měnit jen znovupřeložením programu. Pascal totiž proměnnou velikost pole nezná.
Častější je kombinace obojího.
Občas přicházejí požadavky tak, že je třeba si je někde na chvilku zapamatovat, než na ně přijde řada. Ze statických struktur pak přichází v úvahu fronta (takřka výhradně kruhová) a zásobník.
Fronta na úřadech a podobně funguje tak, že po odbavení se všichni o jedno místo posunou. Při programování by to bylo neefektivní, je snazší posouvat odbavovací okénko. V počítačovém světě také nepoznáme, zda kolonka na číslo je obsazena číslem, a musíme si to proto pamatovat zvlášť (vždy nějaké číslo obsahuje, jen nemá žádný smysl). Proto jako doplněk k poli máme dva ukazatele:
1. ukazatel na prvek, který bude příště na řadě, takzvaný začátek fronty.
2. ukazatel na konec fronty. Až někdy budete podobný problém řešit, přesvědčíte se, že je snazší ukazovat nikoli na poslední prvek v řadě, ale na první volnou pozici. Situace začátek=konec pak má význam prázdné fronty.
Pokud se kterýkoli z ukazatelů po jeho posunutí dostane mimo pole, vrací se z druhé strany na začátek. Například pro pole deklarované zápisem
fronta : array[0..10] of integer;
se posunutí provede příkazem (např. pro začátek fronty):
zac := (zac+1) mod 11;
Pokud se ukazatel posune na jedenácté políčko (mimo matici), je přesunut znovu na začátek.
Průběžně se musí hlídat, zda nedojde k přeplnění fronty. Výše jsem uváděl, že rovnost obou ukazatelů znamená prázdnou frontu. Je tedy logické, že k ní nesmí dojít přidáním prvku do fronty, ale pouze jeho odebráním. Pokud by se mělo přidáním prvku dosáhnout rovnosti ukazatelů, je třeba takový prvek odmítnout (přeplnění fronty).
Zásobník je mnohem jednodušší, má totiž jen vrchol zásobníku. Ve frontě je nejdéle čekající první na řadě (FIFO znamená first in, first out), kdežto v zásobníku poslední (LIFO, last in, first out). Snazší obsluha je opět, pokud ukazatel zásobníku ukazuje na první volné místo. Pokud pak máme nadeklarovámu matici, stejnou jako nahoře, pak při nulové hodnotě ukazatele je zásobník prázdný (a je nutno zabránit každému pokusu odebrat další prvek). Naproti tomu při vložení posledního prvku si můžeme dovolit posunout ukazatel mimo zásobník; může tedy nabívat hodnot od nuly do jedenácti. 0 znamená prázdný zásobník, 11 plný (a pokus o zápis vyvolá přetečení zásobníku). Ve strojovém kódu počítače je zásobník vzhůru nohama (začíná "nahoře" a končí "dole"). Realizace strojovými prostředky je pak ještě jednodušší.
Často se nám stává, že v poli záznamů potřebujeme zaznamenávat proměnné, nadeklarované pomocí klíčového slova record. Klasický příklad představuje seznam zaměstnanců, ale vlastně i každá jiná malá databáze, kvůli které by nestálo za to nutit uživatele, aby si spolu s programem instaloval nějaké dll moduly. Například pole pro evidenci 100 zaměstnanců (max.) by pak mohlo vypadat následovně:
type
os = record
jmeno : string[30];
prijmeni : string[39];
adresa_ulice : string[59];
adresa_mesto : string[59];
psc : string[5];
telefon : string[15];
end;
var
lide : array[0..99] of os;
Při dnešních cenách pamětí to nehraje velkou roli, ale velký rozsah dat se nám vrátí znovu, pokud budeme potřebovat s daty jakkoli manipulovat (například je setřídit). Proto je někdy výhodnější použít dynamicky alokované paměti a v poli držet jen ukazatele na data. Připravíme si obdobný datový typ (os) a ukazatel na něj (uos). V části deklarace proměnných (kapitola var) pak nadefinujeme pole pouze s ukazateli, nikoli s daty (jeden ukazatel má velikost 4 byty).
type
uos = ^os; {vyjímka - zde je použití před deklarací přípustné, protože je předem
známa velikost v paměti; později u struktur by to jinak ani nešlo napsat}
os = record
jmeno : string[30];
prijmeni : string[39];
adresa_ulice : string[59];
adresa_mesto : string[59];
psc : string[5];
telefon : string[15];
end;
var
lide : array[0..99] of uos;
V paměti je ovšem nyní místo záznamu jen ukazatel na záznam. Pokud budeme chtít někdy tento záznam použít, musíme ukazateli přiřadit úsek paměti, kde bude záznam uložen. Učiníme tak tím, že před prvním jeho použitím vyvoláme funkci new( ). Tato funkce nám přidělí volný prostor, se kterým pak můžeme pracovat. Prostor má velikost, danou velikostí deklarovaného záznamu, a nesmí se překročit (zpravidla zde není žádná kontrola před přepsáním další položky). Poté, co již paměť nepotřebujeme, můžeme ji vrátit příkazem dispose( ). Sama se vrátí systému po ukončení běhu programu.
Paměťový prostor pro každou buňku pole můžeme nadeklarovat na začátku tím, že před poslední řádek programu (je zde end s tečkou) vložíme direktivu initialization a vhodný cyklus, který si vyžádá místo v paměti a naplní buňky prázdnými hodnotami (část programu za initialization se provede úplně první bezprostředně poté, co je program spuštěn. Toto klíčové slovo nahrazuje dříve v Pascalu obvyklé begin, patřící k end s tečkou, a vyznačující hlavní program. Tento begin sice vnitřní překladač Pascalu přeloží správně, ale prostředí Delphi při jeho použití generuje další procedury na špatné místo).
initialization
for i:=0 to 99 do begin
new(lide[i]);
lide[i]^.jmeno:='';
lide[i]^.prijmeni:='';
lide[i]^.adresa_ulice:='';
lide[i]^.adresa_mesto:='';
lide[i]^.psc:='';
lide[i]^.telefon:='';
end;
end.
Naše nové datové typy musíme doplnit až za stávající deklaraci typu TForm1:
type
TForm1 = class(TForm)
Memo1: TMemo;
Button1: TButton;
Button2: TButton;
private
{ Private declarations }
public
{ Public declarations }
end;
uos = ^os; {vyjímka - zde je použití před deklarací přípustné, protože je předem
známa velikost v paměti; později u struktur by to jinak ani nešlo napsat}
os = record
jmeno : string[30];
prijmeni : string[39];
adresa_ulice : string[59];
adresa_mesto : string[59];
psc : string[5];
telefon : string[15];
end;
Rovněž opíšeme část, následující za initialization. V místech, kde je třeba měnit hodnotu některého ze záznamů, pak má odkaz tvar jméno pole - index položky v hranatých závorkách - (tím se dosteneme k ukazateli) - stříška - tečka pro oddělení jména položky - jméno položky. Například, pokud máme v políčku SpinEdit1 číslo měněného řádku matice, a políčko Edit1 obsahuje jméno zaměstnance, lze je měnit v paměti (jako odezvu na událost Edit1: OnChange) následujícím příkazem:
procedure TForm1.Edit1Change(Sender: TObject);
begin
os[SpinEdit1.Value]^.jmeno:=Edit1.Text;
end;
Vzhledem k tomu, že na toto cvičení připadá test a není tedy tolik času, můžete si toto téma procvičit někdy ve svém volném čase. V následujícím se budeme věnovat dynamickým datovým strukturám.
Dynamické datové struktury řeší jednak problém přístupu k velkému množství dat (to se netýká těch dnešních - již nahoře jste viděli, že zásobník a fronta se nechají snadno vytvořit v Pascalu jako pole, ať již obsahuje kompletní záznamy, nebo jen ukazatele na ně), jednak problémy s alokací paměti, kdy při překladu, nebo ani při spuštění programu nemusí být známo, která z dat zaberou jakou velikost a bylo by neefektivní si nechat velkou rezervu při deklaraci jednoho s polí a pak nevystačit při kapacitě nějakého jiného.
Dynamické datové struktury se vyznačují tím, že každý záznam obsahuje ukazatel na nějaký další záznam, nebo alespoň na všechny záznamy kromě několika vyjímek ukazují jen ukazatele, které jsou součástí jiných záznamů (v Pascalu existuje alternativní deklarace typu, takže koncové záznamy nemusí prvek ukazatele vůbec obsahovat). Přesněji řečeno, o dynamické struktuře mluvíme právě jen tehdy, platí-li předchozí věta. Data, umístěná do dynamicky deklarované paměti, na které je ovšem ukazováno polem ukazatelů, ať již jsou zpracovávána jako zásobník, fronta, nebo obyčejné pole, nejsou dynamickou datovou strukturou.
V zájmu lepší představivosti znázorňujeme nejen strukturu, ale i její činnost velmi často graficky.
(obrázek představuje lineární spojový seznam, anglicky linked list; "zac" je proměnná, deklarovaná ve statické paměti, jak jsme byli doposud zvyklí).
Pro školní příklad použijeme deklaraci jen s jedním textovým řetězcem v prvku. Chování programu bude ovšem stejné:
type
TForm1 = class(TForm)
Memo1: TMemo;
Button1: TButton;
Button2: TButton;
Edit1: TEdit;
procedure Button1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
uos = ^tos;
tos = record
text : string[55];
dalsi : uos;
end;
var
Form1: TForm1;
p : uos;
const
zac : uos = nil;
implementation
Najdeme poslední prvek a vložíme do něj místo nil ukazatel na nově zgenerovaný prvek (prvek vygenerujeme tak, že pro něj požádáme o paměť procedurou new; pokud by se nejednalo o záznamy (record), ale objekty (object), museli bychom požádat prvek pomocí jeho procedury create, aby se vytvořil sám). Nakonec nově zgenerovaný prvek vyplníme:
Samotná procedura pro obsluhu přídání dalšího prvku na konec seznamu pak bude vypadat následovně:
procedure TForm1.Button1Click(Sender: TObject);
var
p : uos;
begin
p:=zac;
if p=nil then
begin
new(zac);
p:=zac;
end
else
begin
while p^.dalsi<>nil do p:=p^.dalsi;
new(p^.dalsi);
p:=p^.dalsi;
end;
p^.dalsi := nil;
p^.text := Edit1.Text;
end;
Hotový program je kupodivu zde. Ještě jednodušší by bylo, kdybychom nový prvek přidávali na začátek seznamu - nemusíme totiž ošetřovat případ, že seznam je na začátku prázdný - je lhostejné, zda do nově vygenerovaného prvku do ukazatele "další" zapíšeme počáteční nil, či minulou hodnotu adresy prvního prvku v paměti; samozřejmě také odpadá vyhledání konce seznamu:
procedure TForm1.Button3Click(Sender: TObject);
var
p : uos;
begin
p:=zac;
new(zac);
zac^.dalsi := p;
zac^.text := Edit1.Text;
end;
Podotýkám, že tlačítko je označeno jako třetí - na druhé si můžeme připravit výpis. Bez výpisu těžko zjistíme, zda zde nějaká data opravdu jsou. Výpis bude asi nejjednodušší směřovat do vhodné komponenty memo:
procedure TForm1.Button2Click(Sender: TObject);
var
p : uos;
begin
p:=zac;
Memo1.Lines.Clear;
while p<>nil do begin
Memo1.Lines.Add(p^.text);
p:=p^.dalsi;
end;
end;
Pro realizaci zásobníku a fronty budeme potřebovat ještě odebrání prvku ze začátku seznamu. Odebraný prvek nějak zpracujeme (zde to simuluje jeho zobrazení pomocí procedury "showmessage") a jím zabírané místo v paměti následně vrátíme procedurou dispose (u objektů bychom volali jejich proceduru done, čímž objekt požádáme, zby se zrušil sám):
procedure TForm1.Button4Click(Sender: TObject);
var
p : uos;
begin
if zac=nil then ShowMessage('Seznam je prázdný')
else
begin
p:=zac^.dalsi;
ShowMessage('Odstraněn prvek: '+zac^.text);
dispose(zac);
zac:=p;
end;
end;
Častěji ovšem budeme přidávat prvky doprostřed. Protože přidání či smazání prvku bude vždy předcházet vyhledávání, napišme si nejprve proceduru pro vyhledání konkrétního prvku (například za účelem změn obsahu prvku):
procedure TForm1.Button5Click(Sender: TObject);
var
p : uos;
begin
p:=zac;
while (p<>nil) and (p^.text<>Edit1.Text) do p:=p^.dalsi;
if p^.text<>Edit1.Text then ShowMessage('Nenašlo se')
else ShowMessage('Naslo se'); {či případná obsluha}
end;
Vkládání nového prvku bude probíhat obdobně, ale pokud řadíme doprostřed, tedy podle nějaké podmínky (například podle abecedy), nutně vždy dojde k přeběhnutí - to, že jsme prvek měli zařadit, zjistíme, až když jsme u prvku, který měl zůstat za (první nesplňuje danou podmínku řazení). Pokud budeme provádět předběžnou analýzu (před přesunem na další prvek), bude schema vypadat následovně:
Můžeme si připravit program - nejprve za předpokladu, že prvek nebude ani první, ani poslední:
procedure TForm1.Button6Click(Sender: TObject);
var
p, q : uos;
begin
p:=zac;
q:=p^.dalsi;
while (p<>nil) and (q<>nil) and (q^.text<Edit1.Text) do
begin
p:=q;
q:=p^.dalsi;
end;
if q^.text>Edit1.Text then
begin
new(q);
q^.text:=Edit1.Text;
q^.dalsi:=p^.dalsi;
p^.dalsi:=q;
end;
end;
Protože prvek může být i první i poslední, musíme tyto alternativy ošetřit:
procedure TForm1.Button6Click(Sender: TObject);
var
p, q : uos;
begin
if zac=nil then begin {nejprve je nutno ošetřit úplně prázdný seznam}
new(zac);
zac^.dalsi := nil;
zac^.text := Edit1.Text;
exit; {konec procedury}
end;
p:=zac;
if p^.text>Edit1.Text then {varianta pro případ, že nový prvek bude první}
begin
new(zac);
zac^.text:=Edit1.Text;
zac^.dalsi:=p;
exit; {konec procedury}
end
q:=p^.dalsi;
while (p<>nil) and (q<>nil) and (q^.text<Edit1.Text) do
begin
p:=q;
q:=p^.dalsi;
end;
if q^.text>Edit1.Text then
begin
new(q);
q^.text:=Edit1.Text;
q^.dalsi:=p^.dalsi;
p^.dalsi:=q;
end
else {přidání na konec - žádný prvek není podle řadicího kritéria větší}
begin
new(p^.dalsi);
q^.text:=Edit1.Text;
q^.dalsi:=nil;
end;
end;
Uvedený program jsem netestoval, mohou v něm být chyby. Přesto zřetelně naznačuje, o jak komplikované řešení se jedná. Proto se zpravidla využívá kratší vyhledávací algoritmus (také často používaný z důvodu rychlejšího programu). Postup je takový, že pokud hledáme jen jedním pointerem, nemůžeme se vrátit o krok zpět; řešením pak je, že volné místo vytvoříme až za aktuálím prvkem, a aby bylo zachováno řazení, celý obsah akruálního prvku do něj přeneseme; novou hodnotu zapíšeme místo aktuálního prvku, dle následujícího schematu - fialově je nově vytvořené místo, šedé jsou stávající údaje, červeně nově vytvářený prvek:
Toto řešení již bylo několikrát položeno jako otázka u státnic v okruhu Informatika. V Pascalu by procedura mohla vypadat asi takto (u státnic není řešení v konkrétním jazyce třeba, stačí malovat obdélníčky):
procedure TForm1.Button6Click(Sender: TObject);
var
p, q : uos;
begin
if zac=nil then begin {nejprve je nutno ošetřit úplně prázdný seznam}
new(zac);
zac^.dalsi := nil;
zac^.text := Edit1.Text;
exit; {konec procedury}
end;
p:=zac;
while (p^.dalsi<>nil) and (p^.text<Edit1.Text) do p:=p^.dalsi;
if p^.text>Edit1.Text then
begin
new(q);
q^.text:=p^.text;
q^.dalsi:=p^.dalsi;
p^.dalsi:=q;
p^.text:=Edit1.Text;
end
else {přidání na konec - žádný prvek není podle řadicího kritéria větší}
begin
new(p^.dalsi);
p:=p^.dalsi;
p^.text:=Edit1.Text;
p^.dalsi:=nil;
end;
end;
Někdy potřebujeme vypustit prvek (zde 'Bart') ze seznamu:
Opět - nalezneme prvek, ale vypustit musíme následující, abychom neporušili strukturu. Proto na následující ukážeme pomocným ukazatelem q, pak jeho obsah překopírujeme do aktuálního (na který ukazuje p). Následně uvilníme paměť od prvku, na který ukazuje q - to je jediný důvod, proč zakládat další proměnnou a nepsat všude jen p^.dalsi; po zkopírování ukazatele z rušeného prvku na něj již nic jiného neukazuje (p^.dalsi jsme si právě přepsali).
Proceduru si zkuste napsat sami (nyní již je zřejmé jak).
Poznámka - nutno ošetřit zcela prázdný strom a smazání posledního prvku (do kterého již nelze nic překopírovat).
Problém odebrání posledního prvku by řešilo takzvané rekurzivní volání, s využitím předávání pointru odkazem (var). Výhodou tohoto řešení je, že i když jsme "uvnitř" právě prohlížené proměnné, máme nejen její adresu, ale díky volání odkazem pracujeme přímo s proměnnou, která "sem" ukazuje, takže ji můžeme změnit. Nevýhodou je, že místo přesunu na další prvek se volá znovu procedura - každé volání procedury nás stojí na zásobníku minimálně 4 + 4 + 4 byty (ukládá se návratová adresa, registr EBP a adresa naší proměnné). Následující řešení přidání prvku zabere na každé volání ještě další 4 byty, protože obsahuje lokální proměnnou q; alternativní řešení by bylo použít globální proměnnou - v tomto případě by to bylo odůvodnitelné. Rekurzivně volaná procedura by vypadala následovně:
procedure pridej(var p: uos);
var
q : uos; {proměnná by mohla být mezi globálními, kdyby se nepoužila jinde}
begin
if p=nil then
begin {ukládáme na konec seznamu}
new(p); {nové místo se vytvoří tam, kde má}
p^.dalsi := nil;
p^.text := Form1.Edit1.Text; {nutno uvést celé jméno proměnné}
end
else
if p^.text<Form1.Edit1.Text
then pridej(p^.dalsi) {klíčové místo - rekurzivní volání}
else
begin
q:=p;
new(p); {nové místo se vytvoří tam, kde má - ukazatel sem již ukazuje}
p^.dalsi:=q;
p^.text:=Form1.Edit1.Text;
end;
end;
Je třeba ji odněkud zavolat, například ze sedmého tlačítka (vhodná počáteční adresa je naše proměnná zac):
procedure TForm1.Button7Click(Sender: TObject);
begin
pridej(zac);
end;
Rekurzivní odebrání prvku ze seznamu si zkuste napsat sami.
Deklarace procedury musí předcházet jejímu použití, pokud ovšem není uvedena v hlavičce unity (část před klíčovým slovem implementation); není-li ji možné zapsat celou (například používá později definované procedury), je třeba uvést alespoň její první řádek ("procedure...") s uvedením parametrů a za něj (až za středník) doplnit direktivu forward; . Až budeme později proceduru deklarovat, musíme první řádek uvést v identickém tvaru (použijte Ctrl+C a V a smažte "forward"). Dovolil bych si uvést, že podobně jako příkaz skoku jsem to v Pascalu ještě nikdy nepotřeboval (často zmiňovanou vyjímkou jsou dvě procedury, které se vzájemně rekurzívně volají).