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

Egy számtani sorozat minden elemét úgy kapjuk, hogy az eggyel előző eleméhez hozzáadjuk a különbséget (differenciát):

an = an-1 + d

A sorozatra függvényként tekintve, írj rekurzív függvényt, amelyik meghatározza egy számtani sorozat n-edik elemét! A függvény paraméterei: n, kezdo, diff, azaz a keresett elem sorszáma, a kezdőérték és a differencia.

Egészítsd ki úgy a programot, hogy a főprogramban egy ciklussal kiírod egy sorozat első 10 elemét, felhasználva a megírt függvényed!

    5     7     9    11    13    15    17    19    21    23 

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

#include <stdio.h>
 
double szamtani(int n, double kezdo, double diff) {
    if (n == 0)
        return kezdo;
    else
        return diff + szamtani(n - 1, kezdo, diff);
} 
 
int main(void) {
    for (int n = 0; n < 10; ++n)
        printf("%g  ", szamtani(n, 5, 2));
    printf("\n");
    return 0;
}

Helyesség:
1p  A függvény fejléce: kezdő, diff és n paraméterek; visszatérési érték
1p  Báziskritérium: n = 0 esetén a kezdőelemet adja vissza
1p  Rekurzív hívás, egyszerűsítés: diff + előző elem
1p  A rekurzív hívásban a kezdőelem és a differencia változatlanul továbbadva
1p  Minden ágon helyes a visszatérési érték, és nem lehet semmilyen ágon
    a fv. végére érni return nélkül (return n == 0 ? ... : ... is jó)
1p  Főprogram: ciklus és kiírás
1p  A megírt függvény helyes használata
Szépség:
1p  Helyesek a visszatérési értékek, és nincsenek a paraméterek felülírva,
    alapvetően: nincs értékadás a számtani() függvényben
1p  A kód esztétikája:
    a) indentálva a ciklustörzs és a függvénytörzsek,
    b) a változók nevei lehetnek 1 betűsek, de utaljanak a szerepükre
    c) rendeltetésszerű ciklushasználat, pl. nincs külön sorban írt i=0
       miatt "lyukas", hiányos for (; i<hossz; i+=1)

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.

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

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

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