2008 tavasz

Láncolt listák [email protected] PPT 2007/2008 tavasz http://nik.bmf.hu/ppt 1

Témakörök Láncolt listák elvi felépítése Egyirányú egyszerű láncolt lista Egyirányú rendezett láncolt lista Láncolt lista strázsa elemekkel Speciális láncolt listák Implementációs lehetőségek

2

Adatszerkezetek • Adatszerkezet: Az adatelemek egy olyan véges halmaza, amelyben az adatelemek között szerkezeti összefüggések vannak • Tárgyalandó megvalósítások – – – – –

Tömb Láncolt lista Fa, kupac Gráf Hasító táblázat

• Egyéb szerkezetek – Sor – Verem

3

Szükséges alapfogalmak • Előzőleg már megismert fogalmak – – – – – – –

Változó, típus Összetett típus Generikus típusok Osztály, objektum Mutató, referencia Memóriakezelés Rekurzió

• Már megismert adatszerkezetek – Tömbök – Többdimenziós tömbök

4

Lista alapfogalmak • Lista (list): 0 vagy több elem véges sorozata • Ha az elemek mindegyikének azonos a típusa: T, akkor azt mondjuk, hogy a lista típusa: T-k listája • A lista (a1, a2, … , an), ahol ai a lista elemei • Példák listára – – – –

(2, 3, 5, 7, 11, 13, 17, 19) (hélium, neon, argon, krypton, xenon, radon) szövegsor: a felépítő karakterek az elemek dokumentum: szövegsorok a listaelemek

• Lista hossza: az elemek előfordulási száma a listában (az ismétlődéseket is belevesszük) • Üres lista (empty): ha a lista hossza 0, (jele: ε)

5

Lista alapfogalmak • Részlista (sublist): L = (a1, a2, … , an) lista, akkor minden i-re, j-re 1 ≤ i ≤ j ≤ n (ai, ai+1, … , aj). L és ε minden listának részlistája • Részsorozat (subsequence): Egy L = (a1, a2, … , an) listából kapjuk, ha 0, vagy több elemet elhagyunk a listából. A megmaradt elemeknek ugyanolyan sorrendben kell a részsorozatban szerepelniük. L és ε minden listának részsorozata • Előtag, utótag (prefix, suffix): az előtag olyan részlista, ami az első elemmel, az utótag az utolsó elemmel végződik. ε minden listának előtagja és utótagja • Elem pozíciója: hányadik helyen szerepel a listában, használjuk az előző, a következő jelzőket is 6

Láncolt lista definíció • Láncolt lista: A láncolt lista olyan adatszerkezet, amelynek minden eleme tartalmaz egy hivatkozást egy másik, ugyanolyan típusú elemre. • Tárgyalt altípusok: – – – –

Egyszeresen láncolt lista Rendezett láncolt lista Láncolt lista strázsa elemekkel Speciális láncolt listák • Kétirányú • Többszörösen láncolt • Ciklikus

7

Láncolt lista eleme • A láncolt lista egy elemének a definíciója: TLáncElem = Struktúra(tartalom, következő) • Tartalom (példákban tart): a tárolandó adat – egyszerű típus – összetett típus – objektum referencia

• Következő (példákban köv): hivatkozás a láncolt lista következő elemére – tömb index – mutató (TLáncElem típusú) – objektum referencia

• A lista műveleteit megvalósító algoritmusok a konkrét implementációtól függetlenek, ezért ezzel a későbbiekben nem is foglalkozunk 8

Egyirányú láncolt lista jellemzői fej

1

2

fej

1

2

3 ∅

∅

3

• A lánc minden eleme tartalmaz egy hivatkozást a következő elemre • A lánc első elemének címét a listafej tartalmazza (példákban fej változó) • A listafej nem tartalmaz tartalmi részt • A lánc végét az utolsó elem következő részének egy kitüntetett értéke jelzi (példákban ∅) Ennek valódi értéke implementációtól függ • Üres listánál a listafej értéke ez a kitüntetett érték 9

Miért használjuk? A tömb adatszerkezet hátrányai, amelyek miatt érdemes lehet listát használni: 1. 2. 3. 4.

Méret nem változtatható (dinamikus tömbök?) Összefüggő memóriaterületet igényel Beszúrás nehézkes Törlés nehézkes

A 3 4 2 8 9 7 1 1

10

Miért ne használjuk? A lista adatszerkezet hátrányai, amelyek miatt érdemes lehet tömböt használni: 1. 2. 3. 4.

Bonyolult (használata nehézkes, hibalehetőség) Elemek nem érhetőek el közvetlenül indexeléssel A 2. miatt a keresés nehezen gyorsítható, alapesetben csak a lineáris keresés használható A következő elemre való hivatkozás eltárolása miatt nagyobb egy elem helyfoglalása

11


12

Láncolt lista bejárása • Bejárás: Az adatszerkezet valamennyi elemének egyszeri elérése (feldolgozása) • Ez a feldolgozás lehet tetszőleges művelet a lista egy elemének a tartalmával. A teljes listára vonatkozó műveleteket így az egyes elemekre külön-külön elvégezhető műveletek sorozatára kell bontani (pl átlagszámítás: összegzés, megszámlálás) • Bejárás algoritmusa Eljárás Bejárás(fej) p ← fej Ciklus amíg p ≠ ∅ Feldolgozás(p.tart) p ← p.köv Ciklus vége Eljárás vége

(Vizsgálandó esetek: üres lista, nem üres lista)

13

Keresés a listában • Keresés: A lista fej ismeretében egy megadott tartalmú elem megkeresése – eldönteni, hogy van-e ilyen tartalmú elem – ha van, akkor melyik ez az elem Függvény Keresés(fej, mitkeres) p ← fej Ciklus amíg (p ≠ ∅) és (p.tart ≠ mitkeres) p ← p.köv Ciklus vége van ← (p ≠ ∅) Ha van akkor Keresés ← p Függvény vége

(Vizsgálandó esetek: üres lista, nincs ilyen elem, van ilyen elem) 14

Házi feladat – prog. tételek listával • Sorozatszámítás – lista elemeinek összege – lista elemeinek átlaga – stb.

• Eldöntés – adott tulajdonságú elem megtalálható a listában?

• Kiválasztás – megadott elem kiválasztása a listából?

• Keresés – lineáris keresés

• Megszámolás – megadott tulajdonságú elemek megszámolása

• Maximumkiválasztás – valamilyen szempont szerinti legnagyobb elem kiválasztása 15

Új elem felvétele • Lista inicializálása Eljárás Inicializálás(fej) fej ← ∅ Eljárás vége

• Lista elejére új elem beszúrása Eljárás ElejéreBeszúrás(fej, újérték) ElemLétrehozás(uj) uj.tart ← újérték


uj.köv ← fej fej ← uj Eljárás vége

16

Új elem felvétele • Lista végére beszúrás Eljárás VégéreBeszúrás(fej, újérték) ElemLétrehozás(uj) uj.tart ← újérték


uj.köv ← ∅ Ha fej = ∅ fej ← uj különben p ← fej Ciklus amíg p.köv ≠ ∅ p ← p.köv Ciklus vége p.köv ← uj Elágazás vége Eljárás vége 17

Új elem felvétele • Megadott helyre (n) beszúrás Eljárás MegadottHelyreBeszúrás(fej, n, újérték) ElemLétrehozás(uj) uj.tart ← újérték Ha (fej = ∅) vagy (n = 1) akkor uj.köv = fej; fej = uj

(Vizsgálandó esetek: üres lista, egyetlen elem, lista elejére, lista közepébe, lista végére)

különben p ← fej; i ← 2 Ciklus amíg (p.köv ≠ ∅) és (i < n) p ← p.köv; i ← i + 1 Ciklus vége uj.köv ← p.köv p.köv ← uj Elágazás vége Eljárás vége 18

Elem törlése • Megadott tartalmú elem törlése Eljárás Törlés(fej, törlendő) p ← fej; e ← ∅ Ciklus amíg (p ≠ ∅) és (p.tart ≠ törlendő) e ← p p ← p.köv Ciklus vége

(Vizsgálandó esetek: üres lista, nincs elem, első elem, egyetlen elem, középső elem, utolsó elem)

Ha p ≠ ∅ akkor Ha e = ∅ akkor fej = p.köv külöben e.köv = p.köv ElemFelszabadítás(p) különben „Nincs ilyen elem” Elágazás vége Eljárás vége 19

Teljes lista törlése • Az összes elem törlése Eljárás ListaTörlés(fej) Ciklus amíg (fej ≠ ∅) p ← fej fej ← fej.köv ElemFelszabadítás(p) Ciklus vége Eljárás vége


20


21

Rendezett láncolt lista • Rendezett láncolt lista: A láncolt lista elemei tartalmuk szerint valamilyen előre definiált rendezési szempont szerint sorrendben helyezkednek el fej

A

E

X

∅

• Az utólagos rendezés nehézkes, emiatt a lista felépítésekor célszerű rendezni (beszúró rendezés erre alkalmas) • Az előzőek kibővítése az alábbiakkal: – KeresésRendezettben – RendezettBeszúrás

22

Rendezett láncolt lista - keresés • Keresés rendezett listában Függvény KeresésRendezettben(fej, mitkeres) p ← fej Ciklus amíg (p ≠ ∅) és (p.tart < mitkeres) p ← p.köv Ciklus vége van ← (p ≠ ∅) és (p.tart = mitkeres) Ha van akkor Keresés ← p Függvény vége

(Vizsgálandó esetek: üres lista, nincs ilyen elem, van ilyen elem)

23

Rendezett láncolt lista - beszúrás Eljárás RendezettBeszúrás(fej, újérték) ElemLétrehozás(uj); uj.tart ← újérték Ha fej = ∅ uj.köv ← ∅; fej ← uj; különben Ha fej.tart > újérték uj.köv ← fej; fej ← uj különben

üres lista első elem elé

p ← fej; e ← ∅ Ciklus amíg (p ≠ ∅) és (p.tart < újérték) e ← p; p ← p.köv Ciklus vége Ha p = ∅ uj.köv = ∅; e.köv = uj különben uj.köv = p; e.köv = uj Elágazás vége Elágazás vége Elágazás vége Eljárás vége

utolsó elem mögé két elem közé

24

Rendezett láncolt lista - beszúrás • Azonos ágak összevonása után Eljárás RendezettBeszúrás(fej, újérték) ElemLétrehozás(uj); uj.tart ← újérték p ← fej; e ← ∅ Ciklus amíg (p ≠ ∅) és (p.tart < újérték) e ← p; p ← p.köv Ciklus vége Ha e = ∅ akkor uj.köv ← fej fej ← uj különben uj.köv ← p e.köv ← uj Elágazás vége Eljárás vége

25

Miért rendezzük? • Keresési lehetőségek és átlagos lépésszám: Lineáris keresés

Logaritmikus keresés

Tömb

Ο(n)

Rendezett tömb

Ο(n)

Ο(log2n)

Láncolt lista

Ο(n)

Rendezett láncolt lista

Ο(n)

Algoritmus Adatszerk.

• Tehát a keresés ezzel nem gyorsítható 26


27

Néhány optimalizálási ötlet • Mutatott elem mögé beszúrás Eljárás MutatottMögéBeszúrás(p, újérték) ElemLétrehozás(uj); uj.tart ← újérték uj.köv ← p.köv p.köv ← uj Eljárás vége

• Mutatott elem elé beszúrás (a fej nem ismert) Eljárás MutatottEléBeszúrás(p, újérték) ElemLétrehozás(uj) uj.tart ← p.tart uj.köv ← p.köv p.köv ← uj p.tart ← újérték Eljárás vége

28

További ötletek • Mutatott elem törlése (a fej nem ismert) Eljárás MutatottMögéBeszúrás(p) q ← p.köv p.tart ← q.tart p.köv ← q.köv ElemFelszabadítás(q) Eljárás vége

• Az utóbbi kettő egyszerű (és igen hatékony) algoritmus a kivételes esetek miatt nem használható, mivel – Beszúrás: üres lista esetén nincs elem – Törlés: az utolsó elem után nincs elem

Legyen!

29

Strázsa technika • Strázsa (sentinel) elemek: A lista elejére és a végére felvett kiegészítő elemek. Értékes adatot nem tárolnak, csak technikai szerepük van, hogy kiküszöböljék a kivételes eseteket • Elérhető előnyök – egyszerűbb beszúrás/törlés – gyorsabb beszúrás/törlés

• Szükséges kompromisszumok – helyfoglalás – bejárás körülményesebb (hibalehetőség)

• Példa strázsa elemek használatára 2 8 fej -∝ ∝

19

+∝ ∝

30

∅

Technikai megvalósítás • Strázsa elem megkülönböztetése: – Kiegészítő tulajdonság felvételével – Tartalom alapján

• Rendezett lista esetén az első strázsa célszerűen az adott implementációban legkisebb, az utolsó pedig a lehető legnagyobb értéket tartalmazza • Lista inicializálása (az üres lista is tartalmaz elemeket) Eljárás StrázsaInicializálás(fej) ElemLétrehozás(st2) st2.tart ← +∝ ∝ st2.köv ← ∅ ElemLétrehozás(st1) st1.tart ← -∝ ∝ st1.köv ← st2 fej ← st1 Eljárás vége

fej

-∝ ∝

+∝ ∝

∅

31


32

Kétirányú láncolt lista fej

∅

1

2

3

∅

vége

• A lánc minden eleme tartalmaz egy hivatkozást a sorban rá következő, illetve a sorban őt megelőző elemre is • A lánc végét az utolsó elem következő részének egy kitüntetett értéke jelzi (példákban ∅) • A lánc elejét az első elem előző részének egy kitüntetett értéke jelzi (példákban ∅) • A lánc első elemének címét a listafej tartalmazza (példákban fej változó) • A lánc utolsó elemének címét is célszerű tárolni egy külső változóban (vége)

33

Kétirányú láncolt lista • Előnyei az egyirányú listához képest – keresés: Ha van információnk az elem listabeli elhelyezkedéséről (pl. tudjuk, hogy a vége felé helyezkedik el) akkor előnyös lehet – törlés: Előnyös, hiszen azonnal elérhetjük a szomszédos elemeket – beszúrás: Szintén kihasználható a beláncolás során, hogy közvetlenül elérhető minden elem őt megelőző eleme

• Hátrányok az egyirányú listához képest – nagyobb elemenkénti helyfoglalás (az előző elem címét tartalmazó mező miatt) – módosításkor bonyolultabb algoritmusra van szükség, mivel az előző hivatkozást is mindig aktualizálni kell

34

Többszörösen láncolt lista fej1 fej2

1

∅

2

∅

3 ∅

fej3

• A lánc minden eleme tartalmazza n darab következő elem címet • A lánc végét az utolsó elem megfelelő következő részének egy kitüntetett értéke jelzi (∅) • A lánc tartalmaz n darab listafejet • Műveletei gyakorlatilag megfelelnek az egyszerű láncolt listánál megismertekkel, felfogható n darab független láncolt listaként • A tartalmi rész azonban csak egyszer szerepel, emiatt: – kisebb helyfoglalás – módosításkor egyidőben minden láncban módosul a tartalmi rész (ez nyílván csak akkor előny, ha ez a cél) 35

Ciklikusan láncolt lista fej

1

2

3

• A lánc minden eleme tartalmazza a következő elem címét, az utolsó elem pedig a elsőre mutat vissza • A lánc végét külön nem jelöljük, a bejáró algoritmus felelőssége, hogy észrevegye ha már feldolgozott minden elemet • A láncba akár több belépési pont is tárolható • A lista lehet egy- illetve kétirányú is • Előnyei az egyszerű láncolt listához képest: – speciális feladatoknál hasznos (pl. fix méretű sor adatszerkezet) – törlés: nincsenek kivételes első és utolsó elemek – beszúrás: nincsenek kivételes első és utolsó elemek 36


37

Statikus megvalósítás • Statikus láncolt lista: A láncolt lista elemeit egy tömbben tároljuk, a listaelem következő mezője a listában következő elem indexét tartalmazza • A fej egész típusú változó, az első elem indexét tárolja. • A tartalom és a következő mező eltárolható két különböző tömbben is. Miklós Zsuzsa András Palika Tilda Tóni

4 -1 1 5 6 2

fej = 3

38

Implementációs részletek • A lezáró elem lehet egy tetszőleges, indexként nem értelmezhető szám, pl -1 • Értelemszerűen üres lista esetén fej = -1 • ElemFelszabadítás(p : Egész) – A listát tartalmazó tömb p. elemét bejelöli töröltként. Az állapot tárolható az elem egy mezőjében vagy egy másik tömbben

• ElemLétrehozás(új : Egész) – – – –

A listát tartalmazó tömbben keres egy még szabad helyet (Dinamikus tömb esetén ha nincs hely, növeli a tömb méretét) Lefoglalja ezt a helyet Az új változóban visszaadja az indexet

39

Dinamikus megvalósítás • Dinamikus láncolt lista: A láncolt lista elemeit dinamikus memóriakezelés segítségével hozzuk létre, a következő mező értéke így egy mutató lesz a lista következő elemének memóriabeli címére • Minden elem következő mezője egy mutató, ami a lista következő elemének a címét tárolja Miklós Zsuzsa

fej

0

András Palika Tilda Tóni 40

Implementációs részletek • A fej egy mutató típusú változó, ami az első elem memóriabeli címét tárolja • A lezáró elem lehet egy 0 mutató (null, nil stb.) • Értelemszerűen ez jelzi a lista végét, ill. az üres listát is • ElemFelszabadítás(p : Mutató) – Felszabadítja a p mutató által mutatott helyen található TListaElem méretű memóriaterületet

• ElemLétrehozás(új : Mutató) – Dinamikus memóriakezelés segítségével lefoglal helyet egy TListaElem tárolására – Az új változóban visszaadja a lefoglalt memóriaterület címét

41

Objektum-orientált megvalósítás • Technikai megvalósítás tekintetében tulajdonképpen megegyezik a dinamikus megoldással: – – – –

TListaElem struktúra → TListaElem osztály Mutató → Objektum referencia Memória foglalás → Konstruktor hívása Memória felszabadítás → Destruktor hívása

• Részletesebben lásd. gyakorlaton

42

Gyakorló feladatok • • • • •

Elemi programozási tételek Összetett programozási tételek Verem, sor Javított buborékrendezés Strázsa elemekkel rendelkező láncolt lista implementálása • Kétirányú láncolt lista algoritmusok megvalósítása • Többszörösen láncolt lista algoritmusok megvalósítása • Ciklikus láncolt lista algoritmusok megvalósítása

43

2008 tavasz

Recommend Documents