27. Spájané zoznamy


posledná zmena: 19.2.2003

Banner Text 18.2.2003

    čo sme sa doteraz naučili

    • zatiaľ poznáme dve dynamické údajové štruktúry: veľké reťazce (string) a dynamické polia (array of ...)
    • pre dynamické štruktúry platí, že im môžeme počas behu programu meniť veľkosť
    • niektoré operácie sa s nimi robia ťažšie lebo sú menej efektívne, napr. pridávať prvok do stredu poľa, znamená, že najprv pole o 1 predĺžime, potom nejakú časť prvkov v pamäti posunieme a na voľné miesto vložíme nový prvok
    • podobne funguje aj trieda TList (preberá sa na cvičeniach) - je založená na dynamickom poli

    čo sa budeme dnes učiť

    • ukážeme spájané zoznamy: zoznam prvkov, v ktorom si každý prvok pamätá svojho nasledovníka
    • vkladať a vyhadzovať prvky zo zoznamu je veľmi jednoduché
    • indexovať prvky zoznamu je dosť časovo neefektívna operácia

Spájané zoznamy (linked list)

Spájané zoznamy budeme používať najmä ako tréning pre dynamické údajové štruktúry realizované pomocou smerníkov

Prvá verzia - starý štýl

  • každý prvok zoznamu je záznam (record) a okrem samotnej informácie obsahuje smerník na nasledovníka v zozname
  • posledný prvok má hodnotu nasledovníka nil:

zoznam pomocou smerníkov na záznam:

 
type
  prvok = integer;
  PVrchol = ^TVrchol;
  TVrchol = record
    info:prvok;
    next:PVrchol;
  end;

var
  z,p:PVrchol;
begin
  z:=nil;                              // z je prázdny zoznam
  new(z); z^.info:=1; z^.next:=nil;    // z je jednoprvkový zoznam
  new(p); p^.info:=2; p^.next:=nil;    // p je jednoprvkový zoznam
  z^.next:=p;                          // z je dvojprvkový zoznam
  new(p); p^.info:=3; p^.next:=nil;    // p je jednoprvkový zoznam
  z^.next^.next:=p;                    // z je trojprvkový zoznam
end;

výpis prvkov zoznamu:

 
  Label1.Caption:=IntToStr(z^.info)+' '+IntToStr(z^.next^.info)+
                  ' '+IntToStr(z^.next^.next^.info);

alebo všeobecne:

 
  Label1.Caption:='zoznam =';
  p:=z;
  while p<>nil do begin
    Label1.Caption:=Label1.Caption+' '+IntToStr(p^.info);
    p:=p^.next;
  end;

uvoľnenie prvkov zoznamu - chybné riešenie:

 
  while z<>nil do begin
    dispose(z);
    z:=z^.next;
  end;

uvoľnenie prvkov zoznamu - správne riešenie:

 
  while z<>nil do begin
    p:=z^.next;
    dispose(z);
    z:=p;
  end;

Poznámka:

  • ak je info časť nejaká dynamická premenná, napr. string, dynamické pole, objekt alebo smerník na nejakú štruktúru, tak dispose vrcholu automaticky neuvoľňuje aj tieto premenné - tieto budú naďalej udržiavané v heap
  • toto môže niekedy spôsobiť problémy s dynamickou pamäťou - zrejme pre malé školské úlohy nie, ale v budúcnosti pri nejakých zložitejších úlohách môžeme na toto natrafiť
  • také isté dôsledky to má aj vtedy, keď info časť je záznam, ktorý v sebe obsahuje niečo dynamické
  • preto niekedy pred samotným dispose sa uvoľňuje aj pamäť dynamického info, napr. pre string to môže byť z^.info:=''; alebo pre dynamické pole z^.info:=nil; a až potom sa robí dispose(z);

Postupné pridávanie prvkov do zoznamu

vytvárame zoznam pridávaním (všimnite si, že sme prestali používať striešku ^):

 
  z:=nil;
  for i:=1 to 20 do begin
    new(p); p.info:=i; p.next:=z;
    z:=p;
  end;

    prvky sa pridávali na začiatok -- v zozname sú v opačnom poradí

pridávanie prvkov na koniec zoznamu -- treba nájsť posledný prvok v zozname a zaň napojiť nový prvok:

 
  AssignFile(t,'cisla.txt'); Reset(t);
  z:=nil;
  while not seekeof(t) do begin
    new(p); read(t,p.info); p.next:=nil;
    if z=nil then z:=p
    else begin
      k:=z;
      while k.next<>nil do k:=k.next;  // nájde posledný prvok v zozname
      k.next:=p;
    end;
  end;
  CloseFile(t);

efektívnejšie riešenie - oplatí sa pamätať si posledný prvok v zozname -  nebude ho treba stále hľadať:

 
  AssignFile(t,'cisla.txt'); Reset(t);
  z:=nil; k:=nil;
  while not seekeof(t) do begin
    new(p); read(t,p.info); p.next:=nil;
    if z=nil then z:=p
    else k.next:=p;
    k:=p;
  end;
  CloseFile(t);

niekedy budeme používať with:

 
  p:=z;
  while p<>nil do
    with p^ do begin
      Label1.Caption:=Label1.Caption+' '+IntToStr(info);
      p:=next;
    end;

Vrchol zoznamu bude objekt

prvky zoznamu budú objekty (t.j. sú to smerníky):

 
type
  prvok = integer;
  TVrchol = class
    info:prvok;
    next:TVrchol;
    constructor Create(i:prvok; n:TVrchol);
    destructor Destroy; override;
    function vypis:string; virtual;
  end;

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

destructor TVrchol.Destroy;
begin
  // next.Free;   --> rekurzia - napr. pre dlhé zoznamy problém so zásobníkom
  next:=nil;     // v skutočnosti toto priradenie nie je potrebné
end;

function TVrchol.vypis:string;
begin
  Result:=' '+IntToStr(info);
end;

Poznámka:

  • na rozdiel od vrcholu-záznamu (record), pre ktorý info-časť s dynamickou premennou môže robiť problémy, vrchol-objekt automaticky uvoľní všetky svoje stavové premenné, ktoré sú buď veľké reťazce (string) alebo dynamické polia
  • preto v metóde Destroy netreba v týchto prípadoch uvoľňovať takéto info
  • toto neplatí pre stavové premenné, ktoré sú objekty (napr. ak by to bola bitmapa alebo vrchol) - tieto sa neuvoľňujú a musí to zabezpečiť programátor

použite zoznamu z vrcholov, ktoré sú objekty:

 
var
  p:TVrchol;
begin
  p:=TVrchol.Create(11,TVrchol.Create(22,TVrchol.Create(33,nil)));
  Label5.Caption:=p.vypis+p.next.vypis+p.next.next.vypis;
  p.next.next.Free;
  p.next.Free;
  p.Free;

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 vypis:string;
    procedure pridajZ(i:prvok);
    procedure pridajK(i:prvok);
    procedure vsun(pred:integer; i:prvok);
  end;

constructor TZoznam.Create;
begin
  z:=nil; k:=nil;    // v skutočnosti toto urobí automaticky konštruktor
end;

destructor TZoznam.Destroy;
var
  p:TVrchol;
begin
  while z<>nil do begin
    p:=z.next; z.Free; z:=p;
  end;
end;

function TZoznam.vypis:string;
var
  p:TVrchol;
begin
  Result:=''; p:=z;
  while p<>nil do begin
    Result:=Result+p.vypis;
    p:=p.next;
  end;
end;

procedure TZoznam.pridajZ(i:prvok);
begin
  z:=TVrchol.Create(i,z);
  if k=nil then k:=z;
end;

procedure TZoznam.pridajK(i:prvok);
var
  p:TVrchol;
begin
  p:=TVrchol.Create(i,nil);
  if z=nil then z:=p
  else k.next:=p;
  k:=p;
end;

procedure TZoznam.vsun(pred:integer; i:prvok);
var
  p,q:TVrchol;
begin
  if pred<2 then pridajZ(i)
  else begin
    q:=z;
    while (q<>nil) and (pred>2) do begin
      dec(pred);
      q:=q.next;
    end;
    p:=TVrchol.Create(i,nil);
    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;

NDÚ:

  • do triedy TZoznam doplňte metódy:
    • function pocet:integer;
    • procedure vyhodZ;                    // vyhodí prvý prvok
    • procedure vyhodK;                    // vyhodí posledný prvok
    • procedure vyhodIty(index:integer);   // vyhodí í-ty prvok
    • procedure vyhod(i:prvok);            // vyhodí prvok s info i
    • procedure prevrat;                   // prevráti poradie prvkov v zozname
    • function najdi(i:prvok):integer;     // zistí index
    • procedure utried;
         // nájde minimum, dá ho na začiatok,
         // znovu nájde minimum zo zvyšku, dá ho za minimum, ...
    • procedure zarad(i:prvok);
         // zaradí prvok do zoznamu, aby ostal zoznam utriedený
    • procedure vyhodDuplikaty;
         // vyhodí vrcholy s rovnakým info - nechá len prvý z nich
    • function ity(i:integer):TVrchol;     // vráti í-ty prvok
    • constructor Citaj(stream:TStream);   // načíta zoznam z prúdu
  • predpokladajte, že stavové premenné info a next sú súkromné a môžu sa inicializovať len v konštruktore, pre triedu TZoznam napíšte constructor Citaj(stream:TStream), ktorý z otvoreného údajového prúdu načíta a v správnom poradí vytvorí kompletný spájaný zoznam

Polymorfný zoznam

prvkami zoznamu môžu byť nielen inštancie triedy TVrchol, ale aj ľubovoľné odvodené triedy:

 
type
  TZoznam = class
  private
    z:TVrchol;    // začiatok zoznamu
    k:TVrchol;    // koniec zoznamu
  public
    constructor Create;
    destructor Destroy; override;
    function vypis:string;
    procedure pridajZ(i:prvok); overload;
    procedure pridajZ(p:TVrchol); overload;
    procedure pridajK(i:prvok); overload;
    procedure pridajK(p:TVrchol); overload;
    procedure vsun(pred:integer; i:prvok); overload;
    procedure vsun(pred:integer; p:TVrchol); overload;
  end;

...

procedure TZoznam.pridajZ(i:prvok);
begin
  z:=TVrchol.Create(i,z);
  if k=nil then k:=z;
end;

procedure TZoznam.pridajZ(p:TVrchol);
begin
  p.next:=z; z:=p;
  if k=nil then k:=z;
end;

procedure TZoznam.pridajK(i:prvok);
begin
  pridajK(TVrchol.Create(i,nil));
end;

procedure TZoznam.pridajK(p:TVrchol);
begin
  p.next:=nil;
  if z=nil then z:=p
  else k.next:=p;
  k:=p;
end;

...

test polymorfného zoznamu:

 
type
  TVrchol1 = class(TVrchol)
    info1:string;
    constructor Create(i:string; n:TVrchol);  // pozor nie n:TVrchol1
    function vypis:string; override;
  end;

constructor TVrchol1.Create(i:string; n:TVrchol);
begin
  info:=0; info1:=i; next:=n;
end;

function TVrchol1.vypis:string;
begin
  Result:=' '+info1;
end;

...

var
  z:TZoznam;
  i:integer;
begin
  z:=TZoznam.Create;
  for i:=1 to 20 do
    if random(2)=0 then
      z.pridajZ(i)       // inštancia triedy TVrchol
                         // čo je to isté ako   z.pridajZ(TVrchol.Create(i,nil))
    else
      z.pridajZ(TVrchol1.Create(IntToStr(i)+'x',nil));
  Label1.Caption:=z.vypis;
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; p: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; p:TVrchol);
var
  q,r:TVrchol;
begin
  if i<1 then pridajZ(p)
  else begin
    q:=ity(i-1);
    if (q=nil) or (q.next=nil) then pridajK(p)
    else begin
      r:=q.next; q.next:=p; p.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);
  Label1.Caption:='';
  for i:=1 to z.pocet do
    Label1.Caption:=Label1.Caption+z.prvky[i].vypis;

    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);
  Label1.Caption:='';
  for i:=1 to z.pocet do
    Label1.Caption:=Label1.Caption+z[i].vypis;

NDÚ:

zistite, prečo nebude fungovať takáto výmena prvkov zoznamu:

 
var
  t:TVrchol;
...
  t:=z[i1];
  z[i1]:=z[i2];
  z[i2]:=t;

© 2003 AB, KVI
blaho@fmph.uniba.sk