1. Dinamikus tömbök

Feladat: határozzuk meg egy tetszőleges sokszög területét.

Sokszor a program írásakor nem, de a feldolgozás előtt közvetlenül már ismerjük a szükséges memória méretét. Az ilyen feladat megoldható dinamikusan foglalt tömb segítségével: pl. egy sokszög csúcsainak tárolása. A fenti feladat megoldása egy konvex sokszögre, amelynek ismerjük a koordinátáit:

  1. Bekérjük a felhasználótól az oldalak számát.
  2. Lefoglalunk egy megfelelő méretű koordinátatömböt és beolvassuk a csúcsokat.
  3. Keresünk egy belső pontot a sokszögben (pl. súlypont).
  4. Háromszögekre osztjuk a sokszöget, kiszámoljuk és összegezzük azok területét.
  5. Felszabadítjuk a tömböt.
Sokszög területe háromszögekre osztással
Pont *csucsok;
csucsok = (Pont*) malloc(sizeof(Pont)*6);
csucsok[5].x = 12;
csucsok[5].y = 17;
/* .... */
free(csucsok);

A tömbök előnye: gyors, közvetlen adatelérés. Az elemeket tetszőleges sorrendben, közvetlen címzéssel érjük el, hiszen közvetlenül egymás mellett helyezkednek el a memóriában. Ezt gyakran ki is használjuk, pl. bináris keresésnél „ugrálunk” a tömbben.

A tömbök hátránya: lassú az átméretezés. Mivel feltétlenül egymás mellett kell, hogy legyenek az elemek, ha változtatni akarjuk a tömb méretét, újra kell foglalni a memóriaterületet. Ennek lépései: (I.) Le kell foglalni másutt a szükséges méretű területet, (II.) Át kell másolni az elemeket a régi helyről, (III.) Fel kell szabadítani a régi tömböt. A tömbök dinamikus nyújtása ezért nagyon költséges művelet. Ráadásul másolás közben az eredeti tartalom kétszer szerepel a memóriában!


Feladat: kezeljük egy szerverre bejelentkezett felhasználók listáját!

  • Nem tudhatjuk, hogy hányan akarnak majd bejelentkezni hozzánk.
  • A felhasználók száma folyamatosan változik.

Ideális megoldás lenne: minden belépéskor csak az új felhasználónak megfelelő területet foglalni. Ezzel az a probléma, hogy a memóriában elszórva helyezkednek el az adatok. Valahogyan nyilván kellene tartani, hogy hol vannak az egyes elemek! Ha ehhez pointerek tömbjét használnánk, akkor az lesz az, amit folyton át kell méretezni – vagyis visszakapnánk az eredeti probémát.

Tömb a memóriában – nagyon lassú az átméretezés
Egyesével foglalt memóriaterületek
Egyesével foglalt memóriaterületek: láncolás

Ötlet: az egyes elemek tárolják az őket követő elem címét! Így minden elem egyesével foglalható. Minden elem adatát kiegészítjük egy mutatóval, ami ugyan plusz költség, de egy olyan adatszerkezetet kapunk, amire teljesül, hogy

  • tetszőleges méretűre bővíthető dinamikusan,
  • új elem hozzáadásának a költsége nagyon kicsi,
  • elemek törlése is olcsó művelet.

Vegyük észre, hogy minderre a dinamikus memóriakezelés ad lehetőséget: egy olyan adatszerkezetet készülünk most létrehozni, amelyben az egyes elemek külön jönnek létre, és külön szűnhetnek meg. Nem csak az összes tárolt adat élettartamát fogjuk kontrollálni egyszerre, mint a dinamikus tömbnél, hanem az egyes elemekét külön-külön is!

2. A láncolható elem

Láncolt lista (linked list): adatszerkezet, ahol az egyes elemek láncba vannak fűzve azáltal, hogy tárolják a soron következő elem címét.

Lista elemei

Nyelvi szinten egy láncolt listába fűzhető elem önhivatkozó struktúrával írható le:

önhivatkozó
struktúra:
pointerrel!
typedef struct ListaElem {

   … // tetszőleges adat(ok)

   struct ListaElem *kov;
} ListaElem;

Fontos: az önhivatkozás csak mutató segítségével oldható meg. Egy adattag típusa nem egyezhet meg a strukúrával, amiben szerepel, hiszen akkor egy végtelen nagyságú adatszerkezetet kapnánk!

Figyeljük meg, hogy typedef segítségével ugyan létrehozunk egy rövidebb nevet, a struktúrán belül muszáj használni a struct kulcsszót, hiszen ott még nem létezik az alternatív név. Bár általában, ha typedef segítségével definiálunk struktúrát, akkor a struct kulcsszó mellett elhagyható a név, itt ez nem tehető meg az önhivatkozás miatt.

3. A lista nyilvántartása

A lista első elemének címét kell eltárolnunk: ettől elindulva a teljes adatszerkezet bejárható.

Így a lista olyan, mintha az elemei egy madzagra lennének felfűzve. Az utolsó elemben lévő cím NULL: ezzel a speciális értékkel jelezzük, hogy nincsen további elem a listában.


Lista eleje
  1. elem címe: eleje
  2. elem címe: eleje->kov (*eleje).kov
  3. elem címe: eleje->kov->kov (*(*eleje).kov).kov
  4. elem címe: eleje->kov->kov->kov (ami itt NULL)

Ne feledjük: eleje->kov ugyanazt jelenti, mint (*eleje).kov. Az eleje pointer által mutatott struktúra kov adattagja. A -> nyíl operátort azért találták ki, hogy ne kelljen mindig zárójelezni az ilyen kifejezéseket. De ez nagyon kényelmes is: a nyíl emlékeztet a pointerre!

4. A lista bejárása (traversing the list)

A listán ciklussal tudunk végigmenni:

ListaElem *mozgo;

for (mozgo = eleje; mozgo != NULL; mozgo = mozgo->kov) {
    printf("%d", mozgo->szam);
}
Ciklus végig a listán

Nincs új a nap alatt: for (első; meddig; következő). Az első itt a lista eleje: mozgo=eleje. A meddig itt a NULL pointerig: mozgo != NULL. A következő az aktuális elem által mutatott: mozgo=mozgo->kov

Láncolt listák – listaműveletek


Tanulási javaslat:
papír, ceruza, radír!

A következőkben a láncolt listák kezelésének algoritmusairól lesz szó. A listák kezelése közben szinte minden művelet valamilyen pointerművelet; az összes algoritmus a listák láncolását állítja be. Van olyan eset, ahol négy pointert is át kell állítani, megfelelő sorrendben. Ezeket nem szabad magolva tanulni! Azt kell megérteni, hogy mit jelent a lista láncolása, és hogy egy adott listaművelet előtt és után hogyan kellene kinéznie a láncolásnak. Egy rajz alapján a programok nagyon könnyen megalkothatóak! A tervezés és a tanulás ezért a javaslatunk szerint papíron történik! Minden malloc() után egy dobozt kell rajzolni, minden free() után egy dobozt kiradírozni. Minden pointerértékadás egy nyíl megrajzolását jelenti. Ha papíron megy, utána kódban is könnyedén menni fog!

6. Listaépítés – beszúrás előre I.

Új elem a lista elejére
ListaElem *uj;

uj = (ListaElem*) malloc(sizeof(ListaElem)); // 1
uj->kov = eleje; // 2
eleje = uj; // 3
  1. Új elem dinamikus lefoglalása
  2. Az új elem „következő” pointerének beállítása az „eleje” értékére.
  3. Az „eleje” pointer beállítása az új elem címére

Ha az „eleje” mutató kezdetben NULL, a fenti kód akkor is egy teljes listát helyesen épít fel a teljesen ürestől indulva.

7. Listaépítés – beszúrás előre II.

Írjuk meg az előző feladatot függvényként! A függvény vegye át paraméterként a lista eleje mutatót, és a beszúrandó adatot! Például:

ListaElem *eleje = NULL;
elore_beszur(eleje, 2);     // működhet ez???

Működhet ez így? Garantáltan nem! C-ben érték szerinti paraméterátadás van. Ha a függvény első paramétereként átadjuk az „eleje” mutatót, akkor annak csak az értékét fogja megkapni, másolatként. Az „eleje” változó viszont nem fog megváltozni, a beszúrás után még mindig null lesz az értéke. Akármit is csinál az elore_beszur() függvény, a fenti kódrészlet csak hibás lehet! Ezt a problémát még meg kell oldani: a beszúrás által meg kell tudni változtatni a lista elejének címét tároló változót.


A probléma pl. úgy oldható meg, hogy a függvény mindig visszaadja az új „eleje” pointert, amivel felül kell írni a tároltat. A függvény használata ez lesz:

ListaElem *eleje = NULL;
eleje = elore_beszur(eleje, 2); // !

A beszúró függvény, amely visszaadja az új „eleje” pointert:

/* Új elemet hoz létre, és a lista elejére fűzi.
 * Visszatér a megváltozott lista eleje pointerrel. */
ListaElem *elore_beszur(ListaElem *eleje, int adat) {
   ListaElem *uj;
   uj = (ListaElem*) malloc(sizeof(ListaElem));
   uj->adat = adat;
   uj->kov = eleje;
   return uj;       // !
}
Fontos!

A lista elejére kerül az új elem, ezért pont annak a címével tér vissza. Ha nem tároljuk el az új címet, akkor az elem elvész! Ezért a visszatérési értékét eldobni, nem eltárolni az eleje változóban, nagyon súlyos hiba!

Vegyük észre: bár a függvény paramétere ListaElem * típusú, tehát egy pointer, itt mégsem cím szerinti paraméterátadásról van szó. Mert a paraméter, amit átadunk, azaz a változó, aminek az értékét szeretnénk változtatni, maga is pointer típusú. Ha cím szerinti paraméterátadásról lenne szó, a hívásban &eleje lenne, a függvény paraméterének típusa pedig ListaElem **. Ez is jó megoldáshoz vezetne, de egyelőre maradjunk az első változatnál.

8. Listaépítés – hozzáfűzés I.

Ha abban a sorrendben szeretnénk elérni az elemeket, amiben érkeztek, akkor a lista végére kell „beszúrni” (hozzáfűzni) őket.

Új elem a lista végére
ListaElem *mozgo, *uj;

for (mozgo = eleje; mozgo->kov != NULL; mozgo = mozgo->kov) // 1
   ; /* üres ciklus */
uj = (ListaElem*) malloc(sizeof(ListaElem));                // 2
mozgo->kov = uj;
uj->kov = NULL;                                             // 3

Hozzáfűzés a lista végéhez (append):

  1. lefoglaljuk az új elemet,
  2. megkeressük az utolsót (mivel csak az első pointere van meg),
  3. az utolsó elem „következő” mutatóját beállítjuk az új elem címére, az új elemét pedig NULL-ra.

A ciklus egy apró, de fontos dologban különbözik a bejárás ciklusától. Itt a ciklusfeltétel nem mozgo != NULL, hanem mozgo->kov != NULL – vagyis a ciklus nem az utolsó elem után áll meg, hanem még az utolsó elemnél. Az utolsó elemet éppen arról ismerjük meg, hogy a benne lévő kov pointer értéke NULL.

9. Listaépítés – hozzáfűzés II.

Elsőre azt gondolhatnánk, hogy ha hátulra szúrunk be, akkor az „eleje” mutató nem változik. Ez azonban így nem igaz. Üres listában a hátulra fűzéstől változik az „eleje” mutató!

Új elem a lista végére
Itt is fontos az
eleje mutató!
ListaElem *eleje = NULL; // üres lista

eleje = vegere_fuz(eleje, 2);
eleje = vegere_fuz(eleje, 9);

Vagyis nem csak hogy az üres listát külön esetként kell kezelnünk (mivel az előbb mutatott ciklust a benne lévő mozgo->kov != NULL feltétel miatt nem futtathatjuk üres listán!), hanem a lista végére fűző függvényt ugyananúgy kell megoldanunk, mint az elejére beszúrást. Mert az alábbi kódrészletből is láthatóan, változik a lista eleje mutató:

/* az új elem létrehozása */
ListaElem *uj;
uj = (ListaElem*) malloc(sizeof(ListaElem));
uj->adat = /* ... */;
uj->kov = NULL;

if (eleje == NULL) {
   /* üres listánál ez lesz az első elem */
   eleje = uj;
} else {
   /* ha nem üres a lista, az utolsó után fűzzük */
   ListaElem *mozgo;
   for (mozgo = eleje; mozgo->kov != NULL; mozgo = mozgo->kov)
      ; /* üres ciklus */
   mozgo->kov = uj;
}

Akár üres listába, akár egy meglévő lista végébe tesszük az új elemet, az biztos, hogy valahol lesz egy pointer, amelyiknek majd mutatnia kell rá. Azonban hogy hol van ez a pointer, az a listától függően változhat:

  • Ha üres, akkor nincs utolsó elem sem. Ilyenkor a lista elejét mutató pointer kell változzon. Ez eredetileg NULL pointer, amit felülírunk az új elem címével.
  • Ha a lista nem üres, akkor meg kell keresni az utolsó elemet. Ilyenkor annak a kov pointere változik meg.

10. A lista felszabadítása

Hogy néz ki egy lista felszabadítása, azaz az összes elemének törlése a memóriából?

Az alábbi kódrészlet kézenfekvőnek tűnik, de hibás:

for (iter = eleje; iter != NULL; iter = iter->kov) {
   free(iter);                              // hibás
}

Mivel az „iter” által mutatott listaelemet felszabadítjuk, a ciklusmag után a következő elemet előszedő iter=iter->kov utasítás már egy felszabadított területre hivatkozna.


Ezért el kell tárolni a törölt elemből a „következő” mutatót, hiszen a felszabadítás után még szükségünk van rá a továbblépéshez:

iter = eleje;
while (iter != NULL) {
   ListaElem *temp = iter->kov; // következő elem
   free(iter);
   iter = temp;
}

Így végeredményben egy iter = eleje; iter != NULL; iter = iter->kov ciklust kapunk, de az iter->kov kifejezés kiértékelése a ciklustörzs elejére került, eltoltuk időben a free() előttre.

11. Összetett példa: mondatok generálása

Letölthető:
mondat.c

Feladat: írjunk programot, amely véletlenszerűen generált, magyar nyelvű mondatokat ír ki!

A kutya alszik.
A lassú kutya gyorsan fut.

Mit kell ehhez tenni?

  1. Specifikáljuk, milyen a helyes mondat!
  2. Döntsük el, milyen adatszerkezetben tárolhatók a mondatok!
  3. Adjuk meg, mely függvények rakják össze a mondatokat!
  4. Írjuk meg a programot.

A mondatos feladat ötlete a varázslós könyvből származik: Hal Abelson, Gerald Sussman and Julie Sussman: Structure and Interpretation of Computer Programs.

12. Mondatok – adatszerkezet választása

Mondatok: eltérő hosszúságúak lehetnek, szavakból állnak.
Szavak: betűkből állnak, bármilyen hosszúak lehetnek.

A mondat legyen lista, amely szavakból áll. Így tetszőlegesen hosszú mondatok összefűzhetőek, és egyetlen pointerrel hivatkozhatóak. A szó legyen dinamikusan foglalt tömb – abban pedig a szokásos sztring.

A mondatok adatszerkezete
typedef struct SzoLista {
    char *szo;
    struct SzoLista *kov;
} SzoLista;

Karakterekből nem érdemes listát építeni, hiszen akkor minden bájt mellé egy újabb pointert lefoglalnánk. Amúgy is, maradjunk a sztringnél, hogy printf()-fel könnyedén ki tudjuk majd írni a szavakat!

A listaelem és a benne lévő szó is dinamikusan foglalt! Az egyszavas lista foglalásához foglalni kell listaelemet és tömböt is:

/* Egyelemű lista építése egy sztringből.
 * Bemenet: egy sztring - a szó, amit lemásol.
 * Visszatérési érték: az újonnan létrehozott lista. */
SzoLista *ujegyszavas(char const *szo) {
    SzoLista *uj;
    uj = (SzoLista*) malloc(sizeof(SzoLista));
    uj->kov = NULL;
    uj->szo = (char*) malloc(sizeof(char)*(strlen(szo)+1));
    strcpy(uj->szo, szo);

    return uj;
}

13. Mondatok – EBNF megadás, lista építése

EBNF nyelvtani szabályokkal specifikáljuk a mondatot:

kijelentés = névelő, alanyi_rész, állítmányi_rész;
alanyi_rész = melléknév, főnév;
állítmányi_rész = határozó, ige;

melléknév = "piros" | "lassú" | "álmos";
főnév = "macska" | "kutya" | "tanár" | "hallgató";
határozó = "gyorsan" | "lassan";
All the beers!

Példa: névelő, alanyi rész, állítmányi rész:

A vidám hallgató gyorsan iszik.

A vidám hallgató , .

A lista építése:

alanyi_resz = osszefuz(veletlenszo(melleknevek),
                       veletlenszo(fonevek));
allitmanyi_resz = osszefuz(veletlenszo(hatarozok),
                           veletlenszo(igek));
mondat = osszefuz(alanyi_resz, allitmanyi_resz);

A mondat kiírása:

/* kiír egy mondatot, végén ponttal. */
void kiir(SzoLista *mondat) {
    SzoLista *iter = mondat;
    while (iter->kov != NULL) {  /* az utolsó előttiig */
        printf("%s ", iter->szo);
        iter = iter->kov;
    }
    printf("%s.\n", iter->szo);  /* az utolsó */
}

A veletlenszo() a kapott szótömbből véletlenszerűen választ egyet, és visszaad egy új listát, amelyben csak az van. Ehhez előbb meg kell számolnia, hány szó van a tömbben (pointerek tömbje, végén NULL pointer):

Véletlenszerűen választott szó a tömbből:

/* A kapott tömbből (NULL pointer a végén) kiválaszt egy szót,
 * és épít egy egyelemű listát, amelyikben az van. */
SzoLista *veletlenszo(char **szavak) {
   int db;
   for (db = 0; szavak[db] != NULL; ++db)
      ; /* üres - csak megszámolja */
   if (db == 0)
      return NULL;

   int melyik = rand()%db;
   return ujegyszavas(szavak[melyik]);
}

A fenti függvény működése egyszerű: megszámolja a NULL pointerrel terminált tömbben lévő szavakat, utána pedig generál egy véletlenszámot 0 és db-1 között. Végül az annyiadik szó másolatával tér vissza.

Az osszefuz() az első lista végéhez fűzi a másodikat, és visszatér az összefűzöttel. Sem új lista, sem új listaelem nem keletkezik.

/* A két listát összefűzi, és visszaadja az így kapottat.
 * Nem történik új listaelem foglalás. */
SzoLista *osszefuz(SzoLista *egyik, SzoLista *masik) {
    if (egyik == NULL)
        return masik;
    SzoLista *futo;
    for (futo = egyik; futo->kov != NULL; futo = futo->kov)
        ; /* üres */
    futo->kov = masik;
    return egyik;
}
A két lista összefűzése

A függvény működése a következő:

  • Ha az első lista üres, akkor az összefűzött lista a második lista. (Függetlenül attól, hogy az mit tartalmaz.)
  • Ha nem üres, akkor meg kell keresni a legutolsó elemét, és annak NULL értékű kov pointerét beállítani a másik lista elejére. Ezután vissza is lehet térni az előbbi lista elejére mutató pointerrel.

A függvény visszatérési értékét el kell tárolni, ugyanis az az összefűzött mondatra mutató pointer. Mivel új listaelemek nem keletkeznek, az egyik és a másik listákat később nem kell majd felszabadítani, csak a keletkezőt! Tulajdonképp a két bemeneti lista megszűnik önálló életet élni, és csak az összefűzött lista fog létezni.

Elem törlése, rendezve építés

15. Elem törlése listából I.

A törlés problémái nagyon hasonlóak a beszúrásnál látottakhoz: (i) ha a lista első elemét törüljük, módosítani kell az „eleje” pointert, (ii) ha középről kell törölnünk, akkor szükség van egy lemaradó pointerre a mutatók megfelelő átállításához.

Törlés lista belsejéből:

  1. megkeressük a törlendő elemet,
  2. felszabadítjuk,
  3. az előtte lévő kov pointerét az utána lévőre állítjuk. ?!
Törlés a listából

Gond a 3. ponttal: amelyik elemet megtaláljuk így, az azelőtti elemet kell módosítani. Hátrafelé haladni pedig nem tudunk.

16. Elem törlése listából II.

Ötlet: két mutatót mozgatunk végig a listán!

Törlés a listából: lemaradó pointer
lemaradó ptr
(inchworm)
lemarado = NULL; mozgo = eleje;
while (mozgo != NULL && mozgo->adat != keresett) {
   lemarado = mozgo; mozgo = mozgo->kov;
}

A „mozgó” pointerrel vizsgáljuk az elemek értékét, a „lemaradó” pointer mindig eggyel lemaradva követi a „mozgót”.

A ciklusban kihasználjuk a logikai rövidzárat. Akkor megyünk tovább a listában, ha nem értük el még a végét és az aktuális elem nem a keresett. Ha elértük a lista végét, akkor „mozgó” értéke NULL. Ha ilyenkor kiértékelődne az ÉS kapcsolat második fele is, akkor az hibát okozna, hiszen egy NULL pointer értékét próbálnánk megvizsgálni! Fontos tehát, hogy az ÉS kapcsolatban először vizsgáljuk meg, hogy elértünk-e a lista végére és csak utána az aktuális elem értékét!

A törlés így már egyszerű:

törlés
lemarado->kov = mozgo->kov;     // törlendő = ahol megállt
free(mozgo);

17. Elem törlése listából III.

/* törlendő elem keresése */
ListaElem *lemarado, *mozgo;
lemarado = NULL; mozgo = eleje;
while (mozgo != NULL && mozgo->adat != /* ... */) {
   lemarado = mozgo; mozgo = mozgo->kov;
}

/* megtalált elem törlése */
if (mozgo == NULL) {           // nincs ilyen elem
   /* nincs teendő */
} else if (lemarado == NULL) { // az első elemet kell törölni
   ListaElem *ujeleje = mozgo->kov;
   free(mozgo);
   eleje = ujeleje;
} else {                       // a közepéről/végéről törlünk
   lemarado->kov = mozgo->kov;
   free(mozgo);
}

Az elem keresése egy lemaradó pointeres bejárást használ. A ciklus után háromszoros esetszétválasztást kell végezni.

  • Ha „mozgó” értéke NULL, akkor vagy üres a lista és rögtön az első iteráció előtt kiléptünk a ciklusból az ÉS kapcsolat első tagja miatt; vagy végigértünk a listán és az utolsó elem sem egyezett meg a keresettel, tehát az nem szerepel a listában. Akármelyik is, nincs mit törölni, ezért nincs teendő.
  • Ha „mozgó” értéke nem NULL, de „lemaradó” igen, akkor az azt jelenti, hogy az első iteráció előtt kiléptünk a ciklusból azért, mert rögtön az első elem megegyezett a keresettel. Ezt a mozgo == eleje feltétellel is ellenőrizhetnénk. Ilyenkor az első elemre mutató pointert át kell állítani az őt követőre, majd törölni kell őt. A törlés előtt egy ideiglenes változóba (ujeleje) el kell menteni a második elem címét, hiszen az első elem felszabadításával elveszítenénk azt, pedig az lesz az új listafej. (Ez ugyanaz a probléma, mint amit a lista felszabadításánál már láttunk.)
  • Ha mindkét pointer egy létező elemre mutat, akkor a lista közepéből, vagy az utolsó elemet kell törölni. Mindkét esetben annyi a teendő, hogy a „lemaradó” által mutatott elem következő pointerét átállítjuk a „mozgó” utánira (ami akár NULL is lehet), majd töröljük azt, amire a „mozgó” mutat. Ilyenkor a lista eleje pointer változatlan.

18. Rendezve építés I.

Gyakran van szükség arra, hogy rendezetten tároljunk adatokat.

  • A tömböknél az adatok rendezett rögzítése nagyon költséges, hiszen mindig odébb kell csúsztatni a beszúrási pozíció utáni elemeket.
  • Listákat könnyű rendezve építeni, hiszen csak a mutatókat kell megfelelően beállítani.

Tömbök esetén egy új elemet mindig a meglévő adatok után szúrunk be és utána rendezünk, listáknál pedig eleve rendezetten építünk és így ott nincs szükség utólagos rendezésre. Ez jó, mert az utólagos rendezés a listáknál még kevésbé hatékony, mint tömböknél.

Beszúrás egy rendezett listába:

  1. Az első elemre állunk a „mozgó” pointerrel.
  2. Amíg az aktuális elem kisebb, mint a beszúrandó, és nem értük el a lista végét, addig mindig továbblépünk a következőre.
  3. A megtalált elem elé beszúrjuk az újat. Látjuk az előzőt?
Beszúrás a listába

A beszúrásnál a megtalált elem elé kell beszúrni: ezt a problémát is megoldhatjuk lemaradó pointerrel!

19. Rendezve építés II.

A beszúrás folyamata a lemaradó pointeres keresés után: a „lemaradó” pointerét átállítjuk az új elemre, az új elem pointerét átállítjuk a „mozgó”-ra.

Beszúrás a listába
/* új elem létrehozása */
ListaElem *uj;
uj = (ListaElem*) malloc(sizeof(ListaElem));
uj->adat = /* ... */;

/* hely keresése */
ListaElem *lemarado, *mozgo;
lemarado = NULL; mozgo = eleje;
while (mozgo != NULL && mozgo->adat < uj->adat) { // hely?
    lemarado = mozgo; mozgo = mozgo->kov;
}

/* beszúrás */    
if (lemarado == NULL) {   // üres vagy első elé?
    uj->kov = eleje;
    eleje = uj;
} else {
    lemarado->kov = uj;   // lista belsejébe/végére
    uj->kov = mozgo;
}

Az alábbi eseteket kell megkülönböztetni a keresés után.

Ha lemarado == NULL:

  • vagy üres volt a lista, vagyis „mozgó” értéke NULL volt (tehát rögtön az első iteráció előtt kiléptünk a ciklusból az ÉS kapcsolat első tagja miatt),
  • vagy az első elem elé kell beszúrni, ezért az ÉS kapcsolat második tagja miatt léptünk ki az első iteráció előtt a kereső ciklusból.

Ilyenkor mindenképp az új elem lesz ezentúl a lista első eleme. Mindkét esetben értelmes az uj->kov = eleje kifejezés, hiszen az vagy NULL, és akkor egy egyelemű listát kapunk, vagy az első elemre mutat és akkor beszúrtunk eléje egy elemet.

Ha lemarado != NULL:

  • Vagy elértük a lista végét (az ÉS kapcsolat első fele miatt léptünk ki a ciklusból) – ekkor mozgo értéke NULL,
  • Vagy valahová a lista közepére szúrunk be, mert az ÉS kapcsolat második fele nem teljesült, tehát megtaláltuk az első elemet, ami nagyobb, mint a beszúrandó (ekkor mozgo értéke nem NULL).

Mindkét esetben át kell állítani a „lemaradó” által mutatott elem „következő” pointerét az új elemre. Továbbá mindkét esetben a „mozgó” lesz az új elem „következő” pointere:

  1. vagy egy listabeli, létező elem,
  2. vagy a NULL pointer, és így az új elem lesz a lista utolsó eleme innentől kezdve.

Duplán láncolt listák

21. Duplán láncolás és strázsák

A listás algoritmusok nehézségei:

  1. csak előrefelé tudunk menni, hátra nem,
  2. lista első eleme problémás,
  3. nem látunk visszafelé, ezért lemaradó pointer kellett.

Ötletek:

  1. Láncoljunk „duplán” (doubly linked list)!
  2. Helyezzünk el egy-egy extra elemet a lista végein (strázsa, sentinel)!
Duplán láncolt lista

22. A duplán láncolt ListaElem és Lista

A lista egy eleme így:

typedef struct ListaElem {
  …

  struct ListaElem *elozo, *kov;
} ListaElem;
Elem pointerei: előző és következő elem

A két strázsára mutató pointert egy struktúrába tesszük, hiszen ezek egy listához tartoznak:

typedef struct Lista {
  ListaElem *elso;
  ListaElem *utolso;
} Lista;
A lista eleje és vége

A két strázsa elem mindig a lista elején és a végén áll, tehát új elem beszúrásakor sosem fordulhat elő, hogy az első elé vagy az utolsó után kéne beszúrni. Így a beszúrás illetve törlés művelete mindig két létező elem között történik, vagyis minden pozíción ugyanazt a műveletet kell végrehajtani. Az algoritmusok sokkal egyszerűbbek, hiszen nem kell felderíteni azt, hogy milyen speciális pozíció az, ahol a műveletet el kell végezni, és nem kell elágazni eszerint. Fontos, hogy a két strázsa nem tartalmaz értelmes adatot, tehát az értelmes adatok listája az eleje („első”) strázsa utáni elemtől a vége („utolsó”) strázsa előtti elemig tart!

23. Mindkét végén strázsás lista: bejárás

A listán végimenni az alább bemutatott módon lehet:

  1. az „első”, vagyis a kezdő strázsa utáni elemtől indulunk,
  2. az „utolsó”, vagyis a záró strázsa előtti elemig megyünk.
/* kiírja a listában található számokat */
ListaElem *mozgo;
for (mozgo = lista->elso->kov;  // 1
     mozgo != lista->utolso;        // 2
     mozgo = mozgo->kov) {
   printf("%d ", mozgo->adat);
}

A lista->elso->kov: a kezdő strázsa utáni, első hasznos elem. Ezt már fel kell dolgozni, innen indul a ciklus. A lista->utolso a záró strázsa elem; ezt már nem kell feldolgozni, vagyis amint a mozgo != lista->utolso feltétel hamis lesz, a ciklus megáll.

24. Duplán láncolt lista: elem törlése

Beszúrás duplán láncolt listába
ListaElem *mozgo;
mozgo = lista->elso->kov;
while (mozgo != lista->utolso && mozgo->adat != adat) {
   mozgo = mozgo->kov;
}

if (mozgo != lista->utolso) { // megvan?
   mozgo->elozo->kov = mozgo->kov;
   mozgo->kov->elozo = mozgo->elozo;
   free(mozgo);
}

Nem kell lemaradó pointer, nem kell a végeken külön figyelni!

A törlésnél szükség van egy feltételvizsgálatra: le kell ellenőrizni, hogy a törlendő elem egyáltalán benne van-e a listában. Ha a „mozgó” pointer az „utolsó”-n áll meg a keresés során, az azt jelenti, hogy nem találta meg a törlendő elemet a listában. Ebben az esetben a kódrészlet nem csinál semmit. A pointer ilyenkor a végstrázsára mutat, amit nem szabad törölni.

25. Duplán láncolt lista: rendezve beszúrás

A duplán láncolt, strázsás listák előnye igazán akkor válik nyilvánvalóvá, amikor egy új elemet kell beszúrni.

  1. Csak egy pointerre van szükség: arra, amelyik elé kerül az új elem.
  2. A beszúrás művelete mindig azonos: a két strázsa is valódi elem.
Beszúrás duplán láncolt listába
/* új elem létrehozása */
ListaElem *uj;
uj = (ListaElem*) malloc(sizeof(ListaElem));
uj->adat=adat;

/* egyszerű keresés, nincs lemaradó pointer */
ListaElem *mozgo;
mozgo = lista->elso->kov;
while (mozgo != lista->utolso && mozgo->adat < adat)
   mozgo = mozgo->kov;

/* tényleges beszúrás */
uj->elozo = mozgo->elozo;  // ő a szomszédaira mutat
uj->kov = mozgo;
mozgo->elozo->kov = uj;    // a szomszédai rá
mozgo->elozo = uj;

A kétszeres láncolás miatt négy pointert kell helyesen beállítani:

  1. az új elem „előző” pointerét,
  2. az új elem „következő” pointerét (vagyis az új elem a szomszédaira mutat),
  3. az új előtti elem „következő” pointerét,
  4. az új utáni elem „előző” pointerét (az új elem szomszédai rá mutatnak).

A keresésnél sincsen szükség lemaradó pointerre, hiszen a megtalált elemből elérjük az előtte lévő elemet is (mozgo->elozo), amelyre az új elemnek mutatnia kell (visszafelé), és amelynek az új elemre mutatnia kell (előrefelé). Ez a művelet helyesen fut le akkor is, ha a lista üres: ilyenkor a „mozgó” pointer a lista végét jelölő strázsa elemre („utolsó”) fog mutatni. Ezen felül, mivel minden listaelem előtt van még egy elem (lehet, hogy az a strázsa, de van), nincsen szükség az esetszétválasztásra, amely külön kezelte a lista elejét és a belsejét. Legvégül pedig, mivel az eleje strázsa mindenképpen első elem marad, a lista elejét mutató pointer sem változik!

26. Speciális listák

sor (FIFO)
verem (LIFO)

fésűs lista (listák listája)
ciklikus lista

Egyenetlen terhelések, illetve eltérő sebességű folyamatok kiegyenlítésére szokás használni ún. pufferként várakozási sorokat (queue, FIFO – first in, first out). Nagy terhelés esetén a kérések a sor elejéhez adódnak hozzá, a kiszolgáló pedig a végéről veszi el őket, tehát a legrébben érkezett fog a legkorábban sorra kerülni. Ilyen módon nem veszik el egy kérés sem, hiszen a lista dinamikus nő, vagy csökken attól függően, hogy éppen a "termelő" vagy a "fogyasztó" oldal dolgozik gyorsabban.

Várakozási sort egyszeresen láncolt listával érdemes megvalósítani, amelynek nem csak az elejére, hanem a végére mutató pointert is eltároljuk. Így könnyű a végére beszúrni egy elemet: mert az utolsó után fűzzük, és a vége pointert az új elemre állítjuk. Illetve könnyű az elejéről is elvenni egyet: az eleje pointert a másodikra állítjuk, az első pedig az, amit épp kiveszünk.

Példa: egy szerverre időben egyenetlenül elosztva érkeznek be a kérések. Előfordulnak üresjáratok és olyan időszakok, amikor nem tudja olyan sebességgel kiszolgálni a kéréseket, ahogy beérkeznek. Másik példa: a nyomtatási sor a számítógépen. A kinyomtatandó oldalakat megjegyzi a gép, és olyan sorrendben küldi a nyomtatónak, ahogyan azok eredetileg a felhasználó által ki lettek nyomtatva.

A verem (stack, LIFO – last in, first out) olyan lineáris adatszerkezet, amelyben új elemet az elejéhez adunk hozzá (push), és a feldolgozandókat is az elejéről vesszük el (pop). Verem megvalósítása legegyszerűbben egyszeresen láncolt listával lehetséges, amelybe az új elemeket a lista elején tesszük, és a kivett elemek is a lista elejéről származnak.

A verem használható például matematikai kifejezések kiértékelésekor átmeneti tárolónak, és általában olyan algoritmusokban, ahol az adatok feldolgozása azok érkezésének fordított sorrendjében történik.

A fésűs lista egy olyan láncolt lista, amelynek elemei láncolt listák. Olyan esetben, amikor az adatok kétszintű hierarchiában helyezkednek el, érdemes fésűs listát használni – főként, ha mindkét szinten rendezett tárolást szeretnénk.

Példa: egy nyelviskola tanulói – a főlista (sárga) egy eleme egy kurzus (pl. „holland haladó”, „hindi kezdő” stb.). Minden óra tartalmaz egy listát (kék), amelynek elemei a kurzuson résztvevő hallgatók.

A ciklikus lista olyan lista, amelyben az „utolsó” elem után újból az első következik (vagyis az utolsó elem „következő” pointere az elsőre mutat).

Példák:

  • Futó programok listája egy operációs rendszerben. Ha foglalkozott az utolsóval, akkor utána megint az elsővel.
  • Sokszög csúcspontjai: az utolsó után az első jön, az első előtt az utolsó.

Érdekes egy ciklikus lista bejárása. Mivel nem mehetünk NULL pointerig (nincs vége a listának), addig kell futnia a ciklusnak, amíg el nem érjük a lista elejét. Egy ilyen feltétel azonban a lista elején is teljesülne. Ahogy leírjuk ezt, egyből észbe is kapunk:

for (iter = eleje; iter != eleje; iter = iter->kov)

Ehelyett például egy hátultesztelő ciklust alkalmazhatunk, hogy biztosítsuk, lefusson legalább egyszer a ciklustörzs, és a feltétel már a második elemet lássa elsőnek. Ekkor azonban az üres listára külön figyelnünk kell bejáráskor is:

if (eleje == NULL) {
    printf("üres a lista!\n");
} else {
    iter = eleje;
    do {
        …
        iter = iter->next;
    } while (iter != eleje);
}

27. Autók a hídon – komplex példa

Feladat: programot írni, amely egy híd előtti közlekedési lámpát vezérel.


A híd teherbírása 20 tonna. Különböző súlyú járművek haladnak át rajta. A lámpát úgy kell vezérelni, hogy egy jármű csak akkor hajthasson fel, ha nem terhelődik túl a híd.

Alább a program top-down megvalósításának részletei láthatóak.

28. Autók a hídon – megvalósítás

Az autók sorban haladnak:

  • Amelyik elsőnek hajt fel a hídra, az hajt le először.
  • Amelyik elsőnek állt be a lámpához, az hajthat fel először.

A választott adatszerkezet: FIFO = várakozási sor.

typedef struct Auto {
   double tomeg;
   struct Auto *kov;
} Auto;
typedef struct Sor {
   Auto *eleje,
        *vege;
} Sor;

Láthatóan teljesen mindegy programozási szempontból, hogy a lámpánál álló sorról vagy a hídról van szó. Mindkettő ugyanúgy várakozási sorként (FIFO) viselkedik, és ugyanazok a műveletek értelmezettek rájuk: beállni a sorba ugyanaz, mint felhajtani a hídra, és zöld jelzésre elhaladni a lámpa mellett (kiállni a sorból) ugyanaz, mint lehajtani a hídról.

Figyelni kell arra is, hogy a sor fordítva van lerajzolva: a sor eleje a rajzon a jobb szélen szerepel, a vége pedig a bal szélen. Programozási szempontból mindegy, hogy a sor egyik végére tegyük az „új” autókat, és másik végéről vegyük el a „feldolgozattakat.”

Ha egy autó várakozik, és szabaddá válik az út, akkor felhajt a hídra:

if (!ures(sor)) {   /* van várakozó autó? */
    if (mehet_e(sor->eleje, hidon)) {    /* elbírja? */
        Auto *a = elejerol(&sor);   /* sorból kivesz */
        vegere(&hid, a);            /* hídra (sorba) betesz */
    }
}

A listakezelő függvényeknél ügyelni kell azokra az esetekre, amikor üres sorba szúrunk be, vagy az elem kivétele által üressé válik a sor. (A kivett/betett autó kov pointerével is kellene foglalkozni, ez most a lenti példa kódokban elmarad.)

vegere(): egy autó sorba állítása

void vegere(Sor *s, Auto *a) {

   if (sor->vege == NULL) {
      sor->eleje = a;
      sor->vege = a;
   } else {
      sor->vege->kov = a;
      sor->vege = a;
   }
}

elejerol(): sorra kerülő autó

Auto *elejerol(Sor *s) {
   Auto *a = s->eleje;
   if (s->eleje == s->vege) {
      s->eleje = NULL;
      s->vege = NULL;
   } else {
      s->eleje = s->eleje->kov;
   }
   return a;
}

mehet_e(): megmondja, hogy egy adott autó felhajthat-e a hídra. Igazzal tér vissza, ha még elbírja (ilyenkor lehet zöld a lámpa).

bool mehet_e(Auto *a, Sor *hidon) {
    return sor_ossztomeg(hidon) + a->tomeg < 20000; /* 20 t */
}

sor_ossztomeg(): összeadja egy sor autóinak tömegét. A híd terhelésének számítására használható.

double sor_ossztomeg(Sor *sor) {
    Auto *iter;
    double ossz = 0;
    for (iter = sor->eleje; iter != NULL; iter = iter->kov)
        ossz += iter->tomeg;
    return ossz;
}

29. Tűzijáték – komplex példa

Letölthető:
tuzijatek.c

Feladat: írjunk programot, amely tűzijátékot rajzol ki!

Fizika: egy kilőtt lövedék mozgása Δt idő alatt:

  • Helyzete: r = r + vΔt
  • Sebessége: v = v + gΔt

A robbanáskor sok apró darab keletkezik, azok ugyanígy mozognak.


Milyen adatszerkezetben tároljuk a rengeteg pontot? A pontok sorrendje nem számít, a számuk viszont nagyon gyorsan változik. Legyen ezért lista! Az új elemeket tetszőleges helyre tehetjük beszúráskor, akár az aktuális elem elé, akár az aktuális elem mögé – ugyanúgy fog kinézni a mozgás. Bejáráskor figyelni kell majd: a lista bejárása közben kell majd hozzáadnunk új elemeket (robbanáskor) és törölni régieket!

typedef enum Tipus { robbano, eltuno } Tipus;

typedef struct Pont {
    Tipus tipus;
    double x, y, vx, vy;
    double elettartam;
    int szin;

    struct Pont *kov;
} Pont;

30. Tűzijáték – pontok kezelése (kódrészlet)

A top-down megvalósítás gondolatmenete, kódrészletei láthatók alább. Az egyes pontokat kezelő ciklus vázlatosan így néz ki:

lemarado = lista;
iter = lista->kov;                   /* strázsát kihagy */
while (iter != NULL) {
   iter->elettartam -= delta_t;
   if (iter->elettartam > 0) {       // még repülhet?
      iter->x += iter->vx*delta_t;   /* fizika: helyzet + sebesség */
      iter->y += iter->vy*delta_t;
      iter->vy += g*delta_t;
      lemarado = iter;
      kovetkezo = iter->kov;
   } else {                          // vége
      if (iter->tipus == robbano)
         for (i = 0; i < 30; i++)    /* 30 darabra robban */
            beszur(iter, uj_eltuno(iter->x, iter->y, iter->szin));
      kovetkezo = iter->kov;         /* ez a ciklushoz kell */
      lemarado->kov = iter->kov;
      free(iter);                    /* törlés */
   }
   iter = kovetkezo;
}

Ez feldolgozza a pontok listájának minden elemét:

  • Ha lejárt az ideje, felrobbanhat. De mindenképpen eltűnik.
  • Ha még nem, akkor mozog a ferde hajítás képlete szerint.

A beszúráskor az aktuális elem után szúrjuk be az új pontokat (így, a ciklus folytatva, egyből fel is dolgozzuk majd őket). Ez azért egyszerűbb így, mivel könnyebb az aktuális elem után beszúrni, mint elé:

A törléshez pedig nyilvántartunk egy „lemaradó” pointert. Mivel az aktuális elem (iter) törölhető, ezért a ciklus nem végződhet iter=iter->kov sorral – a törlés előtt a kov pointert ki kell menteni a törölt elemből:

Figyelni kell a „lemaradó” pointerre is. Ha nem töröljük az aktuális elemet, akkor a következő iterációban a „lemaradó” pointer arra kell mutasson. Ha viszont töröljük, akkor a „lemaradó” pointer értéke nem változik, a következő iterációban még mindig a törölt elem előttire kell mutasson. A felépített lista elején strázsa van, hogy ne kelljen még a lista eleje miatt is külön esetszétválasztást csinálni.

uj_eltuno(): új pontot hoz létre, amely eltűnik, nem pedig robban.

Pont *uj_eltuno(double x, double y, int szin) {
    Pont *uj;
    uj = uj_pont(x, y, rand()%60 - 30, rand()%60 - 30);
    uj->elettartam = 3 + rand()%10/10.0;
    uj->tipus = eltuno;
    uj->szin = szin;
    return uj;
}

Ez a függvény pedig új pontot hoz létre, amely egy robbanáskor keletkezik. Az élettartama és a sebessége véletlenszám. A struktúrában szereplő kov pointert az uj_pont() függvény NULL-ra állítja csak; az később kap értéket, a listába befűzés során.


beszur(): beszúrja a „mit” elemet a „miután” elemet követően.

void beszur(Pont *miutan, Pont *mit) {
    mit->kov = miutan->kov;
    miutan->kov = mit;
}

A fenti függvény az első paraméterében adott listaelem után fűzi a második paraméterében adott listaelemet. Nem tér vissza semmivel, hiszen ezáltal a lista eleje (ami amúgy is strázsás) nem változik.