Adatszervezés


Alapfogalmak

BEVEZETÉS

A valós világban rendszerekről beszélünk. A dolgok összetevői egymással kölcsönhatásban vannak, viselkednek, tulajdonságaik vannak. Rendszernek nevezzük a közös ismérv alapján összetartozó, egymással meghatározott kapcsolatban lévő elemek jól körülhatárolt együttesét.
Az elem a rendszer azon része, amelyet azért választunk ki, hogy vizsgálódást végezzünk rajta. Segítségével jellemezhető a rendszer. Egy elem is lehet rendszer. A kölcsönhatás az elemek közötti olyan kapcsolat, reláció, amely az adott elemeket a rendszer részévé teszi.
A rendszer több mint az elemek együttese. A rendszerek jellemzői:

A valós rendszerek túlságosan komplexek, a teljes összetettségükben általában nem tudjuk kezelni őket, így egyszerűsítési módszerekre van szükség.
A modellezés lényege az absztrakció, azaz az elemek lényegét, karakterisztikus közös tulajdonságait kiemeljük, a különbözőségeket elhanyagoljuk és a modellbe ezeket a közös tulajdonságokat vonjuk be. A modellben vizsgálunk, kérdéseket teszünk fel, következtetéseket vonunk le, amit a valós rendszerre visszavezetünk. Célja, hogy a valós világról olyan ismereteket szerezzünk, melyek helyesen tükrözik a valós világot. Az ismeretekre azért van szükség, hogy átadhassuk őket. Az ismeret mindig rögzített formában van, és hozzáférhető.
A rendszerben az elemek kölcsönhatásait, tulajdonságait adatokkal írjuk le. Ezt nevezzük adatmodellnek, ami igen bonyolult szerkezetű lehet.


AZ ADATSZERVEZÉS ELEMI SZINTJE

Az adatokat egyszerűen értékeknek vagy értékek halmazának tekinthetjük. Az adattétel kifejezés értékek önálló egységére utal. Azokat az adattételeket, amelyek altételekre oszthatók adacsoport tételeknek, amelyek viszont nem oszthatók tovább elemi adattételeknek nevezzük.
A különböző adatok gyűjteményét a leggyakrabban állományok, rekordok és mezők hierarchiájába szervezik.
Az entitás valamely tárgy vagy fogalom olyan tulajdonságainak összessége, amelyekhez értékek rendelhetők. Ezek az érttékek numerikusak vagy nemnumerikusak lehetnek.
A hasonló attribútumú entitások entitáshalmazt alkotnak. Az entitáshalmaz minden egyes attribútumához értéktartomány tartozik, amely az adott attribútumhoz rendelhető értékek halmazát adja.
Az információ kifejezést az adott attribútumú, illetve a hasznos vagy feldolgozott adatra használják.
Az adatok mezők, rekordok és állományok hierarchoájába szervezésének módja az attribútumok, az entitások és az entitáshalmazok közötti kapcsolatra utal. A mező tehát az entitás attribútumát reprezentáló információ önálló elemi egysége, a rekord egy adott entitás mezőértékeinek összessége, az állomány pedig az entitások rekordjainak összessége adott entitáshalmazban.
Az állomány különböző rekordjai több mezőt is tartalmazhatnak, az állomány egy bizonyos mezőjének értéke azonban egyértelműen meghatározhatja a rekordot. Az ilyen mezőt elsődleges kulcsmezőnek, értékeit pedig kulcsoknak vagy kulcsértékeknek nevezzük.


ADATSZERKEZETEK

Az adatokat sokféle módon szervezhetjük. Az adatszerkezet egy bizonyos adatszervezés matematikai vagy logikai modellje. Az, hogy a különböző modellek közülmelyiket választjuk, két alapvető tényezőtől függ:

  1. A választott modell szerkezetének elegendően gazdagnak kell lennie ahhoz, hogy tükrözni tudja az adatok közötti aktuális és valós kapcsolatokat.
  2. A szerkezetnek elegendően egyszerűnek kell lennie ahhoz, hogy hatékonyan fel lehessen dolgozni az adatokat.

Adatszerkezetek szemléltetése
Egy-egy elem általában adatcsoporttal jellemezhető, melyek adatai mindig összefüggenek. Az adatszerkezetek adattételekből, adatelemekből állnak. Ezek között valamilyen kapcsolat áll fenn.


Bármely adatszerkezet mindig véges számú adatelemet tartalmaz.

Homogén adatszerkezet: Az adatelemek azonos típusúak.
Heterogén adatszerkezet: Az adatelemek külömböző típusúak.

Műveletek az adatszerkezetekkel
Létrehozás: Nem volt adatszerkezet, létrehozás után lesz.
Bővítés vagy beszúrás (csak dinamikus adatszerkezeteknél): Új adatelemek kerülnek be az adatszerkezetbe, az adatelemek száma nő.
Törlés: Megkülönböztetjük a logikai és fizikai törlést:

Csere: Az elemek száma nem változik, csak valamely elem vagy elemek értéke, mert kicserélem egy másik értékre.
Rendezés: A rekordok bizonyos logikai sorrend szerinti átrendezése.
Keresés
Bejárás (elérés): Az adatszerkezet minden elemét érinteni akarom, a kérdés az, hogy ezt milyen sorrendben tehetem meg. A sorrendet alapul véve a bejárás lehet soros, ha az adatszerkezet elemeit valamilyen fizikai sorrend alapján tudjuk megfogni, ahogy le vannak képezve, szekvenciális, ha a bejárásnak valamilyen logikai sorrend az alapja, vagy közvetlen, ha az elérés független a többi adatelemektől.
Feldolgozás: Az adott adatszerkezet hogyan és mire használható.


ADATSZERKEZETEK TÁROLÁSA

A logikai adatszerkezeteket le kell képezni a tárba. A memóriában kétféle módon tárolhatunk adatszerkezeteket.


Folytonos (szekvenciális, vektorszerű) tárolás
A memóriában tárolt elemek egy folytonos tárterületen egymás után helyezkednek el, és az adattételek tárolási jellemzői azonosak (típus, ábrázolási mód, hossz).

___ ___ ___ ___ ___ ___ ___ ___

Ismerni kell a tárterület kezdőcímét, a tárolási jellemzőket, és az elemek számát. Ilyen tárolásnál minden elemet közvetlenül meg tudok fogni.
Minden adatszerkezet tárolható ilyen módon.
Műveletek
Létrehozás: Az adatelemeket, adattételeket egy-egy tárrészbe helyezem el. A kezdőcímtől kezdve minden tételt folytonosan pakolunk a tárba.
Bővítés: A végére újabb elemeket lehet rakni. Beszúrásnál az adott elem behelyezésének helye után lévő elemeket jobbra kell tolni, át kell mozgatni.
Törlés: Megkülönböztetünk fizikai és logikai törlést:

Csere: Bármely elem közvetlenül megfogható és felülírható.
Rendezés: Ha van értelme, akkor mindegyik rendezési algoritmus alkalmazható.
Keresés: Ha van értelme, akkor minden keresési algoritmus alkalmazható.

Szétszórt tárolás
Az adatelemek tárolási jellemzői különbözőek lehetnek. Minden adatszerkezet tárolható szétszórtan.
A tényleges adatelem mellett létezik a tárrésznek egy úgynevezett mutató része is, amely olyan információt tartalmaz, hogy az adott elem után melyik másik elem következik az adott adatszerkezetben.

1. Egyirányban láncolt lista (linked list)

Minden elemnél a mutatórész a következő elem tárolási címét, az adatrész pedig az adatelem értékét tartalmazza. Tudni kell, hogy melyik a lista első eleme. Ennek a címét a fej tartalmazza, ez listán kívüli elem, nem tartozik az adatszerkezethez. Az utolsó elem mutatórésze nem mutat sehova sem, a lista végét jelzi.
Üreslista: Csak a fej létezik a speciális, mutató értékkel.
NIL

Műveletek
Létrehozás: Első lépésként létrehozom az üreslistát, utána bővítek.
Bővítés: A lista bármelyik helyére beilleszthetek egy új tárolási elemet.
Bővítés a lista elején: Lefoglalok egy helyet a tárban. Bárhol megtehetem, de tudom a címét.
Az új elem az eddigi első elemre mutat, a fej pedig az új elemre.
Bővítés a lista végén: Lefoglalom a tárhelyet. Az új elem mutatója a lista végét jelző információ, NIL. Az utolsó elem mutatórészébe beírom az új elem címét, az eddigi utolsó elem mutatója az új elemre fog mutatni. Az utolsó elemet meg kell keresni, végig kell menni a listán, tehát szükség van egy bejárásra.
Bővítés a listában (beszúrás): Az elérés szekvenciális. A listánál a keresés teljes keresés, ahol adatértéket keresek. Minden elemre csak úgy tudok eljutni, ha előtte végig mentem az előtte lévő elemeken. Az aktuális elem az elem, amin állok. Az aktuális elem elé, vagy mögé is beszúrhatok.
Az aktuális elem mögé bővítek: A megelőző elemekről nincs információm. Az új elem mutatórészébe az aktuális elem mutatórészében lévő címet, az aktuális elem mutatórészébe pedig az új elem címét írom.

Az aktuális elem elé bővítek: Az előző módszerrel nem lehet bővíteni, mert nem tudom megmondani, hogy mi az előző elem címe, ezért meg kell jegyezni az aktuális elem előtti elem címét.
Törlés: A bővítés ellentéte.
Első elem törlése: A lista fejébe az első elem mutatóértékét viszem.
Ha az aktuális elemet akarom törölni, akkor az aktuális elem mutatórészét átviszem a megelőző elem mutatórészébe.
Csere: Simán végrehajtható.
Keresés: Csak teljes kereséssel, amennyiben a lista nem rendezett. Ha rendezett, akkor lineáris kereséssel.
Rendezés: Tegyük fel, hogy van egy listám, és azt saját helyén akarom rendezni. Ez nem célszerű, a gyakoribb az, hogy rendezetten hozok létre egy új listát. Ezt úgy tehetem meg, hogy létrehozom az üres listát, és beszúrásos rendezést alkalmazok. A beszúrandó elem helyét lineáris kereséssel keresem meg.
Bejárás: Minden probléma nélkül megtehető.
Feldolgozás: Adatszerkezet-függő.

2. Körkörös (cirkuláris) lista


Az utolsó elem mutatója az első elem címére mutat. Bármelyik elemből körbe tudok menni, a bejárást egyszerűsíti.

3. Kétirányban láncolt lista

Minden elemnek két mutatója van, amelyek a következő és a megelőző elemről tartalmaznak információt. Általában két fej van, a lista elejére és a végére mutatnak, így két irányban tudok haladni.

4. Multilista
Több értelmezése is van.
Az adatelemek összetettek.
Kialakítok az egyik és a másik részre is egy listát. Több mutatórész van, mindegyik egy-egy adatelem-rész szerint láncol. Annyi mutatórész és annyi fej van, ahány lánc.

Ez is lehet kétirányban láncolt, illetve körkörös lista.
Legyenek az adatelemek összetettek, így van egy adatelem sorozatom. Együtt akarom kezelni az azonos értékűek), tehát olyan részlisták jönnek létre, amelyben azonos értékű elemek vannak. Annyi részlista és fej van, ahány féle érték található. A fejek:

Az adatrész is tartalmazhat mutatórészt, amely egy másik listára mutat. Ekkor listákat fűzök fel.

A jelzőrész azt jelzi, hogy a listaelem tényleges adatra, vagy egy másik listára mutat. Jelző: 1 - adatrész, 0 - mutató (bitek).

Ezek tárolási szerkezetek. Vannak olyan adatszerkezetek, amelyekhez jobban illik a folytonos tárolás, másokhoz praktikusabb a szétszórt.
Reprezentáció: A tárolási mód és a leképezés együttese.
Implementáció: A reprezentáció és a műveletek együttese.

Törlés folyamatos tárolás esetén
Amikor adatszerkezetben törlést végzünk, akkor egy tárhely szabadul fel. Kérdés az, hogy hogyan tudunk ezzel a szabad tárhellyel gazdálkodni.

___ ___ ___ ___ _X_ ___ ___ ___

Az egyik megoldás az, hogy a tárhely felszabadulásakor átszervezzük az egészet, azaz a törlendő elemre rácsúsztatjuk a mögötte lévő elemeket. A szabad helyek ilyenkor mindig a lefoglalt tárrész után lesznek. A folyamat igen időigényes, viszont a problémánkat biztosan megoldja.
Hulladékgyűjtés (garbage collection): Csak logikai törlés van, a lyukakat otthagyom, folyamatosan írok tovább. Amikor elfogy a rendelkezésre álló tárhely, akkor a rendszer a szabad helyeket rendszeres időközönként átszervezi, átrendszerezi a végére, hogy összefüggő tárterületet kapjunk. Sok operációs rendszer van, amely így kezeli le a törlést.
A tárhelyeket nyilvántartjuk egy bitmátrix segítségével. A mátrix elemei: 1 (foglalt), 0 (szabad), ez alapján tudok elemeket elrakni. Az adatelemeket nem kell mozgatni, viszont külön nyilvántartás kell.

Törlés szétszórt ábrázolás esetén
A szabadhelyek össze vannak láncolva. Ha új elemet akarok láncolni, akkor a szabadhelyek listájáról leveszem az első elemet, és azt fűzöm az állományhoz. Ha törlést végzek, akkor az adott elem helyét a szabad elemek láncához láncolom. Időben gazdaságos.
A gond az, hogy különböző méretű tárhelyeket láncolok, így olyan algoritmusokat kell alkalmazni, amelyek ellenőrzik, hogy az új elem befér-e a tárrészbe és meg kell keresni azt a tárhelyet, ahova befér (first fit: az első megfelelő tárhelyet foglalom le; best fit: a megfelelőek közül a legkisebbet foglalom le). Ha túl kicsi elemet pakolok bele, akkor nem gazdaságos.
Szabadhelyek nyilvántartása: Mint folytonos tárolás esetén. Bitmátrix segítségével történik.
Hulladékgyűjtési technika, amelyben láncolom a szabadhelyeket. Ha elfogy a szabad hely, akkor láncolok.

Egy szintet vissza, vagy vissza a főmenübe.