Gyakorlat, 10. hét: dinamikus tömbök

Czirkos Zoltán · 2016.08.28.

Dinamikus memóriakezelés. Dinamikusan foglalt tömbök. Halmaz típus és függvényei.

Dinamikus memóriakezelés. Halmaz típus létrehozása dinamikus tömbbel.

Felkészülés a gyakorlatra:

1. 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? 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, egyrészt a hívó is lefoglalhatja a tömböt:

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

int tomb[100];
fv(tomb);

Másrészt dinamikus memóriakezeléssel:

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

Megoldás

Ügyes próbálkozás, de nem. Szintaktikailag is hibás: tömböt se paraméterként átadni, se visszatérési értékként adni, nem lehet. Javítás: lásd fent.

struct DinTomb {
    int db;
    int tomb[db];
};

Megoldás

A C nyelven minden struktúrának ismert kell legyen a mérete: tehát a fordítónak fordítási időben, a program futtatása előtt, el kell tudnia dönteni, hány bájtból fog állni. Ez az egyik dolog, ami miatt a fenti kód helytelen: nem fog egy struktúrában lévő adat (db) alapján egy tömb automatikusan átméreteződni. A másik hiba a látókörökkel kapcsolatos: nem létezik a kódban db nevű változó önállóan. Csak ha létrehozunk a DinTomb struktúrából egy példányt, annak a példánynak lesz valami.db adattagja. De db önmagában nem állhat.

Javítás: a struktúrába ne tegyük bele a tömböt, hanem az kerüljön a struktúrán kívülre. A struktúrába csak egy pointert tegyünk, amelyik azt mutatja, hova került a tömb:

struct DinTomb {
    int db;
    int* tomb;
};

Valószínűleg a tömböt majd dinamikusan kell foglalnunk:

struct DinTomb dt1;
dt1.db = 100;
dt1.tomb = (int*) malloc(sizeof(int) * 100);

Ehhez hasonló a lenti, halmazos feladat.

2. Dinamikus tömbbel visszatérő függvény

Írjunk feladatot, 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! Az új tömb címével és méretével térjen vissza cím szerint átadott paraméterben! A visszatérési érték legyen IGAZ, ha sikerült a művelet, és HAMIS, ha nem.

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! 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).
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

bool valogat(double *eredeti, int meret, double **ujtomb, int *ujmeret) {
    int i;

    double sum = 0;
    for (i = 0; i < meret; ++i)
        sum += eredeti[i];
    double atlag = sum/i;    /* megvan az atlag. */

    int db = 0;
    for (i = 0; i < meret; ++i)
        if (eredeti[i] < atlag)
            ++db;
    /* megvan a darab. */

    double *uj = (double *) malloc(sizeof(double)*db);
    if (uj == NULL)
        return false;
    /* megvan a tomb. */

    int ide = 0;
    for (i = 0; i < meret; ++i)
        if (eredeti[i] < atlag) {
            uj[ide] = eredeti[i];
            ++ide;
        }
    /* kesz az uj tomb. */

    /* visszateresek: */
    *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 ujmeret;
    valogat(szamok, 5, &uj, &ujmeret);
    int i;
    for (i = 0; i < ujmeret; ++i)
        printf("%f ", uj[i]);

    free(uj);

    return 0;
}

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 tömb által módosított double* változót cím szerint kell átvenni, az ujtomb paraméter double** típusú.

3. Halmaz adatstruktúra

Írjunk egy programot, amelyik egy valós számokból álló halmaz típust hoz létre. A halmazban lévő elemek száma lehessen tetszőlegesen nagy! A halmaz a következőket kell tudja (ezek a megírandó függvények):

  • Be lehessen tenni egy elemet a halmazba. (Ha már benne van, nem történik semmi.)
  • Ki lehessen venni egy elemet a halmazból.
  • Le lehessen kérdezni, egy elem benne van-e a halmazban.

A valós számokat, a számítási pontatlanságok miatt nem kellene == operátorral összehasonlítani. Ezt a problémát most hagyjuk figyelmen kívül; koncentráljunk a dinamikus memóriakezelésre!

Megoldás

Az utóbbi kitétel miatt dinamikus memóriát használunk. A halmaz elemeit egy dinamikus tömbben jegyezzük meg; mivel a lefoglalt memóriaterületre csak egy pointerünk van, ezért magunknak kell az éppen aktuális méretet (az elemszámot) nyilvántartani. Egy adott halmazhoz egy konkrét elemszám tartozik; a két elválaszthatatlan adat természetesen egy struktúrába kerül:

typedef struct Halmaz {
    int db;
    double *adat;
} Halmaz;

Ha létrehozunk egy halmaz struktúrát, akkor az memóriaszemetet fog tartalmazni, mind a db, mind az adat mezőben. Ezért egy halmazt az első használat előtt inicializálni kell. Hogy ne szivárogjon a memória, az utolsó használat után a dinamikusan foglalt területet fel is kell szabadítani. Ezért a fenti három függvényen kívül még kettőt írunk, amelyeknek a feladatai ezek lesznek.

A függvények, amelyek valamely halmazon dolgoznak, megváltoztathatják a struktúra tartalmát. Pl. a memóriaterület más helyre kerülhet, vagy a darabszám nőhet. Ezért a függvényeknek nem a struktúrát, vagyis annak másolatát, hanem a struktúrára mutató pointert kell átvegyenek. A betesz és kivesz függvényeknél ez mindenképpen így van, de a kényelem kedvéért érdemes az összeset így megírni. Akkor nem kell majd fejben tartani, melyik függvény vár halmazt, és melyik halmazra mutató pointert. Azok a függvények, amelyek pedig nem változtatják meg a struktúrát (pl. egy halmaz nem változik meg azáltal, hogy ellenőrizzük, tartalmaz-e egy elemet), a halmazra mutató pointert konstans pointerként veszik át. Így a fordító ellenőrizni tudja, nem írtunk-e azokba véletlenül olyan kódot, amely megváltoztatná azt.

A halmazba új számot betenni és számot abból kivenni sajnos költséges művelet. A dinamikusan foglalt tömböt átméretezni nem lehet, mivel lehet hogy előtte, utána másra használt, foglalt memória van. Ezért átméretezés esetén új memóriaterületet kell foglalni, és az elemeket átmásolni. A másolás után pedig a régi memóriaterület felszabadítható, végül pedig a halmaz struktúrában található pointer az új területre állítható át. (A szabványos realloc() függvény egyébként ugyanezt csinálja.)

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

typedef struct Halmaz {
    int db;
    double *adat;
} Halmaz;

/* inicializalatlan strukturat hoz alapallapotba */
void halmaz_init(Halmaz *h) {
    h->db = 0;
    h->adat = NULL;
}

/* halmazt felszabadit az utolso hasznalat utan */
void halmaz_felszabadit(Halmaz *h) {
    free(h->adat);
}

/* igazzal ter vissza, ha benne van az adott elem */
bool halmaz_benne_van_e(Halmaz const *h, double mi) {
    int i;
    for (i = 0; i < h->db; ++i)
        if (h->adat[i] == mi)
            return true;  /* ha valahol megtalaljuk */
    return false;         /* ha sehol nem talaltuk */
}

void halmaz_betesz(Halmaz *h, double mit) {
    double *uj;
    int i;

    /* ha mar benne van, nem kell semmit csinalni */
    if (halmaz_benne_van_e(h, mit))
        return;

    /* atmasoljuk a regi adatokat eggyel nagyobb helyre */
    uj = (double*) malloc((h->db + 1) * sizeof(double));
    for (i = 0; i < h->db; ++i)
        uj[i] = h->adat[i];

    uj[h->db] = mit;  /* vegere az uj */
    free(h->adat);    /* a regi mar nem kell */
    h->adat = uj;     /* atallitjuk a pointert az ujra */
    h->db++;          /* eggyel nott a darabszam */
}

void halmaz_kivesz(Halmaz *h, double mit) {
    double *uj;
    int i, j;

    /* ha nincs benne, nincs dolgunk */
    if (!halmaz_benne_van_e(h, mit))
        return;

    /* uj memoriaterulet, eggyel kisebb */
    uj = (double*) malloc((h->db - 1) * sizeof(double));
    j = 0;
    for (i = 0; i < h->db; ++i)
        if (h->adat[i] != mit)
            uj[j++] = h->adat[i];
    free(h->adat);
    h->adat = uj;
    h->db--;         /* eggyel csokken a darabszam */
}

/* kilistazza egy halmaz tartalmat */
void halmaz_lista(Halmaz const *h) {
    int i;
    for (i = 0; i < h->db; ++i)
        printf("%g ", h->adat[i]);
    printf("\n");
}

int main(void) {
    Halmaz h;

    halmaz_init(&h);
    halmaz_betesz(&h, 3.14);
    halmaz_betesz(&h, 2.0);
    halmaz_betesz(&h, 3.14);
    halmaz_lista(&h);
    halmaz_betesz(&h, 6.1);
    halmaz_lista(&h);
    halmaz_kivesz(&h, 3.14);
    halmaz_lista(&h);
    halmaz_felszabadit(&h);

    return 0;
}

A fenti megoldásban kihasználjuk, hogy free(NULL) a szabvány szerint elfogadott. Azonban egyes régebbi fordítók esetén ebből gond lehet. Ilyenkor a if (ptr!=NULL) free(ptr); formát érdemes használni.

Miután a main() függvény a 6.1-es számot betette a halmazba, így néz ki a program memóriaképe:

A veremben a h struktúra van, amely az egész számot és a pointert tartalmazza; a pointer pedig a dinamikusan foglalható területre mutat, oda, ahol a malloc() hívás helyet talált a három double méretű memóriaterületnek.

4. Halmaz dinamikusan foglalt struktúrával

Írjuk át a programot úgy, hogy a halmazt létrehozó függvények ne egy meglévő, inicializálatlan halmaz struktúrán dolgozzanak, hanem azt is dinamikusan foglalják, és a címével térjenek vissza. Erősen különböztessük meg az új halmazt létrehozó és a meglévő halmazt módosító függvényeket! Az előbbiek visszatérnek egy pointerrel, az utóbbiak várnak egy pointert a módosítandó halmazra. A függvények használata legyen ilyen:

Halmaz *h;

h = halmaz_uj();
halmaz_betesz(h, 3.14);
halmaz_betesz(h, 6.1);
halmaz_lista(h);
halmaz_kivesz(h, 3.14);
halmaz_lista(h);
halmaz_felszabadit(h);

Így a halmazokat kényelmesen adogathatjuk át a függvények között, nem szűnnek meg amiatt, mert lokális változók lennének. Figyeljük meg, hogy ez a szintaktikára nézve is jótékony hatással van: mivel h itt eleve már pointer, sehol nem kell az & címképző operátort használni.

Megoldás

Ilyenkor a memóriaképünk ilyen:

A main()-ben lokális változó csak egy pointer; a kupacon van a struktúra és a tömb is.

A különbség csak a létrehozó és a felszabadító függvényekben van. A létrehozáskor malloc()-oljuk a struktúrát is, és emiatt természetesen a felszabadításnál free()-zni kell azt is:

Halmaz *halmaz_init() {
    Halmaz *ph;
    ph = (Halmaz*) malloc(sizeof(Halmaz));
    ph->adat = NULL;
    ph->db = 0;
    return ph;
}

void halmaz_felszab(Halmaz *ph) {
    free(ph->adat);
    free(ph);
}

5. További feladatok

Implementáljuk a halmazt úgy, hogy rendezett tömböt használ az elemek tárolására! Hogyan kell módosítani a betesz(), kivesz(), benne_van_e(), illetve a metszet(), unio() függvényeket, hogy kihasználják ezt? Hogyan változik az algoritmusok hatékonysága?