Bevezetés
Adatszerkezetek
Adatszerkezet – adatok rendszerének matematikai, logikai modellje – elég jó ahhoz, hogy tükrözze a valós kapcsolatokat – elég egyszerű a kezeléshez
Adatszerkezet típusok – Tömbök – lineáris egy vagy többdimenziós – Kapcsolt listák – a kapcsolati információ is adat – Gráf – adatpárok kapcsolattal – Fa – hurok nélküli gráf. – Verem – LIFO (Last In First Out) – Sor – FIFO (First In First Out). Műveletek – feldolgozási tevékenységek (algoritmusok) – Bejárás - az elemek elérése – Keresés - adott értéknek megfelelő elemek kiválasztása – Beszúrás - új adat beillesztése – Törlés - adatelem eltávolítása – Rendezés - elemeket logikai sorrendbe – Összeválogatás - különböző rendezett adathalmazokból új elemhalmaz kialakítása Bonyolultság – futási idő vagy helyigény az adatok számának függvényében – B(n) 1
1. Lineáris tömbök N db. azonos típusú adatelem – az elemekre egymást követő számokból álló indexhalmazzal hivatkozunk – az elemeket egymást követő memóriahelyek tárolják – az elemekhez bejárás nélkül férünk hozzá LB LB+1 Lower Bound
UB-1 UB Upper Bound
– Hosszúság (Length) L = UB-LB+1
Indexelt alak
Példa
– A1, A2 – A(1), A(2) – A[1], A[2] – DATA(1)=154 ; DATA(2)=52 ; DATA(3)=-33 ; DATA(4)=1 ; 154
52
-33
1
1.1 Hozzáférés tömbelemhez - indexelés 154 LOC(DATA)
52
-33
1
LOC(DATA(4)) 2
LOC(DATA(k))=LOC(DATA)+w*(k-LOC(DATA)) ; w az alapadat tárolási mérete
1.5 Rendezés Ha L n elemű lineáris tömb, akkor ez rendezett, ha L(1)< L(2)
k
hamis
k=k+1 hamis
p≤n-k
p=1
igaz
p=p+1
igaz
L(p)>L(p+1)
hamis
igaz
s=L(p) L(p)=L(p+1) L(p+1)=s Bonyolultság :
n⋅( n −1) = O( n2 ) 2
3
1.6 Keresés 1.6.1 Szekvenciális keresés KER-t keressük, az n elemű L elemei között, LOC a keresett pozíció L(K)≠KER
K=1
L(n+1)=KER
LOC=k
igaz
k=k+1
Bonyolultság : n + 1 = O( n )
hamis
1.6.2 Bináris keresés KER-t keressük, ha L sorbarendezett, Beg, End, Mid segédváltozók, LOC a keresett pozíció, INT az egészrész Beg=LB(L) End=UB(L) Mid=INT((Beg+End)/2) LOC=Mid igaz
igaz
End=Mid-1 Mid=INT(Beg+End)/2
Beg<End és L(Mid)≠KER
KER
hamis
igaz
L(Mid)=KER
hamis
LOC=Null
Beg=Mid+1
Bonyolultság :
hamis A legalább szükséges összehasonlítások száma f(n), Minden összehasonlításkor feleződik a minta
2
f(n)
>n ⇔
f ( n ) = log2 ( n ) + 1
4
2. Többdimenziós tömbök N*M db. azonos típusú adatelem – az elemekre egymást követő számokból álló indexhalmazokból alkotott számpárokkal hivatkozunk – az elemeket egymást követő memóriahelyek tárolják – az elemekhez bejárás nélkül férünk hozzá 1.1 Hozzáférés tömbelemhez - indexelés Kétdimenziós eset LBSOR1
LBSOR1+1
UBSOR1-1
LBSOR2
LBSOR2+1
UBSOR2-1 UBSOR2
LBSORn-1 LBSORn-1+1
UBSORn-1-1UBSORn-1
LBSORn
LBSORn+1
UBSOR1
UBSORn-1 UBSORn
Indexelt alak – A1,1, A12 – A(1,1), A(1,2) – A[1 ] [1], A[1 ] [2] Memória pozíció (A m*n-es mátrix) LOC(A(j,k))=LOC(A)+w*(n*(j-1)+(K-1)) ; w az alapadat tárolási mérete 5
3. Mutatók és mutatótömbök P változó mutató, ha egy egyszerű változó, vagy egy tömbelem memóriacímét tartalmazza. Általában dinamikus tárolásra használják – mutatókból is lehet tömböt szervezni, ezek mindegyik eleme mutató – például változó méretű adatsorok, szabálytalan tömbök tárolására használható LBSOR1
LBSOR1+1
LBSOR2
LBSOR2+1
UBSOR1-1
UBSOR1 UBSOR2-1 UBSOR2
LBSORn-1 LBSORn-1+1 UBSORn-1-1 UBSORn-1 LBSORn LBSOR1
LBSOR1+1
UBSORn
LBSORn+1 UBSOR1-1
UBSOR1
LBSORn-1 LBSORn-1+1 UBSORn-1-1 UBSORn-1
Sor1
S v
Sor2
S v
LBSOR2
LBSORn
LBSOR2+1
LBSORn+1
Sorn-1
UBSOR2-1 UBSOR2 UBSORn
S v
S v
Sor4
3.1 Példa – Mutató aritmetika 6 Ha P változó mutató, akkor a P+1 kifejezés a következő memóriacímet jelenti
3.2 Példa - Egy csoport elemeinek bejárása P sorelemre mutató segéd-pointer, az i. csoport címe Ci mutató, az (i+1). csoport címe Ci+1 P=Ci
hamis
P
„Bejárás”
igaz
4. Rekordok, rekordszerkezetek, állományok A rekord egymáshoz tartozó (a világ egy egyedére vonatkozó) adattételek (mezők, attribútumok) gyűjteménye. – az adattételek lehetnek összetettek** és tovább nem bonthatók egyszerűek* – például változó méretű adatsorok, szabálytalan tömbök tárolására használható
Az állomány rekordok összessége. LB Név SOR1
Testmagasság LB Lakcím** SOR1+1
Testsúly*
4.1 Szintszám, minősítés Az adattételek lehetnek összetettek, altételekkel. Például: Gyermek.Anya.Név Gyermek Név
Apa
Anya Név
Név
7
5. Kapcsolt listák A kapcsolt lista vagy egyirányú lista adatelemek, vagy csomópontok lineáris gyűjteménye, ahol az elemek sorrendjét mutatók rögzítik. Start
– a mutatókat tároló elemet kapcsolómezőnek hívjuk. ●
●
●
●
x
5.1 Kapcsolt listák a memóriában Minden csomóponthoz egy tömbelemet (INFO(k) az indexelt csomópont), Minden követőhöz egy másik tömbelemet (LINK(k)) rendelünk. Start
●
INFO (0,0)
LINK 3
(100,100)
4
(100,0)
2
(0,100)
5
(0,0)
x
5.2 Kapcsolt listák bejárása A PTR mutató az éppen feldolgozott csomópontra mutat. A kezdetet a START mutató jelöli. A vége NULL Hasonló mint a lineáris tömb.
8
PTR=START
PTR≠NULL PTR=LINK(PTR) {PTR}→ INFO feldolgozás
hamis
igaz
5.3 Keresés kapcsolt listában Ugyanaz mint lineáris esetben, csak az összehasonlítás és a léptetés elválik PTR≠NULL
PTR=START PTR=NULL LOC= {PTR}→
igaz
hamis
igaz
KER= {PTR}→INFO hamis
PTR=LINK(PTR)
9
5.4 Keresés rendezett listában Nem ugyanaz, mint lineáris esetben, mert nem tudjuk a középsőt PTR≠NULL
PTR=START PTR=LINK(PTR)
hamis
igaz
igaz
{PTR}→ INFO
igaz hamis
KER= {PTR}→ INFO PTR=LINK(PTR)
hamis
5.5 Beszúrás kapcsolt listába Start
●
●
●
●
x
●
●
●
x
Start
●
●
10
5.6 Törlés kapcsolt listából Start
●
●
●
●
x
●
●
●
x
Start
●
5.7 Kétirányú listák Minden irányban bejárható Első
●
Utolsó
INFO x ●
INFO
● ●
INFO
● ●
INFO ● x
●
5.8 Beszúrás kétirányú listába
Utolsó
Első
●
INFO x ● INFO
INFO
● ●
INFO
● ●
INFO ● x
●
● ●
5.9 Törlés kétirányú listából Első
●
Utolsó
INFO x ●
INFO
● ●
INFO
● ●
INFO ● x
● 11
6. Verem (Stack) Last In First Out Új elem behelyezése (PUSH) a tetejére (TOP) Elem leemelése (POP) 6.1 A verem tárolása a
c
b
6.1.1 PUSH igaz
d
TOP TOP=TOP+1 STACK(TOP)=Elem
maxstk
TOP<MAXSTK hamis
6.1.2 POP
túlcsordul
hamis Elem=STACK(TOP)
TOP=TOP-1
TOP=0 igaz
alulcsordul
12
6.2 Rekurzió 6.2.1. Faktoriális iteratív definíció n!=1˙2˙3…(n-2)˙(n-1)˙n hamis
Fakt=1
k<=n
k=1
N=0
Fakt=Fakt*k
igaz
Fakt=1
6.2.2. Faktoriális rekurzív definíció 0!=1 ; n!=n˙(n-1)! hamis
Fakt()=n*Fakt(n-1)
N=0
igaz
Fakt()=1
A verem és az alprogram kapcsolata
13
7. Sor (Queue) First In First Out
6.1 A sor Első
●
●
●
Windows multitasking
●
x Sor vége
Eszközök Nyomtató
Lemezek
Billentyûzet
Egér
Üzenetek Várakozó sor Rendszer
Alkalmazások Üzenetek
32 bites szál várakozó sor
32 bites szál várakozó sor
32 bites szál várakozó sor
16 bites alk. várakozó sor
elsõdleges
14
8. Bináris fa
Elemek véges halmaza, amely • vagy üres • vagy egyetlen T elemhez (gyökér) kapcsolt két diszjunkt T1 ésd T2 részfa alkotja A A – gyökér (szülő, apa) B D H
C E
F
G J
I K
R(A) - jobboldali részfa (C ,F ,G, I, J, K) L(A) – baloldali részfa (B, D, E, H) C – A jobboldali szukcesszora (gyermek, leszármazott) B – A baloldali szukcesszora Minden csomópontnak 0, 1, illetve 2 szukcesszora lehet Zárócsomópont - 0 szukcesszor Az összekötő vonalak - élek, 0 szukcesszor - levél utolsó él - ág Szintszám : gyökér -0 leszármazott - szülő+1 Generáció : azonos szintszámú elemek Mélység : az azonos ágon elhelyezkedő elemek maximális száma Teljes : az utolsó szintet kivéve a csp-k száma maximális
Kiterjesztett bináris fa – minden csomópontnak 0/2 gyermeke van
15
8.1 Bináris fák ábrázolása kapcsolt szerkezettel Root
● ● A ● ● B ● ● D x
x
● C ● E x
x
F x
x H x
● G ● I
x
J
x
●
x
K x
x
8.2 Bináris fák ábrázolása tömbökkel Root
L(Root) R(Root)
Avail
1
2
3
4
5
A
C
G
J
10
7
8
5
2
3
4
0
10
11
12
13
I
B
D
H
E
0
11
12
0
0
7
8
K
F
0
0
0
6
0
0
9
13
0
0
0
16
8.3 Bináris fák szekvenciális ábrázolása • a gyökér T(1) • ha egy csomópont a T(k)-n van, • akkor ha van L(T(k))=T(2*k) egyébként NULL • akkor ha van R(T(k))=T(2*k+1) egyébként NULL
A B D
1
2
3
4
5
6
7
8
A
B
C
D
E
F
G
NULL
9
10
C E
11
NULL NULL NULL
8.4 Bináris fák bejárása
12
F
G
13
14
NULL NULL
15
NULL NULL
A
Több lehetőség. Pl. • a G gyökér • Az L(G) bejárása az irányítás szerint, • Az R(G) bejárása az irányítás szerint,
B D H
C E
F
G J
I K
17
6.4.1. Pl. az irányítással megegyező bejárás NULL a STACK-en PTR a gyökéren Ameddig a PTR=NULL az összes L() feldolgozása az összes R() a STACK-re PTR=L(PTR) – léptetés TOP=1 A PTR=STACK legfelső elemével (ha nem NULL, R feldolgozás) STACK(TOP)=NULL PTR=Gyökér
PTR≠NULL
STACK(TOP)=R(PTR)
TOP=TOP+1 hamis
igaz igaz
R(PTR) ≠NULL
ADAT(PTR) feldolgozás A
PTR=L(PTR)
ADAT(PTR) feldolgozás
B
igaz D
L(PTR) ≠NULL
TOP=TOP-1
PTR=STACK(TOP)
hamis
H
C E
F
G J
I K
18
hamis
9. Általános fa
Elemek véges halmaza (T), amely • Tartalmaz egy kitüntetett R gyökérelemet • A többi elem nem nulla diszjunkt részfája T-nek A B E J
F
C
D
G
H
I
K L
9.1 Tárolás számítógépen INFO(k) - az elem adatai GYERMEK(k) - az első gyermek TESTVÉR(k) - az első testvér 1 2 3 4 5 6
7
8
9
10
11
12
13
INFO
A
B
C
D
E
F
G
H
I
J
K
L
TESTVÉR
0
3
5
0
7
8
0
10
0
12
13
0
GYERMEK
2
6
0
9
11
0
0
0
0
0
0
0
19
10. Gráf
Két halmazzal jellemezhető adatszerkezet • Csomópontok sorszámozott halmaza (csúcsok) • Az elemeket összekötő e=[u,v] számpárral jellemzett élek halmaza • az összekötött csomópontokat szomszédoknak hívjuk • deg(u) a csomópont foka, a befutó élek száma • deg(u)=0 izolált csomópont v0-ból vn-be haladó élek halmazát P(v0, v1, …v0) útnak nevezzük. P út zárt, ha v0=vn P út egyszerű, ha minden pontja különböző Kör a 3-nál hosszabb egyszerű zárt út. Összefüggő egy gráf, ha bármely két pontja között létezik út. Egy G gráf akkor és csak akkor összefüggő, ha bármely két pontja között létezik egyszerű út. Egy gráf teljes, ha minden csomópontja minden csomópontjával össze van kötve. A fa köröket nem tartalmazó összefüggő gráf G gráf címkézett, ha éleihez adatokat rendelünk. Ha G gráf éleihez rendelt adatok nem negatívak, akkor a gráfot súlyozottnak hívjuk. 20 G gráf irányított, ha az éleknek irányítottságuk van
10.1 Szekvenciális tárolás számítógépen Szomszédsági mátrix A ai,j=1 – ha i-ből j felé halad él A ai,j=0 – egyébként
A
B
C
D
0
1
1
0
B
0
0
0
0
C
0
0
0
1
D
0
0
0
0
A C
B D
Ha A a G gráf szomszédsági mátrixa, akkor Ak mátrix i,j. eleme az i-ből j-be vezető K hosszú utak számát adja. A2 A B C D A
0
0
0
1
B
0
0
0
0
C
0
0
0
0
D
0
0
0
0
Útmátrix pi,j=1 – ha i-ből j felé halad valamilyen út ai,j=0 - egyébként
Egy m pontból álló irányított gráf útmátrixának pij tagja akkor és csak akkor 1, ha a A+A2+….+Am mátrix i,j. eleme nem 0. 21
10.2 Kacsolt szerkezetes tárolás Pontlista
(0,0)
(40,0)
(40,20)
(0,20)
(0,20)
(40,20)
(0,0)
(40,0)
Éllista
22
