14. gyakorlat: generikus algoritmusok

A sztringen végiglépkedés, a karakterek számlálásának módja független attól, hogy konkrétan milyen karaktert keresünk. Az „e” betűs függvény a karaktert int-ként veszi át, hogy kompatibilis legyen az islower() és hasonló függvényekkel.

#include <stdio.h>
#include <ctype.h>

int e_betu_e(int c) {
    return c=='E' || c=='e';
}

/* A feladat megoldasa ez a fuggveny. */
/* A "feltetel" parameter: egy darab int parameteru (c), int
   visszateresi ertekkel rendelkezo fuggvenyre mutato pointer. */
int karakter_szamol(char *str, int (*feltetel)(int c)) {
    int darab, i;

    darab=0;
    for (i=0; str[i]!=0; ++i)
        if (feltetel(str[i]))
            darab++;
    return darab;
}

int main() {
    char szoveg[]="Ernoke 4 eves (jovore 5 lesz).";

    printf("%d e vagy E betű\n", karakter_szamol(szoveg, e_betu_e));
    printf("%d space\n", karakter_szamol(szoveg, isspace));
    printf("%d kisbetű\n", karakter_szamol(szoveg, islower));
    printf("%d számjegy\n", karakter_szamol(szoveg, isdigit));

    return 0;
}

• Az x tengelyen dx lépésközzel haladunk.
• Mindenhol kiszámítjuk f(x) értékét.
• Így meghatározható a rajzon látható téglalapok területe.
• Az integrál közelítő értéke ezek összege: ∑f(x)*dx.

Az integrálandó f(x) függvényt paraméterként vesszük át. Mivel ez a példában egy egyváltozós, valós függvény, C-ben egy olyan függvényként jelenik meg, amelynek egy double paramétere, és double visszatérési értéke van. A paraméter típusa tehát:

double (*f)(double)

Az ezt megvalósító függvény pedig az alábbi. (A dx-szel való szorzást kiemelhettük a szummán kívülre, hogy gyorsabb legyen a program.)

#include <math.h>

double integral(double (*f)(double), double ettol, double eddig, double dx) {
   double osszeg=0.0, x;

   for (x=ettol; x<eddig; x+=dx)
      osszeg+=f(x);               // ∑f(x)

   return dx*osszeg;              // dx * ∑f(x)
}

double sajatf(double x) {
   return 5*x*x + 2*x - 24.3;
}

int main() {
   double t;

   t = integral(sajatf, 14.3, 29.2, 0.1);
   printf("sajatf -> %g\n", t);
   t = integral(sin, 0, 3.1415927, 0.05);
   printf("sin -> %g\n", t);

   return 0;
}

Természetesen akár a könyvtári sin() függvényt is integrálhatjuk, hiszen annak is double sin(double) a típusa.

int osszeg(int a, int b) {
   int szum, i;
   
   szum=0;
   for (i=a; i<=b; i+=1)
      szum=szum+i;
   
   return szum;
}

int akkumulal(int a, int b, int (*akkum)(int, int), int kiindul) {
   int akk, i;
   
   akk=kiindul;
   for (i=a; i<=b; i+=1)
      akk=akkum(akk, i);
   
   return akk;
}

Gondoljunk bele: így olyan összegzések is megvalósíthatóak (pl. kivonás, osztás, négyzetösszeg, stb.), amikre az összegzés függvény megírója eredendően nem is gondolt. A függvény tovább általánosítható lenne, ha az i+=1 lépést is egy függvényre cserélnénk le.

int osszegzo(int a, int b) {
   return a+b;
}

int szorzo(int a, int b) {
   return a*b;
}

int main() {
   printf("1-tol 6-ig osszeg: %d\n", akkumulal(1, 6, osszegzo, 0));
   printf("1-tol 6-ig szorzat: %d\n", akkumulal(1, 6, szorzo, 1));
}

#include <stdio.h>
#include <math.h>

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

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

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

int main() {
   int i;
   double tomb[10]={1.2, 5.6, 9, -1.4, -6, 5, 9.1, 11, 0, -12};
   
   double_rendez(tomb, 10, kisebb);
   for (i=0; i<10; ++i) 
      printf("%7.2f", tomb[i]);
   printf("\n");

   double_rendez(tomb, 10, abszolut_kisebb);
   for (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.

Gondoljuk meg: szétválasztottuk a rendezés algoritmusát az összehasonlítás menetétől. Ennek több előnye van:

• Külön tudjuk megvalósítani őket.
• Az összehasonlítás algoritmusa cserélhető anélkül, hogy a rendező algoritmust módosítani kellene.
• A rendező függvény használója olyan rendezési szempontot is megadhat, amelyre a rendező függvény írója „álmában sem gondolt”.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

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 sztring_csokkeno(const void *pelso, const void *pmasodik) {
    /* -1-gyel megszorzom, es akkor csokkenobe lesz rendezve!
     * a parameterek megforditasa is jo lenne:
     *    return strcmp(pmasodik, pelso); */
    return -1*strcmp((const char *) pelso, (const char *) pmasodik);
}

int main() {
    enum { MERET=15, SZAVAKMERET=5 };
    /* 5 db, max 19 betus szo */
    char szavak[SZAVAKMERET][20]={"mango", "pomelo", "papaja", "grapefruit", "lime"};
    int intek[MERET];
    int i;

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

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

    /* a sztringeket azert sizeofolom, mert a karaktertomb
       meretere vagyok kivancsi, nem pedig a sztring hosszara! */
    qsort(szavak, SZAVAKMERET, sizeof(szavak[0]), sztring_csokkeno);
    for (i=0; i<SZAVAKMERET; i++)
        printf("%s ", szavak[i]);
    printf("\n");

    return 0;
}

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,
            int (*kisebb_e)(void const *pa, void const *pb)) {
   int i;
   void *temp;
   
   temp=malloc(elemmeret);
   
   for (i=0; i<meret-1; ++i) {
      void *pi=(char*)tomb + i*elemmeret;
      void *plk=pi;
      int j;
      
      for (j=i+1; j<meret; ++j) {
         void *pj=(char*)tomb + j*elemmeret;
         if (kisebb_e(pj, plk))
            plk=pj;
      }

      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.