Labor, 10. hét: láncolt listák

Czirkos Zoltán, Pohl László · 2022.11.03.

Egyszeresen láncolt listák.

A lenti feladatok egyszeresen láncolt, strázsa nélküli listával dolgoznak. Meg kell valósítani az összes alapvető műveletet: bejárás, beszúrás, felszabadítás. Javasolt az összes függvény kidolgozása előtt rajzot készíteni: melyik pointer hova mutat a művelet előtt, és hogyan módosulnak azok a művelet hatására! Így sokkal könnyebb megírni a függvényeket is.

A debugmalloc használata minden dinamikus memóriakezelést igénylő feladatnál inkokolt. Használd a listás feladatoknál is!

Felkészülés a laborra:

1. Memóriakezelési hiba

Az alábbi kódok a gyakorlaton megbeszélthez hasonló memóriakezelési hibát tartalmaz. Mit mond rá a fejlesztőkörnyezet? Mi történik a program működése közben? Van-e különbség az első és a második változat között? Beszéld meg a laborvezetővel!

A compiler a beállított -Werror kapcsolónak köszönhetően a figyelmeztető üzeneteket is hibaként kezeli, és nem is gyártja le a hibás futtathatót. Ezt a kapcsolót átmenetileg kiiktatva lehet csak tesztelni a futásidejű viselkedést. Ne feledkezzünk meg a visszaállításáról, mert − amint ez a példa is mutatja − hasznos.

#include <stdio.h>

int *f1(int i) {
    return &i;
}

int main(void) {
    int *p;
    p = f1(10);
    printf("%d\n", *p);
    printf("%d\n", *p);
    return 0;
}
#include <stdio.h>

int *f1(int i) {
    return &i;
}

int main(void) {
    int x = 10;
    int *p = f1(x);
    printf("%d\n", *p);
    printf("%d\n", *p);
    return 0;
}
Megoldás

A probléma a lokális változó címének visszaadása mindkettőben. A függvényben az érték szerint átvett paraméter lokális változóként viselkedik; a függvényből visszatéréskor meg fog szűnni. Ha a címét visszaadjuk a függvényből, az ott egykor szereplő adatot a hívó már hiába próbálja meg elérni, ez nem definiált működés.

Hogy mi történik ilyenkor, azt nem tudhatjuk. Lehet kiíródik a szám, lehet hogy nem. Az is lehet, hogy a fordító észleli a hibát, és ezért inkább NULL pointert visszaadó kódot generál, mert akkor legalább észrevesszük tesztelés közben.

2. Lista kiírása

Adott a lenti programkód. Ez létrehoz egy dinamikusan foglalt, egyszeresen láncolt, strázsa nélküli listát, amelynek az elejére az eleje pointer mutat. Így néz ki:

#include <stdlib.h>

typedef struct ListaElem {
    int adat;
    struct ListaElem *kov;
} ListaElem;


/* létrehoz egy listát, benne egy csomó számmal */
ListaElem *lista_letrehoz(void) {
    int szamok[] = { 8, 14, 13, 17, 1, 19, 16, 5, 3, 11, 2,
                     15, 9, 10, 6, 22, 4, 7, 18, 27, -1 };
    ListaElem *lis = NULL;

    for (int i = 0; szamok[i] != -1; ++i) {
        ListaElem *u;
        u = (ListaElem*) malloc(sizeof(ListaElem));
        u->kov = lis;
        u->adat = szamok[i];
        lis = u;
    }
    return lis;
}


int main(void) {
    ListaElem *eleje;
    
    eleje = lista_letrehoz();
    
    ....
    
    return 0;   
}

Másold be egy új projektbe a kódot! (A további feladatokat is abban oldd majd meg!) Írj ciklust, amely kiírja a képernyőre a listában tárolt számokat! A képernyőn ezt kell kapjad:

27 18 7 4 22 6 10 9 15 2 11 3 5 16 19 1 17 13 14 8

Miért vannak a listában fordítva a számok, a tömbbeli sorrendhez képest?

3. A lista hossza

Írj kódrészletet, amely meghatározza a lista hosszát! Ennek működését könnyen ellenőrizni tudod, ha az eredményt összehasonlítod a képernyőre kiírt lista elemszámával.

Tedd be ezt a programrészt egy függvénybe, amely paraméterként kapja a listát, és visszatér annak hosszával!

4. A lista felszabadítása

A fenti program memóriaszivárgást tartalmaz. Írj egy ciklust, amely felszabadítja a listát! (Ne használj rekurziót!) Tedd be ezt a programrészt egy függvénybe, amely paraméterként veszi át a listát!

5. Beszúrás a lista elejére

Írj függvényt, amely paraméterként átvesz egy listát és egy egész számot. Szúrja be a függvény a számot a lista legelejére!

Ettől a lista eleje mutató megváltozik. Vagyis azt a függvény visszatérési értékként meg kell adja, vagy esetleg cím szerint kell átvegye. Most válaszd az előbbit:

eleje = lista_elejere_beszur(eleje, 21);

Szúrj be számokat a lista elejére, és írd ki a lista tartalmát! A beszúrt számok természetesen fordítva kell megjelenjenek. Ha működik ez a függvény, akkor a kapott létrehozó függvényt (lista_letrehoz()) már kitörölheted, hiszen van saját listaépítőd.

6. Hozzáfűzés a lista végéhez

Írj függvényt, amely egy paraméterként kapott lista végéhez láncol egy új elemet, amely az ugyancsak paraméterként kapott számot tartalmazza! Figyelj arra, hogy üres lista esetén (vagyis ha NULL pointert kap) is helyesen működjön a függvény! Ebben az esetben megváltozik a lista elejét mutató pointer, ezért a fentihez hasonlóan kell kezelni azt.

7. Keresés a listában

Írj függvényt, amely paraméterként egy listát és egy számot vesz át. Visszatérési értékként pedig egy pointert ad a lista első olyan elemére, amely a számot tartalmazza. Ha nincs ilyen, akkor pedig NULL pointert.

Az összes feladat megoldása
#include <stdlib.h>
#include <stdio.h>


/* a lista egy eleme: */
typedef struct ListaElem {
    int adat;               /* Maga az adat */
    struct ListaElem *kov;  /* Pointer a következő elemre */
} ListaElem;


/* lista kiírása kiírása */
void lista_kiir(ListaElem *eleje) {
    ListaElem *p;
    for (p = eleje; p != NULL; p = p->kov)
        printf("%d ", p->adat);
    printf("\n");
}

/* Lista felszabadítása */
void lista_free(ListaElem *eleje) {
    ListaElem *p = eleje;
    /* Végigmegyünk a listán */
    while (p != NULL) {
        /* Ha csak simán azt mondanánk hogy free(p); akkor elveszne a következő */
        /* elemre a pointer, nem mondhatnánk azt hogy: p=p->kov;  */
        ListaElem *tmp = p->kov; /* Ezért eltároljuk a következő elem címét */
        free(p); /* Most már törölhetjük az adott elemet */
        p = tmp; /* Folytassuk a következőtől */
    }
}

/* Adat beszúrása a lista elejére */
ListaElem *lista_elejere_beszur(ListaElem *eleje, int mit) {
    ListaElem *uj = (ListaElem *) malloc(sizeof(ListaElem)); /* Új elem */
    uj->adat = mit; /* Adat bemásolása */
    uj->kov = eleje; /* Az új elem után jön az eddigi lista (akkor is jó, ha üres volt eredetileg) */
    return uj; /* A lista eleje ez az elem lesz */
}

/* Adat beszúrása a lista végére */
ListaElem *lista_vegere_beszur(ListaElem *eleje, int mit) {
    ListaElem *uj = (ListaElem *) malloc(sizeof(ListaElem)); /* Új elem */

    uj->adat = mit; /* Adat bemásolása */
    uj->kov = NULL; /* Ez lesz a lista vége, ezért NULL a következő elem */
    if (eleje == NULL) {
        return uj; /* Ha üres a lista, akkor ez lesz az eleje */
    } else {
        ListaElem *p = eleje; /* Elmegyünk az utolsó elemig (aminek a pointere NULL pointer) */
        while (p->kov != NULL) p = p->kov;
        p->kov = uj; /* És hozzáfűzzük */
        return eleje;
    }
}

/* Lista hosszának kiszámolása */
int lista_hossz(ListaElem *eleje) {
    /* Végigmegyünk a listán és számoljuk az elemeket */
    int hossz = 0;
    ListaElem *p = eleje;
    while (p != NULL) {
        hossz++;
        p = p->kov;
    }
    return hossz;
}

/* Keresés a listában */
ListaElem *lista_keres(ListaElem *eleje, int mit) {
    ListaElem *p;
    for (p = eleje; p != NULL; p = p->kov)
        if (p->adat == mit)
            return p;
    return NULL;
}


/* főprogram */
int main(void) {
    ListaElem *eleje = NULL;

    eleje = lista_vegere_beszur(eleje, 66);
    eleje = lista_elejere_beszur(eleje, 55);
    eleje = lista_vegere_beszur(eleje, 77);
    eleje = lista_elejere_beszur(eleje, 44);
    eleje = lista_elejere_beszur(eleje, 33);
    eleje = lista_elejere_beszur(eleje, 22);
    eleje = lista_elejere_beszur(eleje, 11);
    lista_kiir(eleje);
    printf("\nHossz: %d\n", lista_hossz(eleje));

    ListaElem *tal = lista_keres(eleje, 44);
    if (tal != NULL)
        printf("%d\n", tal->adat);
    else
        printf("nincs ilyen\n");

    lista_free(eleje);

    return 0;
}

8. További feladatok

Ha elkészültél, folytasd a feladatgyűjtemény ehhez a témakörhöz kapcsolódó feladataival!