2. Az adatszerkezetek
Az adattípus megadása a típus értékkészletének, a rajta végzett műveleteknek, az értékek jelölésének és a tárban való ábrázolásának a rögzítését jelenti.
Az adattípusok kétfélek lehetnek: elemiek amelyeknek felhasználói szempontból nincs belső szerkezetük, valamint összetettek, amelyek elemiekből épülnek fel, ezek az adatszerkezetek.
2.1. Elemi adattípusok
Egész számok: Legtöbbször két byte-on ábrázolják, kettes komplenens kódban. Így az értékkészlet a -32768 és 32767 közötti számok halmaza.
Valós számok: A számítógépben kettes vagy tízes számrendszerben is ábrázolhatók a racionális számok. Megadásuk egy 0 és 1 közötti számmal és hatványkitevővel történik (számok normál alakja).
Logikai érték: Igaz és hamis vagy TRUE és FALSE illetve 1 és 0.
Karakter: Egy változóban tetszőleges karaktert tárolhatunk az ASCII kódtábla szerint.
2.2 Összetett adattípusok
Az összetett adattípusokban az egyes adatelemek valamilyen sorrendi, szerkezeti összefüggésben állnak egymással.
A tömb egy olyan sorozat, amelynek elemszáma rögzített és bármely elemére egy indexszel (sorszámmal) hivatkozhatunk. Általában a tömb elemei azonos típusúak.
A szövegtípus hasonlít a tömbhöz. Elemei csak karakterek lehetnek, viszont az elemek száma (a szöveg hossza) változhat. A szövegekkel műveleteket is lehet végezni (pl. hozzáfűzés, részképzés).
Gyakran használt adatszerkezet, amelyet általában nekünk kell megvalósítani, ha szükségünk van rá. A verem adatok sorozatát tartalmazza, de csak speciális műveleteket engedünk meg vele kapcsolatban:
- PUSH(x) - egy x értéket a verem tetejére (a sorozat végére) helyez.
- POP(x) - a verem tetején (a sorozat végén) lévő értéket az x változóba teszi, majd a veremből eltávolítja
A verem szerkezete LIFO (Last In First Out) típusú, ami azt jelenti, hogy az elsőnek betett elemet dolgozhatjuk fel először.
A sor olyan sorozat, amelynek az egyik végére lehet tenni az új elemeket, a másik végéről pedig el lehet venni őket. Ez a FIFO (First In First Out) típusú szerkezet, mely azt jelenti, hogy az elsőnek betett elemet dolgozhatjuk fel először.
A lista olyan szerkezet, mely megmondja, hogy egy adott elemet logikailag melyik követ.
Egy adat mellé egy vagy több mutatóértéket helyezhetünk el, amely mutatók a logikailag következő vagy előző elemet határozzák meg.
|
|
Mindig van egy első elem ez a listafej és egy utolsó elem, amelyet valamilyen formában megkülönböztetünk a listában előforduló elemektől. Ez lehet a 0 vagy a NIL illetve a NULL is.
Ezen a példán jól látszik a lista előnye. A sorrend megváltoztatásához az elemeket nem kell mozgatni, csak a mutatókat kell átírni.
A
halmaz
A halmaz olyan sorozat, ahol az elemeknek nincs definiálva a sorrendje, nincs értelme a következő elemet kérni. Használhatjuk viszont a halmazműveleteket: egyesítés, metszet, halmazkülönbség.
A gráf olyan adatszerkezet, amely csúcsokból (adatelemek), valamint azokat összekötő élekből (kapcsolatok) áll.
Az ilyen típusú szerkezetek megvalósításához szintén a mutatókat használhatjuk.
Egy speciális gráf, amelynél minden csúcs két éllel rendelkezik és van egy kitüntetett csúcsa a gyökér. Ezt a szerkezetet faszerkezetnek is nevezik.
Lényege, hogy az összetett változónak (rekord) adunk egy közös nevet, s az egyes, rendszerint különböző típusú mezőinek szintén. Így lehetővé válik a rekord elemeinek önálló, külön kezelése és a részek együttes feldolgozása is.
pl. személynyilvántartás
- teljes személy: adat
- neve: adat.név
- születési éve: adat.születés.idő.év
Alternatív szerkezet (változó szerkezet)
Az alternatív szerkezet abban különbözik a rekordtól, hogy az egyes részek összetétele függ a tartalomtól, vagyis a rekord felépítése a mezők tartalmától függ.
Ezek az adatszerkezetek a háttértárakhoz kapcsolódnak, olyan rekordsorozatok, amelyek különbözőképpen szervezettek.
Szekvenciális (sorrendi) állomány:
A tárolt adatok csak a rögzítés sorrendjében nyerhetők vissza. Vagy csak olvasni, vagy csak írni lehet bele, illetve a végére új rekordot írni.
Direkt állomány:
Bármelyik rekordja bármikor elérhető, módosítható. Az egyes rekordokat általában sorszámmal tudjuk azonosítani. Az ilyen állományba írhatunk, olvashatunk, illetve az állomány végére új rekordokat vehetünk fel.
Indirekt állomány:
Az indirekt állományok azt a lehetőséget biztosítják, hogy a rekordokat nem sorszámmal, hanem jellemző adatukkal azonosíthatjuk, pontosabban a rekordokat valamelyik mezője (kulcsmező) alapján rendezetten kezelhetjük.
Ekkor az állományhoz tartozik egy táblázat, az indextábla, amely a kívánt adatot, valamint egy rekordra mutató értéket (rekordszám) tartalmaz.