11. gyakorlat: láncolt listák

Tudjuk, hogy a számokat el kell tárolni, mivel csak a legutolsó szám után derül ki az, hogy melyeket kell kiírni. A „tetszőlegesen sok” miatt listát kell alkalmaznunk. Kérdés, hogy egyszeresen vagy kétszeresen láncolt kell legyen. Mivel a kiírás sorrendje nem kötött, válasszunk egy egyszeresen láncolt listát, annak is a legegyszerűbb beszúró függvényét: a lista elejére beszúrást!

A fentiek alapján a lista:

typedef struct Szam {
   int szam;
   struct Szam *kov;
} Szam;

A főprogram szinte nem különbözik attól, mintha tömbbel csinálnánk:

int main() {
   Szam *lista=NULL, *iter;
   int beolv;
   double atlag;

   scanf("%d", &beolv);
   while (beolv!=0) {
      lista=elejere(lista, beolv);
      scanf("%d", &beolv);
   }

   atlag=listaatlag(lista);

   for (iter=lista; iter!=NULL; iter=iter->kov)
      if (iter->szam<atlag)
         printf("%d ", iter->szam);

   felszabadit(lista);

   return 0;
}

Ha nem használnánk külön változót a beolvasott számnak, hanem egyenesen a listába szeretnénk beolvasni, akkor itt most nagy bajban lennénk. Ugyanis a beolvasás előtt már létre kellene hozni egy listaelemet, amit aztán ki kellene törölni, ha nullát olvastunk be.

A listába beszúrás: mindig az elejére tesszük az új számot (ezért amúgy fordított sorrendben lesznek benne):

/* uj elemet szur be a megadott lista elejere.
 * visszater az uj, megvaltozott lista eleje
 * mutatoval. a hasznalata:
 * l = beszur(l, 5);
 */
Szam *elejere(Szam *lista, int szam) {
   Szam *uj=(Szam*) malloc(sizeof(Szam)); /* 1 */
   uj->szam=szam;
   uj->kov=lista;                         /* 2 */
   return uj;                             /* 3 */
}

A lista elemeinek átlaga végülis ugyanolyan, mintha tömbünk lenne. Csak itt meg is kell számolnunk az elemeket:

/* a megadott listan levo szamok atlagat adja */
double listaatlag(Szam *lista) {
   Szam *iter;
   double szum=0;
   int db=0;

   for (iter=lista; iter!=NULL; iter=iter->kov) {
      szum+=iter->szam;
      db++;
   }
   return szum/db;   /* double/int oke */
}

A teljes program letölthető ide kattitva: szamoklistaban.c.

Ez könnyű, hiszen beszúrni egy adott elem után könnyen tudunk. Végigmegyünk a listán, ha az páros, akkor beszúrunk utána egy nullát és saját magát. Vigyázat, két buktató is van! Ha ilyen sorrendben tennénk, akkor fordított lenne az eredmény – vagyis előbb saját magát, és utána a nullát kell beszúrni. (Ehhez inkább külön változókat használ a lenti kód.) Figyelni kell arra is, hogy a beszúrás után az iterátort léptessük, nehogy a következő körben megtaláljuk a nullát vagy a beszúrt számot (hiszen ezek is párosak). Kettővel léptetjük előre, ezáltal olyan állapotot előidézve, mintha a ciklusváltozó a beszúrt elemre mutatna.

/* A listában minden páros szám után beszúr egy nullát,
 * és még egyszer magát a számot.
 */
void lista_202(Szam *lista) {
   Szam *iter;

   for (iter=lista; iter!=NULL; iter=iter->kov)
      if (iter->szam%2==0) {
         Szam *ujszam, *ujnulla;
         ujszam=(Szam*) malloc(sizeof(Szam));
         ujszam->szam=iter->szam;
         ujszam->kov=iter->kov;
         ujnulla=(Szam*) malloc(sizeof(Szam));
         ujnulla->szam=0;
         ujnulla->kov=ujszam;
         iter->kov=ujnulla;
         /* 2-t ugrunk, es utana meg jon a 3. ugras */
         iter=iter->kov->kov;
      }
}

Az 1-2. lépést, vagyis a szám és a pointer másolását összevonhatnánk egy lépésbe:

*ujszam = *iter;

Struktúra értékadással, ugyanis mind a számot, mind a pointert, vagyis az egész struktúrát másoljuk ott.

A teljes program letölthető innen: lista202.c.

Itt figyelnünk kell arra, hogy előfordulhat, a lista első elemét kell törölni. Ilyenkor pedig a lista eleje mutató is megváltozhat. A következő további esetek lehetségesek:

• Miután töröltük az első elemet, lehet hogy a második elem is négybetűs. Ekkor azt is törölni kell. Viszont az az első helyre került – vagyis az első elem vizsgálata nem csak egy feltétel, hanem egy ciklus. Amíg a lista elején négybetűs van, addig töröljük azt.
• Mindeközben elfogyhat a lista – hiszen lehet az is, hogy csak négybetűs szavakat tartalmazott. Sőt az is, hogy eleve üres volt.

Ez a ciklus így néz ki:

while (lista!=NULL && strlen(lista->szo)==4) {
   Szo *torlendo=lista;
   lista=torlendo->kov;
   free(torlendo);
}

Itt kihasználjuk az && operátor rövidzár tulajdonságát. Ha a pointer NULL, akkor már a lista->szo kifejezés ki sem értékelődik, hiszen az egész kifejezés értéke csak HAMIS lehet. Ez fontos, hiszen ez biztosítja azt, hogy ne dereferáljuk a NULL pointert! Emiatt a kifejezés két oldala nem cserélhető meg!

Ezután két eset lehetséges:

• A lista üressé vált, és nincs további teendőnk.
• A lista nem lett üres, amely esetben azonban az elején biztosan nem négybetűs szó van. Az már meg fog maradni, így a lista elejét mutató pointer nem módosul tovább.

Mivel minden törlendő elemet megelőző pointerét kell módosítani a törlésnél, így vagy azt keressük meg, hogy mely elemeknél kell törölni a következőt, vagy lemaradó pointert használunk. Alább a lemaradó pointeres megoldás látható. Figyelni kell, ha egy adott elemet törlünk, akkor a lemaradó pointer nem mozdul, hanem csak az iter! Amúgy pedig együtt mozognak. A programrész:

if (lista!=NULL) {
   Szo *lemarado=lista;
   Szo *iter=lista->kov;

   while (iter!=NULL) {
      Szo *kovetkezo=iter->kov;

      if (strlen(iter->szo)==4) {
         lemarado->kov=kovetkezo;  /* 1 */
         free(iter);               /* 2 */
      } else
         lemarado=iter;
      iter=kovetkezo;              /* 3 */
   }
}

A teljes program letölthető innen: torles11.c.

Ez egyszerűbb, mint gondolnánk. Ha mindig a lista elejéről elveszünk egy elemet, és a megfordított lista elejére betesszük azt, akkor a lista éppen megfordul! Az eredeti lista szép lassan elfogy, és mikor ez megtörténik, akkor a keletkező lista kész.

/* Megfordit egy parameterkent kapott listat, es visszater
 * a megforditott valtozattal.
 * Vigyazat, az eredeti lista elveszik! A fuggveny nem uj
 * listat epit, hanem az eredeti lista elemeinek felhasznalasaval
 * epiti az uj listat. Igy a kapott pointert erdemes az eredeti
 * lista eleje pointerbe visszairni:
 *   szamok = lista_megfordit(szamok);
 */
Szam *lista_megfordit(Szam *lista) {
   Szam *eredeti=lista;
   Szam *megforditott=NULL;

   while (eredeti!=NULL) {
      Szam *atrakott=eredeti, *kovetkezo=eredeti->kov;
      atrakott->kov=megforditott;   /* uj elejere be */   /* 1 */
      megforditott=atrakott;                              /* 2 */
      eredeti=kovetkezo;            /* regibol kihagy */  /* 3 */
   }

   return megforditott;
}

A teljes program letölthető innen: listamegfordit.c.