2009.03.30.
Láncolt listák
[email protected] PPT 2007/2008 tavasz http://nik.bmf.hu/ppt
1
Lista alapfogalmai Egyirányú egyszerű láncolt lista Egyirányú rendezett láncolt lista Speciális láncolt listák
Témakörök 2
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: ε)
Lista alapfogalmak 3
1
2009.03.30.
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
Lista alapfogalmak 4
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
Láncolt lista definíció 5
Lista alapfogalmai Egyirányú egyszerű láncolt lista Egyirányú rendezett láncolt lista Speciális láncolt listák
Témakörök 6
2
2009.03.30.
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)
Láncolt lista bejárása
7
• 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)
Keresés a listában
Sorozatszámítás
Eldöntés
Kiválasztás
Keresés
Megszámolás
Maximumkiválasztás
8
◦ lista elemeinek összege ◦ lista elemeinek átlaga ◦ stb. ◦ adott tulajdonságú elem megtalálható a listában? ◦ megadott elem kiválasztása a listából? ◦ lineáris keresés ◦ megadott tulajdonságú elemek megszámolása ◦ valamilyen szempont szerinti legnagyobb elem kiválasztása
Házi feladat – prog. tételek listával 9
3
2009.03.30.
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
Új elem felvétele 10
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 =
(Vizsgálandó esetek: üres lista, nem üres lista)
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
Új elem felvétele a lista végére
11
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 különben p fej; i 2
(Vizsgálandó esetek: üres lista, egyetlen elem, lista elejére, lista közepébe, lista végére)
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
Új elem felvétele adott helyre
12
4
2009.03.30.
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 Ha p akkor Ha e = akkor fej = p.köv külöben e.köv = p.köv
(Vizsgálandó esetek: üres lista, nincs elem, első elem, egyetlen elem, középső elem, utolsó elem)
ElemFelszabadítás(p) különben „Nincs ilyen elem” Elágazás vége Eljárás vége
Adott tartalmú elem törlése
13
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
(Vizsgálandó esetek: üres lista, nem üres lista)
Teljes lista törlése 14
Lista alapfogalmai Egyirányú egyszerű láncolt lista Egyirányú rendezett láncolt lista Speciális láncolt listák
Témakörök 15
5
2009.03.30.
• 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
Rendezett láncolt lista 16
• 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)
Rendezett láncolt lista - keresés 17
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é
Rendezett láncolt lista - beszúrás
18
6
2009.03.30.
• 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
Rendezett láncolt lista - beszúrás 19
Lista alapfogalmai Egyirányú egyszerű láncolt lista Egyirányú rendezett láncolt lista Speciális láncolt listák
Témakörök 20
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)
Kétirányú láncolt lista
21
7
2009.03.30.
Előnyei az egyirányú listához képest
Hátrányok 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 ◦ 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
Kétirányú láncolt lista 22
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)
Többszörösen láncolt lista
fej
1
2
23
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
Ciklikusan láncolt lista 24
8
