28. Použitie spájaných zoznamov

posledná zmena: 4.3.2003

25.2.2003

čo sme sa doteraz naučili

vytvorili sme triedu TZoznam, pomocou ktorej môžeme veľmi pohodlne pracovať s jednosmerným spájaným zoznamom

čo sa budeme dnes učiť

procedurálny typ a jeho využitie pri práci so spájaným zoznamom
špeciálne typy spájaných zoznamov: dvojsmerný spájaný zoznam, cyklický spájaný zoznam a spájaný zoznam s fiktívnym vrcholom

Evidovanie zmeny v zozname

Do triedy TZoznam pridáme virtuálnu metódu oznamit (notify) a do každej metódy, ktorá nejako modifikuje zoznam pridáme volanie tejto metódy.

napríklad:

type
  TAkcia = (aPridaj,aZmen,aZrus);
  TZoznam = class
  public
    ...
    procedure oznamit(p:TVrchol; akcia:TAkcia); virtual;
    ...
  end;

procedure TZoznam.oznamit(p:TVrchol; akcia:TAkcia);
begin
end;

procedure TZoznam.zmen(i:integer; p:TVrchol);
begin
  ...
  oznamit(p,aZmen);
end;

procedure TZoznam.pridajZ(p:TVrchol);
begin
  ...
  oznamit(p,aPridaj);
end;

procedure TZoznam.zrus(p:TVrchol);
begin
  ...
  oznamit(p,aZrus);
end;

...

Ak by sme niekedy v budúcnosti potrebovali napr. vypisovať informácie o všetkých zmenách v zozname do nejakého Memo, stačí predefinovať virtuálne oznamit a hneď uvidíme všetky zmeny.

napríklad:

type
  TMojZoznam = class(TZoznam)
  public
    procedure oznamit(p:TVrchol; akcia:TAkcia); override;
  end;

procedure TMojZoznam.oznamit(p:TVrchol; akcia:TAkcia);
const
  a:array[TAkcia] of string = ('Pridaj','Zmen','Zrus');
begin
  Form1.Memo1.Lines.Add(a[akcia]+' : '+p.vypis);
end;

Tento prístup má napr. takú nevýhodu, že niekedy bude treba vyrábať nové podtriedy, ak chceme meniť správanie metódy oznamit. Niekedy to zbytočne skomplikuje návrh projektu. Iný spôsob, ktorý nám umožní robiť to isté, ale inak, je pomocou procedurálneho typu.

Procedurálny typ

hodnotou nejakého procedurálneho typu je buď nil alebo procedúra (alebo funkcia) istého typu
pri definovaní procedurálneho typu treba zadefinovať mená a typy parametrov

napríklad:

type procedura = procedure(p:TVrchol; a:TAkcia);

hodnotou premennej typu procedura môže byť odkaz (referencia) na ľubovoľnú procedúru, ktorá má práve dva parametre daných typov
hodnotou môže byť len globálna procedúra - nesmie to byť lokálna procedúra ani metóda nejakej triedy
procedurálny typ môžeme zadefinovať aj tak, že hodnotami môžu byť len metódy nejakej triedy -- za definíciu musíme uviesť of object

napríklad:

type procedura = procedure(p:TVrchol; a:TAkcia) of object;

s premenou typu procedura, môžeme pracovať takto

napríklad:

procedure p1(p:TVrchol; a:TAkcia);
begin
  // spracuj vrchol
end;

type
  procedura = procedure(p:TVrchol; a:TAkcia);
var
  pr:procedura;
begin
  pr:=p1;
  pr(v,aPridaj);    // je to isté ako p1(v,aPridaj);
  pr:=nil;          // teraz už pr volať nesmieme

ak máme dve globálne procedúry p1 a p2, ktoré majú rovnaké formálne parametre ako definícia typu procedura,

tak môžeme aj

var
  pr:array[1..2] of procedura = (p1,p2);
  ...
  pr[1](v,aPridaj);    // zavolá procedúru p1
  pr[2](v.next,aZmen); // zavolá procedúru p2

či je hodnotou premennej proc procedurálneho typu nil alebo nie, nemôžeme testovať takto
```
    if proc<>nil then ...
```
hlásila by sa chyba, že volanie proc má málo parametrov
použijeme štandardnú funkciu Assigned, ktorá zistí, či je v procedurálnej premennej priradená ne-nil-ová hodnota, napr.
```
    if Assigned(proc) then proc(v,aZmen);
```

Nasledujúci príklad, ukáže ako môžeme virtuálnu metódu oznamit nahradiť procedurálnou stavovou premennou akZmena (OnChange)

napríklad:

type
  procedura = procedure(p:TVrchol; a:TAkcia);
  TZoznam = class
  private
    ...
    takZmena:procedura;
          // takZmena je súkromná, používateľ ju môže meniť len pomocou property
  public
    ...
    property akZmena:procedura {read takZmena} write takZmena;
  end;

Všade tam, kde bolo volanie oznamit, príde volanie akZmena, napr.

procedure TZoznam.pridajZ(p:TVrchol);
begin
  ...
  if Assigned(takZmena) then takZmena(p,aPridaj);
end;

Príklad použitia

zadefinujeme si svoju procedúru (správneho typu) zmena
priradíme ju do akZmena

napríklad:

procedure zmena(p:TVrchol; akcia:TAkcia);
const
  a:array[TAkcia] of string = ('Pridaj','Zmen','Zrus');
begin
  Form1.Memo1.Lines.Add(a[akcia]+' : '+p.vypis);
end;

...
  z:=TZoznam.Create;
  z.akZmena:=zmena;
...
  z.akZmena:=nil;   // hocikedy môžeme zmeniť obsah premennej akZmena
...

Použitie procedurálnych typov ukážeme aj na iných príkladoch.

Metóda vsetky

Spustí nejakú akciu na každom vrchole spájaného zoznamu, napr.

type
  prikaz = procedure(p:TVrchol);
  TZoznam = class
  ...
  public
    ...
    procedure vsetky(pr:prikaz);
    ...
  end;

procedure TZoznam.vsetky(pr:prikaz);
var
  p:TVrchol;
begin
  p:=z;
  while p<>nil do begin
    pr(p);
    p:=p.next;
  end;
end;

Filtrovaný výpis

Vypíše len tie vrcholy zoznamu, ktoré spĺňajú nejakú podmienku, napr.

type
  filter = function(p:TVrchol):boolean;
  TZoznam = class
  ...
  public
    ...
    function vypis:string; overload;
    function vypis(f:filter):string; overload;
    ...
  end;

function TZoznam.vypis(f:filter):string;
var
  p:TVrchol;
begin
  Result:=''; p:=z;
  while p<>nil do begin
    if not Assigned(f) or f(p) then Result:=Result+p.vypis;
    p:=p.next;
  end;
end;

function TZoznam.vypis:string;
begin
  Reslut:=vypis(nil);   // výpis bez podmienky, t.j. všetky
end;

Metóda vsetky s filtrom, resp. s viacerými príkazmi, ktoré sa vykonajú s každým vyhovujúcim vrcholom:

type
  prikaz = procedure(p:TVrchol);
  filter = function(p:TVrchol):boolean;
  TZoznam = class
  ...
  public
    ...
    procedure vsetky(pr:prikaz); overload;
    procedure vsetky(f:filter; pr:prikaz); overload;
    procedure vsetky(f:filter; pr:array of prikaz); overload;
    ...
  end;

procedure TZoznam.vsetky(f:filter; pr:prikaz);
var
  p:TVrchol;
begin
  p:=z;
  while p<>nil do begin
    if not Assigned(f) or f(p) then pr(p);
    p:=p.next;
  end;
end;

procedure TZoznam.vsetky(f:filter; pr:array of prikaz);
var
  p:TVrchol;
  i:integer;
begin
  p:=z;
  while p<>nil do begin
    if not Assigned(f) or f(p) then
      for i:=low(pr) to high(pr) do pr[i](p);
    p:=p.next;
  end;
end;

v nasleduj[com príklade predpokladáme, že TVrchol1 je odvodený z TVrchol a obsahuje stringovú premennú info1 (z predchádzajúcej prednášky)

príklad:

function f1(p:TVrchol):boolean;
begin
  Result:=p is TVrchol1;
end;

function f2(p:TVrchol):boolean;
begin
  Result:=not (p is TVrchol1) and (p.info mod 3<>0);
end;

function f3(p:TVrchol):boolean;
begin
  Result:=not (p is TVrchol1) and (p.info mod 3<>0) or
          (p is TVrchol1) and (length(TVrchol1(p).info1)<6);
end;

procedure pr1(p:TVrchol);
begin
  if p is TVrchol1 then TVrchol1(p).info1[1]:=upcase(TVrchol1(p).info1[1])
  else inc(p.info);
end;

procedure pr2(p:TVrchol);
begin
  if p is TVrchol1 then TVrchol1(p).info1:='x'+TVrchol1(p).info1
  else inc(p.info,2);
end;

...
  Memo1.Lines.Add(z.vypis(nil));
  Memo1.Lines.Add(z.vypis(f1));
  Memo1.Lines.Add(z.vypis(f2));
  z.vsetky(f3,pr1);
  Memo1.Lines.Add(z.vypis);
  z.vsetky(nil,[pr2,pr1,pr2]);
  Memo1.Lines.Add(z.vypis);
...

Polynómy

Trieda TPolynom je ukážka použitia spájaných zoznamov. Polynóm je realizovaný spájaným zoznamom, pričom každý vrchol zoznamu obsahuje jeden člen polynómu ako dvojicu: koeficient (real) a exponent (integer). Dohodneme sa, že členy polynómu sú usporiadané zostupne podľa exponentov a zoznam neobsahuje členy s nulovým koeficientom.

deklarácie:

type
  TVrchol = class
    koef:real;
    expo:integer;
    next:TVrchol;
    constructor Create(k:real; e:integer; n:TVrchol);
    function vypis:string; virtual;
  end;

constructor TVrchol.Create(k:real; e:integer; n:TVrchol);
begin
  koef:=k; expo:=e; next:=n;
end;

function TVrchol.vypis:string;
begin
  Result:=FloatToStr(koef)+'*x^'+IntToStr(expo);
end;

///////////////////////////////////////////////////

type
  proc = procedure(v:TVrchol);
  TPolynom = class
  private
    z:TVrchol;
  public
    constructor Create;
    destructor Destroy; override;
    procedure pridaj(k:real; e:integer);
    procedure vyhod(e:integer);
    procedure vsetky(pr:proc);
    function vypis:string;
    procedure deriv;
    procedure pricitaj(p:TPolynom);
    procedure odcitaj(p:TPolynom);
    procedure vynasob(p:TPolynom);
    procedure vydel(p:TPolynom);
    procedure vynasobK(k:real);
    function hladaj(e:integer):TVrchol;
    ....
  end;

function TPolynom.hladaj(e:integer):TVrchol;
begin
   // vráti prvok s expo=e alebo bezprostredného predchodcu (ak neex.) alebo nil,
   // ak neex. ani predchodca
end;

procedure TPolynom.pridaj(k:real; e:integer);
var
  p:TVrchol;
begin
  p:=hladaj(e);
  if p=nil then z:=TVrchol.Create(k,e,z)
  else if p.expo=e then begin
    p.koef:=p.koef+k;
    if p.koef=0 then vyhod(e);
  end
  else p.next:=TVrchol.Create(k,e,p.next)
end;

procedure TPolynom.vyhod(e:integer);
var
  p,q:TVrchol;
begin
  if z<>nil then
    if z.expo=e then begin
      q:=z; z:=z.next; q.Free;
    end
    else begin
      p:=hladaj(e+1);
      if (p<>nil) and (p.next<>nil) and (p.next.expo=e) then begin
        q:=p.next; p.next:=p.next.next; q.Free;
      end
    end;
end;

procedure TPolynom.vsetky(pr:proc);
var
  p:TVrchol;
begin
  p:=z;
  while p<>nil do begin
    pr(p);
    p:=p.next;
  end;
end;

procedure deriv1(v:TVrchol);
begin
  with v do begin
    koef:=koef*expo;
    dec(expo);
  end;
end;

var
  str:string;

procedure vypis1(v:TVrchol);
begin
  str:=str+v.vypis+' + ';
end;

procedure TPolynom.deriv;
begin
  vyhod(0);
  vsetky(deriv1);
end;

function TPolynom.vypis:string;
begin
  str:='';
  vsetky(vypis1);
  if str<>'' then SetLength(str,Length(str)-3);
  Result:=str;
end;

NDÚ:

dodefinujte chýbajúce metódy
zadefinujte ďalšie metódy na

uloženie/čítanie polynómu do/zo Streamu
vyhodnotenie polynómu pre nejakú konkrétnu hodnotu x
vytvorenie tabuľky hodnôt pre nejaké x z daného intervalu a pre daný krok - tabuľku hodnôt treba zapísať do Stream alebo nakresliť graf

Dvojsmerný spájaný zoznam

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

type
  prvok = integer;
  TVrchol = class
    info:prvok;
    prev,next:TVrchol;
    constructor Create(i:prvok; p,n:TVrchol);
    function vypis:string; virtual;
  end;

constructor TVrchol.Create(i:prvok; p,n:TVrchol);
begin
  info:=i; prev:=p; next:=n;
end;

function TVrchol.vypis: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;

Zacyklený zoznam

Spomeňme si na poslednú úlohu z predchádzajúcej prednášky

prečo nie je korektný takýto vymen pre obyčajný zoznam:

procedure TZoznam.vymen(i1,i2:integer);
var
  t:TVrchol;
begin
  t:=prvky[i1];
  prvky[i1]:=prvky[i2];
  prvky[i2]:=t;
end;

Zoznam sa veľmi často pri takomto vymieňaní zacyklí - nejaký vrchol má svojho nasledovníka (next) niektorého z predchádzajúcich v zozname.

NDÚ:

vyriešte metódu vymen korektne

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.

Zoznam s fiktívnym vrcholom

už pri inicializácii zoznamu (konštruktor Create) sa vytvorí jeden vrchol, ktorý bude fiktívny (nebude nás zaujímať hodnota vo vrchole)
takýto zoznam nikdy nebude prázdny! => zjednodušia sa všetky metódy, lebo nemusia testovať na prázdny zoznam
preprogramujte pridajZ, ale aj iné metódy
rozmyslite si, ako sa zmení cyklický zoznam s fiktívnym vrcholom, dvojsmerný zoznam s fiktívnym vrcholom, cyklický dvojsmerný, ...