Dinamikus adatszerkezetek I. – Listák

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.

Pont *csucsok;

csucsok = (Pont*) malloc(sizeof(Pont)*6);
csucsok[5].x = 12;
csucsok[5].y = 17;

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 az 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: 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! Csak az első elem címét kell tudni, a többihez sorban lépdelve el lehet jutni. Így minden elem kiegészül egy mutatóval, ami 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.

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.

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

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)
5. …

Az utolsó elemben lévő cím NULL: ezzel a speciális értékkel jelezzük, hogy nincsen további elem a listában.

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

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.

ListaElem *eleje = NULL; // üres lista

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

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

A lista elejére kerül az új elem, ezért pont annak a címével tér vissza.

Ha ezt nem tároljuk el az új címet, akkor az elem elveszik! Ezért a visszatérési értékét eldobni nagyon súlyos hiba!

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

Elsőre azt gondolhatnánk, hogy ha hátulra szúrunk be, akkor az „eleje” mutató nem változik. Ez így nem igaz! Üres listában a hátulra fűzéstől változik 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. Nevezetesen, hogy vissza kell térnie ennek is az esetlegesen megváltozott lista eleje pointerrel.

C függvény

/* Új elemet helyez el a lista végén, és
 * visszatér a megváltozott lista eleje mutatóval. */
ListaElem *vegere_fuz(ListaElem *eleje, int adat) {
   ListaElem *mozgo, *uj;

   uj=(ListaElem*) malloc(sizeof(ListaElem));
   uj->adat=adat;
   uj->kov=NULL;

   if (eleje==NULL)     // üres lista?
      return uj;

   for (mozgo=eleje; mozgo->kov!=NULL; mozgo=mozgo->kov)
      ; /* üres ciklus */
   mozgo->kov=uj;

   return eleje;
}

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.

El kell tárolni a törölt elemből a „következő” mutatót, hiszen a törlés után még szükségünk van rá a következő elemre lépéshez:

ListaElem *eleje = ………;

while (eleje!=NULL) {
   ListaElem *temp=eleje->kov; // második elem
   free(eleje);
   eleje=temp;
}

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. Döntsük el, milyen adatszerkezetben tárolhatók a mondatok!
2. Specifikáljuk, milyen a helyes mondat!
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.)

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!

Egyszavas mondat létrehozása

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

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

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

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

/* 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, melyik;

   for (db=0; szavak[db]!=NULL; ++db)
      ; /* üres - csak megszámolja */
   if (db==0)
      return NULL;

   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.

/* 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) {
    SzoLista *futo;
    if (egyik==NULL)
        return masik;
    for (futo=egyik; futo->kov!=NULL; futo=futo->kov)
        ; /* üres */
    futo->kov=masik;
    return egyik;
}

Rendezve építés, törlés

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 továbblépünk a következőre.
3. A megtalált elem elé beszúrjuk az új elemet. ?!

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!

for (lemarado=NULL, mozgo=eleje;
     mozgo!=NULL && mozgo->adat<uj->adat;
     lemarado=mozgo, mozgo=mozgo->kov)
  ; /* üres */

A „mozgó” pointerrel vizsgáljuk az elemek értékét, a „lemaradó” pointer mindig eggyel lemaradva követi a „mozgót”. A for 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 kisebb a beszúrandónál. 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=uj; /* „lemaradó” után */
uj->kov=mozgo;    /* „mozgó” elé */

/* Rendezett listába új elemet szúr be. Visszatér az új
   lista eleje mutatóval, ami változhatott. */
ListaElem *rendezve(ListaElem *eleje, int adat) {
   ListaElem *lemarado, *mozgo, *uj;
   uj=(ListaElem*) malloc(sizeof(ListaElem));
   uj->adat=adat;

   for (lemarado=NULL, mozgo=eleje;    // hely megkeresése
        mozgo!=NULL && mozgo->adat < uj->adat;
        lemarado=mozgo, mozgo=mozgo->kov)
      ; /* üres */
   if (lemarado==NULL) { // üres vagy első elé szúrunk be?
      uj->kov=eleje;
      return uj;
   } else {              // lista belsejébe/végére szúrunk be
      lemarado->kov=uj;
      uj->kov=mozgo;
      return eleje;
   }
}

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. a „lemaradó” elem pointerét átállítjuk a „mozgót” követőre
2. töröljük a „mozgó” pointer által mutatott elemet.

lemarado->kov=mozgo->kov; // 1

free(mozgo);              // 2

/* Adott elemet töröl. Visszatér az új eleje mutatóval. */
ListaElem *torol(ListaElem *eleje, int adat) {
   ListaElem *lemarado, *mozgo;

   for (lemarado=NULL, mozgo=eleje;      // törlendő elem keresése
        mozgo!=NULL && mozgo->adat != adat;
        lemarado=mozgo, mozgo=mozgo->kov)
     ; /* üres */

   if (mozgo==NULL)      // üres vagy nincs ilyen elem?
      return eleje;
   if (lemarado==NULL) { // első elemet kell törölni?
      ListaElem *ujeleje=mozgo->kov;
      free(mozgo);
      return ujeleje;
   } else {              // a lista közepéről/végéről törlünk
      lemarado->kov=mozgo->kov;
      free(mozgo);
      return eleje;
   }
}

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;
  struct ListaElem *kov;
} ListaElem;

Érdemes a két strázsára mutató pointert egy struktúrában tárolni:

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őttiig tart!

A listán végimenni az alábbi 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. */
void kiir(Lista *lista) {
   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.

void torol(ListaElem *torlendo) {
   torlendo->elozo->kov=torlendo->kov;
   torlendo->kov->elozo=torlendo->elozo;

   free(torlendo);
}

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

/* megadott adat első előfordulását törli */
void torol(Lista *lista, int adat) {
   ListaElem *mozgo;

   for (mozgo=lista->elso->kov;
        mozgo!=lista->utolso && mozgo->adat != adat;
        mozgo=mozgo->kov)
      ; /* üres ciklus */

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

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ó függvény

/* új elemet szúr a rendezett listába */
void rendezve_beszur(Lista *lista, int adat) {
   ListaElem *mozgo, *uj;

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

   /* Egyszerű keresés, nincs lemaradó pointer */
   for (mozgo=lista->elso->kov;
        mozgo!=lista->utolso && mozgo->adat < adat;
        mozgo=mozgo->kov)
       ; /* üres ciklus */

   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.

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 → duplán láncolt lista strázsákkal

typedef struct Auto {
   double tomeg;
   struct Auto *elozo, *kov;
} Auto;

typedef struct Sor {
   Auto *eleje,
        *vege; /* strázsák */
} Sor;

Hogy a lámpánál álló sorról vagy a hídról van szó, az programozási szempontból mindegy. Mindkettő ugyanúgy 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. Az „előző” és „következő” pointereknél is fogalmazhatunk fordítva. Programozási szempontból mindegy, hogy a két szópár jelentését megfordítjuk-e, mert ugyanazt az eredményt kapjuk. Lényeg, 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->kov, hid)) {    /* elbírja? */
        Auto *a=elejerol(sor);      /* sorból kivesz */
        vegere(hid, a);             /* hídra (sorba) betesz */
    }
}

void vegere(Sor *s, Auto *a){
    a->elozo=s->vege->elozo;
    a->kov=s->vege;
    s->vege->elozo->kov=a;
    s->vege->elozo=a;
}

Auto *elejerol(Sor *s) {
    Auto *a=s->eleje->kov;
    a->kov->elozo=a->elozo;
    a->elozo->kov=a->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).

int mehet_e(Auto *a, Sor *hid) {
    return sor_ossztomeg(hid) + 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->kov; iter!=sor->vege; 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 repül, egyszer csak felrobban.

• A mozgása Δt idő alatt:
  • A helyzete: x = x + vΔt
  • A 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 tárolás láncolt listában. De figyelni kell: új elemek létrehozása, törlések – a lista bejárása közben!

typedef enum Tipus { robbano, eltuno } Tipus;

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

    struct Pont *kov;
} Pont;

Halmaz? A pontok sorrendje nem számít, így pl. az új elemeket tetszőleges helyre tehetjük. Ahogy egyszerű az algoritmus!

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;
      kovetkezo=iter->kov;
      lemarado=iter;
   } else {
      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;
}

A ciklus 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 egyből fel is dolgozzuk majd őket a ciklus folytatva). 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.

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.

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 pointerrel egyelőre nem csinál semmit, mivel a listába ez a függvény nem fűzi még be az elemet.