Gyakorlat, 9. hét: dinamikus tömbök II.

Czirkos Zoltán · 2018.08.22.

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

Felkészülés a gyakorlatra:

1. Ellenőrző feladat

A feladat segít felmérni, hogy állsz a tanulással. A szövege csak a többi megoldással együtt jelenik meg. Óra után pedig rögzítsd a pontszámod a haladási napló mellett – a dolgozat nálad marad.

Feladat

Írj függvényt, amely paraméterként két sztringet kap, és visszaad egy harmadik sztringet, amely összefűzve tartalmazza az előbbi kettőt! Használd a C sztringkezelő függvényeit! Ügyelj a hibakezelésre (nem sikerül memóriát foglalni)!

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

Mintamegoldás és pontozási útmutató

char *osszefuz(char const *s1, char const *s2) {
    int hossz = strlen(s1) + strlen(s2);
    char *res = (char*) malloc((hossz + 1) * sizeof(char));
    if (res == NULL)
        return NULL;
    strcpy(res, s1);
    strcat(res, s2);
    return res;
}

char *almafa = osszefuz("alma", "fa");
if (almafa == NULL) {
    printf("nem volt memória");
} else {
    printf("%s", almafa);
    free(almafa);
}
  • a) osszefuz, a függvény fejléce: char* paraméterei és visszatérési értéke
  • b) a keletkező sztring hosszának meghatározása strlen-nel
  • c) a terület méretének számítása: tömbméret * sizeof(elemtípus); a lezáró \0 miatti +1 valahol hozzá kell legyen adva
  • d) a malloc használata, visszatérési érték eltárolása egy megfelelő típusú pointerben
  • e) egyik sztringrészlet másolása strcpy-val
  • f) másik sztringrészlet másolása strcat-tal
  • g) visszatérési a pointerrel
  • h) példa, a függvény hívása, pointer eltárolása
  • i) tömb felszabadítása, ugyanazt a pointert kapja a free
  • j) mindkét helyen hibakezelés (null ellenőrzése az osszefuz-ben ÉS a példában)

Ha strlen, strcpy, strcat helyett kézzel írt ciklus van, nem jár a kérdéses pont (b, e, f).
Ha nincs dinamikus memóriakezelés, nem járnak a pontjai és a pointeres pontok (a, c, d, g, h, i, j).

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)[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. Ha a függvényben létrehozott tömböt szeretnénk visszaadni, dinamikus memóriakezelést kell használni, és a visszatérési érték a dinamikusan foglalt területre mutató pointer kell legyen..

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

A tömböt majd dinamikusan kell foglalnunk:

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

Megoldás

Teljes zagyvaság, a típus definíciójában nem szerepelhet végrehajtandó utasítás a C nyelvben. Egyébként is, mikor hajtódna végre, amikor még a db változó nem is kapta meg az értékét? Javítás az előző példában részletezett módon.

3. Halmaz típus

Í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):

  • Le lehessen kérdezni, egy elem benne van-e a halmazban.
  • 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.

Készítsünk ábrát, amelyik a halmaz memóriaképét mutatja!

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 „elemek száma lehessen tetszőlegesen nagy” mondatrész miatt dinamikus memóriát használunk. A halmaz elemeit egy nyújtózkodó tömbben jegyezzük meg, amelyre pointer mutat. Emellett az éppen aktuális méretet (az elemszámot) is nyilvántartjuk. 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 feladat által kért három függvényen kívül még két további függvényt írunk, egy inicializáló és egy felszabadító függvényt..

A halmazokon dolgozó függvények általában 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 átvenniük. 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 értéket és melyik 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), konstans halmazra mutató pointert vesznek át. Így a fordító ellenőrizni tudja, nem írtunk-e azokba véletlenül olyan kódot, amely módosítaná az adattagokat.

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 mindig lehet, mivel lehet hogy a memóriában előtte vagy mögötte más adat 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) {
    for (int 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) {
    /* ha mar benne van, nem kell semmit csinalni */
    if (halmaz_benne_van_e(h, mit))
        return;

    /* atmasoljuk a regi adatokat eggyel nagyobb helyre */
    double *uj = (double*) malloc((h->db + 1) * sizeof(double));
    for (int 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) {
    /* ha nincs benne, nincs dolgunk */
    if (!halmaz_benne_van_e(h, mit))
        return;

    /* uj memoriaterulet, eggyel kisebb */
    double *uj = (double*) malloc((h->db - 1) * sizeof(double));
    int j = 0;
    for (int 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) {
    for (int 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. További feladatok: unió, metszet, delta

Implementáljuk az alábbi halmazműveleteket!

  • Metszet: olyan halmaz létrehozása, amelybe két megadott halmaz közös elemei kerülnek.
  • Unió: mindkét halmaz összes eleme bekerül az új halmazba (természetesen csak egyszer).
  • Delta (szimmetrikus differencia): azok az elemek, amelyek csak az egyik, vagy csak a másik halmazban szerepelnek.

Fontos, hogy ezeket a műveleteket ne a meglévő betesz()kivesz() műveletekből építsük meg, mert az nem lesz hatékony. Például az uniót megvalósíthatnánk úgy, hogy mindkét halmaz elemeit a betesz() függvénnyel bedobáljuk a harmadik halmazba, de közben annak dinamikus tömbjét át kellene méretezni annyiszor, ahány elem van. Ezért inkább határozzuk meg a méretet előre, foglaljuk a tömböt egyszerre, és utána végezzük el az adatok másolását!