Adatszerkezetek
1. előadás
Irodalom: Lipschutz: Adatszerkezetek Morvay, Sebők: Számítógépes adatkezelés Cormen, Leiserson, Rives, Stein: Új algoritmusok
http://it.inf.unideb.hu/~halasz http://it.inf.unideb.hu/adatszerk http://www.inf.unideb.hu/~panovics/adatszerk.html
Követelmények: két zh írásbeli vizsga
Bevezetés
Absztrakció, modellalkotás A valós világ rendszereinek alkotóelemei az egyedek, melyek tulajdonságokkal, és viselkedésmőddal rendelkeznek. tulajdonság statikus jellemző viselkedésmód dinamikus jellemző, az egyedek egymáshoz való kapcsolatát jellemzi Modellalkotás: lényeges jellemzők kiemelése, lényegtelenek figyelmen kívül hagyása
Modellalkotás
A modellezés lényege: absztrakció Azon tulajdonságok , melyek lehetőleg minél több egyednél megtalálhatóak: az egyedek karakterisztikus tulajdonságai Viselkedésmód elemek
A modell nem egyedi dolgokkal, hanem ezen dolgok absztrakt osztályaival foglalkozik. Informatikában: tulajdonság: adat viselkedésmód: program
Modellalkotás
Logikai szint absztrakt adatszerkezetek, melyek függetlenek a platformtól, a számítőgéptől
Fizikai szint hardver + szoftver az adatok tárolására szolgáló hely
memória (tár) háttértároló (állományok)
Kölcsönösen egyértelmű leképezés van a két szint között
Absztrakt adatszerkezetek
Adatelemekből állnak Ezek lehetnek egyszerűek (atomiak) összetettek
Az adatelemeknek van egyszerűnek: 1 értéke van összetett: egy értékcsoport alkotja az értékét
Az adatelemek között jól meghatározott kapcsolatrendszer van. Adatlem + kapcsolatrendszer = Abszt. adatszerk.
Absztrakt adatszerkezetek csoportosítási szempontjai
Adatelemek száma változik-e időben statikus dinamikus (akár 0 is lehet)
Adatelemek típusa homogén (az összes adatelem típusa azonos) heterogén
fenti két szempont „ortogonális”, azaz egymástól teljesen független
Absztrakt adatszerkezetek csoportosítási szempontjai
Adatelemek közötti kapcsolatok szerint homogén adatszerkezetben
struktúra nélküli (nincs kapcsolat, pl. halmaz) asszociatív (pl. tömb) szekvenciális (minden a.e. két másik a.e.-el van kapcsolatban, kivéve az elsőt és az utolsót, minden adatelemnek van egy megelőzője és egy rákövetkezője) hierarchikus (minden adatelemnek egy megelőzője és akárhány rákövetkezője van, pl. FA) hálós (minden adatelemnek tetszőleges számú megelőzője és rákövetkezője lehet)
heterogén adatszerkezet esetén nem csoportosítunk a kapcsolatok szerint, mindig rekord adatszerkezetről beszélünk.
Absztrakt adatszerkezetekkel végezhető műveletek
Létrehozás Az üres szerkezeti váz kialakítása az adatelemek értékei is megadhatóak Módosítás nem érinti a szerkezetet, csak az egyes adatelemeket bővítés (dinamikus adatszerkezeteknél) törlés (fizikai és logokai) (csak din. ad.sz.) csere (meglévő a.e. értékét felülírjuk) (logikai törlés = speciális csere: érték felülírása speciális bitkombinációval)
Absztrakt adatszerkezetekkel végezhető műveletek
Rendezés: segítségével az adatszerkezet elemeit egy (elsődleges) kulcs értékei alapján sorba rendezzük. szélsőérték kiválasztásos beszúró buborék shell gyors
Keresés (van-e, esetleg hány van) teljes lineáris (rendezett) bináris (rendezett, folytonos tárolású)
Absztrakt adatszerkezetekkel végezhető műveletek
Elérés segítségével hozzá tudunk férni, meg tudjuk fogni az adatszerkezet egy elemét közvetlen (többi adatelemtől független elérés) szekvenciális (adatelemek közötti kapcsolat alapján)
Bejárás melynek során az összes elemet érintjük Feldolgozás hozzáférünk az a.e.-ekben tárolt információhoz, azokon valamilyen tevékenységet hajtunk végre
Ábrázolási módok
(tárolási modellek, fizikai szint)
Folytonos (vektorszerű) Szétszórt (láncolt) Az adatelemek a memóriában tárhelyen vannak elhelyezve. Egy tárhely: egy bájtcsoportot jelent, amely tárolja az adatelem értékét és szerkezetleíró információt hordozhat
Folytonos (vektorszerű) tárolás
Egy tárhely – egy adatelem értéke A tárhelyek a memóriában egy folytonos, összefüggő tárterületet alkotnak, a tárhelyek mérete azonos Előnyei: közvetlen elérés, a kezdőcím és a tárhely mérete alapján csere műveletet könnyű megvalósítani hatékony rendező algoritmusok hatékony kereső algoritmusok
Hátránya: nem segíti a bővítést és a fizikai törlést
Szétszórt (láncolt) ábrázolás
A tárhelyen az adatelem értéke (érték rész) mellett legalább egy mutató (mutató rész) értékét tároljuk. Mutató: tipikusan memóriacím A tárhelyek mérete nem feltétlen azonos, elhelyezkedésük a memóriában tetszőleges Szétszórt ábrázolás fajtái: egyirányban láncolt lista cirkuláris lista kétirányban láncolt lista multilista
Egyirányban láncolt lista
A tárhely (listaelem) az adatelem értékén kívül egy mutatót tartalmaz, amely a következő listaelem címét tartalmazza. A láncolt lista első elemének címét egy, a láncszerkezeten kívüli mutató, a fejmutató tárolja. A fejmutató nem taratlmaz egyéb adatot a mutatón kívül, így nem része az adatszerkezetnek, csak a hozzáférést biztosítja ahhoz. A láncolt lista végét egy speciális érték, a NIL jelzi. Amennyiben a fejmutató értéke NIL, akkor a lista üres.
