11 Dinamikus adatszerkezetek
- egyirányú láncolt lista
egy elem létrehozása, használata és felszabadítása
egyirányú láncolt lista
11.1 Egy elem létrehozása, használata és felszabadítása
Dinamikus adatszerkezeteket főleg akkor érdemes
használnunk (például tömb helyett), ha nem
tudjuk előre meghatározni mennyi elemünk lesz. Másik
nagy előnye, hogy mindig csak annyi memória van lefoglalva,
amennyire szükségünk van. A memóriát a
program futása alatt foglaljuk le és szabadítjuk
fel, amikor új elemet hozunk létre vagy elemet
törlünk ki.
A dinamikus adatszerkezeteket nagyon jól
használhatók bináris fák, gráfok
tárolására,
ábrázolására is a
számítógépben.
A dinamikus adatszerkezeteknél mindenekelőtt definiálnunk kell egy elemtípust a type
kulcsszó segítségével. Itt mindjárt
definiálhatunk egy pointer (mutató) típust is,
amely egy ilyen elemre fog mutatni. Pl.:
type PElem = ^Elem; { a PTElem egy mutato, ami Elem tipusra mutat }
Elem = record { Elem tipus definialasa }
szam: integer;
kov: PElem;
end;
Ezek után már csak deklarálnunk kell néhány ilyen pointert, pl.:
var p: PElem;
Majd kezdődhet a program fő része. Alapértelmezett értékben, amíg a p pointer nem mutat semmilyen memóriaterületre sem, az értéke nil.
Később ezt az értéket fogjuk hozzárendelni
akkor is, ha például törölünk egy elemet és
azt szeretnénk, hogy valamilyen mutató már ne
mutasson sehová sem a memóriában.
Új elemnek a
new parancs segítségével foglalhatunk le
szabad memóriarészt:
new(p);
A new parancs
lefoglalja a szükséges memóriaterületet, majd a
p pointerbe berakja ennek a memóriaterületnek a címét.
A memória lefoglalása után a lefoglalt elem
egyes részeit (pl. szam) a következő képpen
olvashatjuk be vagy írhatjuk ki:
readln(p^.szam);
writeln(p^.szam);
Megfigyelhetjük, hogy itt már nem p-t, hanem p^-t használunk. Ennek oka, hogy nem a p pointert akarjuk beolvasni vagy kiírni, hanem a p pointer által mutatott memóriaterületnek (p^) a "szam" részét (a p
pointernek nincs szám része, az csak egy 4 bájtnyi
memóriaterület, amely egy memóriacímet
tartalmaz).
Ha már nincs szükségünk a lefoglalt
memóriaterületre, akkor a program végén illik
azt felszabadítani. Ezt a dispose parancs
segítségével tehetjük meg, amely ellentettje a new parancsnak:
dispose(p);
11.2 Egyirányú láncolt lista
A következő interaktív animáció bemutatja az egyirányú láncolt listát:
Az alábbi példaprogram egy egyirányú
láncolt lista kialakítását
szemlélteti. A láncolt listában egész
számokat tárolunk. A program addig olvas be egész
számok, amíg nem adunk meg számként 0-t. Ha
nem 0-t adtunk meg, lefoglaljuk az új elemnek a
memóriát, majd beírjuk a "szam"
részébe a beolvasott egész számot (uj^.szam:=a), beállítjuk, hogy ez után az elem után még nincs következő elem (uj^.kov:=nil), majd beállítjuk az első mutatót (elso:=uj) erre az elemre (ha ez az első elemünk), vagy az utolsó elem következőjét (utolso^.kov:=uj)
erre az elemre (ha már van elemünk a listában).
Végül beállítjuk, hogy a lista utolsó
eleme a most létrehozott új elem (utolso:=uj).
program Pelda32;
uses crt;
type PElem = ^Elem; { a PTElem egy mutato, ami Elem tipusra mutat }
Elem = record { Elem tipus definialasa }
szam: integer;
kov: PElem;
end;
var a: integer;
uj,akt,elso,utolso: PElem;
begin
clrscr; {beolvasas}
repeat
writeln('Kerek egy szamot (0-bevitel vege):');
readln(a);
if a>0 then begin
new(uj);
uj^.szam:=a;
uj^.kov:=nil;
if elso=nil then elso:=uj
else utolso^.kov:=uj;
utolso:=uj;
end;
until a=0;
writeln; {kiiras}
akt:=elso;
while akt<>nil do begin
write(akt^.szam,',');
akt:=akt^.kov;
end;
writeln; {memoria felszabaditasa}
akt:=elso;
while akt<>nil do begin
elso:=akt^.kov;
dispose(akt);
akt:=elso;
end;
end.
A beolvasás után beállítottuk az akt
mutató értékét az első elemre, majd egy
ciklus segítségével kiírtuk az
aktuális elemet és az akt mutatót beállítottuk a következő elemre. Ezt mindaddig elvégeztük, amíg az akt értéke nem nil, vagyis amíg nem írtuk ki az összes elemet.
A memória felszabadítása a program
végén szintén egy ciklus
segítségével történik.
Az egyirányú láncolt
lista segítségével ki tudunk alakítani sort vagy vermet. A sor
kialakítása során a memóriában létrejövő dinamikus adatszerkezetet (mely
valójában egyirányú láncolt lista) szemlélteti az alábbi interaktív animáció:
A
verem
kialakítását mutatja be a következő interaktív animáció:
Az
alábbi alkalmazás segítségével kipróbálhatjuk a dinamikus adatszerkezeteknél
használt parancsokat, miközben megfigyelhetjük milyen folyamat megy végbe a
memóriában:
A fenti alkalmazás
segítségével próbáljunk meg kialakítani pl. egy egyirányú láncolt listát.