A szekvenciális adatszerkezet olyan rendezett pár amelynél az R reláció tranzitív lezártja teljes rendezési reláció. Szekvenciális adatszerkezetben az egyes adatelemek egymás után helyezkednek el, van egy logikai sorrendjük. Az adatok között egy-egy jellegű a kapcsolat: minden adatelem csak egy helyről érhető el és az adott elemtől csak egy másik látható. Két kitüntetett elem: az első és az utolsó. 2
Intuitív ADT és ADS szint:
Ez egy homogén adatszerkezet, azaz azonos típusú véges adatelemek sorozata. Jelölése : L=(a1, a2, ... an ) Ha n=0, akkor L=() az üres lista. A láncolt lista olyan adatszerkezet, amelynek minden eleme tartalmaz egy (vagy több) mutatót (hivatkozást) egy másik, ugyanolyan típusú adatelemre. A lánc első elemének a címét a lista feje tartalmazza. A listafej nem tartalmaz információs részt. A lánc végét az jelzi, hogy az utolsó elemben a rákövetkező elem mutatója üres.
Végigmehetünk az elemeken egymás után. Lehetőség van a módosítás, törlés, beszúrás műveletekre.
3
Az adatok száma nem ismert előre. Nem tudunk, vagy nem akarunk feleslegesen helyet foglalni az adatoknak. A feladat dinamikusan változik.
Statikus ábrázolás: tömbben, a logikai sorrendet indexek mutatják, a szabad helyek is listában. L: 2
SZH: 5
23 10 4
7
1
17 0
2
3
0
4
28 6
5
8
1
9
10 3
6
7
8
9 10
4
5
6
1
Egyirányú láncolt lista fejelem nélkül:
Mutató által mutatott objektum t mu
L: NIL
at ó fejelemmel: fejelem mindig létezik, ha üres a lista, akkor is. L:
FEJ NIL
Mindig van egy aktuális elemre mutató is. 7
8
A lista eleme Kétirányú láncolt lista
NIL
L: NIL
NIL
mutató rész
adat rész 9
10
üres listát ad vissza:
A Lista típus komponensei: – L - a lista első elemének mutatója, – akt - a lista aktuális elemének mutatója, – hiba – jelzi, hogy volt-e hiba az utolsó műveletnél
Create
Filozófia: nem kell „bolondbiztos” program, a programozó nem felhasználó, nem csinál hibát (!?), de lekérdezi, hogy van-e hiba.
L ← NIL akt ← NIL hiba ← false
11
12
2
logikai értéket ad vissza:
logikai értéket ad vissza:
IsEmpty
Error
hiba?
return (L = NIL)
hiba ← false return true
A lekérdezés után hamisra vált.
return false
13
L:
14
L: NIL
NIL
akt:
akt:
15
16
üres lista esetén hiba L:
First
NIL
akt:
L≠NIL? akt ← L hiba ← false
hiba ← true
17
18
3
a lista utolsó elemére kiadott Next hatása akt=NIL lesz L:
Next
NIL
akt:
akt ≠NIL? akt← (akt→mut) hiba ← true hiba ← false
19
Logikai értéket ad vissza:
20
Logikai értéket ad vissza:
IsEndOfList
IsLast
return (akt = NIL)
return (akt ≠ NIL ∧ akt→mut =NIL)
21
Aktuális elem értékét x-ben adja:
Aktuális elem módosítása e-re:
GetValue
SetValue
akt ≠ NIL? x← (akt→adat) hiba ← false
22
akt ≠NIL? (akt→adat) ← e hiba ← false
hiba ← true
23
hiba ← true
24
4
Listaelem létrehozása: NIL
NIL
p: 0 1
NIL
Node típus
1
Deklarálás
2
Létrehozás
0
NIL
Node
Deklarálás
p: Nodep
Jelölés: new (p) 25
26
u:
v:
NIL
p:
0
NIL
NIL
Node
e
p: Az elemet nekünk kell „befűzni” a listába
3
3
Node
Az elemet nekünk kell „befűzni” a listába
27
„e” adatelem beszúrása első elemként
Beszúrás első elemként • Üres és nem üres listára is működik. L: p:
2
28
3
InsertFirst
• Első elem lesz az aktuális.
New(p) (p→adat) ← e (p→mut) ← L L ←p akt ←L hiba ← false
1
29
• Üres és nem üres listára is működik. • Első elem lesz az aktuális.
30
5
InsertLast
Beszúrás utolsó elemként
new(p); (p
L:
2
p:
4
3
u← L; v← (L L←p akt ← L
• Utolsó elem lesz az aktuális.
NIL
L=NIL
Beszúrás üres listába
• Üres és nem üres listára is működik.
→adat) ← e; (p→mut) ← NIL →mut)
v ≠ NIL u ← v; v ←(v
NIL
(u
→mut);
→mut) ← p; akt←p
31
32
InsertLast
new(p); (p
→adat) ← e; (p→mut) ← NIL
Aktuális elem után:
L=NIL
u← L; v← (L L←p akt ← L
→mut) L:
u ← v; v ←(v
Beszúrás nem üres listába utolsóként
akt:
v ≠ NIL
(u
→mut);
1
2 p:
→mut) ← p; akt←p
4
3
33
Aktuális elem után: Ha nincs aktuális elem, az hiba. Az aktuális elem a beszúrt lesz.
34
Aktuális elem elé:
InsertAfter akt ≠NIL?
akt: 1
2 p:
4 e
→ → →
hiba ← false
→
hiba ← true
L:
new(p); (p adat) ← e; (p mut) ← (akt mut) (akt mut)← p akt ← p
L:
1 p:
35
u
akt:
2
4
3
36
6
InsertBefore
Beszúrás aktuális elem elé
akt=NIL
Aktuális elem törlése
→adat) ← e; u← L; v← (L→mut)
p:
new(p); (p
H i b a ← t r u e
L:
v ≠ akt
Akt: u ← v; v ←(v
(u
→mut);
Hiba:
„Beállunk” az aktuális elem elé.
→mut) ← p; (p→mut) ← akt; akt←p; hiba:=false
37
38
p:
p:
L:
L:
Akt:
Akt:
Hiba:
Hiba: „átláncoljuk”
kitöröljük
39
RemoveAkt
Aktuális elem törlése:
p:
akt ≠NIL?
Első elem törlése
Akt: False „átláncoljuk”
p ←L L ← (L mut) akt ← L felszab(p) hiba ←false
p ←L
→
→
p mut ≠akt p ← (p mut)
→ →mut) ← (akt→mut ) felszab(akt) akt ←(p→mut )
hiba ← true
akt = L?
L:
Hiba:
40
(p
hiba ←false
41
42
7
RemoveAkt
Aktuális elem törlése:
Megjegyzések:
akt ≠NIL?
p ←L L ← (L mut) akt ← L felszab(p) hiba ←false
p ←L
→
→
(p mut) ≠akt p ← (p mut)
→ →mut) ← (akt→mut ) felszab(akt) akt ←(p→mut )
hiba ← true
akt = L?
Nem első elem törlése
– Lehetne az is, hogy az akt nem változik. – Lehetnének továbi műveletek is, pl. Teljes lista törlése Listák összefűzése, Elemszám, stb.
– Nem hatékony a megvalósítás:
(p
Last, Remove, InsertBefore, InsertLast
– Hatékonnyá tehető pl.: kétirányú láncolással
hiba ←false
43
44
lista.Empty for i=1 to n A[i] > 0 ?
Adott az A[1..n] egészeket tartalmazó tömb. Helyezzük el a pozitív elemeit rendezett módon egy listába!
lista.IsEmpty lista. I n s e r t F i r s t (A[i])
lista.First; a ← lista.GetValue ¬ lista.IsLast ∧ A[i] > a
S K I P
lista.Next a ← lista.GetValue A[i] ≤ a lista.InsertBefore(A[i]) lista.InsertLast(A[i])
45
46
lista.Empty
lista.Empty
for i=1 to n
for i=1 to n A[i] > 0 ?
A[i] > 0 ?
lista.IsEmpty lista. I n s e r t F i r s t (A[i])
lista.First; a ← lista.GetValue ¬ lista.IsLast ∧ A[i] > a
lista.IsEmpty S K I P
lista. I n s e r t F i r s t (A[i])
lista.Next a ← lista.GetValue A[i] ≤ a lista.InsertBefore(A[i]) lista.InsertLast(A[i]) 47
lista.First; a ← lista.GetValue ¬ lista.IsLast ∧ A[i] > a
S K I P
lista.Next a ← lista.GetValue A[i] ≤ a lista.InsertBefore(A[i]) lista.InsertLast(A[i]) 48
8
lista.Empty
lista.Empty
for i=1 to n
for i=1 to n A[i] > 0 ?
A[i] > 0 ?
lista.IsEmpty lista. I n s e r t F i r s t (A[i])
lista.First; a ← lista.GetValue ¬ lista.IsLast ∧ A[i] > a
lista.IsEmpty S K I P
lista. I n s e r t F i r s t (A[i])
lista.Next a ← lista.GetValue A[i] ≤ a lista.InsertBefore(A[i]) lista.InsertLast(A[i])
lista.First; a ← lista.GetValue ¬ lista.IsLast ∧ A[i] > a
S K I P
lista.Next a ← lista.GetValue A[i] ≤ a lista.InsertBefore(A[i]) lista.InsertLast(A[i])
49
50
lista.Empty
lista.Empty
for i=1 to n
for i=1 to n A[i] > 0 ?
A[i] > 0 ?
lista.IsEmpty lista. I n s e r t F i r s t (A[i])
lista.First; a ← lista.GetValue ¬ lista.IsLast ∧ A[i] > a
lista.IsEmpty S K I P
lista. I n s e r t F i r s t (A[i])
lista.Next a ← lista.GetValue A[i] ≤ a lista.InsertBefore(A[i]) lista.InsertLast(A[i]) 51
lista.First; a ← lista.GetValue ¬ lista.IsLast ∧ A[i] > a
S K I P
lista.Next a ← lista.GetValue A[i] ≤ a lista.InsertBefore(A[i]) lista.InsertLast(A[i]) 52
