Adatszerkezetek 1. Dr. Iványi Péter
1
Adat • Adat minden, amit a számítógépünkben tárolunk és a „külvilágból” jön • Az adatnak két fontos tulajdonsága van: – Értéke – Típusa
2
Adat típusa • Az adatot kódoltan tároljuk • Az adat típusa számunkra azt jelenti, hogy mi is az amit tárolunk. • Ez csak nekünk bír jelentőséggel, a számítógép ezt másképp értelmezi.
3
Adat ábrázolás • Ugyanakkor az adat típusa a számítógép számára is hordoz fontos információt • A fordító programnak tudnia kell, hogy az adatnak mekkora helyet kell lefoglalni a memóriában és hogyan kell kódolni. • Ez az adat belső ábrázolása.
4
Adat ábrázolás • Az emberek számára a belső ábrázolás „érthetetlen” • A ki- és beviteli utasítások számára más ábrázolásra van szükséges, amely az ember számára is olvasható és írható • Ez az adat külső ábrázolása.
5
Adat • A típus azt is meghatározza a fordító számára hogy milyen műveleteket lehet végezni az adatokon. • A fordító program nem dönthet a típusról ezért a programban deklarálnunk kell az adatok típusát.
6
Adat • Deklarálnunk kell a programban használt: – Változók – Függvények
típusát • A programba közvetlenül beírt adat (konstans) típusát nem kell deklarálni, mert a fordító program az adat alakjáról felismeri a típusát.
7
Változók még egyszer • A változó az adat tárolására alkalmas memória hely, melynek van: – Azonosítója, neve – Értéke – Típusa
8
Egyszerű adatok • Számábrázolás
9
Mutatók A memóriában tárolt adatoknak mindig van címük. Azokat a változókat , melyek más adatok címét tartalmazzák mutatónak vagy pointer-nek nevezzük.
adat1
memória címe
adat2
adat3
mutató1
10
Adatszerkezetek • Egyszerű adatszerkezetek összeépítésével lehet létrehozni – Általában beépített adatszerkezet • Tömb • Halmaz • Rekord
– Implementált adatszerkezetek • • • • •
Sor (FIFO) Verem Lista Fa Gráf 11
Tömb • • • •
Azonos típusú adatokat tárolunk egymás után Tömböt alkotó adatok az elemek Az elemekre a tömb indexével hivatkozunk Deklaráció – Tömb elemeinek típusa – Tömb mérete
12
Tömb • Ha a tömbnek egy indexe van, akkor egy dimenziós tömb: vektor • Ha a tömbnek két indexe van, akkor két dimenziós tömb: mátrix • Index – egész számok sorozata nullától vagy egytől • Tárolás – sorfolytonosan, elemeket egymás után – Több dimenziós tömböket leképezzük egy dimenziós tömbre 13
Tömb tárolás a b c
A(1,1) A(1,2) A(1,3) A(2,1) A(2,2) A(2,3) A(3,1) A(3,2) A(3,3)
a
b
c
14
Tömbök feldolgozása • A tömbök feldolgozása szorosan összefügg a ciklusokkal • Tömb minden egyes elemét feldogozzuk – Számláló ciklus
• Tömb elemein valamilyen tulajdonság meglétét vizsgáljuk – Elől- vagy hátultesztelő ciklus
15
Halmaz • Halmaz elemei ugyanolyan típusúak • Egy elem csak egyszer fordulhat elő • Nem minden programozási nyelvben van ilyen típus
16
Rekord • • • •
Elemei különböző típusúak Egy rekord komponenseit mezőnek nevezzük Lehet fix és változó méretű Változó méret esetén – Egy mező értékétől függően a többi mező típusa vagy mérete is változhat
• Rekordokból is lehet tömböket definiálni
17
Jellemzők • Az eddigi adatszerkezetek a programozási nyelvekben általában megtalálhatók. • A további adatszerkezeteket a programozónak kell létrehoznia. • További adatszerkezetek alapja az egy-dimenziós tömb.
18
Sor • Az egymás után beírt adatokat a beírás sorrendjében vehetjük ki. • FIFO – First In First Out • Például: – Két nem egyforma sebességgel működő rendszer közötti adatátvitelt akarunk biztosítani, vagy – Adatok átadása nem folyamatos, pl. lökésszerű
19
Sor • Két alap utasítás van: – IN: egy elemet betesz a sorba • Ha megtelt a sor hibaüzenetet kell adni
– OUT: kiveszi a sor következő elemét • Ha a sor üres akkor is hibaüzenet, vagy • Olyan adatot adunk vissza ami nem fordulhat elő egyébként
20
Megvalósítás 1. • Egy dimenziós tömb: tomb • Egy mutató, mely megmutatja, hogy hol van a következő üres elem a tömbben: mutato – A mutató 0-től indul n-1 –ig (mint a C nyelvben)
21
Megvalósítás, IN függvény in be: adat ha mutato = n akkor ki: sor megtelt különben tomb[mutato] = adat mutato = mutato + 1 ki: érvényes elágazás vége függvény vége
O(1)
22
Megvalósítás, OUT függvény out O(n) ha mutató = 0 akkor ki: üres sor különben ki: tomb[0] /* első elem kivétele */ ciklus i = 2 … mutato tomb[i-1] = tomb[i] ciklus vége mutato = mutato - 1 elágazás vége függvény vége A ciklus lassítja a kivételt, a megvalósítás hátránya!!! 23
Működési példa 1. mutato 0
1
2
Inicializálás
mutato 0
5
1
2
IN(5)
24
Működési példa 2. mutato 0
1
2
IN(6)
5 6
mutato 0
6
1
2
OUT
5
25
Megvalósítás 2. • Egy dimenziós tömb: tomb • Két mutató – A mutató 0-tól indul n-1 –ig (mint a C nyelvben) – psorba: ahova a következő elemet be kell tenni – psorbol: ahonnan a következő elemet ki kell venni
– Ha bármelyik mutató túlmutat a tömb utolsó elemén akkor a mutatót a tömb első elemére irányítjuk.
26
Megvalósítás 2. • Normális esetben a két mutató nem mutathat ugyanoda • Mikor üres a sor? – Ha a psorba egyenlő a psorbol mutatóval.
• Mikor van tele egy sor? – Ha a a psorba utoléri a psorbol mutatót.
• Ugyanaz nem jelentheti mindkét eseményt!!!
27
Megvalósítás 2. • Tele sor jele ha: – psorbol = psorba+1
– Beírás utoléri a kivételt
psorba
...
• Üres sor jele ha:
psorbol
– psorba = psorbol+1
– Kivétel utoléri a beírást
psorbol
... psorba
28
Megvalósítás, IN psorba = 1 psorbol = 0
O(1)
függvény in be: adat ha (psorba+1) = psorbol akkor ki: tele van a sor, érvénytelen különben tomb[psorba] = adat psorba = psorba + 1 psorba ki: érvényes elágazás vége függvény vége psorbol
... 29
Megvalósítás, OUT függvény out ha (psorbol+1) = psorba akkor ki: üres sor különben psorbol = psorbol + 1 ki: tomb[psorbol] elágazás vége függvény vége
O(1)
psorba 1 psorbol
... 30
Megvalósítás 2. • „Végtelenítjük” a sort – Ha bármelyik mutató túlmutat a tömb utolsó elemén akkor a mutatót a tömb első elemére irányítjuk. – Maradék osztást használunk index
index mod 4
0
0
1
1
2
2
3
3
4
0
5
1
…
…
31
Megvalósítás, IN psorba = 1 psorbol = 0 függvény in be: adat ha ((psorba+1) mod n) = psorbol akkor ki: tele van a sor, érvénytelen különben tomb[psorba] = adat psorba = (psorba + 1) mod n ki: érvényes elágazás vége függvény vége 32
Megvalósítás, OUT függvény out ha ((psorbol+1) mod n) = psorba akkor ki: üres sor különben psorbol = (psorbol + 1) mod n ki: tomb[psorbol] elágazás vége függvény vége
33
Működési példa 1. psorba Inicializálás psorbol
psorba 1
IN(1)
psorbol
34
Működési példa 2. psorba 1
OUT
1
OUT
üres sor
psorbol
psorba 1 psorbol 35
Működési példa 3. psorba 0
1
2
3
IN(4)
1 4 psorbol
psorba 0
1
2
3
OUT
1 4
4
psorbol 36
Működési példa 4. psorba 0
1
2
3
1 4 3
IN(3) psorba = 3 + 1 mod 4 = 4 mod 4 = 0
psorbol psorba 0
1
2
3
5 1 4 3
IN(5)
psorbol 37
Működési példa 5. psorba 0
1
2
3
5 1 4 3
IN(6)
a sor tele
psorbol
38
Verem • • • •
Az utoljára bevitt adatot lehet először kivenni LIFO – Last In First Out Stack –nek is szokták nevezni Sok helyen használják – Operációs rendszerek – Függvények hívása
• Verem (véges) és verem mutató (stack pointer)
39
Verem műveletek • PUSH – Elem betétele – Ha tele a verem, hiba
• POP – Elem kivétele – Ha üres a verem, hiba
40
Megvalósítás, PUSH függvény PUSH be:adat ha verem_mutato = n akkor ki: tele van a verem különben verem[verem_mutato] = adat verem_mutato = verem_mutato + 1 elágazás vége függvény vége
41
Megvalósítás, POP függvény POP ha verem_mutato = 0 akkor ki: üres a verem különben verem_mutato = verem_mutato - 1 ki: verem[verem_mutato] elágazás vége függvény vége
42
Működési példa 1. Inicializálás
n=4
3 2 1
verem_mutato = 0
0
PUSH(112)
3 2
verem_mutato = 1
1 0
112 43
Működési példa 2. PUSH(33)
3
verem_mutato = 2
2 1 0
33 112
POP
3
33
2 1 0
33 112
verem_mutato = 1
44
Működési példa 3. 3
POP
112
POP
hiba
2 1 0
33 112
verem_mutato = 0
3 2 1 0
33 112
verem_mutato = 0
45
Postscript • Programozási nyelv, Adobe Systems Inc. – PDF elődje
• Stack alapú • Szótárakat (dictionary) használ • Interpreter alapú – Postscript interpreter értelmezi a programot
46
Postscript műveletek • Post-fix jelölés
Matematikai jelöles
– 6 33 add
6+33
• Az operandus PUSH-t jelent • A művelet kiveszi a stack-ből az értékeket, majd az eredményt visszateszi a stack-re 6
33
add
6
33 6
39
47
6+3/8 Post-fix jelöléssel: 3
8
div
6
add
3
8
div
6
add
3
8 3
0.375
6 0.375
6.375
48
6+3/8 Post-fix jelöléssel: 6
3
8
div
add
6
3
8
div
add
6
3 6
8 3 6
0.375 6
6.375
49
8–7*3 Két módszerrel: 8 7 3 mul sub 7 3 mul 8 exch sub 7 3 mul
8
exch
sub
21
8 21
21 8
-13
50
Példa program %!PS-Adobe-2.0 /inch {72 mul} def /wedge { newpath 0 0 moveto 1 0 translate 15 rotate 0 15 sin translate 0 0 15 sin -90 90 arc closepath } def gsave 4.25 inch 4.25 inch translate 1.75 inch 1.75 inch scale 0.02 setlinewidth 1 1 12 { 12 div setgray gsave wedge gsave fill grestore 0 setgray stroke grestore 30 rotate } for grestore showpage 51
Példa program eredménye
52
Láncolt lista • Akkor használjuk ha a már tárolt adatok közé kell beszúrni új adatokat vagy • A meglevő adatok közül kell törölni • Egy lista elem két mezőből áll: – A tárolandó adat – Egy mutató
• Mindig van egy lista fej – List első elemére mutat – Ha nincs elem, speciális elem: NIL 53
Egyirányú láncolt lista • A listában szereplő elemek láncot alkotnak • Lista utolsó eleme: a mutató NIL Példa lista: Üres lista: listafej
listafej
NIL
1.elem 2.elem 3.elem NIL
54
Egyirányú láncolt lista • A lista elemeit csak úgy érhetjük el, hogy a fejtől indulva végigmegyünk a lista elemein és minden elem feldolgozása után a következő elemre ugrunk. O(n) komplexitás • Egy elem egy rekord: – adat mező: maga a tárolandó adat – kovetkezo mező: a következő elem a listában
55
Lista bejárása, kiírása függvény lista_kiírása i = listafej ciklus iÆkovetkezo <> ki: iÆadat i = iÆkovetkezo ciklus vége függvény vége
NIL
Æ : rekordbeli mezőre hivatkozás 56
Elem keresése függvény keresés O(n) be: elem i = listafej ciklus (i <> NIL ÉS iÆadat <> elem) i = i Æ kovetkezo ciklus vége ha i <> NIL akkor ki: i különben ki: nem létezik a listában elágazás vége függvény vége 57
Elem beillesztése 1. függvény elem_beilleszt be:elem elemÆkovetkezo = listafejÆkovetkezo listafejÆkovetkezo = elem függvény vége listafej
elem
2.elem
1.elem 3.elem NIL
58
Elem beillesztése 2. elemÆkovetkezo = listafejÆkovetkezo
listafej
elem
2.elem
1.elem 3.elem NIL 59
Elem beillesztése 3. listafejÆkovetkezo = elem
listafej
elem
2.elem
1.elem 3.elem NIL 60
Elem törlése 1. függvény elem_torles O(n) be: elem elozo = NIL i = listafej ciklus (i <> NIL ÉS iÆadat <> elem) elozo = i i = i Æ kovetkezo ciklus vége ha i <> NIL akkor elozoÆkovetkezo = iÆkovetkezo elágazás vége függvény vége 61
Elem törlése 2. elem = 2. elem elozo
listafej
i 1.elem 2.elem 3.elem NIL
62
Elem törlése 3. elozoÆkovetkezo = iÆkovetkezo elozo
listafej
i 1.elem
Mi lesz ezzel? 2.elem 3.elem NIL
63
Lista kezelés •
Minden listakezelő rendszerben két listát tartunk 1. A foglalt elemek listája 2. A szabad elemek listája
•
Egy elem törlése azt jelenti, hogy a szabad listába tesszük át az elemet!!!
64
Lista kezelés 1. Szabad lista
Új lista F N
F
N 65
Lista kezelés, beillesztés 1. Szabad lista
Új lista F
F N
N 66
Lista kezelés, beillesztés 1., másképp Szabad lista
Új lista F
F
N
N 67
Lista kezelés, beillesztés 2. Szabad lista
Új lista F
F
N
N 68
Lista kezelés, beillesztés 3. Szabad lista
Új lista F
F
N
N 69
Lista kezelés, törlés 1. Szabad lista
Új lista F
F
N
N 70
Kétirányú lista listafej
Elejétől vagy végétől is be lehet járni a listát.
adat 1
Egyszerű a beillesztés a lista elejére vagy végére
NIL
adat 2
adat 3
NIL 71
Felhasznált irodalom • Vitéz András: Programozás alapjai, előadás vázlat, 2005 http://www.hit.bme.hu/~vitez • Fábián Zoltán: Adatszerkezetek és programozási tételek, 2005 • http://www.cs.princeton.edu/intocs/91float
72
