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.

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