2009.03.30.
Adatszerkezetek
Összetett adattípus Meghatározói: ◦ ◦ ◦ ◦
A felvehető értékek halmaza Az értékhalmaz struktúrája Az ábrázolás módja Műveletei
Adatszerkezet fogalma
Direkt szorzat ◦ Minden eleme a Ti halmazokból vett értékek direkt szorzata
Unió ◦ Értékeit n db különböző típus valamelyikéből veszi
Sokaság ◦ Véges számú, azonos típusú elemekből áll
Az értékhalmaz struktúrája
1
2009.03.30.
Típuskonstrukciós műveletek ◦ Elem felvétele (adott helyre, elejére, végére, …) ◦ Elem törlése (adott helyről, adott érték, …)
Szelekciós műveletek ◦ Elem keresése (hely alapján, érték alapján, kulcs alapján, függvény alapján, …)
Műveletek
Részek függvénnyel kiválasztása ◦ A típus ábrázolása annyi biten történik, ahány biten az egyes résztípusok összesen ábrázolhatók ◦ Pl.: C# bitenkénti felsorolás típusa
Részek névvel kiválasztása (rekord, osztály)
Direkt szorzat típusok
Újradefiniálás ◦ Ugyanazokhoz az adatokhoz más és más módon férhetünk hozzá (C, C++ unió típusa)
Alternatív rekord ◦ Feltételtől függően a rekord vagy egyik, vagy másik típusú értéket tárol (Pascal alternatív rekord típusa)
Unió típusok
2
2009.03.30.
Sorrend nélküli sokaságok ◦ ◦ ◦ ◦ ◦
Halmaz Multihalmaz Intervallumhalmaz Hasító táblázat …
Sorozat típusok
Hierarchikus típusok
Hálós típusok
◦ Verem, sor, prioritási sor, lista, … ◦ Fa, bináris fa, B-fa, … ◦ Gráfok
Sokaság típusok
Ábrázolás: ◦ A halmazbeli elemek értékeinek felsorolása ◦ A halmazbeli elemek értékének megfelelő bit beállítása ◦ A halmazbeli elemek értékeinek megfelelő sorszámú logikai érték igazra állítása
Halmaz
Az elemek között egyértelmű sorrend áll fenn Speciális műveleteik:
◦ Első, utolsó ◦ Elejére, végére ◦ Elsőutániak, utolsóelőttiek
Ábrázolási módok: ◦ Folytonos (szekvenciális) ◦ Láncolt ◦ Blokkolt
Sorozat típusok
3
2009.03.30.
Az adatszerkezet elemei egy egybefüggő memóriaterületen egymás után helyezkednek el Az egyes elemekhez indexeléssel férhetünk hozzá
0.
1.
2.
n.
Előnyök: elemek elérése, keresése egyszerű Hátrányok: törlés, beszúrás nehéz, sok mozgatással jár, elemek száma rögzített
Szekvenciális ábrázolás
Az elemek fizikai és logikai sorrendje eltérő. A logikai sorrendet a következő elem helyének tárolásával valósítjuk meg. Fajtái:
◦ Statikusan láncolt ábrázolás ◦ Dinamikusan láncolt ábrázolás
Előnyök: könnyű beszúrás, törlés, elemek száma dinamikusan változhat Hátrányok: nehéz a keresés
Láncolt ábrázolás
Az elem után következő elem sorszámát (indexét) tároljuk -1
Első elem = 2.
0. 3. 1.
Statikusan láncolt ábrázolás
4
2009.03.30.
Az elem után következő elem referenciáját, vagy mutatóját tároljuk Első elem
Dinamikusan láncolt ábrázolás
Egy blokk több elemet és egy hivatkozást tárol a következő blokkra Egy blokkon belül az elemek indexeléssel érhetők el
Első elem
Blokkolt ábrázolás
Last In First Out (LIFO): a legutoljára betett elemet lehet legelőször kivenni
Utolsó elem
Műveletei: Push, Pop, Üres_e, Tele_e
Verem adatszerkezet
5
2009.03.30.
First In First Out (FIFO). A legelőször betett elemet lehet legelőször kivenni.
Műveletei: Sorba, Sorból, Üres_e, Tele_e
Kivétel helye
Betétel helye
Sor adatszerkezet
Ciklikus sor ◦ Ha valamelyik mutató a sor végére ér, akkor folytatja a mozgását a sor elején
Prioritási sor (rendezett sor) ◦ Minden elem mellett egy rendezési szempont alapját képező értéket is tárolunk ◦ Vagy az elem betételét, vagy kivételét végezzük a rendezési szempont alapján
Speciális sor adatszerkezetek
Lukasievitz lengyel matematikusról nevezték el A kifejezések zárójelek nélküli leírását teszi lehetővé Változatai:
◦ Prefix: a műveletek operandusaik előtt szerepelnek Pl.: infix: (a+b)*(a-b) Prefix lengyel-forma:*+ab-ab
◦ Postfix: a műveletek operandusaik mögött szerepelnek Pl.: infix: (a+b)*(a-b) Prefix lengyel-forma:ab+ab-*
Lengyel-forma
6
2009.03.30.
Infix, zárójeleket is tartalmazó kifejezés lexikális egységeinek azonosítása 2. Infix, zárójeleket is tartalmazó kifejezés postfix lengyel-formára alakítása 3. Postfix lengyel-formájú kifejezés értékének kiszámítása 1.
Kifejezések kiértékelése Lengyelformával
Operandusok a kimenetre Művelet: ◦ Ha a veremben nála nagyobb, vagy egyenlő prioritású művelet van, akkor kivenni a veremből és kiírni a kimenetre ◦ Művelet betétele a verembe
Nyitó zárójel:
Záró zárójel:
◦ Betétel a verembe ◦ Műveletek kivétele a veremből és kiírása a kimenetre a nyitó zárójelig ◦ Nyitó zárójel kivétele a veremből
Postfix lengyel-forma elkészítése
Operandus:
Művelet (n operandusú):
◦ Betétel a verembe ◦ A verem tetején lévő n db operandus kivétele a veremből ◦ A művelet elvégzése ◦ Az eredmény visszaírása a verembe
A műveletsor végén a kifejezés eredménye a veremben lesz
Postfix lengyel-formájú kifejezés értékének kiszámítása
7
