Ugrás a tartalomhoz Lépj a menübe

2.3. Adatstruktúrák

Az egy irányban láncolt lista, két irányban láncolt lista, sor és verem adatstruktúrák jellemzői, létrehozásuk módjai és a hozzájuk kapcsolódó fontosabb műveletek

 

Egy irányban láncolt lista

A láncolt lista olyan homogén, dinamikus, szekvenciális elérésű adatszerkezet, amelynek minden eleme - a tárolandó adatokon kívül - azt az információt is tárolja, hogy a következő elemet hol tárolja a rendszer a számítógép memóriájában.

A lánc első elemének a címét a lista feje tartalmazza. A listafej nem tartalmaz információs részt, azaz tényleges listabeli adatot. A lánc végét az jelzi, hogy az utolsó elemben a rákövetkező elem mutatója üres (NULL).

Új elem felvitele

Új elem felvitelét elvégezhetjük a lista elejére, végére, és adott elem után.

A lista végre történő elem hozzáadásának lépései:

  • a tárolandó adat bekérése vagy előállítása,
  • új listaelem létrehozása; érték beállítása; a következő elem mutatójának „nullázása”,
  • az új elem hozzáfűzése a lista végére,
  • az utolsó elem mutatójának ráállítása az új elemre.

Lista kiírása, feldolgozása

A lista elemein egyesével végig kell menni, és kiírni vagy feldolgozni a tárolt adatot. Az elemek eléréséhez egy segéd mutatót használunk, amelyet kezdetben az első elemre állítunk.

Első, utolsó elem törlése

A lista első elemének törlésénél a „fej” mutatót állítjuk a második elemre, majd felszabadítjuk az első elem által lefoglalt memóriát.

 

Két irányban láncolt lista

Hasonló az egy irányban láncolt listához, ám itt minden listaelem mutatórésze két részből áll: az egyik mutató az adott listaelemet megelőző, a másik az adott listaelemet követő listaelemre mutat. Ha üres a lista, a listát azonosító mutatók értéke végjel.

Két lánc alakul ki, két fejmutatóval. A fejmutatók a két irányban láncolt lista első és utolsó elemére mutatnak. Ha mindkét fejmutató értéke NIL, akkor a két irányban láncolt listának nincs egyetlen eleme sem, azaz üres.

 

A verem fogalma

A verem adatszerkezet egy speciális szekvenciális tároló, amelyből mindig a legutolára betett elemet vehetjük ki legelőször.

Emiatt szokás a vermet LIFO (Last In – First Out) szerkezetnek nevezni.

A verem megengedett műveletei

  • Verembe (push): egy elem betétele a verembe (a verem „tetejére”). Csak akkor lehetséges, ha a verem még nem telt meg.
  • Veremből (pop): a verem „tetején” található elem kivétele a veremből. Csak akkor tudunk elemet kivenni, ha a verem nem üres.
  • Inicializálás:(init): alapállapotba helyezés, űrítés. (Dinamikus megvalósítása esetén ez két különböző eljárás.)
  • Üres?: igaz, ha a veremben egyetlen elemet sem tárolunk.
  • Teli?: igaz, ha a verembe már nem tehetünk újabb elemet, mert megtelt. (Dinamikus megvalósítás esetén csak akkor van tele a verem, ha a rendelkezésünkre álló memória elfogyott)

A verem alkalmazása

Néhány példa a verem adatszerkezet alkalmazására:

  • Programozási nyelvekben az egymásba ágyazott eljárások, illetve függvények, valamint a rekurzió megvalósítása. Az eljárások, függvények lokális változói, érték szerint átvett paraméterei a rendszer veremben kerülnek létrehozásra. Az eljárás végrehajtása után kikerülnek a veremből, azaz megszűnnek. Beágyazott eljárás, függvény hívásakor a veremre kerül a visszatérési cím is, vagyis az, hogy melyik sornál kell majd folytatni a programot, ha a beágyazott eljárás végrehajtásra került.
  • Zárójelezett kifejezés / (), [], {} / helyességének az ellenőrzése. Bal zárójel a verembe kerül, jobb zárójel esetén kivesszük a verem tetején lévő bal zárójelet, és összehasonlítjuk az aktuális jobb zárójellel. Ha párt alkotnak, nem romlott el a zárójelezés, tovább vizsgáljuk. Zárójelezési hibák: nem megfelelő pár; túl sok bal zárójel (a vizsgá- lat végén marad elem a veremben); túl sok jobb zárójel (üres veremből akarunk kivenni). Hasonlóan ellenőrizhető Pascal programban a begin/end; repeat/until; case/end párok helyessége.
  • Undo (mégsem) funkció megvalósítása az alkalmazói programokban. Kissé mó- dosított verem, ugyanis a túlságosan régen végrehajtott műveleteket nem tároljuk. A végrehajtott műveletek kódja (esetleg néhány jellemzője) a verembe kerül, a mégsem végrehajtásakor a legutolsó művelet kódját kivesszük, és visszavonjuk a műveletet.

A verem statikus megvalósítása

Statikus megvalósítás esetén a verembe tett elemeket egy vektorban tároljuk, a veremben lévő elemek számát, más szóval az utoljára betett elem sorszámát egy ún. veremmutató tartalmazza.

Ha új elemet teszünk a verembe, a veremmutató értéke eggyel nő, ha kiveszünk, akkor eggyel csökken.

Üres verem esetén értéke 0, teli verem esetén pedig egyenlő a vektor maximális indexével.

 

Konstans Max=...

 

Típus ElemTipus=...

                 TVerem=Rekord

                                Mut:Egész

                                Elemek:Tömb[1..Max]:ElemTipus

                 Rekord vége

 

Eljárás Init(Változó V:TVerem)

                V.Mut:=0

Eljárás vége

 

Függvény Ures(V:TVerem):Logikai

                Ures:= (V.Mut=0)

Függvény vége

 

Függvény Teli(V:TVerem):Logikai

                Teli= (V.Mut=Max)

Függvény vége

 

Függvény Verembe(Változó V:TVerem;E:ElemTipus):Logikai

                 Ha nem(Teli(V))

                               akkor

                                                V.Mut:=V.Mut+1

                                                V.Elemek[V.Mut]:=E

                                               Verembe:= Igaz

                               különben

                                               Verembe:= Hamis

                 Elágazás vége

Függvény vége

 

Függvény Verembol(Változó V:TVerem;Változó E:ElemTipus):Logikai

                Ha nem(Ures(V))

                                akkor

                                               E:=V.Elemek[V.Mut]

                                                V.Mut:=V.Mut-1

                                                Verembol:= Igaz

                                különben

                                                Verembe:=Hamis

                 Elágazás vége

Függvény vége

 

A sor fogalma

A sor adatszerkezet egy speciális szekvenciális tároló, amelyből mindig a legelsőként betett elemet vehetjük ki legelőször.

Emiatt szokás a sort FIFO (First In – First Out) szerkezetnek nevezni.

A sor megengedett műveletei

  • Sorba (put): egy elem betétele a sorba (a sor „végére”). Csak akkor lehetséges, ha a
  • sor még nem telt meg.
  • Sorból (get): a sor „elején” található elem kivétele. Csak akkor tudunk elemet kivenni,
  • ha a sor nem üres.
  • Inicializálás:(init): alapállapotba helyezés, űrítés.
  • Üres?: igaz, ha a sorban egyetlen elemet sem tárolunk.
  • Teli?: igaz, ha a sorba már nem tehetünk újabb elemet, megtelt. (Dinamikus megvalósítás esetén csak akkor van tele a sor, ha a rendelkezésünkre álló memória elfogyott)

A sor alkalmazása

Néhány példa a sor adatszerkezet alkalmazására:

  • Billentyűzet puffer, nyomtatási sor
  • Gráf szélességi bejárásakor az algoritmus egy sorban tárolja a még nem bejárt, de már kiterjeszett (piros) csúcspontokat.
  • Szimulációk: közlekedés, várakozás szimulálása
  • MI: emlékezet szimulálása: a megismert információk (pl. Memory játékban a felütött lapok) egy sorba kerülnek. Minél jobb a gépi játékos, annál nagyobb a sor kapacitása. Ha a sor megtelik, az elejéről kikerülnek az információk (felejtés)

A sor statikus megvalósítása

Statikus megvalósítás esetén a sorba tett elemeket egy vektorban tároljuk, az első, ill. az utolsó elem sorszámát (mutatóját), valamint a sorban lévő elemek darabszámát egy-egy egész értékben tároljuk.

Ha új elemet teszünk a sorba, a vége mutató, ha kiveszünk egy elemet, akkor pedig az eleje mutató értéke nő (ciklikusan) eggyel. A ciklikus növelés azt jelenti, hogy a maximális érték elérése után a következő lépésben 1 lesz az értéke. Ez a megoldás lehetővé teszi a vektor teljes kihasználását. (Ha a sorba helyezett elemekkel elértük a vektor végét, és közben vettünk ki az elejéről, akkor a sorba tett újabb elemek – fizikailag - a vektor elejére kerülnek)

A darabszám tárolása egyszerűsíti a megvalósítást.

Konstans Max=...

Típus ElemTipus=...

                TSor=Rekord

                               Eleje,Vege,Db:Egész

                               Elemek:Tömb[1..Max]:ElemTipus

                Rekord vége

 

Eljárás Init(Változó S:TSor)

                 S.Db:=0

                 S.Eleje:=1 //Ha egy elemet beteszünk, az S.Eleje és az S.Vege is 1 lesz!

                 S.Vege:=0

Eljárás vége

 

Függvény Ures(S:TSor):Logikai

                 Ures:=(S.Db=0)

Függvény vége

 

Függvény Teli(S:TSor):Logikai

                Teli:=(S.Db=Max)

Függvény vége

 

Függvény Sorba(Változó S:TSor;E:ElemTipus):Logikai

                Ha Nem(Teli(S))

                                akkor

                                               S.Db:=S.Db+1

                                                Ha S.Vege<Max

                                                                akkor

                                                                                S.Vege:=S.Vege+1

                                                               különben

                                                                               S.Vege:=1

                                               Elágazás vége

                                               S.Elemek[S.Vege]:=E

                                               Sorba:=Igaz

                               különben

                                               Sorba:=Hamis

                Elágazás vége

Függvény vége

 

Függvény Sorbol(Változó S:TSor; Változó E:ElemTipus):Logikai

                Ha Nem(Ures(S))

                               akkor

                                               S.Db:=S.Db-1

                                               E:=S.Elemek[S.Eleje]

                                               Ha S.Eleje<Max

                                                               akkor

                                                                               S.Eleje:=S.Eleje+1

                                                               különben

                                                                               S.Eleje:=1

                                               Elágazás vége

                                               Sorbol:=Igaz

                               különben

                                               Sorbol:=Hamis

                Elágazás vége

Függvény vége