27.Prednaska

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

úlohy | cvičenie


Objekt ako vrchol zoznamu

Ukážeme, využitie objektov namiesto záznamov (record). Už vieme, že objekty sú vlastne reprezentované ako smerníky niekam do dynamickej pamäti. Takže, vždy keď niekde zadeklarujeme objektovú premennú (aj ako položku záznamu alebo iného objektu), v skutočnosti deklarujeme smerník (adresu do pamäti). Vrchol zoznamu sme doteraz reprezentovali záznamom, v ktorom bola položka smerník. Teraz ho zadefinujeme objektom, v ktorom stavová premenná Next je opäť typu samotného objektu:

type
  PVrchol = ^TVrchol;
  TVrchol = record
    Info: Integer;
    Next: PVrchol;
  end;
type
 
  TVrchol = class
    Info: Integer;
    Next: TVrchol;
  end;

Prístup pomocou objektov umožňuje zadefinovať aj konštruktor a prípadne aj nejaké metódy:

type
  TVrchol = class
    Info: Integer;
    Next: TVrchol;
    constructor Create(NoveInfo: Integer; NoveNext: TVrchol);
    destructor Destroy; override;
    function Text: string;
  end;
 
constructor TVrchol.Create(NoveInfo: Integer; NoveNext: TVrchol);
begin
  Info := NoveInfo;
  Next := NoveNext;
end;
 
destructor TVrchol.Destroy;
begin
  // Bmp.Free;   ak vrchol obsahuje napr. nejakú bitmapu
  // Next.Free;   --> by bola rekurzia
end;
 
function TVrchol.Text: string;
begin
  Result := ' ' + IntToStr(Info);
end;

Rekurzia nie je chybou: pri uvoľňovaní nejakého vrcholu (napr. zo začiatku zoznamu) sa automaticky uvoľnia aj všetky nasledujúce až po posledný s nil-ovým Next. Rekurzia môže robiť problémy pre dlhé zoznamy, lebo nastane pretečenie zásobníka. Tiež by sme omylom mohli zrušiť časť zoznamu, hoci sme chceli uvoľniť len jeden prvok. Preto radšej do deštruktora nedávame rekurzívne rušenie zvyšku celého zoznamu.

Vytvoríme trojprvkový zoznam z objektov:

var
  Z: TVrchol;
begin
  Z := TVrchol.Create(11, TVrchol.Create(22, TVrchol.Create(33, nil)));
  WriteLn(Z.Text, Z.Next.Text, Z.Next.Next.Text);
  Z.Next.Next.Free;
  Z.Next.Free;
  Z.Free;
  ReadLn;
end.

Môžeme zadefinovať podobnú funkciu Pocet ako v predchádzajúcej časti pre zistenie počtu prvkov zoznamu. Všimnite si podobnosť s podobnou funkciou pre vrcholy ako záznamy:

function Pocet(P: TVrchol): Integer;
begin
  Result := 0;
  while P <> nil do
  begin
    Inc(Result);
    P := P.Next;
  end;
end;

Nasledujúca funkcia ukazuje zisťovanie posledného prvku zoznamu:

function Posledny(P: TVrchol): TVrchol;
begin
  Result := P;
  if Result <> nil then
    while Result.Next <> nil do
      Result := Result.Next;
end;

Táto funkcia vráti nil pre prázdny zoznam alebo posledný vrchol zoznamu.



Trieda TZoznam



Zadefinujeme triedu TZoznam, ktorá zabezpečí základné operácie nad zoznamom - bude mať dve stavové premenné: začiatok a koniec zoznamu. Najprv len najjednoduchšie metódy triedy TZoznam:

type
  TZoznam = class
  private
    Z: TVrchol;    // začiatok zoznamu
    K: TVrchol;    // koniec zoznamu
  public
    constructor Create;
    destructor Destroy; override;
    function Text: string;
    procedure PridajZ(NoveInfo: Integer);
    procedure PridajK(NoveInfo: Integer);
    procedure Vsun(Pred: Integer; NoveInfo: Integer);
  end;
 
constructor TZoznam.Create;
begin
  Z := nil;    // v skutočnosti toto urobí automaticky konštruktor
  K := nil;
end;
 
destructor TZoznam.Destroy;
var
  P: TVrchol;
begin
  while Z <> nil do
  begin
    P := Z.Next;
    Z.Free;
    Z := P;
  end;
end;
 
function TZoznam.Text: string;
var
  P: TVrchol;
begin
  Result := '';
  P := Z;
  while P <> nil do
  begin
    Result := Result + P.Text;
    P := P.Next;
  end;
end;
 
procedure TZoznam.PridajZ(NoveInfo: Integer);
begin
  Z := TVrchol.Create(NoveInfo, Z);
  if K = nil then
    K := Z;
end;
 
procedure TZoznam.PridajK(NoveInfo: Integer);
var
  P: TVrchol;
begin
  P := TVrchol.Create(NoveInfo);
  if Z = nil then
    Z := P
  else
    K.Next := P;
  K := P;
end;
 
procedure TZoznam.Vsun(Pred: Integer; NoveInfo: Integer);
var
  P, Q: TVrchol;
begin
  if Pred < 2 then
    PridajZ(NoveInfo)
  else
  begin
    Q := Z;
    while (Q <> nil) and (Pred > 2) do
    begin
      Dec(Pred);
      Q := Q.Next;
    end;
    P := TVrchol.Create(NoveInfo);
    if Q = nil then
      K.Next := P
    else
    begin
      P.Next := Q.Next;
      Q.Next := P;
    end;
    if P.Next = nil then
      K := P;
  end;
end;



Použitie vlastností



Vytvoríme vlastnosť (property), pomocou ktorej budeme pracovať so zoznamom ako s poľom:

type
  TZoznam = class
    ...
    function Ity(I: Integer): TVrchol;
    procedure Zmen(I: Integer; NovyVrchol: TVrchol);
    ...
    property Prvy: TVrchol read Z;
    property Posledny: TVrchol read K;
    property Prvky[I: Integer]: TVrchol read Ity write Zmen; default;
  end;
 
...
 
function TZoznam.Ity(I: Integer): TVrchol;
begin
  Result := Z;
  while (Result <> nil) and (I > 1) do
  begin
    Result := Result.Next;
    Dec(I);
  end;
end;
 
procedure TZoznam.Zmen(I: Integer; NovyVrchol: TVrchol);
var
  Q, R: TVrchol;
begin
  if I < 1 then
    PridajZ(NovyVrchol)
  else
  begin
    Q := Ity(I - 1);
    if (Q = nil) or (Q.Next = nil) then
      PridajK(NovyVrchol)
    else
    begin
      R := Q.Next;
      Q.Next := NovyVrchol;
      NovyVrchol.Next := R.Next;
      // R.Free;
    end;
  end;
end;

vďaka vlastnosti Prvky môžeme ku prvkom zoznamu pristupovať ako ku prvkom poľa, napr.

  for I := 1 to 20 do
    Z.Prvky[I] := TVrchol.Create(I, nil);
  for I := 1 to Z.Pocet do
    Write(Z.Prvky[I].Text, ' -> ');
  WriteLn;

Rezervované slovo (direktíva) default v riadku property Prvky zabezpečí, že priamo s inštanciou triedy TZoznam môžeme pracovať tak, ako keby to bolo pole a nemusíme písať identifikátor Prvky, napr.

  for I := 1 to 20 do
    Z[I] := TVrchol.Create(I, nil);
  for I := 1 to Z.Pocet do
    Write(Z[I].Text, ' -> ');
  WriteLn;

Ďalšie námety:

  • zistite, prečo nebude fungovať takáto výmena prvkov zoznamu:
var
  Temp: TVrchol;
...
  Temp := Z[I1];
  Z[I1] := Z[I2];
  Z[I2] := Temp;


Procedurálny typ

Naučíme sa pracovať s novým typom, tzv. procedurálnym typom. Pomocou tohto typu budeme vedieť vytvárať premenné, ktorých hodnotou bude nejaká naša konkrétna procedúra (alebo funkcia). V skutočnosti táto premenná bude obsahovať nie samotnú procedúru, ale adresu tejto procedúry v pamäti počítača (niečo ako smerník na procedúru).

Aby sme mohli pracovať s procedurálnym typom, musíme ho najprv zadefinovať v časti type, t.j. zadefinovať identifikátor typu a špecifikáciu typu. Pri špecifikovaní procedurálneho typu definujeme:

  • aký je to typ podprogramu - procedure alebo function
  • koľko bude mať parametrov
  • typ každého parametra
  • či to bude globálny podprogram alebo metóda nejakej triedy

Napr. takéto deklarácie označujú

type
  TProc1 = procedure(I: Integer);               // ľubovoľná procedúra s jedným celočíselným parametron
  TVypis = procedure(S: string; V: TVrchol);    // ľubovoľná procedúra s dvoma parametrami: reťazec a vrchol zoznamu
  TPrirad = procedure(Pole: array of Real);     // ľubovoľná procedúra a jedným parametrom otvorené reálne pole
  TFunkcia = function(X: Real): Real;           // ľubovoľná reálna funkcia s jedným reálnym parametrom
  TFilter = function(V: TVrchol): Boolean;      // ľubovoľná logická funkcia s jedným parametrom vrchol zoznamu
 
  TUdalost = procedure(Sender: TObject) of object;  // ľubovoľná metóda s jedným parametrom typu ľubovoľný objekt

Uvedomte si, že identifikátory (názvy) formálnych parametrov nemajú žiaden špeciálny význam. Tieto typy sú kompatibilné s ľubovoľnými podprogramami, ktoré majú rovnaký počet parametrov s ich rovnakými typmi (bez ohľadu na mená parametrov).

Keď už máme zadefinovaný procedurálny typ, môžeme zadeklarovať aj premennú tohto typu. Potom s takouto premennou v programe môžeme:

  • priradiť do nej ľubovoľnú existujúcu procedúru kompatibilného typu (teda v skutočnosti priradiť jej adresu)
  • priradiť do nej nil, ktorý označuje žiadnu procedúru a túto hodnotu môžeme neskôr testovať
  • spustiť priradenú procedúru (samozrejme, keď to nie je nil)
  • otestovať, či je hodnotou procedurálnej premennej hodnota rôzna od nil - testujeme pomocou preddefinovanej logickej funkcie Assigned

Napr.

var
  Pr: TProc1;
begin
  Pr := nil;
  if not Assigned(Pr) then          // teda, či Pr nie je nil
    Pr := @Procedura;               // priradíme adresu procedúry
  Pr(100);

Zrejme predpokladáme, že existujúci podrogram Procedura má práve jeden celočíselný parameter, napr.

procedure Procedura(X: Integer);
begin
  WriteLn(X: 8, X * X: 8, X * X * X: 8);
end;

V ďalších častiach uvidíme rôzne využitia procedurálneho typu, napr.

  • pamätáme si, ako sa realizujú rôzne operácie, napr. v prefixovom zápise aritmetického výrazu
  • ako sa má spracovať nejaká špecifická udalosť (napr. udalosti vo formulári onChange, onClick, onCreate, ...)
  • akú akciu treba vykonať so všetkými prvkami nejakej štruktúry, napr. s vrcholmi spájaného zoznamu
  • aké podmienky treba odkontrolovať so všetkými prvkami nejakej štruktúry

Ukážme jednoduchý príklad, v ktorom budeme pracovať s procedurálnym typom TProc1 - globálna procedúra s jedným celočíselným parametrom. Najprv zadefinujme niekoľko procedúr, ktoré budú kompatibilné s týmto typom:

procedure Riadok(N: Integer);
begin
  while N > 0 do
  begin
    Write('*');
    Dec(N);
  end;
  WriteLn;
end;
 
procedure Cislo(X: Integer);
begin
  WriteLn('cislo ', X);
end;
 
procedure Okraje(I: Integer);
begin
  WriteLn('*', '*': I - 1);
end;

Všetky tieto procedúry sú typu TProc1 a teda ich môžeme priradiť do premennej tohto typu:

var
  P: TProc1;
  I: Integer;
begin
  if Random(2) = 0 then
    P := @Riadok
  else
    P := @Cislo;
  for I := 1 to 10 do
    P(I);
end;

Program buď vypíše 10 rôzne dlhých riadkov hviezdičiek, alebo 10 riadkov s textom 'cislo ' a číslami od 1 do 10.

Ďalšia ukážka využíva inicializovanie prvkov poľa:

var
  Pole: array [0..4] of TProc1 = (@Cislo, @Riadok, @Okraje, @Okraje, @Riadok);
  I, J: Integer;
begin
  for I := 8 to 10 do
    for J := 0 to High(Pole) do
      Pole[J](I);                // volanie J-tej procedúry s parametrom I
end;

Tento program vypíše:

cislo 8
********
*      *
*      *
********
cislo 9
*********
*       *
*       *
*********
cislo 10
**********
*        *
*        *
**********



Procedurálny typ pre spájaný zoznam



Pri definovaní rôznych metód spájaných zoznamov sa veľmi často stretáme s takouto situáciou, napr.

procedure TZoznam.Vypis;
var
  P: TVrchol;
begin
  P := Z;
  while P <> nil do
  begin
    Write(P.Text, ' -> ');
    P := P.Next;
  end;
end;
 
procedure TZoznam.Pricitaj;
var
  P: TVrchol;
begin
  P := Z;
  while P <> nil do
  begin
    Inc(P.Info);
    P := P.Next;
  end;
end;

Tieto metódy robia nejakú akciu postupne s každým prvkom zoznamu. Tu by sme vedeli využiť procedurálny typ, pomocou ktorého vytvoríme jedinú metódu PreVsetky s parametrom nejaká Akcia a metóda túto akciu spustí pre každý prvok zoznamu. Zrejme akciou bude ľubovoľná procedúra s jedným parametrom - vrcholom zoznamu. Zadeklarujeme

type
  TAkcia = procedure(P: TVrchol);
 
  TZoznam = class
  ...
  public
    ...
    procedure PreVvsetky(Akcia: TAkcia);
    ...
  end;
 
procedure TZoznam.PreVsetky(Akcia: TAkcia);
var
  P: TVrchol;
begin
  P := Zoznam;
  while P <> nil do
  begin
    Akcia(P);      // volanie procedúry, ktorú sme dostali ako parameter
    P := P.Next;
  end;
end;

Teraz môžeme zadefinovať niekoľko procedúr typu TAkcia (nie metódy ale globálne procedúry):

procedure Pricitaj(P: TVrchol);
begin
  Inc(P.Info);
end;
 
procedure Vypis(V: TVrchol);
begin
  Write(V.Text, ' -> ');
end;
 
procedure Vynasob(N: TVrchol);
begin
  N.Info := 2 * N.Info;
end;

Na otestovanie zadefinujme 10-prvkový zoznam a spustíme rôzne akcie:

var
  Z: TZoznam;
  I: Integer;
begin
  Z := TZoznam.Create;
  for I := 1 to 10 do
    Z.PridajK(I);
  WriteLn('zoznam =', Z.Text);
  Z.PreVsetky(@Vynasob);
  WriteLn('zoznam po vynasobeni =', Z.Text);
  Z.PreVsetky(@Pricitaj);
  Write('moj vypis zoznamu =');
  Z.PreVsetky(@Vypis);
  ReadLn;
end.

Vo výpise môžeme vidieť pôvodný zoznam, zoznam po vynásobení 2, a zoznam po pričítaní 1 - tento výpis je už realizovaný pomocou PreVsetky(@Vypis):

zoznam = 1 2 3 4 5 6 7 8 9 10
zoznam po vynasobeni = 2 4 6 8 10 12 14 16 18 20
moj vypis zoznamu = 3 -> 5 -> 7 -> 9 -> 11 -> 13 -> 15 -> 17 -> 19 -> 21 ->



Filtrované akcie



Metódu PreVsetky môžeme pozmeniť tak, aby sa spracovali len tie vrcholy spájaného zoznamu, ktoré spĺňajú nejakú podmienku. Túto podmienku zadefinujeme tiež pomocou procedurálneho typu (logická funkcia):

type
  TFilter = function(P: TVrchol): Boolean;
 
  TZoznam = class
  ...
  public
    ...
    procedure PreVsetky(Podmienka: TFilter; Akcia: TAkcia);
    ...
  end;
 
procedure TZoznam.PreVsetky(Podmienka: TFilter; Akcia: TAkcia);
var
  P: TVrchol;
begin
  P := Zoznam;
  while P <> nil do
  begin
    if not Assigned(Podmienka) or Podmienka(P) then
      Akcia(P);
    P := P.Next;
  end;
end;

Tu si všimnite spojenie if not Assigned(Podmienka) or Podmienka(P) then, ktoré označuje, že Akcia(P) sa vykoná buď vtedy, keď podmienka nie je definovaná (Podmienka je nil) alebo (je definovaná a) jej hodnota pre vrchol P je True. Ak by sme v podmienenom príkaze zapísali if Assigned(Podmienka) and Podmienka(P) then, tak pre nedefinovanú podmienku (Podmienka je nil) by sa ani raz nevykonala Akcia(P).

Podobne môžeme využiť filter aj pre výpis vrcholov zoznamu. Budeme vypisovať len tie, ktoré spĺňajú nejakú podmienku:

type
  TZoznam = class
  ...
  public
    ...
    function Text: string;
    function Text(Podmienka: TFilter): string;
    ...
  end;
 
function TZoznam.Text(Podmienka: TFilter): string;
var
  P: TVrchol;
begin
  Result := '';
  P := Zoznam;
  while P <> nil do
  begin
    if not Assigned({{Blue|Podmienka}) or Podmienka(P) then
      Result := Result + P.Text;
    P := P.Next;
  end;
end;
 
function TZoznam.Text: string;
begin
  Result := Text(nil);   // výpis bez podmienky, t.j. všetky prvky zoznamu
end;

Ukážme aj metódy, ktoré pracujú nielen s jednou akciou, ale s postupnosťou akcií, t.j. metódu PreVsetky zapíšeme s filtrom, resp. s viacerými akciami, ktoré sa vykonajú s každým vyhovujúcim vrcholom:

type
  TAkcia = procedure(P: TVrchol);
  TFilter = function(P: TVrchol): Boolean;
  TZoznam = class
  ...
  public
    ...
    procedure PreVsetky(Akcia: TAkcia);
    procedure PreVsetky(Akcia: array of TAkcia);
    procedure PreVsetky(Podmienka: TFilter; Akcia: array of TAkcia);
    ...
  end;
 
procedure TZoznam.PreVsetky(Akcia: array of TAkcia);
var
  P: TVrchol;
  I: Integer;
begin
  P := Zoznam;
  while P <> nil do
  begin
    for I := 0 to High(Akcia) do
      Akcia[I](P);
    P := P.Next;
  end;
end;
 
procedure TZoznam.PreVsetky(Podmienka: TFilter; Akcia: array of TAkcia);
var
  P: TVrchol;
  I: Integer;
begin
  P := Zoznam;
  while P <> nil do
  begin
    if not Assigned(Podmienka) or Podmienka(P) then
      for I := 0 to High(Akcia) do
        Akcia[I](P);
    P := P.Next;
  end;
end;


Aby sme to mohli otestovať, vytvoríme 2 logické funkcie typu TFilter:

function Parne(P: TVrchol): Boolean;
begin
  Result := P.Info mod 2 ;
end;
 
function Test(P: TVrchol): Boolean;
begin
  Result := P.Info mod 7 > 1;
end;

Otestovanie na 10-prvkovom zozname:

var
  Z: TZoznam;
  I: Integer;
begin
  Z := TZoznam.Create;
  for I := 1 to 10 do
    Z.PridajK(I);
  WriteLn('zoznam =', Z.Text);
  Z.PreVsetky(@Parne, [@Vynasob, @Pricitaj]);
  WriteLn('zoznam po spracovani =', Z.Text);
  Z.PreVsetky(@Test, @Pricitaj);
  WriteLn('zoznam po spracovani =', Z.Text);
  ReadLn;
end.

Môžeme vidieť volanie metódy PreVsetky s postupnosťou akcií (otvorené pole) aj s jednou akciou. Program vypíše:

zoznam = 1 2 3 4 5 6 7 8 9 10
zoznam po spracovani = 1 5 3 9 5 13 7 17 9 21
zoznam po spracovani = 1 6 4 10 6 14 7 18 10 21



Procedurálny typ ako atribút



Procedurálny typ môžeme použiť aj v takejto úlohe: do niektorých metód triedy TZoznam pridáme kontrolný výpis, napr. volanie takejto metódy:

procedure Vypis(S: string; P: TVrchol);
begin
  WriteLn(S, P.Text);
end;

Voláme vo všetkých metódach, ktoré menia samotný zoznam, napr. PridajZ a PridajK:

procedure TZoznam.PridajZ(I: Integer);
begin
  Z := TVrchol.Create(I, Z);
  if Z.Next = nil then
    K := Z;
  Vypis('PridajZ ', Z);
end;
 
procedure TZoznam.PridajK(I: Integer);
begin
  ...
  Vypis('PridajK ', K);
end;

Vďaka tomuto môžeme sledovať priebeh zmien v zozname. Ak by sme ale požadovali na kontrolný výpis v niektorých situáciách použiť inú vypisovaciu procedúru, prípadne by sme niekedy tento výpis chceli zablokovať, výhodne využijeme procedurálny typ. Do triedy TZoznam pridáme novú stavovú premennú procedurálneho typu:

type
  TypVypisu = procedure(S: string; P: TVrchol);
 
  TZoznam = class
    ...
    Vypis: TypVypisu;
    ...
  end;

A volania tejto procedúry upravíme takto:

procedure TZoznam.PridajZ(I: Integer);
begin
  ...
  if Assigned(Vypis) then
    Vypis('PridajZ ', Z);
end;
 
procedure TZoznam.PridajK(I: Integer);
begin
  ...
  if Assigned(Vypis) then
    Vypis('PridajK ', K);
end;

Teraz máme úplne k dispozícii kontrolný výpis, napr. takto

var
  Zoznam: TZoznam;
begin
  Zoznam := TZoznam.Create;
  Zoznam.Vypis := @Vypis;
  for I := 1 to 20 do
    if Random(2) = 0 then
      Zoznam.PridajZ(I)
    else
      Zoznam.PridajK(I);
  Zoznam.Vypis := @nil;

V tejto časti programu najprv zapneme kontrolný výpis (priradíme vypisovaciu procedúru) a potom ho vypneme.

V komplexnejších programoch sa podobné situácie riešia pomocou vlastností (property), napr. takto

type
  TypVypisu = procedure(S: string; P: TVrchol);
 
  TZoznam = class
  private
    ...
    Vypis: TypVypisu;
    ...
  public
    property onChange: TypVypisu write Vypis;
  end;

Priradením vhodnej procedúry zapneme kontrolný výpis onChange (pri zmene), priradením nil ho zrušíme.

Na rovnakom princípe fungujú udalosti komponentov vo formulári. Napr. poznáme udalosť onClick pre tlačidlo Button1:

procedure TForm1.Button1Click(Sender: TObject);
begin
  ...
end;

Táto procedúra sa automaticky zavolá pri každom kliknutí na toto tlačidlo. V skutočnosti má trieda TButton definovanú vlastnosť (property) onClick, niečo ako

type
  TNotifyEvent = procedure(Sender: TObject) of object;
 
  TButton = class(...)
    ...
    property onClick: TNotifyEvent read FOnClick write FOnClick;
  end;

A systém zabezpečí spúšťanie tejto procedúry v správnom momente (pri kliknutí na komponent tlačidlo). Ak o tomto mechanizme vieme a vieme ako funguje, môžeme zapísať napr.

  Button2.onClick := Button1.onClick;

ktorý priradí rovnakú udalosť pre Button2 ako má Button1. Alebo možno niekedy využijeme

  if Assigned(Button1.OnClick) then
    Button1.OnClick := nil
  else
    Button1.OnClick := @Button1Click;


Dvojsmerný spájaný zoznam

Každý vrchol si pamätá aj svojho predchodcu (stavová premenná Prev):

type
  TPrvok = Integer;
  TVrchol = class
    Info: TPrvok;
    Prev, Next: TVrchol;
    constructor Create(I: TPrvok; P, N: TVrchol);
    function Text: string; virtual;
  end;
 
constructor TVrchol.Create(I: TPrvok; P, N: TVrchol);
begin
  Info := I;
  Prev := P;
  Next := N;
end;
 
function TVrchol.Text: string;
begin
  Result := ' ' + IntToStr(Info);
end;
 
type
  TZoznam = class
  private
    Z: TVrchol;
    K: TVrchol;
  public
    constructor Create;
    destructor Destroy; override;
    procedure PridajZ(V: TVrchol);
    procedure PridajK(V: TVrchol);
    procedure VsunPred(Pred, V: TVrchol);
    procedure VsunZa(Za, V: TVrchol);
    procedure Vyhod(V: TVrchol);
 
    property Prvy: TVrchol read Z;
    property Posledny: TVrchol read K;
  end;
 
constructor TZoznam.Create;
begin
  Z := nil;
  K := nil;
end;
 
destructor TZoznam.Destroy;
var
  P: TVrchol;
begin
  while Z <> nil do
  begin
    P := Z.Next;
    Z.Free;
    Z := P;
  end;
end;
 
procedure TZoznam.PridajZ(V: TVrchol);
begin
  V.Prev := nil;
  V.Next := Z;
  if K = nil then
    K := V
  else
    Z.Prev := V;
  Z := V;
end;
 
procedure TZoznam.PridajK(V: TVrchol);
begin
  V.Prev := K;
  V.Next := nil;
  if K = nil then
    Z := V
  else
    K.Next := V;
  K := V;
end;
 
procedure TZoznam.VsunPred(Pred, V: TVrchol);
begin
  if Pred = Z then
    PridajZ(V)
  else if Pred = nil then
    PridajK(V)
  else
  begin
    V.Prev := Pred.Prev;
    Pred.Prev := V;
    V.Next := Pred;
    V.Prev.Next := V;
  end;
end;
 
procedure TZoznam.VsunZa(Za, V: TVrchol);
begin
  if Za = nil then
    PridajZ(V)
  else if Za = K then
    PridajK(V)
  else
  begin
    V.Next := Za.Next;
    Za.Next := V;
    V.Prev := Za;
    V.Next.Prev := V;
  end;
end;
 
procedure TZoznam.Vyhod(V: TVrchol);
begin
  if V = nil then           // nič
  else if Z = V then
  begin
    Z := Z.Next;
    if Z <> nil then
      Z.Prev := nil
    else
      K := nil;
    V.Free;
  end
  else
  begin
    V.Prev.Next := V.Next;
    if V.Next <> nil then
      V.Next.Prev := V.Prev
    else
      K := V.Prev;
    V.Free;
  end;
end;


Cyklický zoznam

Vráťme sa k jednosmernému spájanému zoznamu, v ktorom vieme priamo zmeniť hodnotu niektorého prvku:

var
  Z: TZoznam;
...
  Z := TZoznam.Create;
...
  WriteLn(Z.Text);
  Z[5] := TVrchol.Create(999, nil);
  WriteLn(Z.Text);

Takéto priradenie nahradí pôvodný piaty prvok zoznamu novým vrcholom, ktorému aj zmení hodnotu Next - na nasledovný prvok zoznamu, t.j. šiesty. Ak ale piaty prvok nahradíme, napr. ôsmym vrcholom, dostávame poškodený zoznam, ktorý sa takto jednoducho vypísať nedá:

  WriteLn(Z.Text);
  Z[5] := Z[8];
  WriteLn(Z.Text);

Zoznam sa teraz zacyklil, lebo piaty prvok (s hodnotou 8) má nasledovníka šiesty, šiesty má nasledovníka siedmy, siedmy má nasledovníka ôsmy, lenže ten je už šiesty v poradí a teda má nasledovníka šiesty. Keby sme opravili metódu Text na vypisovanie obsahu zoznamu, mohli by sme toto zacyklenie vidieť (metóda teraz vypíše maximálne prvých 100 prvkov zoznamu).

function TZoznam.Text: string;
var
  P: TVrchol;
  Pocet: Integer;
begin
  Result := '';
  P := Z;
  Pocet := 0;
  while (P <> nil) and (Pocet < 100) do
  begin
    Result := Result + P.Text;
    P := P.Next;
    Inc(Pocet);
  end;
  if P <> nil then
    Result := Result + ' ...';
end;


Cyklický zoznam


  • posledný prvok odkazuje na prvý
  • ak je zoznam neprázdny, tak neobsahuje nil
  • treba správne rozpoznať koniec zoznamu (napr. pre výpis, všetky, hľadanie hodnoty a pod.)
  • môžeme použiť len jediný smerník a to na posledný prvok (premenná K - nasledovníkom K je začiatok zoznamu), teda netreba potom udržiavať dva smerníky
  • naprogramujte metódy PridajZ, PridajK, Pocet, Ity a pod.


späť | ďalej