Gyakorlat, 11. hét extra: láncolt listás gyakorlófeladatok

Czirkos Zoltán · 2020.11.15.

Láncolt listák használata algoritmusokban.

Ez az írás néhány válogatott feladatot tartalmaz. Ezek gyakorlaton és laboron szerepeltek volna, ha a rendkívüli rektori szünet miatt nem maradnak el a 10. heti órák. A listák építését, kezelését lehet gyakorolni ezekkel; nagyon hasonlóak a második ZH feladataihoz.

1. 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. Ez hatékonyabb is, mert a feladat megoldásához nem épít új tárolót:

int hany_kulonbozo(ListaElem *eleje) {
    int db = 0;
    for (ListaElem *iter = eleje; iter != NULL; iter = iter->kov) {
        /* van-e előtte ugyanilyen elem? */
        bool van = false;
        ListaElem *elozo = eleje;
        while (elozo != iter && !van) {
            if (elozo->ertek == iter->ertek)
                van = true;
            elozo = elozo->kov;
        }
        /* 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;
    for (ListaElem *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) {
    for (ListaElem *iter = eleje; iter != NULL; iter = iter->kov)
        if (iter->ertek == ertek)
            return true;
    return false;
}

int lista_elemszam(ListaElem *eleje) {
    int db = 0;
    for (ListaElem *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);
    }
}

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

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!

Házi feladat átírni a programot úgy, hogy fájlt olvasson be. Teszteléshez egy minta: nevsor-utf8.txt, illetve nevsor-latin2.txt.

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 szabvanyos bemenetrol a sorokat.
 * visszater egy uj Tankor listaval. */
Tankor *tklista_beolvas(void) {
    Tankor *tklista = NULL; /* ez lesz a kimenet */
    Hallgato temp;          /* a beolvasashoz */
    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;
}

4. Átszállások

Szöveges fájlokban metrójáratok megállóinak neveit tároljuk, soronként egyet. A nevek maximum 50 betűsek. A programod feladata, hogy láncolt listákba beolvassa a járatok adatait, és megmondja két adott járatról, hogy át lehet-e szállni egyikről a másikra, vagy nem; ha igen, akkor az is kérdés, hogy hol.

  • Írj függvényt, amely paraméterként egy fájlnevet kap, visszatérési értéke pedig egy járat megállóinak listája – a fájlban szereplő sorrendben.
  • Írj függvényt, amely megvizsgál két, paraméterként kapott megállólistát, hogy van-e átszállási lehetőség (azonos megállónév). A függvény visszatérési értéke egy sztring legyen, amely a megálló neve. (Mivel kell visszatérnie a függvénynek, ha nem lehet átszállni?)
  • Egészítsd ki mindezt teljes programmá, amelyben beolvasod az m2.txt és az m3.txt nevű fájlokat! Ha át lehet szállni, írd ki a megálló nevét, ha nem, akkor pedig írd ki azt! Ne felejtsd el felszabadítani a memóriát, amit foglaltál!

Adatok a teszteléshez: m1.txt, m2.txt, m3.txt és m4.txt.

5. Szállóvendégek

Egy hétemeletes szállodában a szobafoglalásokat egy olyan struktúrában tárolják, amely egy egészként tartalmazza a szobaszámot és egy maximum 50 karakteres sztringben a vendég nevét. A szobák a szokásos módon vannak számozva, a százasok helyiértéke adja meg az emeletet, a tízesek és egyesek pedig az adott szinten lévő szoba sorszámát (pl. 712 = 7. emelet, 12. szoba). A földszint a 0. szint.

  • Írj függvényt, amely a paramétereként megadott nevű szöveges fájlból beolvassa a vendégek listáját egy láncolt listába, és visszatér a lista címével! A fájlban az egyes foglalások külön sorban helyezkednek el, a sor elején a szobaszám áll, utána a név. (Hozz létre ilyen szövegfájlt néhány adattal, hogy tesztelni tudj!)
  • Írj függvényt, amely paraméterként kapja a vendégek listáját és a szintek tömbjét; az utóbbi, emelet sorszámával indexelt tömbbe pedig beírja, hogy az egyes emeleteken hány vendég lakik!
  • Írj függvényt, amely megkapja az így keletkezett szintek tömbjét, és visszatér a legzsúfoltabb emelet sorszámával, tehát azzal, ahol a legtöbb vendég van éppen!

Egészítsd ki ezeket teljes programmá, amely a felhasználótól beolvas egy nevet és megmondja, hogy az illető megszállt-e a szállóban a foglalasok.txt szerint, és ha igen, akkor a legzsúfoltabb emeleten van-e a szobája!

Megoldás
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct vendeg {
    int szoba;
    char nev[51];
    struct vendeg *kov;
} vendeg;

vendeg *beolvas(char const *fajlnev) {
    vendeg *lista = NULL, *uj, tmp;
    FILE *fajl;

    fajl = fopen(fajlnev, "rt");
    while (fscanf(fajl, "%d %[^\n]", &tmp.szoba, tmp.nev) == 2) {
        uj = (vendeg *) malloc(sizeof(vendeg));
        uj->szoba = tmp.szoba;
        strcpy(uj->nev, tmp.nev);       /* v. *uj = tmp */
        uj->kov = lista;
        lista = uj;
    }
    fclose(fajl);

    return lista;
}

void betoltottseg(vendeg *lista, int *szintek) {
    vendeg *iter;
    int i;
    for (i = 0; i < 8; ++i)
        szintek[i] = 0;
    for (iter = lista; iter != NULL; iter = iter->kov)
        szintek[iter->szoba / 100] += 1;
}

int legtobb_vendeg(int *szintek) {
    int i, max = 0;
    for (i = 1; i < 8; ++i)
        if (szintek[i] > szintek[max])
            max = i;
    return max;
}

vendeg *keres(vendeg *lista, char const *nev) {
    vendeg *iter;
    for (iter = lista; iter != NULL; iter = iter->kov)
        if (strcmp(iter->nev, nev) == 0)
            break;
    return iter;
}

int main(void) {
    char vendegnev[51];
    vendeg *lista = beolvas("foglalasok.txt");

    scanf("%[^\n]", vendegnev);
    vendeg *talalat = keres(lista, vendegnev);

    if (talalat == NULL) {
        printf("A vendég nincs a szállóban.\n");
    } else {
        int szintek[8];
        betoltottseg(lista, szintek);
        int legzsufoltabb = legtobb_vendeg(szintek);
        if (legzsufoltabb == talalat->szoba / 100)
            printf("A vendég a legzsúfoltabb szinten lakik.\n");
        else
            printf("A vendég nem a legzsúfoltabb szinten lakik.\n");
    }

    while (lista != NULL) {
        vendeg *temp = lista->kov;
        free(lista);
        lista = temp;
    }

    return 0;
}