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

Írj függvényt, amely paraméterként két sztringet kap, és visszaad egy olyan 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!

A feladat megoldására 7 perc áll rendelkezésre.

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

Figyelj a javításnál, hova kell pointer, és hol lehet char tomb[]! Mindegyik tétel 1 pontos:

1. osszefuz, a függvény fejléce: char* pointer paraméterei és visszatérési értéke; a paraméterek lehetnek char tomb[] alakúak, de a visszatérési érték semmiképp
2. a keletkező sztring hosszának meghatározása strlen-nel
3. a terület méretének számítása: tömbméret * sizeof(elemtípus); a lezáró \0 miatti +1 hozzá kell legyen adva
4. a malloc használata, visszatérési érték eltárolása char* típusú pointerben
5. egyik sztringrészlet másolása strcpy-val
6. másik sztringrészlet másolása strcat-tal
7. visszatérés a pointerrel
8. példa, a függvény hívása, pointer eltárolása
9. tömb felszabadítása, ugyanazt a pointert kapja a free
10. 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).

A dinamikusan foglalt területet föl is kell szabadítani. Az összefűz függvény egy pointert ad vissza a foglalt területre, amit emiatt kétszer is fel kell használnunk: először a printf()-nek adva, hogy kiírja a szöveget, utána pedig a free()-nek, hogy felszabadítsa azt. Emiatt egy változóra is szükségünk van:

char *s = osszefuz("alma", "fa");
printf("%s", s);
free(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);

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.

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. (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.