19. fejezet: Dinamikus adatszerkezetek

A programunkban használt változókat a program elején deklarálnunk kell. Ezeknek a memóriát a program futása kezdetén lefoglalja. A tömbök méretét is fordítási időben kell megadnunk, azon később már nem változtathatunk: ezért mindig a lehető legnagyobb tömböt deklaráljuk, legfeljebb nem használjuk ki. Ezek az adatok egy stack nevű memóriaterületen helyezkednek el, statikus adatoknak nevezzük őket.
Gondoljuk el a következő példát: emberek mozgását követjük két helyszín között, melyeket két tömb ír le. Ha valaki egyik helyszínről átmegy a másikra, az egyik tömbből kivesszük, a másikba betesszük. Így mindkét tömb mérete az emberek maximális száma kell, hogy legyen, vagyis pontosan kétszer annyi memóriát foglalunk le, mint amennyit egy időben felhasználunk.
Másik példa: egy program, mely a képernyőre kattintva egy új objektumot hoz létre. Ezek száma tetszőleges, mekkora tömböt deklaráljunk a tárolásukra?

Valójában már eddig is használtuk a dinamikus memóriaterületet. Deklarálunk egy osztályt: var g:TButton, majd létrehozunk egy objektumot: g:=TButton.Create(Form1). A g mutató a statikus memóriaterületen van, az általa mutatott objektum viszont futási időben jön létre. A memória foglalása csak a Create végrehajtásának pillanatában történik meg. A dinamikusan, futás közben létrehozott objektumokat a program a heap nevű memóriaterületen tárolja. Ezt korlátozhatjuk, de lehet akár a teljes rendelkezésre álló szabad memória is.

Lista és rekurzív típusdeklaráció

Figyeljük meg a következő típust!

TYPE lancszem=class
  adat:integer;
  mutato:lancszem;
end;

Egy lancszem típusú objektum tartalmaz egy egész számot és egy osztály típusú mutatót. A mutató egy újabb, lancszem típusú objektumra mutat. A fordító képes értelmezni ezt a rekurziót (önhivatkozást). Ez a mutató fogja megmutatni a memóriában a következő láncszemet. A következő példában látható, hogyan lehet tetszőleges számú egész számot ebben a láncszemekből álló listában tárolni. Ha egy mutató nem mutat sehová (a lánc utolsó eleme), értékét NIL-re állítjuk. Ez egy speciális mutató-érték, jelzi, hogy a mutató nem mutat sehová.

VAR fej:lancszem; //mutató a lista első elemére, fejére
    utolso:lancszem; //mutató a lista utolsó elemére
    n:integer;
BEGIN
  fej:=nil;
  Repeat
    readln(n);
    if n>0 then begin
      if fej=nil then begin
        fej:=lancszem.Create;
        utolso:=fej;
      end else begin
        utolso.mutato:=lancszem.Create;
        utolso:=utolso.mutato;
      end;
      utolso.adat:=n;
      utolso.mutato:=nil;
    end;
  Until n=0;
END.

A fejmutató csak egyszer kap értéket, amikor az első elemet helyezzük el a listában. Új elem berakásakor létrehozunk a heap-en egy új láncszem objektumot, és az eddigi utolsó elem mutatóját ráállítjuk.

A lista bejárása mindig a fejétől kezdődik, és elemenként történik, mert minden elemre csak az őrá mutató elem által juthatunk.

 
utolso:=fej;
  while utolso<>nil do begin
      writeln(utolso.adat);
      utolso:=utolso.mutato;
  end;

Ha a listából elemet törlünk a destruktor segítségével, az őt megelőző elem mutatóját arra az elemre (vagy nil-re) kell állítani, amelyre eredetileg a törölt elem mutatott. Elem beszúrásakor is ügyelni kell a mutatók módosítására.

Lista vagy tömb?

A lista bizonyos szempontból jobb, más szempontból rosszabb a tömbnél.
A lista mellett szól:

mérete dinamikusan változtatható
adott elem törlése, elem beszúrása gyors, mert a listaelemeket nem kell mozgatni a memóriában, elég csak két mutató értékét módosítani

A tömb mellett szól:

a tömb adott sorszámú elemét gyorsan megkaphatjuk (indexelés), míg a lista 100. eleméhez a fejtől kiindulva végig kell lépegetni az előző elemeken
a memóriafelhasználás rugalmatlan, de tervezhető

Ha tehát a tömbünkön jellemzően for-ciklussal lépegetünk végig, használhatunk helyette listát. Ha azonban sokszor ugrálunk a tömbelemek között, a tömb használata gyorsabb programot eredményez.
Ha a tömbös programunk elindul, a tömb biztosan befért a memóriába. A lista viszont, mivel mérete folyamatosan nőhet, egyszer csak kinőheti a memóriát.
Ha dinamikusan növekvő adatszerkezetre van szükségünk, csak a lista jöhet szóba. Az indexelés okozta sebességcsökkenésre megfelelő algoritmusokkal kell megoldást találnunk.

Beépített lista típus

A Free Pascal rendelkezik beépített listatípussal, melyhez a lista kezelését megkönnyítő metódusok is tartoznak. A TList class által megvalósított lista csak mutatókat képes tárolni, ellentétben az előző példával, ahol a listaelem adatmezője integer. Viszont egy mutató tetszőleges adatot tároló objektumra mutathat.
A TList legfontosabb eljárásai és függvényei:

Create
Count: megadja a lista elemszámát
Add(mutató): a mutatót, mint adatot, a lista végéhez fűzi (tárolja)
Remove(mutató): megkeresi a mutató első előfordulását, és törli a listából
Delete(sorszám): az adott sorszámú elemet törli a listából; a számozás 0-val kezdődik!
Items[sorszám]: tömbként viselkedik, megadja az adott sorszámú mutatót

Látható, hogy így a listát tömbhöz hasonlóan tudjuk kezelni. A fenti példát nézzük meg ezzel a listatípussal is! Mivel a listaelemekben nem tudunk számokat tárolni, külön létre kell hoznunk számot tároló objektumokat, ez lesz a TSzam class.

USES Classes;

TYPE TSzam=class
  adat:integer;
end;

VAR sz:TSzam;
    lista:TList;
    n,i:integer;

BEGIN
  lista:=TList.Create;
  Repeat
    readln(n);
    if n>0 then begin
      sz:=TSzam.Create;
      sz.adat:=n;
      lista.Add(sz);
    end;
  Until n=0;

  for i:=0 to lista.Count-1 do
    writeln(TSzam(lista.Items[i]).adat);
  readln;
END.

Megjegyzések: a TList a Classes unitban van. Figyeljük meg a kiírásnál szereplő típuskényszerítést: a TList elemei egyszerű mutatók (Pointer típus), meg kell tehát adnunk, hogy TSzam-ként akarjuk őket kezelni.

Előző Tartalom Következő