Labor, 10. hét: 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:

• A listákról szóló előadás átismétlése.

Ha még nem vitted föl a gyakorlaton írt próba ZH pontszámát, tedd meg!

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

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?

Í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!

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!

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

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

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

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

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