ADATSZERKEZETEK (VEREM, SOR)

Petrik tananyagtár: Adatszerkezetek (verem, sor) Petrik Lajos Vegyipari, Környezetvédelmi és Informatikai Szakközépiskola Szoftverfejlesztő szak, 14. évfolyam, OKJ szám: 54 481 02 0010 54 04

___________________________________________________________________________

ADATSZERKEZETEK (VEREM, SOR) 1.

ADATSZERKEZET FOGALMA

Az adatszerkezet egymással kapcsolatban álló adatok összessége, amelyen meghatározott, az adatszerkezetre jellemző műveletek végezhetők el. Az adatok közötti kapcsolatok alapján megkülönböztethetünk: - szekvenciális szerkezeteket, sorozatokat (pl. szekvenciális fájl, verem, sor, lista): azonos típusú elemeket tartalmaznak, minden elemnek (az utolsót kivéve) pontosan egy rákövetkező eleme van, ez meghatározza a feldolgozás sorrendjét. - hierarchikus szerkezeteket: egy elemek hierarchikusan egymás alá vannak rendelve. (pl. bináris fa, általános fa) - hálós szerkezeteket: bármely elem bármely másikkal kapcsolatban állhat (gráf) Az adatszerkezetek nagyobb része a programozási nyelvekben nem definiált, azt a programozó hozza létre problémák megoldásához. 2.

VEREM (STACK)

2.1

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. 2.2

A verem megengedett műveletei -

2.3

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 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.

1


___________________________________________________________________________ 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

Megjegyzések: - Ebben a megvalósításban a Veremből, Verembe műveletek végrehajtásának sikerét egy logikai értékkel adjuk vissza, a műveleteket ezért függvényszerűen írtuk meg. Hívásuk pl.: Ha Nem(Verembe(V,E)) Akkor Uzenet(„Tele a verem!”)

-

Kicsit hatékonyabb, ha a Verembe függvényben a Ha nem(Teli(V)) feltétel helyett Ha Teli(V)-t írunk, és a két ágat felcseréljük. (Csak nem olyan szép.) A statikus megvalósítás hátránya, hogy akkor is lefoglaljuk a maximális veremterületet, ha a veremben kevés elem van.

2


___________________________________________________________________________ 2.4

A verem dinamikus megvalósítása

Dinamikus megvalósítás esetén a verem elemeit láncoltan ábrázoljuk, minden elemhez tartozik egy mutató, amely a következő elemre mutat. A legutolsó elemhez tartozó mutató NIL. A TVerem típust egy mutatóként definiáljuk, amely a verem tetején lévő elemre mutat. Verembe tételkor egy rekordnyi (TVeremRekord) helyet lefoglalunk a heap-ben, az adatrészbe beírjuk az új elemet, és a rekordot a verem elé láncoljuk. Kivételkor a verem tetején található rekord adatrészét kiolvassuk, majd a rekordot kiláncoljuk a veremből, helyét felszabadítjuk. Type ElemTipus=... Mutato=^TVeremRekord TVeremRekord=Rekord Adat:Elemtipus Mut:Mutato Rekord vége TVerem=Mutato Eljárás Init(Változó V:TVerem) V:=Nil Eljárás vége Függvény Ures(V:TVerem):Logikai Ures:= (V=Nil) Függvény vége Függvény Teli(V:TVerem):Logikai Teli:= KevesAHeapEgyElemhez // Pascalban: Függvény vége

MaxAvail<SizeOf(TVeremRekord)

Függvény Verembe(Változó V:TVerem;E:ElemTipus):Logikai Változó Uj:Mutato Ha nem(Teli(V)) akkor Lefoglal(Uj) // Pascal: New(Uj) Uj^.Adat:=E Uj^.Mut:=V V:=Uj 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 Változó Regi:Mutato Ha nem(Ures(V)) akkor E:=V^.Adat Regi:=V V:=V^.Mut Felszabadit(Regi) // Pascal: Dispose(Regi) Verembol:=Igaz különben Verembe:=Hamis Elágazás vége Függvény vége

3


___________________________________________________________________________ Eljárás Urit(Változó V:TVerem) Változó E:ElemTipus Ciklus amíg nem(Ures(V)) Verembol(V,E) Ciklus vége Eljárás vége

Megjegyzés: - Az Urit eljárás nem helyettesíthető az Init-tel, mivel az utóbbi nem szabadítja fel a verem elemei által lefoglalt heap területet. Az Urit eljárást viszont használhatjuk az Init helyett. 2.5

A verem alkalmazása

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

3.

-

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.

SOR (QUEUE)

3.1

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. 3.2

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.

4


___________________________________________________________________________ 3.3

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 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

5


___________________________________________________________________________ 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

3.4

A sor dinamikus megvalósítása

Dinamikus sor esetén az elemeket (a dinamikus veremhez hasonló módon) láncoltan ábrázoljuk, minden elemhez tartozik egy mutató, amely a következő elemre mutat. A legutolsó elemhez tartozó mutató NIL. A TSor típust egy két mutatót (Eleje, Vége) tartalmazó rekordként definiáljuk. Sorba tételkor egy rekordnyi (TSorRekord) helyet lefoglalunk a heap-ben, az adatrészbe beírjuk az új elemet, és a rekordot a sor végére láncoljuk. Kivételkor a sor elején található rekord adatrészét kiolvassuk, majd a rekordot kiláncoljuk a sorból, helyét felszabadítjuk. Type ElemTipus=... Mutato=^TSorRekord TSorRekord=Rekord Adat:Elemtipus Mut:Mutato Rekord vége TSor=Rekord Eleje,Vege:Mutato Rekord vége

Eljárás Init(Változó S:TSor) S.Eleje:=Nil S.Vege :=Nil Eljárás vége Függvény Ures(S:TSor):Logikai Ures:= (S.Eleje=Nil) Függvény vége

Függvény Teli(S:TSor):Logikai Teli:= KevesAHeapEgyElemhez Függvény vége

// Pascalban:

6

MaxAvail<SizeOf(TSorRekord)


___________________________________________________________________________ Függvény Sorba(Változó S:TSor;E:ElemTipus):Logikai Változó Uj:Mutato Ha nem(Teli(S)) akkor Lefoglal(Uj) Uj^.Mut:=Nil Uj^.Adat:=E Ha Ures(S) akkor S.Eleje:=Uj különben S.Vege^.Mut:=Uj Elágazás vége S.Vege:=Uj; 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 Változó Regi:Mutato Ha nem(Ures(S)) akkor E:=S.Eleje^.Adat Regi:=S.Eleje S.Eleje:=S.Eleje^.Mut Felszabadit(Regi) // Pascal: Dispose(Regi) Sorbol:=Igaz különben Sorbol:=Hamis Elágazás vége Függvény vége Eljárás SorUrit(Változó S:TSor) Változó E:ElemTipus Ciklus amíg nem(Ures(S)) Sorbol(S,E) Ciklus vége Eljárás vége

3.5

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)

7

ADATSZERKEZETEK (VEREM, SOR)

Recommend Documents