Umíte pascalsky - 33.lekce ...

Umíte pascalsky?
33.lekce
Vytisknout  

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

Řešit úkol Prohlídka hodnocení úkolu Dotazy,připomínky

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.