Dinamikus adatszerkezetek I. – Listák

Pont *p1, *p2, *p;

p1 = (Pont*) malloc(sizeof(Pont));
p2 = (Pont*) malloc(sizeof(Pont));

p = p1; // 1

p = p2; // 2

p = (Pont*) malloc(sizeof(Pont)); // 3

A fenti kód elején kettő pontot hozunk létre, és ehhez tartozóan három pointert. Az alsó, jelölt kódsorok jelentését érdemes átgondolni: az értékadás ezekben a sorokban új Pont típusú objektumot tárolni képes memóriaterületet már nem hoz létre. Ehelyett csak egy meglévő pontra mutat rá újabb pointerrel. Az első értékadás után a p-ban és a p1-ben tárolt hivatkozással is a bal oldali pontot érjük el. A második után pedig a p2 és a p ugyanaz, a jobb oldali objektumot látjuk. Ezek egyike sem azt jelenti, mint amit a legalsó sor: az létrehoz egy harmadik Pont tárolására alkalmas területet is.

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

Pont *csucsok;
csucsok = (Pont*) malloc(sizeof(Pont) * 6);
/* ... */
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.

Ö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!

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

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

typedef struct ListaElem {

   … // tetszőleges adat(ok)

   struct ListaElem *kov;
} ListaElem;

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

Az első elemet listafejnek (head, list head) is szokás nevezni. Ennek a címét eltároljuk külön, a többié pedig szép sorban kiolvasható az egyes listaelemekből. Í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.

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

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!

A listán ciklussal tudunk végigmenni:

ListaElem *mozgo;

for (mozgo = eleje; mozgo != NULL; mozgo = mozgo->kov)
    printf("%d", mozgo->szam);

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

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!

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.

Í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;       // !
}

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.

ListaElem *uj;
uj = (ListaElem*) malloc(sizeof(ListaElem)); // 1
uj->adat = /* ... */;

ListaElem *mozgo = eleje;
while (mozgo->kov != NULL)                   // 2
    mozgo = mozgo->kov;
mozgo->kov = uj;                             // 3
uj->kov = NULL; 

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ó!

/* 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 = eleje;
   while (mozgo->kov != NULL)
      mozgo = mozgo->kov;
   mozgo->kov = uj;
}

Mivel a lista elejét mutató pointer megváltozik, ha mindezt függvényként szeretnénk használni, ennek is vissza kell majd térnie azzal.

ListaElem *eleje = NULL; // üres lista

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

Ha egymás után sok elemet kell a lista végéhez fűznünk, az előbbi kódrészlet problémás lehet. Annak mindig meg kell keresnie a lánc végét, ami a lista növekedtével egyre tovább tart.

Ilyenkor megéri egy külön pointert fenntartani, amelyik nem a lista elejét, hanem a végét mutatja. Bár ez bármikor megkereshető lenne az elejéről indulva, ha megvan egy változóban, akkor a hozzáfűzés is elvégezhető azonnal, a lista méretétől függetlenül.

ListaElem *eleje = /* ... */;
ListaElem *vege = /* ... */;

ListaElem *uj = /* ... */;

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

ListaElem *eleje = /* ... */;
ListaElem *vege = /* ... */;

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

/* hozzáfűzés */
if (eleje == NULL) {
    eleje = uj;
    vege = uj;
} else {
    vege->kov = uj;
    vege = uj;
}

Az üres lista esetét természetesen ilyenkor is meg kell különböztetni, mert annak nem csak az első eleme nem létezik, hanem az utolsó sem. Kezdetben a lista elejét és végét mutató pointer is NULL értékű; az első elem hozzáfűzésekor kap mindkettő értéket. Ha nem üres a lista, akkor viszont a végén lévő elemet fogja követni az új; a hozzáfűzés után a vége mutatót is állítjuk. (Most az elágazás mindkét ága a vege = uj értékadással fejeződik be, ezt elég lenne leírni egyszer is – de talán így jobban látszik, hogy mi történik.)

Ennek az algoritmusnak, ötletnek – ti. hogy megjegyezzük mindig azt is, hol van a lista vége –, nagy jelentősége van. Így lehet ugyanis várakozási sort implementálni, ahogy azt a lentebbi autós példában is látni fogjuk.

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);
}

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 *kov = iter->kov; // következő elem
    free(iter);
    iter = kov;
}

Í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.

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!

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.

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.

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:

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;
}

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";
ige       = "fut" | "olvas" | "iszik";

Példa:
névelő, alanyi rész, állítmányi rész
A vidám hallgató gyorsan iszik.

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

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ó */
}

SzoLista *veletlenszo(char **szavak) {
    int db = 0;
    while (szavak[db] != NULL)
        ++db;
    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.

SzoLista *osszefuz(SzoLista *egyik, SzoLista *masik) {
    if (egyik == NULL)
        return masik;
    SzoLista *futo = egyik;
    while (futo->kov != NULL)
        futo = futo->kov;
    futo->kov = masik;
    return egyik;
}

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

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. ?!

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

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

lemarado = NULL;
mozgo = eleje;
while (mozgo != NULL && mozgo->adat != mit) {
    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 törlendő. 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!

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

/* törlendő elem keresése */
ListaElem *lemarado = NULL;
ListaElem *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);
}

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

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?

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

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.

/* hely keresése */
ListaElem *lemarado = NULL;
ListaElem *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;
}

Duplán láncolt listá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)!

A lista egy eleme így:

typedef struct ListaElem {
    …

    struct ListaElem *elozo, *kov;
} ListaElem;

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 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!

/* kiírja a listában található számokat */
ListaElem *mozgo = lista->elso->kov;  // 1
while (mozgo != lista->utolso) {  // 2
    printf("%d ", mozgo->adat);
    mozgo = mozgo->kov;
}

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.

ListaElem *mozgo = lista->elso->kov;
while (mozgo != lista->utolso && mozgo->adat != adat) {
    mozgo = mozgo->kov;
}

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

ListaElem *mozgo = lista->elso->kov;
while (mozgo != lista->utolso && mozgo->adat < adat)
    mozgo = mozgo->kov;

uj->elozo = mozgo->elozo;  // ő a szomszédaira mutat
uj->kov = mozgo;
mozgo->elozo->kov = uj;    // a szomszédai rá
mozgo->elozo = uj;

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.

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)) {
    if (mehet_e(sor->eleje, hidon)) {    /* elbírja? */
        Auto *a = elejerol_kivesz(&sor);
        vegere_betesz(&hid, a);
    }
}

void vegere_betesz(Sor *s, Auto *a) {
   if (sor->vege == NULL) {
      sor->eleje = a;
      sor->vege = a;
   } else {
      sor->vege->kov = a;
      sor->vege = a;
   }
}

Auto *elejerol_kivesz(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;
}

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

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

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;

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;   /* helyzet + sebesség */
      iter->y += iter->vy*delta_t;
      iter->vy += g*delta_t;
      lemarado = iter;
      kovetkezo = iter->kov;
   } else {                          // vége
      for (i = 0; i < 30; i++)       /* 30 darabra robban */
         beszur(iter, uj_eltuno(iter->x, iter->y, iter->szin));
      kovetkezo = iter->kov;
      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.