Ugrás a tartalomhoz

Adatstruktúrák és algoritmusok

Házy Attila, Nagy Ferenc (2009)

1.4. Az absztrakt adat és adattípus

1.4. Az absztrakt adat és adattípus

Az adat fogalma az értelmező szótár szerint:

„Az adat valakinek vagy valaminek a megismeréséhez, jellemzéséhez hozzásegítő (nyilvántartott) tény vagy részlet.” (Lásd [1]).

Mi adatnak fogunk tekinteni minden olyan információt, amelynek segítségével leírunk egy jelenséget, tanulmányunk tárgyát, vagy annak egy részét. Az adat formai megjelenésére nem leszünk tekintettel, ettől lesz absztrakt. (Absztrakt adat.) Egy rúd hosszát megadhatjuk úgy is, hogy mondjuk százhuszonhét centiméter. Itt nem fontos, hogy a százhuszonhét a 127 formájában van-e megadva, esetleg , vagy alakban. (Egy számítógépes program számára persze ez egyáltalán nem mindegy.) Ez a fejtegetés sem sokkal konkrétabb. Például mi az az információ? Erre a kérdésre a választ nem feszegetjük. Az adat fogalma az alkalmazások, példák és feladatok során lesz tisztább. Tulajdonképpen azt is nehéz megmondani, hogy mi nem lehet adat.

1.7. Definíció. Az absztrakt adat valamely halmaznak az eleme. Ezen halmaz bármely elemét felhasználhatjuk a munkánkban, számításainkban, az alkalmazott valóságmodellben, objektumainak leírásában, megadásában.

1.8. Definíció. Az absztrakt adattípus egy leírás, amely absztrakt adatok halmazát és a rajtuk végezhető műveleteket adja meg (definiálja) nem törődve azok konkrét (gépi) realizálásával.

1.9. Definíció. n-változós (n-áris) műveletnek nevezzük az a leképzést, függvényt, ahol az absztrakt adat halmazát jelöli. Azaz ez a leképzés egy absztrakt adat -eshez szintén egy ugyanolyan absztrakt adatot rendel hozzá.

A műveletek közül kiemelkednek a bináris (binér) műveletek, amelyekben tehát az elnevezés alapján is érthetően a művelet elempárokhoz rendel hozzá egy elemet eredményképpen. Például a valós számok esetén ilyen művelet lehet két szám összeadása. Számunkra fontosak az egyes műveletek tulajdonságai. A tulajdonságok megléte, vagy meg nem léte lehetővé teszi vagy éppen nem teszi lehetővé, hogy a formuláinkat átalakítsuk, egyszerűsítsük. Ilyen tulajdonságok például az asszociativitás, kommutativitás, disztributivitás, idempotencia, stb., melyeket az alkalmas helyeken tárgyalunk.

Példák absztrakt adattípusokra:

  • logikai érték,

  • természetes szám,

  • egész szám,

  • racionális szám,

  • valós szám,

  • komplex szám,

  • sorozat,

  • halmaz,

  • dinamikus halmaz.

    • tömb

    • verem

    • sor

    • lista

    • fa

    • gráf

1.4.1. A logikai absztrakt adattípus

A logikai absztrakt adattípus egy olyan halmazt ad meg, amelynek két eleme van, a hamis és az igaz. Jelölésben L={hamis, igaz}. Röviden az elemeket a h (hamis) és az i (igaz) jellel jelöljük.

A típus műveletei lehetnek unáris (unér) és bináris (binér) aszerint, hogy hány operandusuk van. (Lehetnek többoperandusú műveletek is, de ezek a korábbiakkal kifejezhetők.)

Unáris műveletek

Unáris művelet a Negáció, (tagadás, NEM, NOT). Jele: felülvonás a logikai adat neve fölött. Pl.: és . Művelettáblája:

További három unáris művelet alkotható, amelyek azonban triviálisak. Ezek az identikus művelet, a hamis és az igaz művelet. Ez utóbbi kettő konstans eredményt ad.

Művelettábláik:

Bináris műveletek

Bináris műveletből 16-ot lehet felírni. A műveletek erősorrendje csökkenő erő szerint (prioritás, zárójelezés nélkül írhatók) a következő: NEM, ÉS, VAGY, KIZÁRÓ VAGY, Ekvivalencia, Implikáció.

A NEM, ÉS, VAGY műveletek tulajdonságai:

Ezen három művelettel (NEM, ÉS, VAGY) az összes többi (a többváltozósak is) kifejezhetők.

1.7. Példa.

Szintén kifejezhető az összes művelet csupán a (NEM, VAGY), vagy a (NEM, ÉS), vagy a (NEM, KIZÁRÓ VAGY), vagy a (NEM VAGY) vagy a (NEM ÉS) műveletekkel.

1.8. Példa.

A diszjunktív normálforma

1.10. Definíció. Elemi konjunkció

Változók vagy tagadottjainak a konjunkciója, melyben a változók legfeljebb egyszer fordulnak elő.

1.11. Definíció. Diszjunktív normálforma (DNF)

Elemi konjunkciók diszjunkciója.

Művelettábla alapján DNF előállítása: Ahol az eredmény oszlopban i van, azokat az eseteket diszjunkcióval kötjük össze úgy, hogy a változók konjunkcióiból formulát alkotunk. A formulában i esetén a változó szerepel, h esetén a változó negáltja.

1.9. Példa.

Innen .

A logikai változó realizálása történhet bitekkel: hamis – 0, igaz – 1.

1.12. Definíció. Izomorfizmus

Két algebrai struktúrát izomorfnak nevezünk, ha létezik olyan kölcsönösen egyértelmű megfeleltetés a két struktúra elemei között, amely esetén a műveletek is szinkronizálódnak. Ez azt jelenti, hogy ha az egyik struktúra az , a másik struktúra a , a kölcsönösen egyértelmű megfeleltetés pedig , akkor fennáll, hogy minden és esetén. Az megfeleltetést nevezzük izomorfizmusnak.

1.10. Példa. Legyen a pozitív valós számok halmaza a szorzás művelettel felruházva, és az összes valós szám halmaza az összeadás művelettel. Akkor az megfeleltetés, ahol , izomorfizmust valósit meg, hiszen a logaritmus azonosságai szerint: minden pozitív és esetén.

Legyen most az halmaz az logikai adattípus a negáció, a konjunkció és a diszjunkció műveletével felruházva. Legyen a halmaz a számokból álló halmaz, amelyen értelmezzük az alábbi három múveletet:

  • Ellentett elem képzése unáris művelet : , a kivonás művelete révén.

  • Szorzás bináris művelet: , a számok szorzási műveletének megfelelően.

  • Bitösszegzés bináris művelet: a számokra érvényes szokásos összeadás, kivonás és szorzás művelete révén.

Ekkor a most definiált három művelet a negáció, konjunkció, és diszjunkció műveletének megfeleltetve, valamint a logikai mennyiségeknek a biteket a fenti módon megfeleltetve a logikai adattípus és a bit adattípus között izomorfizmust hoztunk létre. Azt mondjuk, hogy a logikai adatokat bitekkel modellezzük. Amilyen törvényszerűséget találunk az egyikben, az izomorfizmus révén megtaláljuk a törvény párját a másikban.

A logikai típus nagyon fontos, mert az értékeket feszültségszintekhez lehet társítani, a műveleteket pedig úgynevezett kapuáramkörökkel valósíthatjuk meg. A kapuáramkör fizikai (technikai) felépítése lényegtelen a számunkra, az változott az idők folyamán (relék, diódák, tranzisztorok, stb.). Sematikusan úgy jelölhetjük őket, mint egy dobozba zárt átalakító szerkezet, amelynek vannak bemenetei és kimenetei. A bemeneteken bemenő jeleket dolgozzák fel a rendeltetésüknek megfelelően, és az eredmény megjelenik a kimeneteken.

Példa kapuáramkörökre:

Kapuáramkörökből felépíthető az úgynevezett félösszeadó (Half Adder). Feladata egyetlen bitpozíción képezni a két bit összegét és az átvitelt, tehát a művelet mindig kétjegyű eredményt képez, melynek alacsonyabb helyiértékű bitje az összegbit, magasabb helyiértékű bitje az átvitelbit (Carry bit).

A félösszeadó több-bites számok összeadásakor csak fél munkát végez, helyesen csak a legalacsonyabb bitpozíción működik. A további pozíciókon három bitet kell összeadni, a két összeadandó bitet és az előző pozícióról jövő átvitelbitet. A teljes összeadó (Full Adder) ezt valósítja meg.

Felírva a két eredményoszlopra a diszjunktív normálformákat, tulajdonképpen megkapjuk a műveletek egy lehetséges kapuzását.

Ezt a látszólag bonyolult formulát le lehet egyszerűsíteni és a teljes összeadó felépíthető két félösszeadó és egy VAGY kapuáramkörből. Előtte azonban egy segéd formulát vezetünk le.

1.13. Lemma.

Bizonyítás. Láttuk, hogy

Akkor

Ezután a teljes összeadó levezetése az alábbi lehet:

Jelölje és az első, valamint a második félösszeadő által adott eredmény összegbitet és az átvitelbitet. Akkor

A teljes összeadó sematikus ábrája:

1.4.2. A karakter absztrakt adattípus

A karakter absztrakt adattípus a szöveges információ megjelenítést teszi lehetővé. A szövegeinket elemi egységekből építjük fel.

1.14. Definíció. Karakter

A karakter a tágabb értelemben szövegesen lejegyzett adat legkisebb, elemi egysége, egy tovább már nem bontható szimbólum.

A karakterek halmazát -szel fogjuk jelölni.

A karaktereket osztályozhatjuk jellegük szerint. Eszerint a karakterek lehetnek: számjegyek, betűk, írásjelek (pont, vessző, felkiáltó jel, stb.), speciális jel (félgrafikus jel, matematikai jelek, hieroglifák, szimbólumok, stb.), vezérlőjel (csengő, soremelés, lapdobás, kocsi vissza, file vége, escape, stb.).

A karakter absztrakt adattípusra jellemző, hogy az halmaz elemei között rendezettséget vezetünk be, amely konvención, megállapodáson alapul. Előre rögzítjük a sorrendjüket. (Ezt a sorrendet nevezhetjük ábécé sorrendnek.) A sorrend szerint az egyes karaktereket sorszámmal láthatjuk el. Két műveletet be is vezethetünk ezáltal. Az egyik lehet a Hátrább_álló, a másik lehet az Előbb_álló. A Hátrább_álló a két karakter közül azt adja eredményül, amelyik az -ben hátrább áll, azaz amelyiknek a kettő közül nagyobb a sorszáma, míg az Előbb_álló azt adja, amelyiknek kisebb a sorszáma. A sorszámot a karakter kódjának nevezzük.

1.11. Példa. Előbb_álló('K','C')='C', és Hátrább_álló('K','C')='K'.

Ha bevezetünk bináris műveleti jeleket a két műveletre, például legyen az Előbb_álló jele , a Hátrább_álló jele , akkor az előzőleg felírt példa lehet

Civilizációnkban rendkívül sok karakterrel találkozhatunk. Az informatikában kezdetben nem sokat használtak fel ezek közül. Szorított a tárolóhely hiánya. Jelentős lépés volt, amikor az akkor legfontosabbnak tekintett jelkészletet egységesítették, szabványosították. Ez volt az ASCII kódtáblázat (American Standard Code for Information Interchange, az információcsere amerikai szabványos kódja), amely hétbites kód volt. Jellemzője, hogy 0-tól 127-ig terjed az egyes karakterek kódja és az első 32 jel (0-31) vezérlőjel. Ilyenek például a csengő (7), a soremelés (10), a lapdobás (12), a kocsi vissza (13), a file vége (26), az escape (27). Vezérlőjel még (törlőjel) a 127-es kódú karakter. A többi jel látható. Ilyenek a helyköz (32), a számjegyek növekvő sorrendben (48-57), az angol ábécé nagybetűi (65-90), az angol ábécé kisbetűi (97-122). A kisbetű kódja 32-vel nagyobb, mint a neki megfelelő nagybetűé. A teljes ASCII kódtáblázat a mellékletben látható. Az ASCII kódok tárolása a byte-os memória és társzervezés következtében az egy byte egy karakter elvet követte. Mivel egy byte-on 256 féle bitmintázat helyezhető el, ezért kihasználatlan maradt a 127-es kód feletti 128-255 számtartomány 128 eleme. Ugyanakkor az informatika nemzetközivé válása miatt szükségessé vált a nemzeti ábécék jeleinek az alkalmazása is, amelyet az ASCII tábla bővítésével igyekeztek megoldani. Az ASCII tábla bővítése sajnos rossz irányba történt, A 128 elemű eredeti készletet jóval több, mint további 128 jellel kellett volna bővíteni. Megtartották az egy byte-os szerkezetet. Ezért a 127-es kód feletti kódokat több célra kellett használni, hogy mindenkinek az igényét kielégítsék. Bevezették a kódlap fogalmát. Definiáltak például Latin-1 kódlapot, amelybe sok ékezetes betű is belefért, persze felrúgva ezzel a betűk ábécé sorrendjét. A magyar ő és ű betű azonban ebbe sem fért bele. Azt a Latin-2 kódlapra tették. Az eredmény az lett, hogy ha a szöveget megjelenítő program nem tudta, hogy a szövegfile eredetileg milyen kódlap alapján készült (honnan tudta volna, amikor ez az információ a file-okban nem szerepel), akkor amennyiben ő más kódlap szerinti megjelenítésre volt beállítva, a szöveg akár olvashatatlanná is vált. Ugyanannak a kódnak többféle karakter is megfelelt a kódlapoknak megfelelően. Másik probléma volt az, hogy vannak nyelvek, amelyeknek több ezer írásjel szimbóluma van, amelyek eleve nem férnek el egy ilyen 256-os táblázatban. Ezeket kétbyte-os ábécében helyezték el. Azonban ezek a törekvések bár bevezetésre kerültek, a problémákat nem szüntették meg már csak azért sem, mert egy szöveg tartalmazhat különböző nyelven megírt részleteket is.

A megoldást a Unicode Standard szolgálja. Az 1.0 verzió 1991-ben jelent meg, jelenleg (2011) a 6.0 verziónál tartunk. A Unicode rendszerben a karakter absztrakt fogalom és a neve egyedileg azonosítja, amely nem változtatható. A karaktereket egy-egy rá egyedileg jellemző egész számmal, a karakter kódpontjával (code point) kapcsoljuk össze. Ezek a kódpontok egy kódtérben (codespace) helyezkednek el, amely nevezetesen a nullával kezdődő és a hexadecimális 10FFFF-fel végződő egész számok tartománya. A kódpont mindig ugyanazt a karaktert jelöli és fordítva, egy karakternek mindig ugyanaz a kódpontja. A kódtér mérete 1 114 112 kódpont.Majdnem mindet karakterkódként használják. Vannak speciális célra fenntartott kódpont tartományok. A számunkra (Európa) szokványos karakterek többsége az első 65 536 kódponton elfér. Ezt a tartományt BMP-nek (Basic Multilingual Plane) nevezik. A maradék több mint 1 millió hely elegendő az összes ismert karakter, írásjel kódolására, beleértve a minoritások által használt vagy a történelemből ismert írásképeket.

Lényeges tulajdonsága a Unicode-nak, hogy a karakter absztrakt fogalmát leválasztja annak a képernyőn vagy a nyomtatón megjelenő képétől. A képpel a Unicode nem foglalkozik. (Pl. a karakter mérete, színe, dőlése, kövérsége, kiemelt mivolta, alakja stb.) A karakter Unicode kódját az U+xxxx, U+xxxxx vagy a U+xxxxxx alakban adjuk meg, ahol x hexadecimális számjegy és a számérték a kódpont.

Az absztakt karakter reprezentálására a számítógépben három lehetőségünk van. Ezek a UTF-32, a UTF-16 és a UTF-8 kódolási formák. (UTF - Unicode Transformation Format.) Meg kell különböztetni a kódolt karakter és a szövegelem fogalmát. A szövegelem egy vagy több kódolt karaktert jelent. Például a hullámos vonallal felül díszített u betű előáll az u betű és a felül hullámos vonal karakterek kódjából. Tehát a karakterkép esetleg több elemből is összetevődhet. Tekintsük most az egyes kódolási formákat. Bármely formát is választjuk, ezek egymásba veszteség nélkül áttranszformálhatók.

A UTF-32 esetén a kódpont szerinti egész szám és a kettes számrendszerbeli 32 bites megfelelője között egy-egy értelmű a kapcsolat.A kód mérete fix, négy byte. Emiatt a tárigény nagy.

A UTF-16 esetén a U+0000, ..., U+FFFF kódpontok 16 biten jelennek meg, míg a U+10000, ..., U+10FFFF kódpontok egy 16 bites páron ábrázolódnak a következő módon.

xxxxxxxxxxxxxxxx

xxxxxxxxxxxxxxxx

000uuuuuxxxxxxxxxxxxxxxx

110110wwwwxxxxxx 110111xxxxxxxxxx

Itt a wwww szám az uuuuu-1-et jelenti binárisan. Látható, hogy ez a kódolás BMP-re optimalizált. A Unicode elődje.

A UTF-8 byte-orientált kódolás, ASCII alapú, az ASCII-re transzparens, azaz ugyanúgy ábrázolja. A kód mérete változó, 1-4 byte lehet. A vezető byte jelzi a karaktert leíró byte-szakaszt. Kedvező a HTML és Internetes protokollok számára. A kódpont ábrázolásának módja a következő.

00000000 0xxxxxxx

0xxxxxxx

00000yyy yyxxxxxx

110yyyyy 10xxxxxx

zzzzyyyy yyxxxxxx

1110zzzz 10yyyyyy 10xxxxxx

000uuuuu zzzzyyyy yyxxxxxx

11110uuu 10uuzzzz 10yyyyyy 10xxxxxx

A további információkhoz juthatunk a Unicode Standard leírására a [3]-ból.

1.4.3. Az egész szám

Az egész szám esetén nagyon megszoktuk a 10-es alapú számrendszer használatát. Valójában nem törődünk a szám leírásával. Egy szám esetében a számítógép nem a 10-es, hanem a 2-es alapot használja a szám reprezentálására. Attól még az a szám ugyanaz a szám. Nincs értelme absztrakt egész szám esetén beszélni például egy szám számjegyeiről. Más a helyzet abban a pillanatban, amikor az absztrakt adattípus szerinti adatot konkrétan meg akarjuk jeleníteni. Akkor már nem lényegtelen az ábrázolási forma. Próbáljuk meg például összeszorozni papíron kézzel és ceruzával a hetvenkilencet és a negyvenhetet úgy, hogy a két számot 79 és 47 alakban adjuk meg, valamint úgy is, hogy és alakban. Az első esetre van egy módszer, egy könnyen megjegyezhető séma, amely szerint a kisiskolás is el tudja végezni a számítást, a másik esetben pedig nehéz ilyet adni, holott a szorzat létezik az ábrázolástól függetlenül. Adható persze az ábrázolástól független módszer is két nemnegatív egész szám összeszorzására. Ennek a módszernek a neve ma gyakran úgy olvasható, hogy „orosz paraszt” módszer. Az elnevezés nem teljesen jogos, mert a módszert már az ókori egyiptomiak is ismerték és használták [4]. A módszer lényege, hogy a szorzatot fokozatosan gyűjtjük össze és a zérusból indulunk ki. A szorzót vizsgáljuk. A vizsgálat abból tart, hogy megnézzük, hogy páratlan-e. Ha igen, akkor a szorzandót hozzáadjuk a szorzathoz, ha nem, akkor nem adjuk hozzá. Ezután a szorzót lecseréljük a felének az egész részére, a szorzandót pedig lecseréljük a duplájára. A vizsgálat mindaddig ismétlődik, míg a szorzó zérussá nem válik. (Lássuk be, hogy a módszer mindig a helyes szorzathoz vezet két nemnegatív egész szám esetén!)

1.12. Példa. Szorozzuk össze a 79-et és a 47-et az orosz „paraszt” módszerrel!

Az absztrakt adattípus egy fekete doboz, amelybe beletesszük az adatot tárolásra és kivesszük, ha szükségünk van rá. Nem érdekes, hogy a doboz hogyan végzi a tárolást. Ami viszont fontos az az, hogy az absztrakt adattípushoz elválaszthatatlanul hozzátartoznak azok a műveletek, amelyeket az adatokkal végezni lehet.

1.15. Definíció. Adatstruktúrának nevezzük az absztrakt adattípus konkrét megjelenési formáját.

A műveletek az adatstruktúrához ugyanúgy hozzátartoznak, mint az absztrakt adattípushoz. Példák adatstruktúrára:

  • lista, verem,

  • sor, elsőbbségi (prioritásos) sor,

  • bináris kupac, binomiális kupac,

  • fa, gráf, hálózat.

Adatstruktúra a számábrázolás módja is. Az elnevezésekben azonban az absztrakt adattípus és az adatstruktúra nevek gyakran keverednek, hiszen tartalmilag hasonló dolgokról van szó.