Láncolt listák. Egyszerű, rendezett és speciális láncolt listák. Programozás II. előadás. Szénási Sándor

Láncolt listák Egyszerű, rendezett és speciális láncolt listák

Programozás II. előadás http://nik.uni-obuda.hu/prog2 Szénási Sándor

[email protected]

Óbudai Egyetem,Neumann János Informatikai Kar

Láncolt listá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

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

Tömb Láncolt lista Fa (bináris fa, B-fa, kupac) Gráf Hasító táblázat

• Műveletek szempontjából – Egyszerű adattárolás • Új elem felvétele • Elem törlése/módosítása • Bejárás • Keresés tetszőleges feltétel szerint – Rendezett adattárolás • Keresés kulcs szerint – Sor – Verem [email protected]

Programozás II.

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

[email protected]

Programozás II.

4

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: – Láncolás szempontjából • Egyszeresen láncolt • Többszörösen láncolt – Rendezés szempontjából • Rendezetlen (egyszerű) • Rendezett – Egyéb szempontok szerint • Strázsa elemek használata • Speciális listák (ciklikus, kétirányú, stb.)

[email protected]

Programozás II.

5

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, T típusú – 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, M típusú – tömb index – mutató (TLáncElem típusú) – objektum referencia

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

[email protected]

Programozás II.

6

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 egy külső változó, a listafej tartalmazza (példákban fej változó néven) • A listafej nem elem, csak egy hivatkozás (nincs tartalmi része) • 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ó függő) • Üres listánál a listafej értéke ez a kitüntetett érték

[email protected]

Programozás II.

7

Tömb és dinamikus adatszerkezetek összehasonlítása • A tömb adatszerkezet hátrányai – 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

• Dinamikus adatszerkezetek hátrányai – Bonyolult (használata nehézkes, hibalehetőség) – Elemek nem érhetők el közvetlenül indexeléssel – Az előző 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

[email protected]

Programozás II.

8


Láncolt lista bejárása • Bejárás: Az adatszerkezet valamennyi elemének egyszeri elérése • A bejárás célja lehet – Az egyes tartalmak feldolgozása – Az egyes tartalmak visszaadása a hívónak

• A tartalmak feldolgozása egymástól független, így kb. megfelel a sorozatszámítás programozási tételnek • Bejárás algoritmusa eljárás ListaBejárás(fej) p  fej ciklus amíg p   FELDOLGOZ(p.tart) p  p.köv ciklus vége eljárás vége

[email protected]

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

Programozás II.

10

Keresés a listában • Keresés: A lista fej ismeretében egy megadott feltételnek megfelelő tartalom megkeresése – eldönteni, hogy van-e ilyen tartalmú elem – ha nincs, akkor a visszatérési érték hamis

• Keresés algoritmusa függvény ListábanKeresés(fej, F feltétel) p  fej ciklus amíg (p  ) ˄ ¬F(p.tart) p  p.köv ciklus vége van  (p  ) ha van akkor vissza (van, p.tart) különben vissza van elágazás vége függvény vége [email protected]

Programozás II.

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

11

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

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

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

• Keresés – lineáris keresés

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

• Maximum kiválasztás – valamilyen szempont szerinti maximális tartalmú kiválasztása

[email protected]

Programozás II.

12

Inicializálás és új elem felvétele (elejére) • Lista inicializálása: a lista alaphelyzetbe állítása eljárás ListaInicializálás(címsz. fej) fej   eljárás vége

• Lista elejére új elem beszúrása eljárás ListábaBeszúrásElejére(címsz. fej, érték) új  LÉTREHOZ(M) új.tart  érték

új.köv  fej fej  új eljárás vége


[email protected]

Programozás II.

13

Új elem felvétele (végére) • Lista végére beszúrás eljárás ListábaBeszúrásVégére(címsz. fej, érték)

új  LÉTREHOZ(M) új.tart  érték


új.köv   ha fej =  fej  új különben p  fej ciklus amíg p.köv   p  p.köv ciklus vége

p.köv  új elágazás vége eljárás vége

[email protected]

Programozás II.

14

Új elem felvétele (megadott helyre) • Megadott helyre (n. pozíció) beszúrás eljárás ListábaBeszúrásN(címsz. fej, érték, n)

új  LÉTREHOZ(M) új.tart  érték ha (fej = ) ˅ (n = 1) akkor új.köv = fej; fej = új

(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  ) ˄ (i < n) p  p.köv; i  i + 1 ciklus vége új.köv  p.köv

p.köv  új elágazás vége eljárás vége

[email protected]

Programozás II.

15

Elem törlése • Megadott tartalmú elem törlése (ha van ilyen) eljárás ListábólTörlés(címsz. fej, törlendő) p  fej; e   ciklus amíg (p  ) ˄ (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önben e.köv = p.köv elágazás vége FELSZABADÍT(p) különben hiba „nincs ilyen elem” elágazás vége eljárás vége

[email protected]

Programozás II.

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

16

Teljes lista törlése • Az összes elem törlése eljárás ListaTeljesTörlése(címsz. fej) ciklus amíg (fej  ) p  fej


fej  fej.köv FELSZABADÍT(p)

ciklus vége eljárás vége

[email protected]

Programozás II.

17


Rendezett láncolt lista • A rendezés érdekében kiegészítjük a láncolt lista elemeket egy új, kulcs nevű tulajdonsággal • Ennek típusa mindig összehasonlítható • Ez a kulcs lehet – egy tartalomtól független mező – a tartalom egy része – maga a tartalom

• Rendezett láncolt lista: a láncolt lista elemei kulcs szerint rendezett sorrendben követik egymást • Az utólagos rendezés nehézkes, emiatt a lista felépítésekor célszerű rendezni (beszúró rendezés erre alkalmas) • Az ábrákon az egyszerűség kedvéért a kulcs = tartalom változatot fogjuk használni fej

[email protected]

A

E

Programozás II.

X



19

Rendezett láncolt lista - keresés • Kulcs szerinti keresés rendezett láncolt listában függvény RendezettListábanKeresés(fej, kulcs) p  fej ciklus amíg (p  ) ˄ (p.kulcs < kulcs) p  p.köv ciklus vége van  (p  ) ˄ (p.kulcs = kulcs) ha van akkor vissza (van, p.tart) különben vissza van elágazás vége függvény vége

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

[email protected]

Programozás II.

20

Rendezett láncolt lista - beszúrás • Megadott elem beszúrása rendezett listába eljárás RendezettListábaBeszúrás(címsz. fej, kulcs, érték) új  LÉTREHOZ(M); új.kulcs  kulcs; új.tart  érték ha fej =  akkor új.köv  ; fej  új különben ha fej.kulcs > kulcs akkor új.köv  fej; fej  új különben p  fej; e   ciklus amíg (p  ) ˄ (p.kulcs < kulcs) e  p; p  p.köv ciklus vége ha p =  akkor új.köv = ; e.köv = új különben új.köv = p; e.köv = új elágazás vége elágazás vége elágazás vége eljárás vége

[email protected]

Programozás II.

üres lista első elem elé

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

21

Rendezett láncolt lista – beszúrás második változat • Azonos ágak összevonása után eljárás RendezettListábaBeszúrás(címsz. fej, kulcs, érték) új  LÉTREHOZ(M) új.kulcs  kulcs új.tart  érték p  fej; e   ciklus amíg (p  ) ˄ (p.kulcs < kulcs) e  p; p  p.köv ciklus vége ha e =  akkor új.köv  fej fej  új különben új.köv  p e.köv  új elágazás vége eljárás vége [email protected]

Programozás II.

22

Miért rendezzük? • Logaritmikus keresés láncolt listáknál nem használható 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.

• További lehetőségek – Ha nincs keresett kulcsú elem, akkor gyorsabban kapunk választ – Rendezett feldolgozás szükséges (pl. nevek listázása ABC sorrendben) [email protected]

Programozás II.

23


Néhány optimalizálási ötlet • A fej mutató használata nélkül, csak egy belső lista elemre való hivatkozással (p) is tudunk beszúrni, illetve törölni • Mutatott elem mögé beszúrás eljárás MutatottElemMögéBeszúrás(p, érték) új  LÉTREHOZ(M) új.tart  érték új.köv  p.köv p.köv  új eljárás vége

• Mutatott elem elé beszúrás (a fej nem ismert) eljárás MutatottElemEléBeszúrás(p, érték) új  LÉTREHOZ(M) új.tart  p.érték új.köv  p.köv p.tart  érték p.köv  új eljárás vége [email protected]

Programozás II.

25

További ötletek • Mutatott elem törlése (a fej nem ismert) eljárás MutatottElemTörlése(p) q  p.köv p.tart  q.tart p.köv  q.köv FELSZABADÍT(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

• Megoldás: készítsünk olyan láncolt lista implementációt, amely kiküszöböli ezeket a kivételes eseteket

[email protected]

Programozás II.

26

Strázsa technika • Strázsa (sentinel) elemek: A lista elejére és a végére felvett kiegészítő elemek. Értékes tartalmat 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

[email protected]

Programozás II.

19

+

27



Technikai megvalósítás • Strázsa elem megkülönböztetése: – Kiegészítő tulajdonság felvételével – Tartalom/kulcs alapján – Pozíció alapján (mindig első és utolsó)

• Rendezett lista esetén az első strázsa az adott implementációban legkisebb, az utolsó pedig a legnagyobb kulcs értékét tartalmazza • Lista inicializálása (az üres lista is tartalmaz elemeket) eljárás StrázsaInicializálás(címsz. fej) st2  LÉTREHOZ(M) st2.tart  + st2.köv   st1  LÉTREHOZ(M) st1.tart  - st1.köv  st2 fej  st1 eljárás vége

fej [email protected]

-

+ Programozás II.

 28


Kétirányú láncolt lista felépítése fejE



1

2

3



fejV

• 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 fejE változó) • A lánc utolsó elemének címét is célszerű tárolni egy külső változóban (példánkban a fejV)

[email protected]

Programozás II.

30

Kétirányú láncolt lista értékelése • 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

[email protected]

Programozás II.

31

Többszörösen láncolt lista felépítése és értékelése fej1

fej2

1



2



3 

fej3

• A lánc minden eleme tartalmazza n darab következő elem címet (ekkor n-szeresen láncolt listáról beszélhetünk) • 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 minden láncban módosul a tartalmi rész (ez nyilván csak akkor előny, ha ez a cél)

[email protected]

Programozás II.

32

Ciklikusan láncolt lista felépítése és értékelése

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éskor nincsenek kivételes első és utolsó elemek – beszúráskor nincsenek kivételes első és utolsó elemek

[email protected]

Programozás II.

33


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, kulcs és a következő mező eltárolható egy vagy több különböző tömbben is • A mérete nem változtatható, de a beszúrás és törlés szempontjából előnyösebb lehet, mint egy hagyományos tömb

fej = 3

[email protected]

Miklós

4

Zsuzsa András Palika

-1 1 5

Tilda Tóni

6 2

Programozás II.

35

Statikus megvalósítás implementációja • • • •

T implementációja: tárolni kívánt típus (példában szöveg) M implementációja: egész szám, tömb indexeket tárol  implementációja: pl. -1 Műveletek implementációja: – FELSZABADÍT(p : Egész) • a listát tartalmazó tömb p. elemét bejelöli töröltként. Ez az állapot tárolható az elem egy mezőjében vagy egy másik tömbben – LÉTREHOZ : Egész • a listát tartalmazó tömbben keres egy még szabad helyet • lefoglalja ezt a helyet • visszatérési értéke ennek a helynek az indexe

[email protected]

Programozás II.

36

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

[email protected]

Programozás II.

37

Dinamikus megvalósítás implementációja • • • •

T implementációja: tárolni kívánt típus (példában szöveg) M implementációja: mutató, ami memória címeket tárol  implementációja: spec. nyelvi elem (null, NULL, nil, 0, stb.) Műveletek implementációja: – FELSZABADÍT(p : Mutató) • felszabadítja a p által hivatkozott memóriacímen található listaelem méretű memóriaterületet – LÉTREHOZ : Mutató • dinamikus memóriakezelés segítségével lefoglal egy listaelem méretű memóriaterületet • visszatérési értéke ennek a memóriaterületnek a címe

[email protected]

Programozás II.

38

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

• Célszerűen az egész láncolt lista önmagában is lehet egy objektum, így a paraméterként minden esetben átadott fej mutató lehet ennek egy belső mezője (ez jelentősen egyszerűsíti az algoritmusokat) • Részletesebben lásd. gyakorlaton

[email protected]

Programozás II.

39

Irodalomjegyzék • Javasolt/felhasznált irodalom – Cormen, Leiserson, Rivest: Algoritmusok, Műszaki Könyvkiadó, 1997 – Pap, Szlávi, Zsakó: μlógia34 – Módszeres programozás: Adattípusok, ELTE TTK, 1998 – Knuth: A számítógép programozás művészete – 1. kötet. Alapvető típusok, Műszaki Könyvkiadó, 1988 – Szénási: Algoritmusok, adatszerkezetek II., Óbudai Egyetem, 2014

[email protected]

Programozás II.

40

Láncolt listák. Egyszerű, rendezett és speciális láncolt listák. Programozás II. előadás. Szénási Sándor

Recommend Documents