Gyakorlat, 12. hét: láncolt listák II.

Czirkos Zoltán · 2016.08.28.

Láncolt listák használata algoritmusokban.

Felkészülés a gyakorlatra:

1. A teljes szöveg visszafelé

Az alábbi program beolvas egy szöveget fájl vége jelig, majd kiírja azt visszafelé. Elmélkedjünk rajta, miért!

#include <stdio.h>

void forditva_kiir(void) {
    int c = getchar();
    if (c != EOF) {
        forditva_kiir();
        putchar(c);
    }
}


int main(void) {
    forditva_kiir();
    return 0;
}

Írjunk meg ezt a programot úgy, hogy nem használunk rekurziót, hanem magunk építünk vermet!

Megoldás

A verem tároló lényege, hogy ha beleteszünk egy adatot, az mindig a tetejére kerül, és ha kiveszünk belőle egyet, akkor azt mindig a tetejéről vesszük ki. Amelyik legutoljára bekerült, az jön ki elsőnek (LIFO, last in, first out). Vermet egyszeresen láncolt listából nagyon könnyű csinálni. Ha mindig a lista elejére szúrjuk az új elemet, és mindig a lista elejéről vesszük el, ha ki kell venni egyet, akkor pont vermet kapunk. (Azért érdemes a lista elejét, és nem a végét kezelni ilyen módon, mivel a lista eleje mutató így épp arra mutat, amire kell, nem kell végiglépkedni a lista végéig.)

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>


typedef struct Verem {
    char karakter;
    struct Verem *alatta;
} Verem;


void verembe(Verem **v, char c) {
    Verem *uj = (Verem *) malloc(sizeof(Verem));
    uj->karakter = c;
    uj->alatta = *v;             /* alatta az eddigi legfelso lesz */
    *v = uj;                     /* mostantol ez van a tetejen */
}


char verembol(Verem **v) {
    Verem *elso = *v;            /* az elsot fogjuk eldobni */
    char adat = elso->karakter;  /* kimentjuk a szamot belole */
    *v = elso->alatta;           /* a masodik lesz az elso */
    free(elso);
    return adat;
}


bool verem_ures(Verem **v) {
    return *v == NULL;
}


int main(void) {
    Verem *v = NULL;
    int c;
    
    printf("Kedves draga jo felhasznalo! Irj egy tetszolegesen hosszu szoveget, EOF-ig!\n");
    while ((c = getchar()) != EOF)
        verembe(&v, c);
    
    printf("Kedves draga jo felhasznalo! A szoveged visszafele:\n");
    while (!verem_ures(&v))
        putchar(verembol(&v));

    return 0;
}

2. Hány különböző?

Adott az alábbi struktúrájú, egész számokat tároló láncolt lista:

struct ListaElem {
    int ertek;
    struct ListaElem *kov;
};

Készítsünk programot, amely megszámolja, hogy a listában hány különböző érték van! Az eredeti listát ne változtassuk meg!

Megoldás

Két kézenfekvő megoldás kínálkozik:

  • Építünk egy másik listát, amit halmazként használunk: csak akkor teszünk bele egy számot, ha még nincs benne. Ennek a listának a hossza adja a megoldást.
  • Vagy: végigmegyünk a listán, és minden elemnél megvizsgáljuk, hogy az előtte lévőek között szerepel-e. Ha nem, megnövelünk egy számlálót.

A második bonyolultabbnak hangzik, de egy sokkal rövidebb megoldást ad:

int hany_kulonbozo(ListaElem *eleje) {
    int db = 0;
    ListaElem *iter, *elozo;
    for (iter = eleje; iter != NULL; iter = iter->kov) {
        /* van-e előtte ugyanilyen elem? */
        bool van = false;
        for (elozo = eleje; elozo != iter; elozo = elozo->kov)
            if (elozo->ertek == iter->ertek) {
                van = true;
                break;
            }
        /* ha nincs, bevesszük a számlálásba*/
        if (!van)
            db += 1;
    }
    return db;
}

Az első megoldás, felülről lefelé tervezéssel:

int hany_kulonbozo_2(ListaElem *eleje) {
    ListaElem *uj = NULL;
    ListaElem *iter;
    for (iter = eleje; iter != NULL; iter = iter->kov)
        if (!lista_benne_van_e(uj, iter->ertek))
            lista_betesz(&uj, iter->ertek);
    int db = lista_elemszam(uj);
    lista_felszabadit(uj);
    return db;
}

A segédfüggvényei sokan vannak:

bool lista_benne_van_e(ListaElem *eleje, int ertek) {
    ListaElem *iter;
    for (iter = eleje; iter != NULL; iter = iter->kov)
        if (iter->ertek == ertek)
            return true;
    return false;
}

int lista_elemszam(ListaElem *eleje) {
    int db = 0;
    ListaElem *iter;
    for (iter = eleje; iter != NULL; iter = iter->kov)
        db += 1;
    return db;
}

void lista_betesz(ListaElem **peleje, int ertek) {
    ListaElem *uj;
    uj = (ListaElem*) malloc(sizeof(ListaElem));
    uj->ertek = ertek;
    uj->kov = *peleje;
    *peleje = uj;
}

void lista_felszabadit(ListaElem *eleje) {
    ListaElem *iter = eleje;
    while (iter != NULL) {
        ListaElem *torlendo = iter;
        iter = iter->kov;
        free(torlendo);
    }
}

3. Fésűs lista

Írjunk programot, amelyik tankörszámokat, NEPTUN kódokat, neveket és átlagokat tárol:

13 MZPERX 5.1 Köb Üki

Ez azt jelenti, hogy Köb Üki a 13-as tankörbe jár, MZPERX a kódja és 5.1-es az ösztöndíjátlaga.

Építsünk egy fésűs listát ezekből az adatokból! A „külső” lista legyen a tankörök listája, azokon belül pedig a „belső” listák a hallgatókat tartalmazzák elemekként!

Megoldás

A megoldásban egy fésűs listát kell alkalmazni: kívül a tankörök listája, és mindegyik tankör tartalmaz egy névsort (hallgatók listája).

Minden beolvasott hallgatónál előbb meg kell keresni a tankört (vagy létrehozni, ha még nincs), és utána abba a listába betenni. Mivel a feladat nem határozza meg a sorrendet, egyszerűen az elejére szúrjuk be az adatokat.

#include <stdio.h>
#include <stdlib.h>


/* egy hallgato adatai - lancolt listaban */
typedef struct Hallgato {
    char neptun[6 + 1];     /* a neptun kodja, max 6 */
    char nev[30 + 1];       /* a neve, max 30 */
    double atlag;           /* az atlaga */
    struct Hallgato *kov;
} Hallgato;


/* egy tankor adatai: egy nevsor */
typedef struct Tankor {
    int szam;               /* sorszama */
    Hallgato *nevsor;       /* nevek */
    struct Tankor *kov;
} Tankor;


/* beolvassa a megadott nevu fajlbol az adatokat.
 * visszater egy új Tankor listaval. */
Tankor *tklista_beolvas(void) {
    Tankor *tklista = NULL; /* ez lesz a kimenet */
    Hallgato temp;          /* a fajlbol olvasashoz */
    int tk;

    /* %[^\n] - sztring enterig */
    while (scanf("%d %s %lf %[^\n]", &tk,
                 temp.neptun, &temp.atlag, temp.nev) == 4) {
        Tankor *iter;       /* tankorlista bejarashoz */
        Hallgato *ujh;      /* uj hallgato */

        for (iter = tklista; iter != NULL && iter->szam != tk; iter = iter->kov)
            ;   /* ures, csak keres */
        if (iter == NULL) { /* ha null, nem lett meg, uj kell */
            iter = (Tankor*) malloc(sizeof(Tankor));
            iter->szam = tk;
            iter->kov = tklista;
            iter->nevsor = NULL;
            tklista = iter; /* elejere */
        }
        ujh = (Hallgato*) malloc(sizeof(Hallgato));
        *ujh = temp;        /* minden adatot bemasolunk! */
        ujh->kov = iter->nevsor;
        iter->nevsor = ujh; /* elejere */
    }
    return tklista;
}


/* kilistazza a tankort es a nevsorokat. */
void tklista_listaz(Tankor *tklista) {
    Tankor *tkiter;         /* tankorok iteratora */
    Hallgato *hgiter;       /* hallgatok iteratora */

    for (tkiter = tklista; tkiter != NULL; tkiter = tkiter->kov) {
        printf("%2d. tankor -- \n", tkiter->szam);
        for (hgiter = tkiter->nevsor; hgiter != NULL; hgiter = hgiter->kov)
            printf("%6s %-30s %g\n", hgiter->neptun, hgiter->nev, hgiter->atlag);
    }
}


void tklista_felszabadit(Tankor *tklista) {
    while (tklista != NULL) {
        Tankor *kov = tklista->kov;     /* kimentjuk */

        Hallgato *nevsor = tklista->nevsor;
        while (nevsor != NULL) {
            Hallgato *kov = nevsor->kov;   /* kimentjuk */
            free(nevsor);
            nevsor = kov;
        }

        free(tklista);
        tklista = kov;
    }
}


int main(void) {
    Tankor *tklista;        /* az osszes adat listaja */

    tklista = tklista_beolvas();
    tklista_listaz(tklista);
    tklista_felszabadit(tklista);

    return 0;
}