Adatszerkezetek osztályozása

Listák

Fák

Adatszerkezetek osztályozása. Műveletek adatszerkezetekkel

Adatelem az a legkisebb adategység, amelyre hivatkozni lehet.

Az adatszerkezet az adatelemek egy olyan véges halmaza, amelyben az adatelemek között szerkezeti összefüggések vannak. Az összekapcsolódás módja határozza meg az elemek egymáshoz való viszonyát, illetve azokat a művelteket, amelyeket rajta végezhetünk.

A matematikai adatszerkezet egy <A,R> rendezett pár, ahol

A: adatelemek halmaza

R: az A halmazon értelmezett valamilyen reláció

A matematikai adatszerkezetek az R reláció bonyolultsága alapján csoportosíthatók.

1. Az adatszerkezetek osztályozása

1.1 Szerkezet szerinti csoportosítás

1.1.1 Homogén adatszerkezetek (Azonos típusú adatelemekből épül fel)

Struktúra nélküli adatszerkezet

Az egyes adatelemek között nincs kapcsolat. Nem beszélhetünk az elemek sorrendjéről.

Pl. halmaz

Asszociatív adatszerkezet

Az adatelemek között lényegi kapcsolat nincs. Ez az adatszerkezet valamilyen közös tulajdonság alapján összeállított halmaz, amelyekből részismérvek alapján részhalmazokat választhatunk ki. Az adatszerkezet elemei tartalmuk alapján címezhetők. pl.: tömb, ritka mátrixok, táblák.

bulletKözvetlen elérésű
bulletVéletlen elérésű

Szekvenciális adatszerkezetek

A szekvenciális adatszerkezet olyan <A, R> rendezett pár amelynél az R reláció tranzitív lezártja teljes rendezési reláció

Szekvenciális adatszerkezetben az egyes adatelemek egymás után helyezkednek el. Az adatok között egy-egy jellegű a kapcsolat: minden adatelem csak egy helyről érhető el és az adott elemről csak egy másik látható. Pl. egyszerű lista

Hierarchikus adatszerkezetek

A hierarchikus adatszerkezet olyan <A,R> rendezett pár, amelynél van egy kitüntetett elem a gyökérelem úgy, hogy

A gyökér nem lehet végpont
Bármely gyökértol különböző elem egyszer és csak egyszer lehet végpont
Bármely gyökértol különböző elem a gyökérbol elérhető

A hierarchikus adatszerkezeteknél az adatelmek között egy-sok jellegű kapcsolat áll fenn. Minden adatelem csak egy helyről érhető el, de egy adott elemből tetszés szerinti számú adatelem látható.
Pl. fa, összetett lista

Hálós adatszerkezetek

A hálós adatszerkezet olyan <A,R> rendezett pár, amelynél az R relációra semmilyen kikötés nincs.

A hálós adatszerkezetek adatelemei között a kapcsolat sok-sok jellegű: bármelyik adatelemre több helyről is eljuthatunk, és bármelyik adatelemtől elvileg több irányban is mehetünk tovább.

Pl. gráf, irányított gráf

1.1.2 Heterogén adatszerkezetek

Különböző típusú adatokból épül fel. pl.: Record

1.2 A memóriában történő helyfoglalás szerinti csoportosítás

1.2.1 Statikus adatszerkezetek

Véges számú adatelemből épül fel és ezek csak értéküket változtathatják hosszukat nem

pl.: Tömb, rekord, halmaz

1.2.2 Dinamikus adatszerkezetek

Adatelemek száma tetszőleges, az adatelemek száma változhat.

pl.: Lista, Fa, Gráf

Lehet rekurzív, melynek definíciója önmagára való hivatkozást tartalmaz. Nem lineáris, ha több ilyen hivatkozás van.

bulletfile-ok: nem rekurzív
bulletláncolt lista: rekurzív lineáris
bulletösszetett lista, fa, gráf: rekurzív, nem lineáris

3. Műveletek adatszerkezetekkel

Az adatszerkezetek meghatározzák, a rajtuk végezhető műveleteket

bulletTömb: Műveletek, csak az egyedi összetevokön végezhetők (kivétel a paraméterátadás)
bulletRekord: A mezőkön, a mező típusának megfelelő műveletek végezhetők
bulletHalmaz: Csak a teljes halmazon végezhetők műveletek:
bulletlétrehozás: (feltétellel, felsorolással)
bulletin: az adott elem benne van-e a halmazban
bullet+: unió
bullet*: metszet
bullet-: külömbség
bulletösszehasonlítás

Láncolt lista:

bulletbeszúrások
bullettörlések
bulletbejárás, feldolgozás (pozícionálás, érték kiolvasása)
bulletjelzés: üres-e, van-e következő elem

Verem, sor:

bulletelem be
bulletelem ki
bulletüres-e

Összetett lista

bulletCons
bulletAppend
bulletList

fa:

bulletelem hozzáadása (levél, gyökér)
bullettörlés (levél, 1 leágazású csúcs, 2 leágazású csúcs)
bulletbejárás (preorder, postorder, inorder)
bulletteszek (levél-e, van-e adott oldali részfája)...

Mindegyiken elvégezhető: üres szerkezet inicializálása

Adatelemeken végezhető műveletek (ahol ez engedélyezett)

bulletcsere - egy adatelem értékének megváltoztatása
bulletrendezés
bulletkeresés - egy adott értékű vagy adott feltételt kielégítő adatelemek helyének megkeresése
bulletbejárás - valamennyi adatelem egyszeri elérése, feldolgozás

Listák:

Egyszerű lista (láncolt lista)

Gyűrű

Kétirányú lista

Összetett lista (multilista)

A lista adatszerkezet Homogén szekvenciális (lineáris), dinamikus adatszerkezet Az adatelemek között egy-egy jellegű kapcsolat van, minden adatelembol egy helyrol érheto el és minden elembol csak egy másik látható.

Láncolt lista (lineáris lista, lánc)

Egy láncolt lista n darab azonos típusú adatelem sorozata. Jelöljük: L=(a1 a2...an) Ha n=0, akkor L=() az üres lista. A láncolt lista olyan adatszerkezet, amelynek minden eleme pontosan egy mutatót tartalmaz, egy másik, ugyanolyan típusú elemre. A lánc első elemének a címét a lista feje tartalmazza. A listafej nem tartalmaz információs részt. A lánc végét az jelzi, hogy az utolsó elem a rákövetkező elem mutatójaként NIL-t tartalmaz.

Pl: type Elem = record

bulletInfo : Infotype;

Következo : ^Elem;

end; {Elem}

var Fej:^Elem;

{inicializálás} Fej:=NIL; {üres lánc}

 

lista 3 elemmel

| Fej |--|--->|1.elem|--|--->|2.elem|--|--->|3.elem|NIL|

 

Láncolt lista, lineáris lista, lánc - szinonimák Láncolt listán a következő műveletek végezhetők:

bulletüres lánc inicializálása
bulletelem beszúrása a lánc elejére
bulletelem beszúrása a lánc végére
bulletelem beszúrása az aktuális elem elé
bulletelem beszúrása az aktuális elem után
bulletelem törlése a lánc elejéről
bulletelem törlése a lánc végéréről
bulletaz aktuális elem törlése
bulleta lánc Fej eleme legyen az aktuális
bulletaz aktuális elem értékének kiolvasása
bulletjelezzük, hogy az aktuális elemre van-e rákövetkező
bulletaz aktuális elemet követő elem legyen az aktuális
bulletjelezzük, ha a lánc üres

A lánc elején való beszúrás algoritmusával az elemeket a feldolgozással fordított sorrendben tároljuk. Ha azt akarjuk, hogy a tárolás megfeleljen a beszúrás sorrendjének, az elemeket a lánc végére kell beszúrnunk.

Beszúrás a lánc végére

Ez az algoritmus eléggé rossz hatékonyságú, mert mindannyiszor végig kell járnunk az egész láncot, ahhoz hogy megtaláljuk az utolsó elemet. Ha többször is akarjuk használni ezt a műveletet, akkor a lánc elejét jelző pointer mellé a lánc végét jelző pointert is érdemes beiktatni. Meg kell jegyeznünk, hogy ez a megoldás bonyolítja a többi láncműveletet, mivel biztosítanunk kell, hogy minden egyes módosításnál a lánc vége pointert is aktualizáljuk.

Ha az elemeket a beszúrás sorrendjétől függetlenül akarjuk tárolni, pl. rendezve, akkor a beszúrást egy adott elem elé vagy mögé kell végrehajtanunk.

Egy adott elem elé való beszúrást általában egyszerűbb úgy megvalósítani, hogy az elem utáni beszúrás algoritmusát alkalmazzuk, majd megcseréljük az új és az adott elemben levő információkat. Ezzel a módszerrel elkerülhetjük, hogy az egész láncot végig kelljen járnunk ahhoz, hogy megtaláljuk a beszúrandó elem elotti elemet.

3.2 Egy elem keresése

Egy adott értékű elem keresése, első pillanatban úgy tűnhet, egyszerű bejárási probléma. Nézzük a következő algoritmust:

bulletvar p, Fej : Elemcim;

...

p:= Fej;

while (p <> nil) and (p^.Info <> Keresettérték) do

p:=p^.Következo;

if p <> nil then {találat} ...

Vegyük észre, hogy a while ciklusban a logikai feltétel nem mindig definiált. Valójában, ha p=nil, a p^ struktúra nem létezik. Ilyen esetben a fordító hibát jelezhet. Megoldás vagy bekapcsoljuk a rövidzárvizsgálatot a beálításoknál, vagy bevezetünk egy logikai változót (egy flag-et var Nemtalalt: booolean;), mely jelzi, ha Nil-hez értünk és a feltételvizsgálatba ezt a változót helyezzük.

Gyűrűk

A Végérebeszúr2 algoritmusban az eljárást úgy gyorsítottuk, hogy bevezettünk a Fej mellé még egy lánc vége pointert. Egy másik megoldás lehet, ha a listát ciklikussá tesszük azáltal, hogy az utolsó elemet ez elsőhöz láncoljuk.

Egy ciklikus listát gyűrűnek nevezünk. Ennek a struktúrának az az előnye, hogy a lánc bármely eleméből kiindulva elérhetjük a lista valamennyi másik elemét. Az első elemet felismerhetjük, ha teszteljük a Fej pointert.

Műveletek gyűrűkön:

A beszúrás, törlés, és az elemek bejárása hasonló a lineáris listáknál leírtakhoz.

Figyelnünk kell azonban a bejárásnál arra, hogy a lista végét nem jelzi többé nil pointer.

Kétirányú listák

Ha a feladatban gyakran kell a lista eloző eleméhez hozzáférnünk, akkor célszerű minden egyes elemet kiegészíteni még egy pointerrel, az eloző elem felé. Ekkor kétirányú listát kapunk.

Egy kétirányú lista is lehet ciklikus, ekkor kétirányú gyűrűről beszélünk. Ez a struktúra mind az Eloző pointer, mind a ciklikusság előnyeit magában hordozza. Igy a törlési műveletek és a lista végét kezelő műveletek egyszerűbbek.

Összetett listák (multilisták)

Elemei lehetnek adatelemek és újabb listák.

Részei

bulletLista fej
bulletLista farok

Reprezentációja mutató párral

bulletFejre mutató, mutató
bulletFarokra mutató, mutató.

Fák:

FA: Homogén (minden eleme azonos típusú), ezen belől hiearchikus, dinamikus (nem kötött az elemszám) adatszerkezet. Fő előnye a listákhoz képest, hogy gyorsabb a bejárása.

Alapfogalmai: elemek, csúcspont, szögpont, élek

Gyökérelem a fa első eleme, amelynek nincs megelozője.

Levélelemek, a fa azon elemei, amelyeknek nincs rákövetkezőjük.

Közbenső elem az összes többi.

Az út a gyökértől kiinduló valamely elemhez tartó él-sorozat.

Egy elemnek a gyökértől mért távolságán a köztük lévő utat alkotó élek számát értjük.

A gyökértől azonos távolságra lévő elemek alkotják a fa szintjeit.

Szint a gyökértol való távolság : 0. szint a gyökérelem, 1.szint a gyökérelem rákövetkezoi. A fa szintjeinek a száma a fa magassága ( A példában 3).

bulletMinden levélelem a gyökértől pontosan egy úton érhető el.

Részfa: Minden közbenső elem egy részfa gyökereként tekinthető, így a fa részfákra bontható.

Üresfa az a fa, amelyiknek egyetlen eleme sincs.

Bináris fák

Nem bináris fák

Kiegyensúlyozott fák

Kereső fák

Bináris fa

Binárisnak nevezünk egy fát, ha minden elemének legfeljebb két rákövetkezője van.

Szigorú értelemben vett bináris fáról akkor beszélünk, amikor minden elemnek 0 vagy 2 rákövetkező eleme van.

Bináris fáknál beszélhetünk baloldali és jobboldali részfákról.

Bináris fa bejárási stratégiák

preorder

bulletgyökérelem bejárása
bulletbaloldali részfa bejárása
bulletjobboldali részfa bejárása

prostorder

bulletbaloldali részfa bejárása
bulletjobboldali részfa bejárása
bulletgyökérelem bejárása

inorder

bulletbaloldali részfa bejárása
bulletgyökérelem bejárása
bulletjobboldali részfa bejárása

Bineáris fák reprezentálása (minden elem két mutatót tartalmaz)

Nem bináris fák

Nem binárisak azok a fák melyeknek kettőnél több leágazásuk is lehetséges

Ábrázolásuk:

1, Két mutató. az első mutató a leágazásra, a második egy következő mutatóra

2, Mutató lánc: két mutató első leágazás és következő testvér

Kiegyensújozott fák

Adott elemekből többféleképpen is építhetünk fel fákat .

bulletMinimális magasságú fa : Olyan fa, amelynek a magassága az adott elemszám esetén lehető legkisebb. Valójában minden szintre a maximális elemszámú elemet építjük be.
bulletEgy fát kiegyensúlyozottnak nevezünk, ha minden szintjén az egyes részfák magassága nem ingadozik többet egy szintnél.
bulletTökéletesen kiegyensúlyozott fa : Egy fa akkor tökéletesen kiegyensúlyozott, ha minden elem bal- illetve jobboldali részfájában az elemek száma legfeljebb eggyel tér el.

Bináris kereső fák

Az adatelemek között definiálható egy rendezési sorrend

 

 

minden csúcsra igaz:

bulletBalra a nálla kisebb elemek helyezkednek el
bulletJobra a nagyobb elemek helyezkednek el

A feltételt sokféleképpen kielégíthetjük, de a gyorsabb kezelés érdekében kiegyensúlyozott fákat használunk.

Műveletek bináris rendezési fákon:

Beszúrás

bulletLevélelem beszúrása
bulletA levél kulcsa alapján megkeressük azt az egy leágazású csúcsot vagy levélelemet, amelyen levélelemként elhelyezkedne

bulletAllokálunk neki helyet, létrehozzuk az elemet
bulletA megtalált csúcs megfelelő mutatóját beállítjuk
bulletGyökérelem beszúrása: O
bulletMegnézem, hogy a beszúrandó elem kisebb vagy nagyobb a gyökérnél
bulletHa a beszúrandó elem kisebb a gyökérnél
bulletGyökér + jobboldali részfa jobbra
bulletBaloldali részfát két részre bontom B1 < O; B2 > O
bulletB1 beszúrása az új elemtől balra
bulletB2 beszúrása az eredeti gyökértol jobbra
bulletha a beszúrandó elem nagyobb a gyökérnél ...
bulletTörlés
bulletLevélelem törlése: Az ősének mutatóját NIL-re állítom
bulletEgy leágazású csúcs törlése: elődjének mutatóját rá állítjuk a leágazás csúcsára
bulletKét leágazású csúcs törlése
bulletVagy a baloldali részfa legnagyobb elemét veszem, ami vagy levél, vagy 1 leágazású csúcs. A két elemet értékét felcserélem, és az eredeti értéket tartalmazó elemet a már definiált módon törlöm.
bulletVagy a jobboldali részfa legkisebb elemét veszem, felcserélem az értékeket, és az eredeti értéket tartalmazó elemet törlöm.
bulletBejárás: Inorder módon bejárható
bulletElem keresése: A gyökérből kiindulva < > vizsgálatok szerint bal illetve jobb részfán haladva. Rekurzív módon viszonylag egyszerűen megoldható.