Dynamické datové struktury
Datová struktura, jejíž rozsah je přesně určen deklarací a během výpočtu se nemění, se nazývá statická datová struktura.
Mezi statické struktury patří například pole a záznam.
Při řešení některých úloh však často potřebujeme proměnnou takového datového typu, který by umožňoval počet složek během výpočtu měnit podle
aktuální situace. Tyto datové struktury, jejichž rozsah se během výpočtu mění, nazýváme dynamické datové struktury.
Spojový seznam
Příkladem dynamické datové struktury je spojový seznam.
Ten je na počátku programu prázdný a během realizace se počet jeho prvků mění přidáváním
nových prvků nebo odebíráním existujících prvků.
Pro snadnější pochopení budeme používat grafického znázornění (vláček - mašinka + vagónky)
Jednotlivé prvky seznamu - dynamické proměnné - rozmístíme v paměti zcela libovolně, ale předtím ke každému z nich
přidáme proměnnou, která udává, identifikuje následující prvek v seznamu - proměnnou typu ukazatel - ukazuje na dynamickou proměnnou.
Spojový seznam je vytvořen z dynamických proměnných (typu TPrvek), které jsou propojeny pomocí ukazatelů (typu TUkaz).
Deklarace typu ukazatel vypadá takto:
|
type TUkaz = ^TPrvek;
|
|
|
TPrvek je typ dynamické proměnné (doménový typ ukazatele).
Deklarace proměnné typu ukazatel se provádí obvyklým způsobem:
var Ten, Ktery: TUkaz;
Jediná povolená operace s proměnnými typu ukazatel je test na rovnost.
if Ten <> Ktery then ...
Deklarace typu dynamická proměnná (typ prvek sezznamu) vypadá takto:
type TPrvek = record
Dalsi : TUkaz;
Hodnota : <typ hodnoty prvku> ;
end;
|
|
|
Proměnná typu dynamická proměnná se nedeklaruje, ale vytváří (generuje) (v okamžiku potřeby za běhu programu)
procedurou new(ukazatel);
Například:
|
new(Ktery);
|
|
|
|
vymezí ve volné paměti místo pro dynamickou proměnnou
Ktery^ typu TPrvek a ukazatel identifikující tuto proměnnou uloží do proměnné Ktery.
|
Dynamická proměnná (prvek seznamu), kterou identifikuje hodnota ukazatele Ktery se označuje Ktery^.
|
|
Ktery - ukazatel na dynamickou proměnnou
Ktery^ - udává dvojici samu (strukturovaná proměnná - dvě složky)
Ktery^.Dalsi - udává jméno dalšího prvku
Ktery^.Hodnota - udává hodnotu dynamické proměnné Ktery^
|
Proměnná typu ukazatel může nabývat hodnoty procedurou new() nebo přiřazovacím příkazem.
Jestliže neukazuje nikam, říkáme, že má hodnotu nil.
Například uvedené příkazy znamenají:
|
Ten := nil ;
|
|
|
|
proměnná Ten neukazuje nikam
|
|
new(Tam) ;
|
|
|
|
vytvoří se nová dynamická proměnná (prvek seznamu), na kterou ukazuje
ukazatelová proměnná Tam a má nedefinovanou ukazatelovou i hodnotovou složku
|
|
Tento := Tam;
|
|
|
|
ukazatel Tento ukazuje na stejnou dynamickou proměnnou jako ukazatel Tam;
|
Uvolnění dynamické proměnné , kterou již nepotřebujeme, provedeme procedurou
dispose(ukazatel);
Například:
|
|
|
dispose(Tam);
|
|
|
|
odstraní se dynamická proměnná Tam^ a hodnota proměnné Tam (ukazatel) přestane být definovaná
|
Příklad 1:
Nechť jsou deklarovány typy a proměnné takto:
type TUkaz = ^TPrvek;
TPrvek = record
Dalsi : TUkaz;
Hodnota : <typ hodnoty prvku> ;
end;
var Seznam, Pom: TUkaz;
Vytvořte spojový seznam Seznam s prvky [2, 9, 4].
V levém sloupci jsou příkazy v Pascalu, vedle grafické znázornění a komentář.
|
Seznam := nil;
|
|
|
|
ukazatel Seznam neukazuje nikam.
|
|
new(Pom);
|
|
|
|
Vygeneruje se nový prvek seznamu na který ukazuje ukazatel Pom s nedefinovanými složkami.
|
|
Pom^.Hodnota := 2;
Pom^.Dalsi := nil;
|
|
|
|
hodnotová složka dynamické proměnné Pom^ bude číslo 2.
|
|
seznam := pom;
|
|
|
|
ukazatel seznam ukazuje na tutéž dynamickou proměnnou jako pom
|
new(pom);
Pom^.Hodnota := 9;
|
|
|
|
vytvoří se nová dynamická proměnná s hodnotovou složkou 9, na ketrou ukazuje
ukazatel pom
|
|
Pom^.Dalsi := seznam;
|
|
|
|
dojde k propojení obou dynamických proměnných
|
|
seznam := pom;
|
|
|
|
ukazatel seznam se přemístí na začátek seznamu (to je jeho úloha -
ukazovat na první prvek seznamu od kterého lze postupovat k dalším prvkům)
|
new(pom);
Pom^.Hodnota := 4;
|
|
|
|
vytvoří se nová dynamická proměnná s hodnotovou složkou 4, na ketrou ukazuje
ukazatel pom
|
|
Pom^.Dalsi := seznam;
|
|
|
|
dojde k propojení všech dynamických proměnných
|
|
seznam := pom;
|
|
|
|
ukazatel seznam se přemístí na začátek seznamu, seznam je hotov.
|
Z příkladu vídíme, že prvky se do seznamu vkládají užitím pomocné
proměnné (pom) typu ukazatel v opačném pořadí (od konce).
Nyní můžeme (díky příkladu) napsat proceduru pro vložení prvku s danou hodnotovou částí (parametr
copak) do celočíselného seznamu, na jehož začátek ukazuje daný ukazatel (parametr start).
procedure Vloz_prvek_seznam(copak:integer;var start:TUkaz);
begin
new(pom);
pom^.Dalsi := start;
pom^.Hodnota := copak;
start := pom;
end;
|
|
{nová dynamická prom. na kterou ukazuje pom}
{připojení k seznamu}
{vložení hodnotové složky}
{přemístění originálního ukazatele na začátek}
|
Podobně lze provádět odstranění prvku ze seznamu.
Příklad 2:
Odstraňte z takto vytvořeného seznamu (na jehož začátek ukazuje ukazatel seznam) prvek
(dynamickou proměnnou) s hodnotovou složkou 4.
|
pom := seznam;
|
|
|
|
ukazatel pom ukazuje na odstraňovaný prvek
|
|
seznam := pom^.Dalsi;
|
|
|
|
ukazatel seznam přesuneme na začátek nového seznamu
|
|
dispose(pom);
|
|
|
|
odstraníme požadovanou dynamickou proměnnou
|
Z příkladu odvoďte proceduru Uber_prvek_seznam(var start:TUkaz) pro odstranění prvku z celočíselného seznamu,
na který ukazuje ukazatel start (začátek seznamu).
Abychom mohli sestavit první program s dynamickou proměnnou, je třeba ještě vytvořit proceduru
Tisk_seznam(var star:TUkaz), která umožní vytisknout všechny prvky existujícího seznamu.
Příklad 3:
Nyní již můžeme vytvořit program Dynamic, který podle volby uživatele umožňuje vytvořit celočíselný seznam
ze zadaných hodnot a vytisknout prvky aktuálního seznamu.
Program Dynamic může vypadat takto:
| program
Dynamic; |
|
|
type TUkaz = ^TPrvek;
TPrvek = record
Dalsi:TUkaz;
Hodnota:integer;
end;
var seznam, pom:TUkaz;
radky,sloupce,volba,cislo :integer;
|
|
{typ ukazatel na dyn.proměnnou}
{typ dynamická proměnná}
{ukazatelová, vazebná složka}
{hodnotová složka}
{ukazatelové proměnné}
{proměnné pro výběr volby a číslo}
|
| |
procedure Vloz_prvek_seznam(var start:TUkaz; copak:integer);
var pomoc:TUkaz;
begin
|
|
|
new(pomoc);
pomoc^.Hodnota:=copak;
pomoc^.Dalsi:=start;
start:=pomoc;
|
|
{generace nové dyn.proměnné}
{definování její hodnotové složky}
{napojení do seznamu}
{přemístění ukazatele na zač.seznamu}
|
end;
| | |
|
procedure Tisk_seznam(var start:TUkaz);
var pomoc:TUkaz;
begin
|
|
|
writeln;
pomoc:=start;;
repeat
write(pomoc^.Hodnota,',');
pomoc:=pomoc^.dalsi;
until pomoc=nil;;
writeln;;
|
|
{pomoc.ukazatel na začátek}
{opakuj}
{tisk hodnotové složky}
{posun na dalěí prvek}
{dokud nejsme na posledním prvku}
|
end;
| | |
|
Begin
| |
|
seznam^.dalsi:=nil; writeln;
writeln('Program Dynamic umoznuje:');
repeat
writeln('1 - zadat prvek do seznemu');
writeln('2 - vytisknout seznam');
writeln('0 - konec');
write('Zadejte svoji volbu:');readln(volba);
case volba of
1: begin
write('Zadejte prvek do seznamu:');
readln(cislo);
Vloz_prvek_seznam(seznam,cislo);
end;
2: Tisk_seznam(seznam);
0: ;
end;
until volba=0;
|
|
{definování ukazatele u posledního prvku}
{nabidka cinnosti}
{zadani volby}
{realizace volby}
|
| End. |
| |
|
Domácí úkol:
Doplňte program Dynamic o volby umožňující odstranit první prvek seznamu, zjistit počet prvků v seznamu,
zjistit, zda seznam není prázdný, zjistit, zda se zadaný prvek vyskytuje v seznamu.
On-line účast na řešení úkolu
Pomocí volby Řešit můžete (po přihlášení) odeslat vaše řešení domácího úkolu (každý úkol smíte řešit jen
jednou). Volbou Hodnocení
si přečtete hodnocení a komentář od vyučujícího. Dotaz nebo připomínku můžete opakovaně zasílat pomocí tlačítka Dotazy,
Komunikace (na levém okraji) zobrazuje příklad možné komunikace s vyučujícím.
|
