26.Prednaska

Z Pascal
Prejsť na: navigácia, hľadanie
26. Prednáška

úlohy | cvičenie


Dynamické premenné

Pripomeňme si, ako sa pracuje s dynamickými premennými:

  • zadeklarujeme smerníkový typ aj smerníkovú premennú, napr.
type
  PInteger = ^Integer;
var
  P, Q: PInteger;
  • vytvoríme dynamickú premennú - pomocou procedúry New - jej adresa bude v smerníkovej premennej
  New(P);
  • pracujeme so smerníkmi aj dynamickými premennými - priraďovanie premennej, priraďovanie hodnoty
  P^ := 13;
  Q := P^;
  Inc(Q^);
  • uvoľňovanie Dispose - pozor, nie viackrát to isté - smerník je teraz nedefinovaný
  Dispose(P);
  Dispose(Q);   // toto volanie tu nesmie byť, ak P aj Q odkazovali na tú istú dynamickú premennú

Väčšinou sme takto mali pre každú dynamickú premennú jednu (alebo aj viac) statickú, v ktorej bol smerník (adresa) na túto premennú.



Spájanie dynamických premenných



Skúsme dať smerník do dynamickej premennej, napr. zadeklarujeme záznam, v ktorom budú informácie o nejakých zamestnancoch (meno a plat). Okrem toho si zamestnanec môže pamätať aj jedného svojho kolegu (to bude smerník na toho kolegu):

type
  TZaznam = record
    Meno: string[15];
    Plat: Real;
    Kolega: ^TZaznam;
  end;
  PZaznam = ^TZaznam;
var
  Prvy, Druhy: PZaznam;

Môžeme vytvoriť dvoch zamestnancov (zatiaľ bez priradenia kolegov):

begin
  New(Prvy);
  Prvy^.Meno := 'Bohuslav';
  Prvy^.Plat := 1234;
  Prvy^.Kolega := nil;
  New(Druhy);
  Druhy^.Meno := 'Eleonora';
  Druhy^.Plat := 555;
  Druhy^.Kolega := nil;

dva samostatné záznamy o zamestnancoch

Teraz môžeme prvému zamestnancovi priradiť druhého ako jeho kolegu:

  Prvy^.Kolega := Druhy;

spojenie dvoch záznamov

Premennú Druhy teraz už viac nepotrebujeme na prístup k Eleonore, lebo už o nej vie Bohuslav a cez neho sa dostaneme aj k jeho kolegyni. Môžeme vytvoriť ďalšieho zamestnanca a pripojiť ho na koniec takto vytváraného zoznamu:

  New(Druhy);
  Druhy^.Meno := 'Emil';
  Druhy^.Plat := 330;
  Druhy^.Kolega := nil;

3. záznam

A pripojiť na koniec môžeme takto:

  Prvy^.Kolega^.Kolega := Druhy;
spojené 3 záznamy

Opäť môžeme smerníkovú premennú Druhy použiť na ďalšieho, už štvrtého zamestnanca:

  New(Druhy);
  Druhy^.Meno := 'Dobromila';
  Druhy^.Plat := 2000;
  Druhy^.Kolega := nil;

4. záznam

Nebudeme tohto nového zamestnanca pripájať na koniec zoznamu (za Emila), ale úplne na začiatok ešte pred Bohuslava. Preto najprv Dobromila dostane svojho kolegu Bohuslava:

  Druhy^.Kolega := Prvy;

A teraz sa stane prvým zamestnancom Dobromila:

  Prvy := Druhy;

V tomto momente oba smerníky ukazujú na ten istý začiatok zoznamu:

spojené 4 záznamy

Vypíšme teraz mená všetkých zamestnancov od prvého po posledného:

  WriteLn(Prvy^.Meno);
  WriteLn(Prvy^.Kolega^.Meno);
  WriteLn(Prvy^.Kolega^.Kolega^.Meno);
  WriteLn(Prvy^.Kolega^.Kolega^.Kolega^.Meno);

Samozrejme, že toto funguje len pre zoznam, ktorý ma aspoň 4 zamestnancov - inak program spadne. Program teraz vypísal:

Dobromila
Bohuslav
Eleonora
Emil

Spájaný zoznam

To, čo sme videli vyššie, je malá motivácia novej dátovej štruktúry, v ktorej ukladáme postupnosť nejakých prvkov (najčastejšie rovnakého typu). V tejto štruktúre je jeden prvok významný (prvý prvok) a máme na neho odkaz. Všetky prvky v tejto štruktúre sú navzájom previazané, t.j. prvý prvok obsahuje odkaz na druhý, druhý má odkaz na tretí, atď až posledný prvok už na ďalšieho neodkazuje, ale obsahuje nil.

Tejto štruktúre budeme hovoriť Spájaný zoznam (anglicky Linked List). Prvok spájaného zoznamu budeme označovať vrchol a najčastejšie sa bude deklarovať takto:

type
  PVrchol = ^TVrchol;
  TVrchol = record
    Info: string[15];    // informačná ľubovoľný typ
    Next: PVrchol;
  end;

Všimnite si, že najprv je deklarovaný smerníkový typ PVrchol a až v ďalšom riadku TVrchol, na ktorý sa odkazuje smerník.

Každý zoznam musí mať aspoň jeden smerník, ktorý bude odkazovať na jeho začiatok. Tento smerník je veľmi dôležitý a ani omylom by sa nemal prepísať, lebo stratíme celú štruktúru. Okrem tohto smerníka budeme často využívať rôzne pomocné smerníky. Napr.

var
  Z: PVrchol;    // začiatok zoznamu
  P, K: PVrchol;    // pomocné smerníky
begin
  Z := nil;    // prázdny zoznam



Vytváranie zoznamu



Budeme vytvárať zoznam postupným pridávaním prvkov do zoznamu

  • najprv pridáme na začiatok:
  New(P);
  P^.Info := 'Novy';
  P^.Next := Z;
  Z := P;
vznikol jednoprvkový zoznam: Z odkazuje na prvý (jediný) vrchol, tento už nemá nasledovníka (jeho Next je nil)
  • ďalší prvok pridáme na koniec zoznamu:
  New(P);
  P^.Info := 'Novy';
  P^.Next := nil;
  Z^.Next := P;
vznikol dvojprvkový zoznam: Z odkazuje na prvý vrchol, tento prvý má nasledovníka (odkazuje na neho Next)

Vo všeobecnosti by sme nový vrchol pridávali na koniec zoznamu nejakým takýmto testom:

  if Z = nil then                          // zoznam je prázdny
    Z := P
  else if Z^.Next = nil then               // zoznam má len jeden prvok
    Z^.Next := P
  else if Z^.Next^.Next = nil then         // zoznam má dva prvky
    Z^.Next^.Next := P
  else if Z^.Next^.Next^.Next = nil then   // zoznam má tri prvky
    Z^.Next^.Next^.Next := P
  else                                     // zoznam má štyri prvky
    Z^.Next^.Next^.Next^.Next := P;

Toto funguje len pre krátke zoznamy (do 4 prvkov). Keď zoznam nie je prázdny (Z <> nil) treba poslednému prvku (ktorého Next = nil) nastaviť nového nasledovníka (Next := P). Teda najprv treba nájsť posledný prvok:

 if Z = nil then                       // zoznam je prázdny
   Z := P
 else
 begin
   K := posledný vrchol;         // K má byť taký, že K^.Next = nil
   K^.Next := P;
 end;

Posledný vrchol zoznamu budeme hľadať takto: keď zoznam nie je prázdny, tak skúsime predpokladať, že zoznam je len jednoprvkový a teda K:=Z; Pozrieme, či je naozaj K posledný, teda či je K^.Next=nil. Ak nie, do K priradíme jeho nasledovníka (teda K^.Next) a znovu zistíme, či je posledný. Ak nie, znovu a znovu sa posunie na ďalší vrchol a znovu ho skontrolujeme. V Pascale to zapíšeme:

  K := Z;
  while K^.Next <> nil do
    K := K^.Next;

Premenná K bude teda postupne prechádzať od prvého prvku po predposledný, t.j. kým K^.Next=nil. Na prechod na ďalší prvok sme použili zápis K:=K^.Next; t.j. do K priradíme nasledovný prvok za K. Teda, teraz to vyzerá takto:

  New(P);
  P^.Info := 'Novy';
  P^.Next := nil;
  if Z = nil then
    Z := P
  else
  begin
    K := Z;
    while K^.Next <> nil do
      K := K^.Next;
    K^.Next := P
  end;

Častou začiatočníckou chybou je zápis

  K := Z;
  while K <> nil do
    K := K^.Next;

Po skončení tohto cyklu bude v premennej K hodnota nil, akurát toto priradenie bude pre dlhšie zoznamy dlhšie trvať.

Na tomto príklade vidíme, akým spôsobom sa bude často pracovať so spájanými zoznamami:

  • najprv do nejakej pomocnej premennej priradíme smerník na prvý prvok zoznamu (t.j. kam odkazuje premenná Z),
  • potom v cykle, kým ešte nie sme na konci
  • spracujeme vrchol, napr. ho vypíšeme, pozmeníme, spočítame, ...
  • presunieme sa na nasledovný vrchol
  • po skončení cyklu je v pomocnej premennej nil

Vypísanie zoznamu - od prvého po posledný

  WriteLn('*** zoznam ***');
  P := Z;
  while P <> nil do
  begin
    Write(P^.Info, ' -> ');
    P := P^.Next;
  end;
  WriteLn;
  WriteLn('*** koniec ***');

Opäť ukážeme častú začiatočnícku chybu. Program tiež vypíše všetky prvky:

  while Z <> nil do
  begin
    Write(Z^.Info, ' -> ');
    Z := Z^.Next;
  end;
  WriteLn;

Ale, ak bol Z jediný smerník na začiatok zoznamu, týmto programom sme definitívne k tomuto zoznamu stratili prístup.

Okrem vytvárania nového zoznamu je dôležité vedieť správne takýto zoznam uvoľňovať, t.j. postupne uvoľniť každý jeden prvok (Dispose). Teda najprv podobný algoritmus ako bol výpis:

  P := Z;
  while P <> nil do
  begin
    Dispose(P);    // spracuj vrchol
    P := P^.Next;
  end;

Lenže toto je úplne zle! Treba si uvedomiť, že Dispose(P) spôsobí zrušenie nielen dynamickej premennej, na ktorú odkazuje, ale premenná P teraz obsahuje nedefinovaný smerník. Preto ďalší príkaz P:=P^.Next; chce pracovať s nedefinovaným smerníkom, čo sa nesmie!

Okrem toho, tento cyklus pracuje s pomocným smerníkom P, asi preto, aby sa neznehodnotil smerník Z na začiatok zoznamu - čo je zrejme v tomto konkrétnom prípade zbytočné. Zoznam uvoľníme teraz už správne napr. takto:

  while Z <> nil do
  begin
    P := Z^.Next;  // zapamätaj si nasledovníka
    Dispose(Z);    // uvoľni vrchol
    Z := P;        // teraz prejdi na nasledovníka
  end;



Podprogramy



Ďalej ukážeme použitie podprogramov, kde parameter alebo výsledok funkcie je typu smerník na vrchol, resp. spájaný zoznam. Zapíšme najprv výpis prvkov zoznamu ako podprogram:

procedure Vypis(P: PVrchol);
begin
  while P <> nil do
  begin
    Write(P^.Info, ' -> ');
    P := P^.Next;
  end;
  WriteLn;
end;

Keď budeme chcieť vypísať vrcholy zoznamu, zadáme

  Vypis(Z);

Vďaka tomu, že táto procedúra má hodnotový parameter P, pri volaní je P lokálnou premennou, do ktorej sa priradí smerník Z. Zmenou parametra P sa teda nemení hodnota premennej Z.

Už asi tušíte, že v tomto prípade by použitie var-parametra nemuselo dopadnúť dobre. Teda

procedure Vypis(var P: PVrchol);
begin
  while P <> nil do
  begin
    Write(P^.Info, ' -> ');
    P := P^.Next;
  end;
  WriteLn;
end;

a volanie

  Vypis(Z);

Znehodnotí smerník Z - smerník na začiatok zoznamu má teraz hodnotu nil.

Pritom var-parameter pre smerník je často dosť užitočný. Nasledujúci podprogram pridáva nový vrchol na začiatok zoznamu:

procedure PridajZ(var Z: PVrchol; Info: string);
var
  P: PVrchol;
begin
  New(P);
  P^.Info := Info;
  P^.Next := Z;
  Z := P;
end;

a volanie

  Z := nil;
  PridajZ(Z, 'prvy');
  PridajZ(Z, 'druhy');
  PridajZ(Z, 'treti');
  PridajZ(Z, 'stvrty');
  Vypis{Z|;

Vytvorí trojprvkový zoznam a vypíše:

stvrty -> treti -> druhy -> prvy ->

Teraz zapíšme niekoľko užitočných funkcií:

  • funkcia zistí posledný vrchol zoznamu, keď neexistuje, vráti nil
function Posledny(Z: PVrchol): PVrchol;
begin
  Result := Z;
  if Result <> nil then
    while Result^.Next <> nil do
      Result := Result^.Next;
end;
  • funkcia zistí počet vrcholov zoznamu:
function Pocet(Z: PVrchol): Integer;
begin
  Result := 0;
  while Z <> nil do
  begin
    Inc(Result);
    Z := Z^.Next;
  end;
end;
  • Funkcia vytvorí nový vrchol:
function Vrchol(Info: string; Next: PVrchol): PVrchol;
begin
  New(Result);
  Result^.Info := Info;
  Result^.Next := Next;
end;

Teraz môžeme procedúru PridajZ, ktorá pridáva nový vrchol na začiatok zoznamu zapísať elegantnejšie:

procedure PridajZ(var Z: PVrchol; Info: string);
begin
  Z := Vrchol(Info, Z);
end;

Pridávanie nového vrchola na koniec zoznamu zapíšeme takto:

procedure PridajK(var Z: PVrchol; Info: string);
var
  K: PVrchol;
begin
  K := Posledny(Z);
  if K = nil then
    Z := Vrchol(Info, nil)
  else
    K^.Next := Vrchol(Info, nil);
end;

Uvoľnenie všetkých vrcholov zoznamu:

procedure Uvoľni(var Z: PVrchol);
var
  P: PVrchol;
begin
  while Z <> nil do
  begin
    P := Z^.Next;
    Dispose(Z);
    Z := P;
  end;
end;



Testovanie rýchlosti pridávania prvkov



Teraz môžeme otestovať vytváranie aj väčšieho zoznamu.

  Z := nil;
  for I := 1 to 100 do
    PridajK(Z, 'x' + IntToStr(I));   // vyskúšajte aj PridajZ
  Vypis(Z);
  WriteLn('pocet = ', Pocet(Z));
  Uvolni(Z);

V závislosti od rýchlosti vášho počítača, sa tento testovací program bude výrazne spomaľovať pre väčší počet pridávaných vrcholov. Môžeme vyskúšať (konštanty 50000 a 5000 si prispôsobte):

  Z := nil;
  for I := 1 to 50000 do
  begin
    if I mod 5000 = 0 then
      WriteLn(I);
    PridajK(Z, 'x' + IntToStr(I));   // vyskúšajte aj PridajZ
  end;
  WriteLn('pocet = ', Pocet(Z));
  Uvolni(Z);

Môžete vidieť, že čím je zoznam dlhší, tým pomalšie sa pridávajú na koniec nové vrcholy. Ak by sme tento program spustili pre PridajZ, tak zbehne pomerne rýchlo aj pre 5000000 prvkový zoznam (do if dajte 500000).

Procedúra PridajK je preto tak veľmi pomalá, lebo pre každý pridávaný prvok začne od úplného začiatku hľadať koncový vrchol a ten je už dosť ďaleko. Tejto procedúre by pomohlo, keby sme jej okrem smerníka Z na začiatok zoznamu posielali aj smerník K na koniec zoznamu:

procedure PridajK(var Z, K: PVrchol; Info: string);
var
  P: PVrchol;
begin
  P := Vrchol(Info, nil);
  if K = nil then
    Z := P
  else
    K^.Next := P;
  K := P;               // nový posledný vrchol
end;

Keď teraz otestujeme túto procedúru, zistíme, že je porovnateľne rýchla ako PridajZ:

  Z := nil;
  for I := 1 to 5000000 do
  begin
    if I mod 500000 = 0 then
      WriteLn(I);
    PridajK(Z, K, 'x' + IntToStr(I));
  end;
  WriteLn('pocet = ', Pocet(Z));
  Uvolni(Z);

Základné operácie so zoznamom

Pridávanie prvkov na začiatok alebo na koniec zoznamu sú dôležité operácie, ale sú to práve tie najjednoduchšie. Náročnejšie operácie budú vkladanie nových vrcholov na správne miesto, vyhadzovanie niektorých vrcholov, prípadne zmena poradia v zozname.



Hľadanie v zozname



Pri hľadaní vrchola s nejakou vlastnosťou (napr. Info = hľadaná hodnota), musíme prechádzať celý zoznam od prvého možno až do konca. Pre Veľmi dlhé zoznamy je to časovo náročná operácia. Napíšme funkciu, ktorá vráti smerník na prvý výskyt vrchola s hľadaným Info. Ak takýto vrchol neexistuje, funkcia vráti nil:

function Hladaj(Z: PVrchol; Hladam: string): PVrchol;
begin
  Result := Z;
  while (Result <> nil) and (Result^.Info <> Hladam) do
    Result := Result^.Next;
end;

While-cyklus skončí, buď keď Result=nil, vtedy prešiel celý zoznam a taký vrchol nenašiel, alebo keď Result^.Info=Hladam, t.j. v Result je hľadaný vrchol. Ak by sme chceli využiť túto funkciu a niečo s nájdeným vrcholom urobiť, zapísali by sme to takto:

P := Hladaj(Z, 'x100');
if P <> nil then
  P^.Info := 'ahoj';

Niekedy budeme potrebovať nájsť nie prvý výskyt, ale vykonať nejakú akciu so všetkými vrcholmi, ktoré spĺňajú nejaké kritérium. Napr. modifikujeme všetky vrcholy, ktorých Info obsahuje nejaký znak:

procedure Zmen(P: PVrchol; Znak: Char);
begin
  while P <> nil do
  begin
    if Pos(Znak, P^.Info) <> 0 then
      P^.Info := 'xxx';
    P := P^.Next;
  end;
end;


Hľadať vrcholy s nejakou vlastnosťou budeme potrebovať aj vtedy, keď budeme nejaké vrcholy vkladať na zadané miesto, alebo nejaké vyhadzovať.



Vsúvanie do zoznamu



Zatiaľ sme do zoznamu vkladali nové vrcholy buď na začiatok, alebo na koniec. Vo všeobecnosti sa vkladaný vrchol pripája k vrcholu, ktorý bude pred ním a samozrejme bude treba správne za tento vkladaný napojiť zvyšok zoznamu. Začnime najjednoduchšou verziou: vložíme nový vrchol ako druhý prvok zoznamu:

procedure Vloz2(var Z: PVrchol; Info: string);
var
  Novy: PVrchol;
begin
  Novy := Vrchol(Info, nil);
  if Z = nil then
    Z := Novy
  else
  begin
    Novy^.Next := Z^.Next;
    Z^.Next := Novy;
  end;
end;

zoznam a nový vrchol

nový vrchol má nového nasledovníka


prvý vrchol zoznamu má nového nasledovníka

Ak zoznam ešte nebol prázdny, tak samotné pripojenie nového vrcholu pozostáva z dvoch priradení: najprv sa novému vrcholu vyrobí nasledovník (to bol doterajší nasledovník prvého) a až potom sa tento nový vrchol stane nasledovníkom prvého vrcholu. Uvedomte si, že prehodenie týchto dvoch priradení úplne pokazí previazanosť vrcholov v zozname.

Tento istý podprogram sa dá zapísať aj jednoduchšie:

procedure Vloz2(var Z: PVrchol; Info: string);
begin
  if Z = nil then
    Z := Vrchol(Info, nil)
  else
    Z^.Next := Vrchol(Info, Z^.Next);
end;

Uvedomte si, že v príkaze Z^.Next := Vrchol(Info, Z^.Next); sa vykonajú naše dve kľúčové priradenia a našťastie v správnom poradí:

  NovyVrchol^.Next := Z^.Next;
  Z^.Next := NovyVrchol;

Ďalší podprogram pridáva nový vrchol za nájdený nejakým hľadaním (napr. funkciou Hladaj). Ak nenájde, vrchol vloží na koniec:

procedure VlozZa(var Z: PVrchol; Hladam, NoveInfo: string);
var
  P: PVrchol;
begin
  P := Hladaj(Z, Hladam);
  if P = nil then                  // nenašiel
    PridajK(Z, NoveInfo)
  else
    P^.Next := Vrchol(NoveInfo, P^.Next);
end;

Tento postup sa podobá vkladaniu za prvý prvok. Všimnite si, že parameter Z musí byť var-parameter, lebo táto procedúra niekedy môže zmeniť začiatok zoznamu (napr. keď bol zoznam prázdny).

Ak ale chceme vložiť prvok pred nájdený, bude to komplikovanejšie. Na vkladanie prvku totiž potrebujeme poznať predchodcu vkladaného miesta, a teda aj hľadanie bude náročnejšie.

procedure VlozPred(var Z: PVrchol; Hladam, NoveInfo: string);
var
  P, Novy: PVrchol;
begin
  if (Z = nil) or (Z^.Info = Hladam) then
    PridajZ(Z, NoveInfo)
  else
  begin
    P := Z;
    while (P^.Next <> nil) and (P^.Next^.Info <> Hladam) do
      P := P^.Next;
    // nájde buď vrchol tesne pred hľadaným, alebo zastane na poslednom vrchole
    // P^.Next := Vrchol(NoveInfo, P^.Next);
    New(Novy);
    Novy^.Info := NoveInfo;
    Novy^.Next := P^.Next;
    P^.Next := Novy;
  end;
end;

zoznam a nový vrchol

našli sme správne miesto


správne sme ho prepojili

V tomto riešení je dôležitý while-cyklus, ktorý hľadá miesto, kde bude vkladať nový vrchol. V tomto cykle nezisťujeme Info vo vrchole P^, ale Info pre P^.Next^. Tiež P^.Next:=Vrchol(NoveInfo,P^.Next); sme rozpísali, aby bolo lepšie vidieť, postupné vytváranie spojení.



Vyhadzovanie zo zoznamu



Vyhadzovanie zo zoznamu je podobne náročné, ako vsúvanie nového vrcholu pred iný vrchol. Na správne vyhodenie zo zoznamu potrebujeme poznať vrchol, ktorý je tesne pred vyhadzovaným vrcholom. Totiž tomuto predchodcovi budeme meniť jeho Next.

Najprv zapíšme najjednoduchší problém - vyhodenie prvého prvku zo zoznamu - v skutočnosti sme ho robili vo while-cykle pri uvoľňovaní celého zoznamu (porovnajte s procedúrou Uvolni). Môžeme zapísať:

procedure VyhodPrvy(var Z: PVrchol);
var
  P: PVrchol;
begin
  if Z <> nil then
  begin
    P := Z^.Next;
    Dispose(Z);
    Z := P;
  end;
end;

Samotná procedúra Uvolni by sa teraz dala zapísať takto elegantne:

procedure Uvolni(var Z: PVrchol);
begin
  while Z <> nil do
    VyhodPrvy(Z);
end;

Ak chceme vyhodiť ľubovoľný vrchol, ktorý spĺňa nejaké kritérium, hľadáme predchodcu vyhadzovaného prvku. Teda sa to podobá vkladaniu nového vrcholu pred hľadaný:

procedure Vyhod(var Z: PVrchol; Hladam: string);
var
  P, Q: PVrchol;
begin
  if Z <> nil then
    if Z^.Info = Hladam then
      VyhodPrvy(Z)
    else
    begin
      P := Z;
      while (P^.Next <> nil) and (P^.Next^.Info <> Hladam) do
        P := P^.Next;
      // nájde buď vrchol tesne pred hľadaným, alebo zastane na poslednom vrchole
      if P^.Next <> nil then
      begin
        Q := P^.Next^.Next;
        Dispose(P^.Next);
        P^.Next := Q;
      end;
    end;
end;

hľadáme v zozname

našli sme


správne sme ho vyhodili

Teda, keď nájdeme hľadaný vrchol, v premennej P máme jeho predchodcu (lebo P^.Next^.Info=Hladam). Zapamätáme si nasledovníka vyhadzovaného vrcholu (do premennej Q), uvoľníme jeden vrchol a na záver predchodcovi zmeníme jeho nového nasledovníka.

Všimnite si časť (vyznačená zelenou farbou), v ktorej vyhadzujeme jeden konkrétny vrchol (smerník na neho máme v P^.Next). Keď to porovnáme s tým, čo robí procedúra VyhodPrvy, môžeme vidieť, že sa robí to isté, ale namiesto parametra Z tu bude P^.Next. Naozaj to môžeme nahradiť a zapísať elegantnejšie:

procedure Vyhod(var Z: PVrchol; Hladam: string);
var
  P: PVrchol;
begin
  if Z <> nil then
    if Z^.Info = Hladam then
      VyhodPrvy(Z)
    else
    begin
      P := Z;
      while (P^.Next <> nil) and (P^.Next^.Info <> Hladam) do
        P := P^.Next;
      VyhodPrvy(P^.Next);
    end;
end;

Zamyslite sa, čo bude treba zmeniť, ak chceme vyhodiť nie jeden vrchol, ale všetky, ktoré spĺňajú nejakú podmienku.


Zásobník a rad

V zimnom semestri sme niekoľkokrát realizovali dátové štruktúry zásobník TStack a rad TQueue.



Dátová štruktúra zásobník



Vieme, že na prácu s takouto štruktúrou máme k dispozícii niekoľko metód:

  • Push - na Vrch zásobníka sa vloží nový prvok (niekedy sa tomu hovorí aj Push_Front, lebo nový prvok sa vkladá na začiatok, teda Front)
  • Pop - z Vrchu zásobníka sa zoberie najvrchnejší prvok a ten sa vráti ako hodnota - samozrejme, že Pop funguje, len ak je zásobník neprázdny (niekedy sa tomu hovorí aj Pop_Front, lebo sa vyberá prvok zo začiatku teda Frontu)
  • Top - táto funkcia vracia hodnotu prvku na Vrchu zásobníka (samozrejme, keď nie je prázdny) (niekedy sa tomu hovorí aj Front)
  • Empty - funkcia vráti True, ak je zásobník prázdny

Zrealizujme zásobník pomocou spájaného zoznamu - pridávať aj odoberať budem prvky zo začiatku a obe tieto operácie už vieme, že sú veľmi jednoduché.

type
  PVrchol = ^TVrchol;
  TVrchol = record
    Info: Integer;     // typ prvkov v zásobníku
    Next: PVrchol;
  end;
 
  TStack = class
  private
    Vrch: PVrchol;
  public
    destructor Destroy; override;
    procedure Push(Info: Integer);
    function Pop: Integer;
    function Top: Integer;
    function Empty: Boolean;
  end;
 
destructor TStack.Destroy;
var
  P: PVrchol;
begin
  while Vrch <> nil do
  begin
    P := Vrch^.Next;
    Dispose(Vrch);
    Vrch := P;
  end;
end;
 
procedure TStack.Push(Info: Integer);
var
  P: PVrchol;
begin
  New(P);
  P^.Info := Info;
  P^.Next := Vrch;
  Vrch := P;
end;
 
function TStack.Pop: Integer;
var
  P: PVrchol;
begin
  if Empty then
    raise Exception.Create('prazdny zasobnik');
  Result := Vrch^.Info;
  P := Vrch;
  Vrch := Vrch^.Next;
  Dispose(P);
end;
 
function TStack.Top: Integer;
begin
  if Empty then
    raise Exception.Create('prazdny zasobnik');
  Result := Vrch^.Info;
end;
 
function TStack.Empty: Boolean;
begin
  Result := Vrch = nil;
end;



Dátová štruktúra rad



Vieme, že na prácu s takouto štruktúrou máme k dispozícii niekoľko metód:

  • Append - na Koniec radu sa vloží nový prvok (niekedy sa tomu hovorí aj Push_Back, lebo nový prvok sa vkladá na koniec, teda Back)
  • Serve - z Vrchu radu sa zoberie prvý prvok a ten sa vráti ako hodnota - samozrejme, že Serve funguje, len ak rad nie je prázdny (niekedy sa tomu hovorí aj Pop_Front, lebo sa vyberá prvok zo začiatku teda Frontu)
  • First - táto funkcia vracia hodnotu prvku na Vrchu radu (samozrejme, keď nie je prázdny) (niekedy sa tomu hovorí aj Front)
  • Empty - funkcia vráti True, ak je rad prázdny

Zrealizujme rad pomocou spájaného zoznamu - pridávať prvky budeme na koniec (vieme, že je vhodné mať k dispozícii ešte jeden smerník, ktorý bude odkazovať na posledný prvok zoznamu), odoberať budem prvky zo začiatku a obe tieto operácie už vieme, že sú veľmi jednoduché.

type
  PVrchol = ^TVrchol;
  TVrchol = record
    Info: Integer;     // typ prvkov v zásobníku
    Next: PVrchol;
  end;
 
  TQueue = class
  private
    Vrch, Koniec: PVrchol;
  public
    destructor Destroy; override;
    procedure Append(Info: Integer);
    function Serve: Integer;
    function First: Integer;
    function Empty: Boolean;
  end;
 
destructor TQueue.Destroy;
var
  P: PVrchol;
begin
  while Vrch <> nil do
  begin
    P := Vrch^.Next;
    Dispose(Vrch);
    Vrch := P;
  end;
end;
 
procedure TQueue.Append(Info: Integer);
var
  P: PVrchol;
begin
  New(P);
  P^.Info := Info;
  P^.Next := nil;
  if Vrch = nil then
    Vrch := P
  else
    Koniec^.Next := P;
  Koniec := P;
end;
 
function TQueue.Serve: Integer;
var
  P: PVrchol;
begin
  if Empty then
    raise Exception.Create('prazdny rad');
  Result := Vrch^.Info;
  P := Vrch;
  Vrch := Vrch^.Next;
  Dispose(P);
  if Vrch = nil then
    Koniec := nil;
end;
 
function TQueue.First: Integer;
begin
  if Empty then
    raise Exception.Create('prazdny rad');
  Result := Vrch^.Info;
end;
 
function TQueue.Empty: Boolean;
begin
  Result := Vrch = nil;
end;



Dátová štruktúra obojstranný rad - Deque



S touto štruktúrou sme sa zatiaľ nestretli. Je to štruktúra, ktorá je kombináciou oboch doterajších štruktúr: pridávať aj odoberať prvky môžeme nielen zo začiatku ale aj z konca. Operácie by mohli vyzerať takto:

  • Push_Front - pridá na začiatok radu
  • Push_Back - pridá na koniec radu
  • Pop_Front - odoberie zo začiatku radu
  • Pop_Back - odoberie z konca radu
  • Front - hodnota prvého prvku radu
  • Back - hodnota posledného prvku radu
  • Empty - či je rad prázdny

Všetky tieto operácie sú jednoduché okrem Pop_Back, ktorá bude náročnejšia. Ostatné metódy sme realizovali v TStack a TQueue. Naprogramujte všetky metódy, ale hlavne metódu Pop_Back.

type
  PVrchol = ^TVrchol;
  TVrchol = record
    Info: Integer;     // typ prvkov v zásobníku
    Next: PVrchol;
  end;
 
  TDeque = class
  private
    Vrch, Koniec: PVrchol;
  public
    destructor Destroy; override;
    procedure Push_Front(Info: Integer);
    procedure Push_Back(Info: Integer);
    function Pop_Front: Integer;
    function Pop_Back: Integer;
    function First: Integer;
    function Back: Integer;
    function Empty: Boolean;
  end;


späť | ďalej