Tömb és láncolt lista
Elmélet
(Egy rövid összefoglaló azoknak, akik még nem értik teljesen. Remélem, segít...)
Ha a program írásakor tudjuk, hogy hány adatot akarunk tárolni (pl. 20 kis tank lesz egyszerre a játéktéren), akkor egyszerűen meg tudjuk mondani a fordítónak, hogy 20 lesz, ennyinek kell hely a memóriában. Ilyenkor ő foglalkozik a memória kezeléssel, nekünk nem kell törődnünk vele. (Pl. 10 egész szám tárolására jó lesz az int tomb[10]. No de mi van akkor, ha nem tudjuk, mennyi lesz?
Ha a program írásakor nem tudjuk, mennyi memóriára lesz szükségünk, akkor dinamikusan (menet közben) kell kérnünk az operációs rendszertől. Erre való a "malloc" függvény (Memory ALLOCation). Megmondjuk, hogy mennyi kell, aztán annyit kapunk. Ha így kérünk helyet, akkor az operációs rendszer (siker esetén) megmondja, hogy hol kaptunk helyet. Mivel az egy memória cím, ezért ezt egy pointer-ben (memóriacímet tároló változó típus) tudjuk elmenteni.
Ha viszont van egy olyan lehetőségünk, hogy bárminek el tudjuk tárolni a helyét a memóriában, akkor könnyen készíthetünk dinamikus listát is. Ennek az a lényege, hogy nem egy nagy területet kérünk (pl. 200 tanknak a játékunkhoz), hanem
- Minden listaelemet (pl. a tank adatait tároló struct) kiegészítünk egy mutatóval, ami el tudja tárolni a lista következő elemének a helyét.
- Amikor szükségünk van egy új elemre, akkor szépen foglalunk neki helyet ("malloc" és hasonlók), feltöltjük adatokkal (pl. tank kezdő pozíciója, lövedékek száma stb.), majd felvesszük a listába: az eddigi utolsó elem az új elemre fog mutatni, mint következőre...
Így annyi új elemet veszünk fel, amennyit csak akarunk. Csak arra kell figyelni, hogy mindegyik szépen bekerüljön a listába. Általánosan amikor az ember dinamikus listával művel valamit (új elem hozzáadása, elem törlése, beszúrása, minden elem törlése, elemek átrendezése), a következőkre kell figyelni:
- Memória lefoglalása (ha kell), ha nem sikerül (malloc NULL-t ad vissza), akkor hiba lekezelése.
- A listában megfelelő elem keresése: sokszor meg kell keresni azt az elemet, amit érint a művelet. Ilyen lehet az az elem, ami után be akarunk szúrni, vagy az utolsó, ha a lista végéhez akarunk hozzáfűzni valamit. Ilyenkor figyeljetek arra, nehogy a lista végén "leszaladjatok" a listáról a memória végtelen vadjárataiba. (Ha nincs következő elem, a rá mutató pointer mindig legyen NULL!)
- Elemek kifűzése, befűzése, a pointer-ek átrendezése: ezt érdemes lerajzolni. Meg kell nézni, minek hova kell mutatnia a művelet után és ehhez mit kell módosítani. Figyeljetek arra, hogy ha hiba történik (pl. malloc nem sikerül), a listát akkor sem szabad tönkretenni! A művelet végén mindig használható állapotban kell lennie a listának. (A kifűzött elemek területét szabadítsátok fel, az összes többit pedig tényleg el lehessen érni.)
Aztán persze lehet ezt bonyolítani bőven: ha a lista utolsó eleme következőként az elsőre mutat, egy gyűrűszerű képződményt kapunk. (Ennek ha nekiállunk megkeresni a végét, akkor bizony sokáig fog tartani... és ez igaz akkor is, ha egy olyan elemet keresünk, ami nem létezik.)
A dinamikus listában macerás visszafelé menni, ezért előfordul, hogy a következő elemre mutató pointer mellett van mégegy, ami meg az előzőre mutat. Így akkor visszafelé is lehet ugrálni. Ilyenkor persze minden műveletnél a visszafelé mutató pointerek láncát is rendbe kell rakni.
Implementációk
Egy egyszerű példaprogramot is feltöltöttem. Jo sok kommentárt írtam bele, hogy emészthetőbb legyen. Ha bonyolultnak érzitek, keressétek minden műveletnél azt, hogy melyik rész dolgozik a tárolt adatokkal, melyik rakja rendbe a pointereket stb.)
Az alábbi programban leprogramoztam az egyszeresen láncolt listákon értelmezett összes fontos műveletet. A cél a kód tömörsége volt. A használatot a main() függvényben példákkal illusztrálom.
- elem beszúrása előre, hátulra, adott pozícióra
- elem beszúrása a rendezés szerinti helyére
- elem törlése elölről, hátulról, kulcs alapján
- lista megfordítása
- lista rendezése
- lista törlése (lefoglalt memória felszabadítása)
- elemek kiírása képernyőre
Két irányba láncolt lista
A két irányba láncolt dinamikus lista lényege, hogy van egy olyan pointer is minden elemben, ami az előző elemre mutat. Így nem csak előre lehet lépkedni a listában, hanem visszafelé is. Az alábbi példaprogram nagyon hasonlít az példaprogramotelőzőre. Az új sorokat meg is jelöltem benne. (Lásd a megjegyzést a forráskód elején!)
