3. tétel: Adattípusok

(Adatok jellemzői. Elemi adattípusok, ábrázolásuk, problémáik. Típusösszetételi módok, sorozat típusú adatok műveletei. Tömbök, táblázatok, listák, vermek, sorok ábrázolása, műveletei, alkalmazása.)

Adatok jellemzői: azonosító, hozzáférési jog, kezdőérték, hatáskör, élettartam, értéktípus

Elemi típusok

Az elemi típusok megadása az értékhalmazukkal, a rajta definiált műveletekkel, relációkkal történik, illetve a lehetséges ábrázolásukkal.

Véges típus: olyan elemi típus, melynek értékhalmazába véges sok érték tartozik.

Diszkrét típus: olyan elemi típus, mely esetén létezik a „rákövetkező” és a „megelőző” művelet.

1.) Egész típus

Ábrázolás: kettes komplemens kód (2 byte-on) – túlcsorduláseszély!

(Első bit az előjelbit (1, ha a szám negatív), a pozitív számokat bináris számként tároljuk, a negatív számok = a szám abszolút értékének 1-es (bitről bitre vett) komplemense +1. Egyes műveletekre nézve a halmaz nem zárt, túlcsordulás léphet fel, így az asszociativitás és a disztributivitás szabálya is sérül.)

2.) Valós típus

Értékhalmaz: nyelvfüggő, a Min’Valós és a Max’Valós alapban nem definiált.

Lebegőpontos, normalizált, eltolt nullpontú (6 byte). Lényegében csak a racionális számokat, azon belül is a véges tizedestörttel leírhatóakat tudja a számítógép teljes pontossággal ábrázolni. Teljesen eltérő nagyságrendű számokkal végzett műveletek esetében alulcsordulás léphet fel. Az asszociativitás és a disztributivitás az ábrázolás pontatlansága miatt sérül.)

3.) Logikai típus

4.) Karakter típus

A jel-kód egymáshoz rendelése valamely kódkészlet alapján történik (ált. 7+1 bites ASCII-kóddal). A speciális billentyűkhöz (pl. kurzornyilak, funkcióbillentyűk) általában két kódot rendelnek hozzá, az első mindig nulla.

5.) Felsorolás típus: (annyi biten, amennyi a legnagyobb sorszám ábrázolásához szükséges)

6.) Mutató típus

7.) Részintervallum típus (az értékhalmaz ármilyen diszkrét típusból származtatható = ős)

Összetett típusok:

Típusösszetételi módok:

konstrukciós művelet: összetett típus struktúráját elemi típusokból hozza létre;

szelekciós művelet: egyes részek kiválasztása.

Típuskonstrukciók:

direktszorzat = rekord;

unió + direkt szorzat = alternatív rekord;

halmazképzés = halmaz;

iterált: sorozatok;

rekurzió: rekurzív adatszerkezet;

hierarchia = gráf.

Az összetett típusokat struktúrájuk szerint 3 nagyobb csoportba osztjuk:

direkt szorzat: T=T1 X T2 X … Tn. Értékeit n, akár különböző típus értékhalmazának direkt szorzatából veszi;

unió (vagy alternatív típus): T=T1  T2  … Tn. Értékeit n, különböző típus valamelyikéből veszi;

sokaság: T=T1*. Értékei több (véges sok) azonos típusú elemből állnak.

a.) Rekordtípus konstrukció
b.) Alternatív rekord

c.) Hatványhalmaz típuskonstrukció

d.) Tömbtípus

e.) Szövegtípus

Összetett típus, nem típuskonstrukciós eszköz. Meghatározható a max. karakterszám. (max. hosszúságú karaktersorozatok halmaza), alfabetikus rendezés.

f.) Sorozattípus:

A bázistípus iteráltja (elemek között egyértelmű a sorrend)

Műveletek: első, utolsó, első utáni, utolsó előtti, elejére, végére, elejéről, végéről, elsőre, következőre.

Ábrázolás:

folytonos – memóriabeli sorrend = sorozatbeli sorrend

láncolt: láncolt rekordok sorozata, az ábrázolás történhet dinamikusan (szabadon „garázdálkodik” a memóriával) illetve statikusan (előre lefoglalt max. méretű tömbben mutatók)

blokkolt: elemek csoportját blokkokban ábrázolom, melyeket láncoltan ábrázolom.

Az egyes sorozat típusokat a rajtuk definiált műveletek halmaza határozza meg. Eszerint a következőket különböztethetjük meg:

1.) Tömb

indexeléssel választhatóak ki az elemei;

műveletek: üres, elemszám(T):egész, elemérték(T,i):elemtípus, elemmódosítás(T,i,x)

axiómák:

üres tömb minden eleme nem definiált

egy elem módosítása nem változtatja meg a tömb hosszát

tömb elemének pontosan az az értéke, melyet az elemmódosítás művelet adott neki

az elemek értéküket módosításáig megőrzik

ábrázolás:

szekvenciális
(adatok a memória egybefüggő tartományán, viszonylag egyszerű és kézenfekvő kezelési módszer az elemekre)
Mátrixban (kétindexes tömb, tárolása), sorfolytonsan, oszlopfolytonosan

láncolt:
Az ElemCím kiszámítása egyenértékű a „láncon végighaladással”. A mátrix esetén speciális láncolásokat definiálhatunk:
– sorfolytonos; itt (i-1)*N + (j-1) lépéssel érhetem el a keresett elemet
– sorkezdettel ellátott ábrázolás: a sorok kezdetei tömbben, melynek elemszáma így a sorok számával egyenlő; minden egyes sorkezdethez láncoltan kapcsolódnak az azon sorba tartozó elemek; max(i+j) lépéssel az összes elem elérhető
– ortogonálisan láncolt: sor- és oszlopirányban is láncolt a mx! Ez a leghatékonyabb eljárás.

alkalmazás:

címfüggvények kiszámítása;

speciális szerkezetű tömbök:
(1) van benne ismétlődő elem:
alsóháromszög-mátrix, tridiagonális mx, szimmetrikus mx,
(2) van benne generáló elem:
Vandermonde-mátrix (itt minden sort egy elem generál, ezért egy vektorban tárolom az elemeket)
(3) hiányosan kitöltött mátrixok:
a mx elemeit spec. mxban tároljuk, ahol a sorok száma egyenlő a hiányos mx-ban található nem nulla elemek számáva, oszlopainak száma 3 (érték, eredeti sorindex, eredeti oszlopindex) – jóval gazdaságosabb tárolás

2.) Táblázat
Kettős arculatú, egyrészt hasonlít a halmazra; mivel az elemek sorrendje a sokaságon belül nem definiált; valamint bármely két elemnek a kulcsa különböző. Az indexelhetősége miatt „tömb-rokon” is egyben.

sorozat: elem = (kulcs, érték)

axiómák:

üres táblázat minden eleme nem definiált, az elemszám 0

ha van még hely, akkor elem beszúrható, és az elemszám eggyel nő, kivéve, ha ugyanolyan kulcsot már tartalmaz a táblázat

létező elem törölhető, és az elemszám eggyel csökken, nem létező elem törlése nem definiált

létező elem módosítható, és ekvivalens egy törlés és egy beszúrás művelettel; nem létező elem módosítása és a kulcs módosítása nem definiált

ha van keresett kulcsú elem a táblázatban, akkor az kereshető

műveletek: üres, beillesztés, törlés, keres (paramétere a kulcs, értéke az eredmény), hibás?

kulcstranszformációs vagy indexfüggvények:

(egyértelmű hozzárendeléssel bíró kulcsfüggvényt szinte lehetetlen találni – kulcsütközés problémája)

konstruálása:
- osztó módszer
- szorzó módszer
- számjegyes módszer
- jel-kód módszer
- összetett kulcsok transzformációja

kulcsütközések feloldása:
- tulcsordulási terület módszere
– láncolt altáblák módszere
– lineárisan szétszórt altáblák módszere
– másodlagos kulcs bevezetése
– hierarchikus módszer
– blokkolt altáblák

alkalmazása:

keresés

rendezés kulcstranszformációval

3.) Lista

Egyszerű lista esetében az első elemtől kezdve sorban lehet haladni, az aktuális elemmel műveleteket lehet végezni, s mögé beszúrni elemet.

műveletek: első, üres, üres?, következő, beszúrMögé, beszúrElejére, kihagy, utolsó?,

elejére, elemÉrték, elemMódosít

axiómák:

Üres lista üres.

Üres listának nincsen eleme.

Üres listának nincsen aktuális, első, … utolsó eleme.

Nincsen elsőt megelőző és utolsót követő eleme a listának.

Ciklikus listában az elsőt megelőző az utolsó, az utolsót követő pedig az első.

Az Utolsóra művelettel kiválasztott elem az elemszám-adik, az első elemét az Elsőre művelet választja ki.

A beszúrMögé művelet bővíti a listát az adott elemmel. Az új elem az ’aktuális’ mögé kerül. Üres listába elsőként kerül be az új elem. Az új válik ’aktuálissá’. Ha nincs ’aktuális’ elem, akkor a művelet eredménye nem definiált.

Kihagyni az ’aktuális’ elemet lehet, az ’aktuális’ a következő lesz. Ha nincs kijelölve az ’aktuális’ elem, akkor nem lehet kihagyni sem.

Két, egymás után illesztett lista listát alkot. Elemei az eredeti kettő elemei lesznek, az eredeti sorrendben.

A következő elem az, amelyet a következőre lépés után aktuálisként érzékelünk, az előző az, amelyet az előzőre lépés után aktuálisként érzékelünk…

speciális listák:

kétirányú (kétszeresen láncolt) lista: utolsó elemtől is lehet visszafele haladni
plusz műveletek: utolsó?, beszúrElé , első?

ciklikus lista: egy- vagy kétirányú, az utolsó elemét az első követi
nincs szükség az összes alapműveletre (utolsó?, beszúrElejére nem kell) plusz művelet az „előző”

gyűrű: olyan ciklikus lista, melynek nincsen kitüntetett első eleme
nincs szükség az összes alapműveletre (utolsó?, beszúrElejére, első nem kell) plusz művelet az „előző”

ábrázolás:

szekvenciális: lista ábrázolása egy tömbben - elemek változtatása nehézkes

láncolt
– statikusan láncolt: lefoglal egy max. méretű területet a memóriában – láncolás a tömbön belül megoldott, mutatók helyett tömbindexek!
– dinamikusan láncolt: folyamatos helyfoglalás, felszabadítás
– blokkolt: blokkon belül szekvenciális, blokkok között láncolt

alkalmazás:

kiválogatás listával, összefuttatás listával, beszúrásos rendezés

4.) Verem

Az adatok sorrendje megfordul.

műveletek: üres, üres?, tele?, verembe (tetejéről), veremből (tetejéről), Tető

axiómák:

Üres verem üres. Az a verem, melyben legalább egy elem van, nem üres.

Üres veremnek nincsen legfelső eleme, így kivenni sem tudunk belőle

Tele verembe nem lehet további elemet betenni.

A verem legfelső eleme az utoljára betett eleme.

A veremből a legfelső elemet lehet kivenni, a többi elem nem változik.

ábrázolás:

szekvenciálisan, láncoltan (a verem tetején levő elem címét kell megadni, illetve minden veremelemnek tartalmaznia kell az alatta levő elem címét – egyfajta speciális, láncolt ábrázolású lista, speciális műveletekkel)

speciális verem: duplaverem
Két, előre rögzített, maximális összhosszúságú sorozatot egyetlen, folyamatos tartományban tárolunk, úgy, hogy az egyik sorozat a tartomány elejére, a másik a tartomány végére illeszkedik – mindkettő „befelé”, egymás felé terjeszkedik, az ellenkező irányba fogy. Megvalósítása dupla veremmel történik.

alkalmazás:

sorrend megfordítása

eljáráshívások megszervezése

duplaverem – hatékonyság javítható

5.) Sor

Csak az adatszerkezet végére lehet elemet illeszteni, elejéről lehet kilépni.

műveletek: első, tele?, üres, üres?, sorból, sorba

axiómák:

Üres sor üres. Az a sor, melyben legalább egy elem van, nem üres.

Az üres sornak nincsen legelső eleme, így kivenni sem tudunk belőle

Tele sorba nem lehet további elemet betenni.

A sor első eleme a legrégebben betett elem.

A sorból az első elemet lehet kivenni, a többi elem nem változik.

ábrázolás:

láncoltan: listákhoz hasonlóan; a „fejmutató” mellett szükséges a sor vége is

szekvenciálisan: nem szerencsés; gond az 1. elem kivétele – sok mozgatással jár

szekv. ciklikus: az utolsó indexű elemre az első következik; a hossz-számláló bevezetése itt hatékonyítja az eljárásokat

alkalmazás:

input/output puffer (gép és környezet kommunikációjához használt adatszerkezet a sor)

szimulációk – egy processzor, több folyamat azonos időben

kétvégű sor

prioritási sor

PROGRAMOZÁSI MÓDSZERTAN

Frena András

2002-06-22T11:28:00

Peter Szamoskozi