13. hét: generikus algoritmusok

Czirkos Zoltán, Nagy Gergely, Pohl László · 2024.08.21.

Gyakorlófeladatok az előadás anyagához kapcsolódóan.

1. Függvénypointerek

Függvénypointerek tömbje

Vizsgán volt

Definiálj olyan 3 elemű tömböt, amely olyan mutatókat tartalmaz, melyek a fenti feladat függvényére mutathatnak!

Megoldás 
/* így néz ki a függvény, amiről szó van */
int fv(int *t, int meret);

/* így néz ki egy, a fenti típusú függvényre mutató pointer */
/* a neve lesz a pointer neve; elé csillag, és zárójelbe. */
int (*pfv)(int *t, int meret);

/* ha ezekből kell egy 3 elemű tömb, akkor nem egy pfv pointer
   van, hanem egy három elemű tpfv tömb. a paraméterek nevei
   természetesen itt is, és eggyel feljebb is elhagyhatóak,
   vagyis mindkét lenti sor egyformán jó. */

int (*tpfv[3])(int *t, int meret);          /* <- ez a megoldás */
int (*tpfv[3])(int *, int);                 /* <- vagy ez is jó */

Ugyanúgy kell mindent deklarálni, ahogy használni fogjuk! tpfv az egy tömb, amit ha megindexelünk [3], akkor kapunk egy pointert *, ami egy (int *, int) paraméterű függvényre mutat, amit meghívva egy int a visszatérési értéke.

A (*pfv) köré azért kell a zárójel, mert nélküle int * pointerrel visszatérő függvény lenne, nem pedig pedig függvényre mutató pointer:

int *fv(int*, int);         /* int* függvény */
int (*pfv)(int*, int);      /* int függvényre mutató ptr */

foreach()

Írj függvényt, amely átvesz egy int típusú elemekből álló tömböt, annak méretét, valamint egy olyan függvényt, amely egy int paramétert vár és visszatérési értéke void. A megírandó függvény járja végig a tömböt és minden elemére hívja meg a paraméterként átvett függvényt!

qsort() valós számok tömbjére

A qsort() könyvtári függvény generikus, segítségével bármilyen típusú adatok rendezhetőek. A rendezéshez az adott, általunk használt adattípushoz készítenünk kell egy összehasonlító függvényt. Készíts egy olyan függvényt, amelyik int típusú számok összehasonlításához használható a qsort()-hoz. Mutass példát, hogyan kell használni a függvényt!

Megoldás 
int integer_osszehasonlito(const void *pelso, const void *pmasodik) {
    const int *elso = (const int *)pelso;
    const int *masodik = (const int *)pmasodik;

    if (*elso < *masodik)
        return -1;
    if (*elso > *masodik)
        return 1;
    return 0;
}


int intek[5];

/* veletlen elemek */
srand(time(0));
for (int i = 0; i < 5; i++)
    intek[i] = rand()%100;

/* rendezes es kiiras */
/* itt az int-et batran sizeofolhatom */
qsort(intek, 5, sizeof(intek[0]), integer_osszehasonlito);
for (int i = 0; i < 5; i++)
    printf("%d ", intek[i]);
printf("\n");

qsort() pontok tömbjére

Adott a következő, pontok koordinátáit tároló rekord: 

struct pont {
    double x;
    double y;
};

Egy ilyenekből álló tömböt szeretnénk rendezni úgy, hogy az origótól lévő távolságuk szerint növekvő sorrendben legyenek. A rendezéshez a qsort() könyvtári függvényt használjuk. Írd meg az ennek negyedik paraméterében használható összehasonlító függvényt.

Sztringek visszafelé

Írj összehasonlító függvényt a qsort() számára, amellyel sztringek visszafelé (csökkenő) sorrendbe rendezhetőek! Mi erre a legegyszerűbb megoldás?

Megoldás

A strcmp() visszatérési értéke pozitív vagy negatív, nagyobb vagy kisebb sztring esetén. Ezt negálva megfordul a sorrend:

int strcmp_neg(void const *pa, void const *pb) {
    return -1 * strcmp((char const *) pa, (char const *) pb);
}

Még rövidebb megoldáshoz jutunk, ha fordítva adjuk neki a paramétereket, hiszen ha a<b, akkor b>a:

int strcmp_neg(void const *pa, void const *pb) {
    return strcmp((char const *) pb, (char const *) pa);
}

Numerikus integrálás

Tekintsünk egy valós, egyváltozós függvényt, például: 

double fv(double x) {
    return x*x + 2*x + 5;
}

Írj C függvényt, amelyik trapéz-módszerrel numerikus integrálást végez. Visszatérési értéke legyen az integrál értéke; paraméterei az integrálandó függvény, az intervallum és a lépésköz.

Egyenlet megoldása

Készíts függvényt, ami egy folytonos függvény nullahelyét megkeresi egy adott intervallumban, intervallumfelezéssel. A függvény paraméterként kapja az intervallumot, amelyben keres, és a függvény pointerét. Építsen be egy hibahatárt, amelyen belül a nullahelyet megtaláltnak tekinti. A függvény a nullahely valós értékével térjen vissza.

Generikus lista és fa

A láncolt lista és a bináris fa példák olyan adatszerkezetekre, amelyekre minden programnak szüksége lehet. Ezek kezelésének módja (például listaelem beszúrása) független attól, hogy milyen adatokat tartalmaznak.

Deklarálj olyan listát, amely típus nélküli mutató segítségével tetszőleges adatot képes tárolni! Írj függvényeket, amelyek a lista elejére, végre fűznek egy elemet, illetve egy megadott elemet törölnek a listából!

Végezd el ugyanezt bináris fára is! A beszúráskor végzendő összehasonlításhoz vegyél át egy függvényt, amely összehasonlítja a két beszúrandó adatot, és amelynek a visszatérési értéke hasonlít az strcmp()-éhez!

double-öket rendező függvény

Írjunk függvényt, amely paraméterként kap egy double elemekből álló tömböt, és rendezi azt! A rendezés szempontja (növekvő, csökkenő, abszolútérték szerint növekvő stb.) is legyen a függvény paramétere!

Megoldás 
#include <stdio.h>
#include <math.h>

/* rendezi a tombot a megadott szempont szerint */
void double_rendez(double tomb[], int meret, bool (*kisebb_e)(double a, double b)) {
    for (int i = 0; i < meret - 1; ++i) {
        int lk = i;
        for (int j = i + 1; j < meret; ++j)
            if (kisebb_e(tomb[j], tomb[lk]))
                lk = j;

        double temp = tomb[lk];
        tomb[lk] = tomb[i];
        tomb[i] = temp;
    }
}

/* igaz, ha a<b */
bool kisebb(double a, double b) {
    return a < b;
}

/* igaz, ha |a|<|b| */
bool abszolut_kisebb(double a, double b) {
    return fabs(a) < fabs(b);
}

int main(void) {
    double tomb[10] = {1.2, 5.6, 9, -1.4, -6, 5, 9.1, 11, 0, -12};

    double_rendez(tomb, 10, kisebb);
    for (int i = 0; i < 10; ++i)
        printf("%7.2f", tomb[i]);
    printf("\n");

    double_rendez(tomb, 10, abszolut_kisebb);
    for (int i = 0; i < 10; ++i)
        printf("%7.2f", tomb[i]);
    printf("\n");

    return 0;
}

A fenti függvények nem követik az strcmp() konvenciót: az összehasonlító függvények nem kompatibilisek azzal. Azonban nincs is erre szükség itt még, hiszen a rendezendő adatok típusa adott.

Saját generikus rendező függvény

Alakítsuk át az előbbi rendezőfüggvényünket úgy (bármelyik algoritmust is választottuk), hogy ne double, hanem tetszőleges elemekkel dolgozzon!

Megoldás

Ehhez a függvénynek void* pointerrel kell átvennie a tömböt (mivel a típusait nem ismeri), és ugyancsak paraméter kell legyen az egyes elemek mérete is. Az elemek cseréje nem végezhető el értékadással, de segítségül hívhatjuk a memcpy függvényt, amely adott méretű memóriaterületet másol. Az „ideiglenes változó” helyébe – amely a háromlépéses cseréhez kell – is egy külön, típus nélküli memóriaterület lép. Mivel ennek mérete függvényparaméter, dinamikusan foglaljuk. A hasonlító függvény is void*-okat kell várjon, nem pedig double-öket. 

void rendez(void *tomb,
            int meret, size_t elemmeret,
            bool (*kisebb_e)(void const *pa, void const *pb)) {
    void *temp;

    temp = malloc(elemmeret);

    for (int i = 0; i < meret - 1; ++i) {
        void *pi = (char*)tomb + i * elemmeret;
        void *plk = pi;

        for (int j = i + 1; j < meret; ++j) {
            void *pj = (char*) tomb + j * elemmeret;
            if (kisebb_e(pj, plk))
                plk = pj;
        }

        if (plk != pi) {
            memcpy(temp, plk, elemmeret); /* temp=lk */
            memcpy(plk, pi, elemmeret);   /* lk=i */
            memcpy(pi, temp, elemmeret);  /* i=temp */
        }
    }

    free(temp);
}

A teljes program letölthető innen: genrend.c.