4. Adatszerkezetek
Ebben a fejezetben adatszerkezetekkel kétféle szempontból
foglalkozunk. Egyrészt olyan feladatokat adunk, amelyek adat-
szerkezetek megvalósításával, másrészt pedig olyanokat, ame-
lyek adatszerkezetek alkalmazásával kapcsolatosak.
Ahogyan az algoritmusok körében használunk elemi utasítá-
sokat, illetve a végrehajtás menetét szervező utasításokat,
ugyanúgy az adatok körében is megkülönböztetünk elemi, illet-
ve összetett adatokat (adatszerkezeteket).
Háromféle összetételi módot használunk: az elsőnél az adat
néhány, esetleg különböző típusú elemibb adat egymásutánja
(rekord), a másodiknál a részekre osztás többféleképpen is
megtörténhet (alternatív szerkezet, rekord), míg a harmadik
esetén azonos tipusú elemek sokaságából. Az első kettővel az
adatfeldolgozásról szóló fejezetben foglalkozunk.
A harmadik esetben halmazról beszélünk, ha az elemek kö-
zött nincs semmiféle sorrend, sorozatról, ha minden elemhez
egyértelműen tartozik egy következő elem, hierarchikus szer-
kezetről (fa), ha egy elem után több következő is lehet, il-
letve hálós szerkezetről (gráf), ha több előző is lehet.
A fejezetben vizsgált adatszerkezetek:
- lista,
- verem,
- sor,
- tömb, táblázat,
- fa,
- gráf,
- adatállományok.
Javasolt irodalom:
1. J. Nievergelt - J.C. Farrar - E.M. Reingold: Matematikai
problémák megoldásainak számítógépes módszerei.
Műszaki Könyvkiadó, 1977.
2. O.J. Dahl - E.W. Dijkstra - C.A.R. Hoare: Struktúrált
programozás.
Műszaki Könyvkiadó, 1978.
3. Varga L.: Rendszerprogramok elmélete és gyakorlata.
Akadémiai Kiadó, 1978.
4. A.V. Aho - J.E. Hopcroft - J.D. Ullman: Számítógép algo-
ritmusok tervezése és analízise.
Műszaki Könyvkiadó, 1982.
5. N. Wirth: Algoritmusok + adatstruktúrák = programok.
Műszaki Könyvkiadó, 1982.
6. D.E. Knuth: A számítógépprogramozás mővészete, 1.
Műszaki Könyvkiadó, 1987.
7. Számítástechnika középfokon.
OMIKK, 1987.
4.1 Lista
LISTA adatszerkezetről beszélünk, ha az elemek fizikai
sorrendjétől eltérő logikai sorrendet jelölünk ki mutatók se-
gítségével. Egy elem mutatója a logikai sorrendben mindig az
őt követő elem fizikai helyét mutatja.
Ezt az adatszerkezetet gyakran kell alkalmazni. Hasznos,
ha az adathalmazunk olyan nagy, hogy nem tudjuk egy megenge-
dett tárolási egységben elhelyezni. Ilyenkor a 'csomagokat'
egymásután fűzve elérhetjük a megfelelő méretet. Használjuk
akkor is, ha egy adategység olyan nagy, hogy mozgatása sok
időt vesz igénybe és mi rendezett adathalmazt szeretnénk lét-
rehozni. Ebben az esetben azért lesz a lista praktikus, mert
itt az elemek logikai sorrendje nem feltétlenül kell, hogy
megegyezzen a fizikai sorrenddel. LISTA használatával az ele-
meket tetszőleges számú szempont szerint fel tudjuk fűzni,
így az adatok mozgatása nélkül lehet többféle rendezettséget
felépíteni.
Célszerű a használata akkor is, ha az adathalmazban gyako-
ri a törlés, illetve a beszúrás művelete.
4.2 Verem
A VEREM olyan adatszerkezet, amelynél mindig az utoljára
berakott elemet tudjuk megnézni, illetve megnézni és levenni.
j adatot csak a VEREM tetejére lehet rakni.
Eljárások, rekurzió megvalósítása lényegesen egyszerűbb,
ha tudunk vermet használni a paraméterek és a visszatérési
cím tárolására. Ezt az adatszerkezetet általában önállóan nem
használjuk, hanem mindig valamilyen jellegű feladat megol-
dására (pl. fabejárásnál hol kell a bejárást folytatni, a
QUICKSORT rendezésnél milyen szakaszokat kell még rendezni
stb.). Ezeket a feladatokat a megfelelő részeknél helyeztük
el, így itt csak néhány általános jellegű feladatot közlünk.
Az alfejezet végén található feladatok a FORTH nyelvhez
kapcsolódnak. Ebben a nyelvben szinte minden adatot verembe
kell helyezni, s ott végezni velük műveleteket. A FORTH nyelv
emiatt néhány újabb műveletet definiál veremkezelésre: a fel-
ső két elem cseréje, a legfelső megduplázása, a felső alatti
megduplázása, a felső három ciklikus cseréje stb.
4.3 Sor
Olyan adatszerkezettel foglalkozunk ebben az alfejezetben,
amelyet sokszor alkalmazunk, talán anélkül, hogy tudnánk ró-
la. Az adathalmaz elemeit csak olyan sorrendben tudjuk olvas-
ni, ahogyan beraktuk. Akkor hasznos az adatok ilyen tárolása
például, ha adatállományt küldünk egy gépről egy másik gépre
és a két eszköz sebessége nem azonos. Ilyenkor létrehoznak
egy ideiglenes adattárolót, un. puffert, amelynek az a funk-
ciója, hogy a küldött adathalmazt fogadja, majd ha nincs
több, vagy elfogyott a hely a pufferben, akkor továbbítsa
feldolgozásra. Természetes, hogy az adatok sorrendjét nem
változtatja meg, hisz furcsa is lenne, ha egy nyomtatandó
szöveg betűit felcserélné.
A feladatok modellezni próbálják az adatszerkezetet, majd
egészen összetett problémákon keresztül mutatják meg a gya-
korlatban is előforduló feladatok nehézségét.
Az alfejezetben szereplő diszkrét szimulációs feladatok
megoldásához szükségeses valószinűségszámítási ismeretek.
Ezek alapján lehet meghatározni a 'rendszertelenül érkező'
elemek (vásárlók, autók stb.) érkezésének eloszlását.
4.4 Tömbök; táblázatok
Gyakran adódik olyan probléma, hogy az adathalmaz elemeit
nem sorban egymás után szeretnénk elérni. Ilyenkor célszerű
táblázatok (vagy másként: mátrixok, tömbök) alkalmazása.
A táblázatokkal kapcsolatos feladatokat csoportosítani le-
het például a következő szempontok szerint. Az egyik csopor-
tot azok alkotják, melyekben nem a mátrix egésze a lényeges,
csak az egyes elemek. Ilyen feladatok például a TBLZATOKban
való keresés, elemek valamilyen szempont szerinti csoportosí-
tása. A másik feladatcsoport lehetne, a MTRIX egészére vo-
natkozó SZMITSOK elvégzése (mátrixszorzás, összeadás stb.).
A harmadik problémakört a mátrixok tárolásaival kapcsolatos
feladatok alkotják. Ez egyrészt azért fontos, mert a memóriá-
ban csak sorban, egymás után helyezkedhetnek el az adatok,
mégis meg kell valahogyan oldani az indexek alapján az elemek
elérését.
Egy másik jellemző problémakör az elemek tárolása. Sok
egyforma elem esetén célszerű csak a különbözőket tárolni.
Ezt ketté lehet választani. Nem mindegy ugyanis, hogy a sok-
szor előforduló elemek valamilyen szabályos elrendezésben
szerepelnek, vagy szétszórtan. Az első esetben lehet azt a
megoldást választani, hogy a tárolandó elemeket sorban lerak-
juk a memóriába és egy un. CMFÜGGVÉNY segítségével, adott
koordinátákból kiszámítjuk a memóriabeli helyét. Ha nem talá-
lunk a nullától különböző elemek elhelyezkedésében semmilyen
rendszert, akkor HÉZAGOSAN KITÖLTÖTT MTRIXokkal van dolgunk.
4.5 Fa és gráf
Halmazbeli elemek közti kapcsolatokat gyakran kell olyan
formában leírni, hogy azt számítógéppel is kezelni lehessen.
Tipikus feladatok közé tartozik például két helység közötti
legrövidebb út megtalálása. Egy ilyen gráfot többféleképpen
is meg lehet adni. Egyik módja, hogy megadjuk az élek által
összekötött csúcsokat, máik lehetőség, hogy ún. csúcsmátrixot
veszünk fel. Ebben a megszámozott csúcsokat felírjuk 'víz-
szintesen' és 'függőlegesen', majd az így kapott mátrixba
1-est írunk oda, ahol a két csúcs között él van. Speciális
gráfként természetesen fákat is lehet ábrázolni, sőt speciá-
lis, bináris fát is. A bináris fák használata nagyon tanácsos
nagy adathalmaz tárolásakor, ha valamilyen rendezettséget vá-
runk el. Ilyenkor ugyanis optimális felírási sorrend esetén
nagyon kevés lépés kell egy elem kiválasztásához.
4.6 Adatállományok
A számítógépek egyik legfontosabb alkalmazási területe az
adatfeldolgozás. Nagy adathalmaz kezelése elképzelhetetlen
lenne olyan eszközök nélkül, amelyek az adatok maradandó tá-
rolását teszik lehetővé. Az ilyen eszközökön létrehozott
adatállományokat file-oknak is nevezzük. Többek között hasz-
nálunk szekvenciális, relatív (direkt elérésű) adatállományo-
kat az adatok tárolására. Ezek szervezésével, lehetőségeinek
kihasználásával foglalkozik ez az alfejezet. A konkrét megva-
lósítások nagyon gépfüggőek ezért az Olvasóra bízzuk, hogy
azt a saját gépén megvalósítsa.