Všechny typy proměnných, se kterými jsme se doposud setkali, byly statické. Nemohli jsme je vytvářet a rušit za běhu programu. Nyní se podíváme, jak toto omezení obejít.
Prvně si ovšem musíme objasnit pár slovíček:
statická proměnná = proměnná, který v paměti zabírá předem
stanovené místo. Potřebné místo se zabírá (alokuje) již při překladu
(=spuštění) programu. Pole a všechny proměnné, které jsme až dosud
poznali (kromě typu soubor), jsou statické. Například nemůžeme do stoprvkového
pole přidat sto prvý prvek.
Lze to sice obejít pomocí toho, že definujeme pole s většími rozměry, než
jsou potřeba, ale není to ideální řešení - zabíráme zbytečně místo v
paměti a nemůžeme vědět, že jsme ho alokovali dost i pro náročné
údaje. (Dobře, mám seřadit několika prvků, tak si nadefinuji 1000 prvkové
pole, bude sice z větší části nevyužito, ale co když nějaký šílenec
zadá 9999 hodnot?...)
dynamická proměnná = proměnná, která se vytvoří až v průběhu
programu.
S dynamickými proměnnými se musí manipulovat
pomocí ukazatelů (nemůžeme totiž dopředu znát jejich název...). Pořádně si zopakujte použití ukazatelů (minulá lekce).
K práci s dynamickými proměnnými slouží několik procedur:
| Abecední pořadí | Příkaz | Význam |
|---|---|---|
| 1 | New(Ukazatel); | procedura vytvoří novou dynamickou proměnnou a nastaví na ni ukazatel Ukazatel |
| 2 | Dispose(Ukazatel); | procedura zruší dynamickou proměnnou, na kterou ukazuje ukazatel Ukazatel |
Ukažme si to na příkladu:
program Ukazka;
type PString = ^string;
var retezec : Pstring;
begin
New(retezec); {Vytvoří novou dynamickou proměnnou typu string}
retezec^:='Ahoj lidi';
Writeln(retezec^);
Dispose(retezec); {Zruší dynamickou proměnnou, na kterou ukazuje retezec}
New(retezec); {Nová dynamická proměnná, s původní vůbec nesouvisí}
Writeln(retezec^);
Dispose(retezec);
Readln;
end.
Dynamická proměnná má ten typ, na který ukazuje daný ukazatel. Nyní již umíme s dynamickými proměnnými zacházet. Osamostatněná dynamická proměnná výhody nepřináší, ale existují tzv. seznamy proměnných. (Existence seznamu je umožněna jednou zvláštností typu ukazatel).
Definujeme-li ukazatel, nemusíme předem definovat typ, na který ukazuje.
(Ale musíme ho dodefinovat později).
Toto jsou tedy zcela správné zápisy:
type PJmeno = ^Jmeno;
PSeznam = ^Seznam;
Jmeno = string;
Seznam = record
Prijmeni : string;
Dalsi : PSeznam;
end;
Měli-li jsme jednoduchou dynamickou proměnnou, nemohli jsme nadefinovat novou, neboť ta původní by se nám ztratila. Jak vidíte na příkladu, dovoluje nám zvláštnost ukazatele dynamické proměnné "zřetězit". Někde si uděláme ukazatel na první proměnnou, ta bude ukazovat na druhou, ta na třetí....
Takto zřetězeným proměnným se říká seznam. Rozlišujeme dva druhy seznamů.
Ostatní druhy seznamů (=prapodivně zřetězené) pro nás nemají význam.
V praxi se postupuje tak, že se nejdříve udělá jakési držadlo - to
neobsahuje žádné podstatné informace, pouze ukazuje na začátek skutečného seznamu
dat (u oboustranně zřetězeného seznamu pak musí ukazovat i na prvek poslední).
Zpočátku neukazují držadla nikam (ukazatele mají hodnotu nil) Pak se
vytvoří dynamická proměnná a ukazatele se odpovídajícím způsobem změní.
Podívejme se na to, jak vytvořit takový jednostranně zřetězený seznam.
program PrikladNaSeznam;
{Program vytvoří jednostranně zřetězený seznam, chcete-li skončit, zadejte prázdné jméno}
type PSeznam = ^TSeznam;
TSeznam = record
Jmeno : string;
Vek : Byte;
Dalsi : PSeznam;
end;
var Prvni,Soucasny : PSeznam;
Seznam : TSeznam;
ZJmeno : string;
ZVek : Byte;
begin
New(Prvni); {Vytvoříme novou dynamickou proměnnou, na kterou bude ukazovat Prvni}
Soucasny:=Prvni; {Soucasny ukazuje tamtéž}
Soucasny^.Dalsi:=nil; {Nic dalšího zatím není}
Soucasny^.Jmeno:='nikdo';
Soucasny^.Vek:=0; {Tím bychom měli hotové jakési držadlo}
repeat
Writeln('Jméno : ');
Readln(ZJmeno);
Writeln('Věk : ');
Readln(ZVek);
if ZJmeno <> '' then
begin
New(Soucasny^.Dalsi); {Nová dynamická proměnná}
Soucasny:=Soucasny^.Dalsi; {Ukazatel současný přesměrujeme na ní}
Soucasny^.Jmeno:=ZJmeno;
Soucasny^.Vek:=ZVek;
Soucasny^.Dalsi:=nil;
end;
until ZJmeno='';
end.
Napsali jsme program, který vytvoří jednoduchý
seznam proměnných. Abyste si práci se seznamem procvičili - dopište ho tak,
aby získaný seznam i vypsal.
Podívejte se také na to, jak vytvořit a vypsat oboustranně zřetězený
seznam. Jak vypíšete oboustranně zřetězený seznam od konce? A jak to uděláte
s jednosměrně zřetězeným?
Např. u jednosměrně zřetězeného seznamu je výhodné definovat seznam druhý,
oboustranně zřetězený a ten pak vypsat...
Občas se nám stane, že potřebujeme nějaký prvek ze seznamu vyřadit. Lze to udělat tak, že vymyslíme nějakou smyšlenou hodnotu a danému prvku tuto hodnotu přiřadíme. Při vypisování pak všechny takovéto hodnoty budeme ignorovat. Tento způsob ale není moc efektivní.
Vyřazení prvku z jednostranně zřetězeného seznamu je poměrně
jednoduché. Musíme ovšem začít s prvek Predchazejicim. Nejprve nastavíme
zvláštní ukazatel na mazaný prvek. (PSmaz:=Predchazejici.Dalsi). Poté změníme
hodnotu ukazatele Predchazejiciho na prvek následující za Mazanym (Predchazejici.Dalsi:=Predchazejici.Dalsi^.Dalsi);
A nyní zbývá odstranit příslušnou dynamickou proměnnou (Dispose(PSmaz);).
(Nakreslete si obrázek, data jsou čtverečky a ukazatele jsou šipky)
Vyřazení prvku z oboustranně zřetězeného seznamu si objasníme na
jednoduchém příkladu. Zde také pochopíte vkládání prvku do tohoto
seznamu. (U jednostranně zřetězeného seznamu se pak sami pokuste vymyslet,
jak by se dalo udělat.)
program PrikladNaSeznam;
{Program vytvoří oboustranně zřetězený seznam a umožní jeho úpravy)}
type PSeznam = ^TSeznam;
TSeznam = record
Jmeno : string;
Vek : Byte;
Predchozi : PSeznam;
Dalsi : PSeznam;
end;
var Hlavicka,Soucasny : PSeznam;
Seznam : TSeznam;
ZJmeno : string;
ZVek : Byte;
r : char;
procedure Inicializace; {Vytvoří si jakési držadlo}
begin
New(Hlavicka); {Vytvoříme novou dynamickou proměnnou, na kterou bude ukazovat Hlavicka}
Hlavicka^.Dalsi:=Hlavicka; {Nic dalšího zatím není, tak ať ukazuje na sebe - kruhový seznam}
Hlavicka^.Predchozi:=Hlavicka;
Hlavicka^.Jmeno:='nikdo';
Hlavicka^.Vek:=0; {Tím bychom měli hotové jakési držadlo}
Soucasny:=Hlavicka; {na které teď ukazuje Soucasny}
end;
procedure Zadej; {Vytvoří oboustranně zřetězený kruhový seznam}
begin
repeat
Write('Jméno : ');
Readln(ZJmeno);
if ZJmeno <> '' then
begin
Write('Věk : ');
Readln(ZVek);
New(Soucasny^.Dalsi); {Nová dynamická proměnná}
Soucasny^.Dalsi^.Predchozi:=Soucasny; {Ukazatel Predchozi nové proměnné je nastaven
na současnou hodnotu Soucasny}
Soucasny:=Soucasny^.Dalsi; {Ukazatel současný přesměrujeme na novou proměnnou}
Soucasny^.Jmeno:=ZJmeno;
Soucasny^.Vek:=ZVek;
Soucasny^.Dalsi:=Hlavicka; {Ať se nám kruh neporuší}
Writeln;
end;
until ZJmeno='';
end;
procedure Vypis; {Vypíše celý seznam}
begin
Writeln('Celý seznam :');
Soucasny:=Hlavicka;
repeat
Soucasny:=Soucasny^.Dalsi;
Writeln(Soucasny^.Jmeno:40,Soucasny^.Vek:20);
until Soucasny^.Dalsi=Hlavicka;
Writeln('To je vše');
end;
procedure Zmen; {Vypíše všechny prvky a u každého se zeptá na možnost změny}
var c:char;
begin
Writeln('Celý seznam :');
Soucasny:=Hlavicka;
repeat
Soucasny:=Soucasny^.Dalsi;
Writeln(Soucasny^.Jmeno:20,Soucasny^.Vek:20, ' Změnit(A/N):');
Readln(c);
c:=UpCase(c);
if C='A' then
begin
Write('Nové jméno :');
Readln(ZJmeno);
Write('Nový věk :');
Readln(ZVek);
Soucasny^.Jmeno:=ZJmeno;
Soucasny^.Vek:=ZVek;
end;
until Soucasny^.Dalsi=Hlavicka;
Writeln('To je vše');
end;
procedure Odstran; {Odstraní vybrané prvky ze seznamu}
var Smaz:PSeznam;
c :char;
begin
Writeln('Celý seznam :');
Soucasny:=Hlavicka;
repeat
Soucasny:=Soucasny^.Dalsi;
Writeln(Soucasny^.Jmeno:40,Soucasny^.Vek:20,'Odstranit(A/N)');
Readln(c);
c:=UpCase(c);
if C='A' then
begin
Smaz:=Soucasny;
Soucasny^.Predchozi^.Dalsi:=Soucasny^.Dalsi; {Predchozi prvek ukazuje na prvek za mazaným}
Smaz^.Dalsi^.Predchozi:=Smaz^.Predchozi;{Následující prvek ukazuje před mazaný}
Soucasny:=Smaz^.Predchozi; {Soucasny, jako by tam mazaný prvek vůbec nebyl}
Dispose(Smaz); {Teprve nyní můžeme proměnnou vymazat}
end;
until Soucasny^.Dalsi=Hlavicka;
Writeln('To je vše');
end;
procedure Pridej; {Přidá nový prvek do seznamu - před vybraný prvek}
var Novy:PSeznam;
c :char;
begin
Writeln('Celý seznam :');
Soucasny:=Hlavicka;
repeat
Soucasny:=Soucasny^.Dalsi;
Writeln(Soucasny^.Jmeno:20,Soucasny^.Vek:20,'Přidat před něj nový(A/N)');
Readln(c);
c:=UpCase(c);
if C='A' then
begin
Write('Nové jméno :');
Readln(ZJmeno);
Write('Nový věk :');
Readln(ZVek);
New(Novy);
Novy^.Jmeno:=ZJmeno;
Novy^.Vek:=ZVek;
Novy^.Dalsi:=Soucasny;
Novy^.Predchozi:=Soucasny^.Predchozi;
Soucasny^.Predchozi:=Novy;
Novy^.Predchozi^.Dalsi:=Novy;
end;
until Soucasny^.Dalsi=Hlavicka;
Writeln('To je vše');
end;
begin
Inicializace;
repeat
writeln('Co chcete dělat : ');
writeln;
writeln('V - Vytvořit seznam');
writeln('Z - Zobrazit seznam');
writeln('O - Opravit údaje');
writeln('S - Smazat některá data');
writeln('P - Přidat nové prvky');
writeln('K - Končit');
Readln(R);
R:=UpCase(R);
case R of
'V': Zadej;
'Z': Vypis;
'O': Zmen;
'S': Odstran;
'P': Pridej;
end;
until R='K';
end.
Doufám, že jste na tomto příkladu pochopili výhodnost používání procedur a příkazu case. Nechápete-li seznamy, nic si z toho nedělejte, mně jejich pochopení trvalo rok a půl. Chcete-li seznamy pochopit (a umět s nimi pracovat), kreslete si obrázky - prvek je obdélníček, ze kterého vedou šipky, kam všude ukazuje. Ale hlavně to chce cvik, a proto žádný strach a směle do toho!
Např. jednosměrně zřetězený seznam : ------- -------- --------- -------- | |-------->| |------->| |--->| |----->... ------- -------- --------- -------- Nyní se pomocí těchto schémat pokuste přepsat příklad tak, aby pracoval s jednostranně zřetězeným seznamem. (Nakreslete diagram a zjistěte, co je třeba udělat, přidáváme-li nový prvek, které ukazatele se musí změnit, kolik pomocných ukazatelů je třeba...) Rada : Při přidávání a odebírání vypisujte pomocí Writeln až prvek následující za Soucasnym, či si udělejte pomocný ukazatel na předchozí proměnnou - u jednostranně zřetězeného seznamu musíte totiž znát prvek před prvkem vyřazovaným (viz diagram). Až program přepíšete, čtěte dále.
K řazení seznamu jen krátce - obvykle se používá stejná metoda, jak u pole (porovnáváme dva prvky a ty pak prohodíme. Obvykle se prohazují jen hodnoty, ukazatele se nechávají být). Vytvoříme si pomocnou proměnnou, do které zaznamenáváme počet prohození. Po každém průchodu celého seznamu začneme od začátku (a vynulujeme pomocnou proměnnou). To opakujeme tak dlouho, dokud není seznam seřazen (= hodnota naší pomocné proměnné je nula).
Na závěr si uvědomme, že jednostranný seznam se dá velice dobře uložit ve formě souboru (položku po položce).
To by bylo pro dnešek vše. DCV: Stačí, pochopili-li jste dnešní lekci. Zkuste si napsat seznam spolužáků a jejich sourozenců. (Ukazatel na seznam sourozenců je součástí dynamické proměnné spolužák ==> rozvětvený seznam).