Adatszerkezetek Listák Dr. Iványi Péter
1
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 elemre mutat: NIL 2
Egyirányú láncolt lista • A listában szereplő elemek láncot alkotnak • Lista utolsó eleme: a mutató NIL Példa lista: listafej
Üres lista: listafej NIL
1.elem 2.elem 3.elem NIL
3
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 adat
kovetkezo 4
Lista bejárása, kiírása függvény lista_kiírása i = listafej ciklus i <> NIL ki: iàadat i = iàkovetkezo ciklus vége függvény vége
à : rekordbeli mezőre hivatkozás 5
Lista kiírása 1. Kiírás:
i = listafej
1. Elem
1.elem 2.elem 3.elem NIL
6
Lista kiírása 2. Kiírás:
listafej i
1. Elem 2. Elem
1.elem 2.elem 3.elem NIL
7
Lista kiírása 3. Kiírás:
listafej
1. Elem 2. Elem 3. Elem
1.elem 2.elem
3.elem NIL i 8
Lista kiírása 4. Kiírás:
listafej
1. Elem 2. Elem 3. Elem
1.elem 2.elem
3.elem NIL i
NIL 9
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
10
Elem beillesztése 2. elemàkovetkezo = listafejàkovetkezo
listafej
elem
2.elem
1.elem 3.elem NIL 11
Elem beillesztése 3. listafejàkovetkezo = elem
listafej
elem
2.elem
1.elem 3.elem NIL 12
Elem beillesztése 4. listafej
2.elem
1.elem 3.elem NIL 13
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 14
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 15
Elem törlése 2. elem = 2. elem elozo
listafej
i 1.elem 2.elem 3.elem NIL
16
Elem törlése 3. elozoàkovetkezo = iàkovetkezo elozo
listafej
i 1.elem
Mi lesz ezzel? 2.elem 3.elem NIL
17
Lista kezelés •
A listakezelő rendszerben általában 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!!!
18
Lista kezelés 1. Szabad lista
Új lista F N
F
N 19
Lista kezelés, beillesztés 1. Szabad lista
Új lista F
F N
N 20
Lista kezelés, beillesztés 1., másképp Szabad lista
Új lista F
F
N
N 21
Lista kezelés, beillesztés 2. Szabad lista
Új lista F
F
N
N 22
Lista kezelés, beillesztés 3. Szabad lista
Új lista F
F
N
N 23
Lista kezelés, törlés 1. Szabad lista
Új lista F
F
N
N 24
Listák és tömbök • Tömb: véletlen elérés (random access) • Lista: Szekvenciális elérés
Művelet Tömb Beillesztés O(n) Törlés a végéről O(1)
Lista O(1) O(n)
25
Listák és tömbök • Josephus probléma (demonstrálja a különbséget) – Flavius Josephus – Első századbeli történész – Ő és 40 ember egy barlangban ragadt, rómaiak által körülvéve – Az öngyilkosságot választották a fogság helyett – Kiválasztják ki öl meg kit – Josephus és még egy ember maradt meg • Josephus rávette a másikat hogy adják meg magukat
26
Josephus probléma • Választási probléma – – – –
n darab ember körbe áll „Valahol” elkezdve a k-adik embert kivégzik Ezután a k-1 -edik embert végzik ki Stb
27
Listák és tömbök • Az emberek a lista csomópontjai – Mutatja, hogy milyen könnyű egy elemet „törölni” – Mennyire nehéz egy elemet megtalálni, • végig kell menni a többi elemen
• Tömb esetén – Nehéz törölni • A többi elemet „előre kell tolni”
– Könnyű az n-edik elemet megtalálni • Csak a pozíció indexét kell használni
28
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 29
Körkörös listák listafej
1.elem 3.elem 2.elem
30
Körkörös listák listafej 1.elem
2.elem
3.elem
31
Lista mutató nélkül • Nem minden nyelv támogatja a mutatókat • Tömböt is használhatunk „szimulációként” • A tömb minden eleme egy rekord record Entry { integer next; // a következő elem integer prev; // az előző elem string name; real balance; }
32
Lista mutató nélkül Index 0 1 2 (fej) 3 4 5 6
Next 1 -1 4
Prev 4 0 -1
0
2
Name Balance Kovács I. 111 Kiss B. 2341 Nagy S. 34 Horváth E. 745 Lovas G. 9657
3., 5., 6. elemek nem részei a listának Szabad elemek indexeiből egy másik tömböt lehet csinálni 33
Lista nyomtatása függvény lista_kiírása i = fej ciklus i > 0 ki: i, tomb[i].Name, tomb[i].Balance i = tomb[i].Next ciklus vége függvény vége
34
Külső-belső adatok • Egy lista elem két mezőből áll: – A tárolandó adat – Egy mutató
• A kérdés, hogy az adatot az elemben vagy azon kívűl tároljuk?? – Internal storage – External storage
35
Belső adatok listafej
1.elem 2.elem
NIL
36
Belső adatok • • • •
Az adatelérés hatékonyabb Egyszerűbb memória kezelés Kevesebb memória foglalásra van szükség A csomóponttal egy időben végezzük az adatok lefoglalását
37
Külső adatok listafej
NIL
1.elem 2.elem
38
Külső adatok • Általánosabb – Ugyanaz az adatszerkezetet lehet használni különböző adatokkal
• Bonyolultabb memória kezelést igényel
39
Adatok keresése • Általános esetben a keresés: O(n) • Hogyan lehet hatékonyabbá tenni? – Sorba rendezett lista – „Move-to-front” heurisztika • A megtalált elemet a lista elejére helyezzük • A legutoljára használt elemet lehet a leggyorsabban megtalálni
– Más adatszerkezetet használunk az „indexelésnél”, melyben könnyebb keresni: • Fák • Hasító táblák 40
Alkalmazás • A LISP és Scheme nyelveknél az alap adatszerkezet az egyirányú lista – Funckionális nyelvek – A listát „csomópontokból” építjük fel – Egy csomópontnak két része van • car: a csomópont adatszerkezete • cdr: mutató a következő elemre
41
Programozási nyelvek osztályozása • Procedurális nyelvek – Kifejezések sorozatát hajtjuk végre mely valamilyen eredményhez vezet – Változókat, ciklusokat használunk – Program állapotok
• Funkcionális nyelvek – – – –
Nem igazán használunk tárolt állapotokat Nem ciklusokat hanem rekurziót használunk Függvényeket hívunk és a visszatérési értékeket használunk Változók módosítása mellékhatás!
42
Lisp programozási nyelv • Kifejlesztése: 1960-ban, John McCarthy, Massachusetts Institut of Technology • LISt Processing – Lista feldolgozás • Fortran –nal egyidős • Szakértői rendszerekben, mesterséges intelligencia kutatásban használj(t)ák • „Programozható programnyelv”-ként is szokták definiálni 43
Lisp és a grafikus rendszerek • Objektum modellező és CAD rendszerek – Allegro Solid + Common Lisp – ACIS + Scheme – AutoCAD + AutoLisp
• Repülőgépjegy foglalási rendszer • Üzleti döntéshozó rendszerek
44
ABUSE játék
45
Mesterséges intelligencia • Tudás reprezentálás • Harold Cohen művész programja: AARON
46
AutoCAD „programozása” • AutoCAD egy alap CAD rendszer • A CAD rendszer szinte minden aspektusa módosítható – – – – – –
ActiveX Visual Basic AutoLisp és Visual Lisp ObjectARX Menük módosítása DIESEL – szöveg processzálás, pl. státusz sor 47
ObjectARX void chngAtt() { ads_name entres; ads_point ptres; AcDbObjectId _Id, _attId; AcDbObjectIterator *pIttr = NULL; if(acedEntSel("Select a Block Reference", entres, ptres) != RTNORM ) { //Selection failed return; } acdbGetObjectId(_Id, entres); AcDbObjectPointer pRef(_Id,AcDb::kForRead); if(pRef.openStatus()!=Acad::eOk) { //Open failed return; } 48
ObjectARX pIttr = pRef->attributeIterator(); while(!pIttr->done()) { _attId = pIttr->objectId(); AcDbObjectPointer pAtt(_attId,AcDb::kForWrite); if(pAtt.openStatus()==Acad::eOk) { pAtt->setTextString("We changed this"); break; } pIttr->step(); } delete pIttr; }
49
Visual Basic Option Explicit Sub chngAtt() Dim objEnt As AcadObject Dim objRef As AcadBlockReference Dim varAtts As Variant Dim objAtt As AcadAttributeReference Dim emptyPt As Variant ThisDrawing.Utility.GetEntity objEnt, emptyPt, "Select Block: „ If objEnt.ObjectName = "AcDbBlockReference" Then Set objRef = objEnt If objRef.HasAttributes Then varAtts = objRef.GetAttributes Set objAtt = varAtts(0) objAtt.TextString = "We changed this" End If End If End Sub
50
AutoLisp (defun C:chngAtt (/ Mainent entList entAtt entNewAttVal) (setq Mainent (entsel)) (setq entList (entget (car Mainent))) (setq entAtt (entget (entnext (cdr (assoc -1 entList))))) (setq entNewAttVal (subst (cons 1 "We changed this") (assoc 1 entAtt) entAtt) ) (entmod entNewAttVal) (entupd (car Mainent)) (princ) )
51
Lisp • Language of Infinite Stupid Parantheses
(megszámlálhatatlan ostoba zárójelek nyelve)
; megjegyzés (elem1 (elem2 (elem3 elem4) (elem5 ‘(elem6 . elem7)) ) ) 52
Lisp alapelemek • A nyelv programok és adatok leírására egyetlen szerkezetet használ, a John Carthy által kidolgozott szimbólikus kifejezéseket, Skifejezéseket.
53
Lisp alapelemek • Alapelemek: – Listák • Atomok sorozata zárójelek között
– Atomok • Definíció: – „minden ami nem lista”, – a nyelv eszközeivel nem bontható tovább
• Konstans atomok • Szimbólikus atomok
54
Kiértékelés • • • •
LISP = Lista feldolgozás Feldolgozás folyamata = kiértékelés AutoLISP egy interpretált nyelv Interpreter szíve az evaluator = kiértékelő, értelmező • A felhasználó interaktív módon párbeszédet folytat az értelmezőprogrammal.
55
Kiértékelési ciklus 1. Az értelmező program beolvas egy S-kifejezést 2. A kifejezést kiértékeli • • •
meghatározza a kifejezés értékét mintha függvény lenne lehetnek mellékhatások
3. A kifejezés értékét kiírja, majd kezdi az 1. ponttól
56
Kiértékelési ciklus • A három lépésnek megfelel egy-egy LISP függvény: READ, EVAL, PRINT • Ezért nevezik ezt a végtelen ciklust: – read-eval-print ciklusnak
57
Kiértékelés sorrendje 1. Konstans atom értéke: maga az atom 2. Szimbólikus atom értéke: a szimbólumhoz rendelt értéke 3. Lista esetén függvényként értékeli ki
58
Lisp függvények • A függvények általános formája: (művelet A ... B)
így sohasem kérdés hogy melyik művelet hajtódik végre először • Ellentétben a matematikai kifejezéssel: 3 + 5 * 4
• amit csak megfelelő gyakorlás után tudunk megoldani: először a szorzást majd az összeadást hajtjuk végre 59
Kezdjünk el programozni! • Az egyik legegyszerűbb számítógép a zsebkalkulátor • Egyszerű számítási műveletek: • • • • • •
(+ (+ (+ ((* (/
5 5) -5 5) 5 -5) 5 5) 3 4) 8 12) 60
Függvény lista kiértékelése • A kiértékelés balról jobbra történik • Először az argumentumokat értékeli ki, majd a teljes kifejezést • A kiértékelés eredménye is egy kifejezés: atom vagy lista !!! • Mivel az adat lista és a függvény lista „azonos” ezért megvalósítja a Neumann elvet: adat és program nem különböztethető meg 61
Műveletek egymásba ágyazása • Egy művelet argumentuma lehet szám vagy egy másik művelet. • Egymásba ágyazás esetén először a legbelső zárójel közötti részt redukáljuk számmá, majd a követkető szintet és így tovább.
62
Példa (* (+ 2 2) (/ (* (+ 3 5) (/ 30 10)) 2))
= (* 4 (/ (* 8 3) 2))
= (* 4 (/ 24 2)) = (* 4 12) = 48 63
Infixből Postfixbe konverzió Infix A*B+C A+B*C A*(B+C) (A+B)*C
Postfix AB*C+ ABC*+ ABC+* AB+C*
64
A*B+C vége OpStack
Postfix
NIL
NIL
65
A OpStack
NIL
Postfix
a
NIL
66
* OpStack
*
Postfix
a
NIL
NIL
67
B OpStack
Postfix
a
*
b
NIL
NIL
68
1. + OpStack
Postfix
a
*
b
NIL
NIL
69
2. + OpStack
NIL
Postfix
a
b
*
NIL
70
3. + OpStack
Postfix
a
+
b
NIL
*
NIL
71
C OpStack
Postfix
a
+
b
NIL
*
c
NIL 72
1. vége OpStack
Postfix
a
+
b
NIL
*
c
NIL 73
2. vége OpStack
a
Postfix
b
NIL
*
c
+ NIL
74
A*B+C OpStack
a
Postfix
b
NIL
*
c
+ NIL
75
Házi feladat • Írjunk programot mely megfordítja az elemek sorrendjét. • Írjunk programot amely megszámolja a listában előforduló elemek számát!
76
