Pascal I.      Pascal II.      Delphi       Linkek     
Pascal II.
01. Eljárások, függv...
01. Gyakorló feladatok
02. Felsorolt típus, ...
02. Gyakorló feladatok
03. Állományok kezelése
03. Gyakorló feladatok
04. Unitok, CRT unit
04. Gyakorló feladatok
05. DOS unit, rendezé...
05. Gyakorló feladatok
06. Rekurzió, quicksort
06. Gyakorló feladatok
07. Backtracking
07. Gyakorló feladatok
08. GRAPH unit
08. Gyakorló feladatok
09. Kép mozgatása
09. Gyakorló feladatok
10. Winmouse unit
10. Gyakorló feladatok
11. Dinamikus adatsze...
11. Gyakorló feladatok
12. Dinamikus adatsze...
12. Gyakorló feladatok
13. Dinamikus adatsze...
13. Gyakorló feladatok
Programozás 2 (Pascal)


     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.

     

(C) 2004-2013, PaedDr. Végh Ladislav, Komárno, Szlovákia