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.

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.

3. Műveletek adatszerkezetekkel

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

Láncolt lista:

Verem, sor:

Összetett lista

fa:

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

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

Listák:

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

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

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:

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

Reprezentációja mutató párral

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

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

prostorder

inorder

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 .

Bináris kereső fák

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

minden csúcsra igaz:

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