Gyakorlat, 8. hét: dinamikus tömbök I.

Czirkos Zoltán · 2019.10.26.

Dinamikus memóriakezelés. Dinamikusan foglalt tömbök.

Felkészülés a gyakorlatra:

1. Negyedik kis ZH

Ezen az órán van a negyedik kis ZH.

2. Hol a hiba?

Az alábbi kódrészletek mindegyike legalább egy, de lehet hogy több helyen is, hibás. Miért? Ne csak a hibára mutassunk rá, hanem magyarázzuk meg a hibát! Miért nem lehetséges, hogy működjenek a programkódok? Mi az elvi akadály? Vagy működnek, csak más baj van? Hogyan lenne javítható?

int *fv(void) {
    int i = 2;
    return &i;
}
Megoldás

A változó meg fog szűnni a függvényből visszatérés után. Hiába adjuk vissza a címét, a hívó már nem használhatja azt semmire – dangling pointer. Ha csak a változó értékére vagyunk kíváncsiak, adjuk vissza azt: int, és return i.

int *fv(void) {
    int tomb[100];
    tomb[0] = 2;
    return tomb;
}
Megoldás

Ugyanaz a hiba, mint az előbb. Nem a tömböt adjuk vissza, csak a tömb kezdőcímét – a visszatérés pillanatában azonban a tömb kitörlődik a memóriából, a helye felszabadul. Ezért a hívó használhatatlan pointer kapna. Javítani kétféleképpen lehet. A hívó is lefoglalhatja a tömböt:

void fv(int *tomb) {
    tomb[0] = 2;
}

int tomb[100];
fv(tomb);

Vagy dinamikus memóriakezeléssel, ilyenkor a meghívott függvény foglalja a tömböt:

int *fv(void) {
    int *tomb;
    tomb = (int*) malloc(sizeof(int) * 100);
    tomb[0] = 2;
    return tomb;
}

3. Mindentegybevéve

A feladat ismert lehet egy régebbi gyakorlatról: adott egy sztring, amelyből ki kell szűrni a szóközöket. Az előállított sztringben „mindenegybeleszírva”. Oldjuk ezt meg úgy, hogy a függvény visszatérési értéke az új sztring! (Tehát se a meglévő karaktertömb módosításáról, se egy meglévő karaktertömbbe írásról most nem lehet szó.)

Honnan fogja tudni a hívó, hogy milyen hosszú lett a kapott karaktertömb?

Mutassunk példát a függvény használatára!

Megoldás

A dinamikus memóriakezelésnek itt két előnye is jól jön számunkra. Egyik, hogy a függvényből vissza tudunk adni olyan tömböt, amelyet annak belsejében foglaltunk le. Ennek dinamikusnak kell lennie, különben megszűnne visszatéréskor. A másik, hogy a tetszőlegesen nagy tömb méretét futási időben megadhatjuk.

Kétszer megyünk végig a tömbön: egyszer azért, hogy megszámoljuk, hány nem szóköz karakter van, másodszor pedig azért, hogy az addigra lefoglalt tömbbe a karaktereket átmásoljuk.

A szóköztelenítő függvény NULL értéke jelezheti a hibát, a malloc()-hoz hasonlóan.

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

char *szokoztelenit(char const *mit) {
    int nemszokoz = 0;
    for (int i = 0; mit[i] != '\0'; ++i)
        if (mit[i] != ' ')
            nemszokoz += 1;
    
    char *str = (char*) malloc(sizeof(char) * (nemszokoz+1));
    if (str == NULL)
        return NULL;    /* :( */
    
    int j = 0;
    for (int i = 0; mit[i] != '\0'; ++i)
        if (mit[i] != ' ')
            str[j++] = mit[i];
    str[j] = '\0';
    
    return str;
}

int main(void) {
    char *egybeirva = szokoztelenit("hello vilag alma korte");
    if (egybeirva == NULL) {
        printf("hiba történt, nincs szóköztelenített sztring");
    } else {
        printf("%s", egybeirva);
        free(egybeirva);
    }
    
    return 0;
}

4. Az átlagnál kisebbek

Írjunk függvényt, amelyik egy paraméterben kapott double tömbből kiválogatja az átlagnál kisebb elemeket, és egy újonnan lefoglalt dinamikus tömbbe rakja azokat!

Honnan fogja tudni a hívó, hogy milyen hosszú lett a kapott tömb? Oldjuk meg ezt a következőképp: az új tömb címével és méretével térjen vissza a függvény cím szerint átadott paraméterben! A visszatérési értéke legyen IGAZ, ha sikerült a művelet, és HAMIS, ha nem.

Mutassunk példát a függvény használatára! Készítsünk ábrát a főprogram és a függvény lokális változóiról, illetve a dinamikusan foglalt memóriaterületekről abban a pillanatban, amikor épp visszatérni készül a függvény!

Megoldás

A gondolatmenet: double tömböt kell foglalnunk, és abba az elsőből válogatnunk. De mekkorát? Azt a foglalás előtt még meg kell számolni, mint az előző feladatban! Vagyis:

  1. átlag számítása,
  2. keresett elemek számlálása (mert most már tudjuk az átlagot),
  3. foglalás (mert most már tudjuk a méretet),
  4. keresett elemek másolása (mert most már van hova másolni).

Koncentráljunk a nyelvi elemekre! A double **ujtomb ijesztőnek tűnhet. De nincs itt semmi újdonság: a tömböt pointerével és méretével vesszük át, az új tömböt pointerével és méretével adjuk vissza. Mivel a függvény által módosított double* változót cím szerint kell átvenni, az ujtomb paraméter double** típusú. Lásd a hívás helyét a főprogramban.

A memóriaképen sárgával az alsó sorban a main() függvény lokális változói láthatóak. A középső sorban kékkel a valogat() függvény lényeges lokális változói sorakoznak. Legfelül zöld szín a dinamikusan foglalt területet jelöli.

A main() függvény uj nevű változója egy pointer. Erre mutat rá a valogat() függvény ujtomb nevű változója. Ezért is lett annak double ** a típusa, ahogy arról fentebb már szó esett. Mindkettő uj nevű változó a dinamikus tömbre mutat; a main() függvény uj és db nevű változójának is a valogat() ad értéket.

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

bool valogat(double *eredeti, int meret, double **ujtomb, int *ujmeret) {
    /* átlag meghatározása */
    double sum = 0;
    for (int i = 0; i < meret; ++i)
        sum += eredeti[i];
    double atlag = sum/meret; 

    /* darabszám (tömbméret) meghatározása */
    int db = 0;
    for (int i = 0; i < meret; ++i)
        if (eredeti[i] < atlag)
            ++db;            

    double *uj = (double *) malloc(sizeof(double) * db);
    if (uj == NULL)
        return false;

    int ide = 0;
    for (int i = 0; i < meret; ++i)
        if (eredeti[i] < atlag)
            uj[ide++] = eredeti[i];

    *ujtomb = uj;
    *ujmeret = db;
    return true;
}


int main(void) {
    double szamok[5] = {3.4, 8.5, 4.6, 9.1, 1.2};

    double *uj;
    int db;
    valogat(szamok, 5, &uj, &db);
    /* itt ellenőrizni kellene, sikerült-e a foglalás... */
    for (int i = 0; i < db; ++i)
        printf("%g ", uj[i]);
    free(uj);

    return 0;
}