Labor, 8. hét: dinamikus tömbök

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

Dinamikus tömbök létrehozása és kezelése.

A mai óra célja kettős. Egyrészről a dinamikus memóriakezeléssel foglalkozunk. Másrészről újra elővesszük kicsit a sztringeket (karaktertömböket).

Felkészülés a laborra:

1. Számok visszafelé

Írj programot, amely megkérdezi a felhasználótól, hány darab valós számot olvasson be; aztán elvégzi a számok beolvasását is egy dinamikusan foglalt tömbbe, és végül kiírja őket fordított sorrendben!

Tipp

Ahhoz, hogy ez bárhány darab számra működjön – ne korlátozza a beolvasható számok darabszámát se egy tömb mérete, se a verem mérete –, dinamikus memóriakezelést kell használni. Emlékezz vissza az előadásra: dinamikus memória a malloc() függvénnyel foglalható, amely visszaadja a lefoglalt terület kezdőcímét. Ez tetszőleges típusú pointerré konvertálható, amilyen tömbelemeket szeretnénk. Ha már nincs a memóriaterületre szükségünk, akkor a free() függvénnyel kell felszabadítani azt. A foglalást nyilván azután tudjuk megtenni, hogy a felhasználó megmondta, hány darab számot szeretne megadni.

Megoldás

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

int main(void) {
    int db;
    printf("Hany szam lesz?\n");
    scanf("%d", &db);

    double* szamok = (double*) malloc(sizeof(double) * db); // !
    if (szamok == NULL) {
        printf("Nem sikerult a memoria foglalasa.\n");
        return 1;
    }

    printf("Ird be a(z) %d szamot:\n", db);
    int i;
    for (i = 0; i < db; ++i) {
        scanf("%lf", &szamok[i]);                           // !
    }

    for (i = db-1; i >= 0; --i) {
        printf("%g\n", szamok[i]);
    }

    free(szamok);                                           // !

    return 0;
}

2. Számok visszafelé – újra

Hogy nézne ki az előző program, ha nem lehetne előre tudni, hány darab szám lesz? Vagyis ha nem előre adott hosszúságú sorozatot, hanem végjeles sorozatot (pl. utolsó szám után -1) kellene beolvasni? Írd meg így is a programot, minden új számnál megnyújtva a tömböt!

Tipp

Ha nem tudjuk előre, hány elem lesz, nem tudjuk előre lefoglalni nekik a memóriaterületet. Ezért jobb híján, legalábbis jelenlegi tudásunk szerint, kénytelenek vagyunk minden szám beolvasása után megnyújtani a tömböt. Ennek lépései:

  1. Új tömb foglalása.
  2. Meglévő számok átmásolása.
  3. Régi tömb felszabadítása.
  4. Új szám sor végéhez fűzése.

Ne feledd, a pointerek tetszőlegesen beállíthatók bármelyik dinamikusan foglalt tömbre! A lényeg, hogy egy foglalt terület címét sose veszítsük el – ha elveszítjük, sehogy nem fogjuk többé elérni az ott tárolt adatokat, és felszabadítani sem tudjuk már.

Megoldás

Csak a beolvasó rész módosul; természetesen összeolvad a memóriafoglalós résszel. A fent említett lépések az alábbi kódban meg vannak jelölve.

Kezdetben, amíg még nincs szám, tömbnek sem kell lennie; ekkor a pointer lehet NULL. Lehetne egyébként malloc(0*sizeof(double)) is – malloc(0) szabályos, ahogyan free(NULL) is, éppen az ehhez hasonló algoritmusok miatt.

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

int main(void) {
    int i;
    
    /* számok beolvasása */
    printf("Ird be a szamokat, vegen -1!\n");
    int db = 0;
    double* szamok = NULL;
    double ujszam;
    while (scanf("%lf", &ujszam) == 1 && ujszam != -1) {
        /* itt a tömb nyújtása */
        double* ujtomb = (double*) malloc(sizeof(double) * (db+1)); // 1
        for (i = 0; i < db; ++i)
            ujtomb[i] = szamok[i]; // 2
        free(szamok); // 3
        szamok = ujtomb; // 4
        szamok[db] = ujszam;
        ++db;
    }

    for (i = db-1; i >= 0; --i) {
        printf("%f\n", szamok[i]);
    }

    free(szamok);

    return 0;
}

3. Nagyon hosszú sor beolvasása

A gets() kapcsán említettük az előadáson, hogy egy teljes sornyi szöveg beolvasása egy „tyúk vagy tojás” probléma elé állít minket. Amíg nem foglaltuk le a tömböt, nem tudjuk beolvasni a szöveget; viszont amíg nem olvastuk be a szöveget, nem tudjuk, milyen hosszú lesz, és így nem tudjuk lefoglalni a tömböt.

Hasonlóképp oldható meg ez a probléma, mint ahogyan azt az előbb, a végjeles sor beolvasásánál láttuk: a tömb most nem számokat, hanem karaktereket tartalmaz, a végjel pedig nem a -1, hanem az újsor karakter. Egy dologra kell csak figyelni: vajon mit tartalmaz a tömb, ha a sztring teljesen üres? Hány elemű ilyenkor a tömb?

Olvass be egy tetszőlegesen hosszú sort, és írd ki azt újra!

Megoldás

A könnyű kezelhetőség miatt, érdemes a tömb végére mindig lezáró nullát tenni – elvégre is, sztringről van szó, amit előbb-utóbb egy printf()-nek, vagy hasonló függvénynek oda szeretnénk adni. Emiatt az üres tömb is már 1 elemű, hogy a lezáró nulla beleférjen. A nyújtásnál db+1+1-es elemszámot kell megadni, db karakter volt addig, +1 az új karakternek, +1 a lezáró nullának.

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

int main(void) {
    printf("Irj be egy tetszolegesen hosszu sort!\n");
    int db = 0;
    char* sor = (char*) malloc(sizeof(char) * 1);
    sor[0] = '\0';
    char ujkar;
    while (scanf("%c", &ujkar) == 1 && ujkar != '\n') {
        /* itt a tömb nyújtása */
        int i;
        char* ujtomb = (char*) malloc(sizeof(char) * (db+1+1));
        for (i = 0; i < db; ++i)
            ujtomb[i] = sor[i];
        free(sor);
        sor = ujtomb;
        ujtomb[db] = ujkar;
        ujtomb[db+1] = '\0';
        ++db;
    }

    printf("[%s]\n", sor);

    free(sor);

    return 0;
}

4. hosszu_sort_olvas()

Alakítsd át úgy az előző programot, hogy a beolvasást egy függvénybe teszed át! A függvénynek legyen visszatérési értéke a sztringet tartalmazó memóriaterület címe!

Mutasd be, hogyan kell használni ezt a függvényt!

Megoldás

A felszabadítás free()-je marad a főprogramban! Az nem költözhet a függvénybe, mert ha a függvény visszatérés előtt felszabadítaná a tömböt, elvesznének az adatok.

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

char* hosszu_sort_olvas() {
    int db = 0;
    char* sor = (char*) malloc(sizeof(char) * 1);
    sor[0] = '\0';
    char ujkar;
    while (scanf("%c", &ujkar) == 1 && ujkar != '\n') {
        /* itt a tömb nyújtása */
        int i;
        char* ujtomb = (char*) malloc(sizeof(char) * (db+1+1));
        for (i = 0; i < db; ++i)
            ujtomb[i] = sor[i];
        free(sor);
        sor = ujtomb;
        ujtomb[db] = ujkar;
        ujtomb[db+1] = '\0';
        ++db;
    }

    return sor;
}

int main(void) {
    printf("Irj be egy tetszolegesen hosszu sort!\n");
    char* sor = hosszu_sort_olvas();
    printf("[%s]\n", sor);
    free(sor);

    return 0;
}

5. További feladatok

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