1. NHF szépségverseny

Varga János programja


Nevezés: infoc KUKAC eet.bme.hu címre
kb. 640×480 PNG screenshot + néhány mondatos leírás

Generikus algoritmusok

3. Menürendszer I. – a feladat

Írjunk programot, amelyben menüből választhatjuk ki a teendőt!

1. Adatbevitel
2. Módosítás
3. Keresés
4. Nyomtatás
5. Névjegy

Választás: _
1. Összeadás
2. Szorzás
3. Hatványozás

0. Kilépés

Melyik? _

A sormintákkal mindig az a baj, hogy nehezen módosítható, nehezen karbantartható programkódot eredményeznek.

Itt, hogy a switch(), ahol a beírt szám alapján kiválasztjuk a teendőt, ne legyen túl áttekinthetetlen, az egyes lépéseket eleve függvénybe tettük. Ez jó is – egészen addig, amíg nem kell módosítani a menüt. Tegyük fel, hogy a 2-es menüponthoz szeretnénk beszúrni a kivonást. A teendők:

  • Beszúrunk egy printf()-et az összeadás és a szorzás közé.
  • Ezek után a többit is átszámozzuk (szorzás, hatványozás).
  • A switch() előtti if()-nél átírjuk a számot (amely a menüpontok számával van összefüggésben) 5-re.
  • Beírjuk a switch()-be az új case 2-t.
  • Átszámozzuk a többi case-t is.

Ennél biztosan kell legyen jobb megoldás is. A menüpontok nevei betehetőek tömbbe, és akkor egy ciklussal elvégezhető a kiírás és a beszámozás. Vajon a menüpontok maguk, azaz a függvények is betehetőek a tömbbe? Ha igen, meg tudjuk szüntetni a második oldali sormintát is!

4. Ismétlés: a függvényhívás menete

A hívó: paraméterek a verembe, visszatérési érték a veremből.
A hívott: kezeli a lokális változóit.

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

double negyzet(double a) {
    return a * a;
}

int main(void) {
   double x = negyzet(5.9);
   double y = sin(6.1);

   printf("%g", x + y);
   return 0;
}

A függvényhívás előtt a következő történik:

  • A hívó main() beteszi a verembe a paramétereket.
  • Helyet csinál a visszatérési értéknek is.
  • Meghívja a függvényt, ami által bekerül a verembe a visszatérés címe (vagyis hogy hol kell folytatni a programot a függvényből visszatérvén).

Minden függvényhíváskor létrejön tehát egy rész a veremben, amely az adott híváshoz tartozik, és visszatéréskor megszűnik: ez a keret (stack frame).

A negyzet() függvényben a működés:

  • A paramétereit a veremben találja.
  • A visszatérési értéket a verembe teszi, a megfelelő memóriaterület felülírásával.
  • Amikor visszatér, akkor a hívóhoz ugrik vissza, az eltárolt visszatérési cím alapján.

A függvényhívás után a hívó:

  • A veremben megtalálja a visszatérési értéket. Ezt felhasználja, ha szeretné.
  • Kitörli a veremből az általa betett dolgokat, hiszen azokra már nincsen szükség.

Mi lenne, ha egy másik függvényt hívnánk meg ugyanolyan kerettel?

5. Függvényre mutató pointer: a háttérben…

Ha két függvénynek egyforma a fejléce, egyformán kezelik a vermet, és ezért kompatibilisek egymással.

double negyzet(double a);
double sin(double alfa);

A függvényre
mutató pointer.
int main(void) {
  double (*fptr)(double);   // ptr létrehozása
  double x;

  fptr = negyzet;           // ptr beállítása
  x = fptr(3);  /* negyzet(3) */
  fptr = sin;
  x = fptr(5);  /* sin(5) */

  return 0;
}

Mi is történik itt? Tegyük fel, hogy van egy függvényünk, amelyik egy darab double paramétert vár, és egy darab double paramétert kap vissza. Ha meghívjuk ezt a függvényt, akkor a hívó felépít hozzá egy keretet, amelyben ezeknek az értékeknek meglesz a megfelelő helye. A hívott fogja tudni, hogy a verem tetejéhez képest hol találja a paramétereket és hova kell tennie a visszatérési értéket. (Ennek technikai részleteiről természetesen a fordító gondoskodik.)

Ha van egy másik függvényünk, amelynek ugyanilyen a prototípusa, akkor a hívási keret megfelelő felépítése után meghívhatjuk azt is. Hiszen az a függvény a veremben ugyanott fogja keresni az ugyanolyan típusú értékeket. Vagyis ha a keretet megfelelően építjük föl, meghívható akár a negyzet(), akár a sin() függvény. Ennek pedig semmi akadálya nincs, ha a két függvény prototípusa megegyezik.

Így bevezethetjük a függvényre mutató pointer típust. Ez azt a memóriacímet tárolhatja, ahol a függvény található a memóriában. A függvény hívása pedig az alábbi módon történhet:

  • Felépítjük a hívási keretet a megfelelő módon.
  • Arra a memóriacímre ugrunk a végrehajtással, amire a pointer hivatkozik.
  • Miután visszatért, a veremből kivesszük a visszatérési értékét, és töröljük a keretet.

Mivel azt tudni kell, hogy mi legyen a hívási keret felépítése, ezért a függvénypointer típusában benne kell legyen az általa hivatkozott függvény prototípusa. Ezért néz így ki fent az fptr változó definíciója:

double (*fptr)(double);

A jobb oldali zárójel és a benne lévő double mutatja, hogy egy függvényről van szó, amelynek egy double paramétere van. A * jelzi, hogy az fptr változó egy ilyen függvényre mutat. A bal oldali double pedig azt, hogy ha meghívjuk a függvényt, egy double-t kapunk vissza.

Egy értékre mutató pointernél is a pointer típusából tudja a fordító, hogy a dereferálása esetén milyen típusú értéket vehetünk ki a memóriából (pl. int* egy egész számra mutat). A függvényre mutató pointereknél ugyanez a helyzet: a pointer típusából tudja a fordító, hogy mik a hívott függvény paraméterei és mi a visszatérési értéke. Vagyis hogy hogyan kell számára a hívási keretet felépíteni.

6. A függvénymutató típus szintaktikája

Minden függvénynek van egy címe. Ez a cím képezhető, elmenthető egy függvénymutató típusú változóba, és egy függvénymutató segítségével meghívható a függvény.

Definiálhatunk változót és típust is:

Fontos a *-ot és a nevet
körbevevő zárójel!
/* függvénymutató típusú változó */
VisszaTíp (*változónév)(ParamTíp, ParamTíp…);     // változó

/* függvénymutató típus */
typedef VisszaTíp (*TípNév)(ParamTíp, ParamTíp…); // típus

Ha a függvénymutató változóban a név elé nem tennénk *-ot, akkor az nem mutató lenne. Ha pedig nem tennénk az így becsillagozott kifejezést zárójelbe, akkor a double *fptr(int) azt jelentené, hogy egy fptr nevű függvényt deklarálunk, amely double*-gal tér vissza. Amit tehát fontos megjegyezni:

  • zárójel veszi körül a változó nevét a csillaggal,
  • az argumentumoknál csak a típusokat soroljuk fel, vesszővel elválasztva.

A typedef-et gyakran itt is két sorban írjuk le. Először definiáljuk azt a típust, amely egy adott függvényt jelent, utána pedig azt a típust, amely egy ilyen függvényre mutat:

typedef int KaraktertEvoFuggveny(char);
typedef KaraktertEvoFuggveny *FvPtr;

Ilyenkor nincsen szükség zárójelezésre sem, mivel a sorok egymás utánisága miatt már egyértelmű a fordító számára, hogy a * operátor az FvPtr-re értendő, tehát egy olyan típusú pointer a definiált típus.


Példa:

void kiir(char *str) {
    printf("%s", str);
}
typedef void (*StringFunc)(char *);

StringFunc fptr = kiir;
fptr("hello világ"); // fv. hívás operátora: kerek zárójel ( )

A függvényekre mutató pointerek és a tömbök között szintaktikailag igen nagy a hasonlóság. Egy tömb és egy függvény neve önmagában a címét képzi. Az érték eléréséhez a tömböknél az indexelő operátorra [], van szükség, a függvényeknél pedig a függvényhívó operátorra ().

  Kezdőcíme Értéke (eleme / hívása)
Tömb tomb tomb[2]
Függvény fv fv(3)

7. Menürendszer II. – a mutató típus

A menüpontok függvényei:

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

int szoroz(int a, int b) {
   return a * b;
}
int hatvanyoz(int a, int b) {
   int i, eredmeny = 1;
   for (i = 0; i < kitevo; ++i)
      eredmeny *= a;

   return eredmeny;
}

Vagyis minden függvény megkap két számot és elvégez rajtuk egy műveletet, aminek az eredményét a visszatérési értékben közli.


Ezekre a függvényekre egy ilyen pointer tud mutatni:

typedef int (*MenuFv)(int, int);

8. Menürendszer III. – a tömb és használata

typedef int (*MenuFv)(int, int);

typedef struct {
   char const *nev;
   MenuFv pfv;
} MenuPont;
MenuPont menupontok[] = {
   { "Összeadás", osszead },
   { "Szorzás", szoroz },
   { "Hatványozás", hatvanyoz },
   { NULL, NULL }   /* végjel */
};

Mivel mutatókat tárolnak, ezért utolsó elemnek betehető egy NULL érték, ami jelzi a végét – így biztonságosan kezelhető. Ez egy végjel: amikor egy ciklus fut a tömbön, a tömb tartalma alapján tudni fogja, hol van a vége. Nem kell majd külön szerepelnie a programban a tömbméret megadásának sem. Ezt a trükköt már rengetegszer használtuk.


A menüpontok kiírása:

menü kiírása
és a hívás
for (i = 1; menupontok[i-1].nev != NULL; ++i)
   printf("%d. %s\n", i, menupontok[i-1].nev);

meret = i; /* a for() végén i = tömb mérete */

A for ciklus indexváltozójának utolsó értéke a NULL elem indexe, vagyis a tömbben lévő értékes elemek száma. Ezzel az értékkel tudjuk ellenőrizni, hogy a felhasználó által bevitt menüpont értéke érvényes-e.

A kiválasztott menüpont végrehajtása:

if (0 < valasztas && valasztas < meret) {
   eredmeny = menupontok[valasztas-1].pfv(a, b); // függvénypointer
   printf("Eredmény: %d\n", eredmeny);
}
else {
   printf("Nincs ilyen menüpont\n");             // ha rossz az index
}

A fenti kifejezés működése részletesen:

Kifejezéstípus
menupontokstruktúrák tömbje, a menüpontok leírása
menupontok[index]egy struktúra, menüpont leírása
menupontok[index].fvegy függvényre mutató pointer
menupontok[index].fv(2.6, 3)2.6, 3 paraméterekkel meghívva az egyik függvény

Amit csináltunk:

  • a függvénymutatókat tároljuk egy tömbben,
  • a menüpontok leírását is tároltuk a tömbben,
  • mivel ezek összetartoztak, páronként egy struktúrába kerültek.

Ennek a megoldásnak az előnye az, hogy

  • egy új menüpont hozzáadása nagyon egyszerű, csak a tömböt kell módosítani
  • a működés automatizált,
  • könnyű hibatűrő programkódot készíteni.

9. Generikus (általános) algoritmusok

Mivel a függvények értékként kezelhetőek, és paraméterként adhatóak át, egyes algoritmusok működése megfogalmazható általánosságban is.

Mennyi a valószínűsége annak, hogy…

  • hogy kockával 6-ost dobunk? (1/6)
  • hogy fejet vagy írást dobunk? (1/2)
  • hogy egy (-1…1; -1…1) véletlenszerűen választott pont az egységkörbe esik? (π/4)
  • … mennyi a π értéke?!

Monte-Carlo-módszer: végezzük el a „kísérletet” 1000-szer, és számoljuk meg, hányszor sikerült!

Fej vagy írás, melyiknek hány százalék a valószínűsége? Írjunk egy függvényt, amely generál ezer darab 0 (fej) vagy 1 (írás) értékű véletlenszámot, és megnézi, hogy mekkora arányban lettek nullák:

double fejvagyiras(void) {
    int i, hanyszor;
    
    hanyszor = 0;
    for (i = 0; i < 1000; ++i)
        if (rand()%2 == 0)
            hanyszor += 1;
            
    return hanyszor / 1000.0;   /* egész osztást elkerülni! */
}

Ennek a visszatérési értéke 0,5 körül lesz.

Ha a kockával hatosokra vagyunk kíváncsiak, ugyanerre a függvényre van szükség, csak a feltétel más. Ha az egységkörbe eső pontokra, akkor is. Általánosítsuk ezért! Az elvégzendő „kísérletet” vegyük át paraméterként! A kísérletnek, mint függvénynek bemenő adata nincsen (void paraméterű), a visszatérési értéke egy logikai, igaz/hamis érték (bool típus).

A kísérlet függvényre mutató pointer típusa:

bool (*kiserlet)(void);

A montecarlo() függvény:

double montecarlo(bool (*kiserlet)(void)) {
    int i, hanyszor;

    hanyszor = 0;
    for (i = 0; i < 1000; ++i)
        if (kiserlet())
            hanyszor += 1;

    return hanyszor / 1000.0;   /* egész osztást elkerülni! */
}

Ez meghívja ezerszer a paraméterként kapott függvényt, és megszámolja, hányszor adott vissza igazat.

Példa kísérlet függvény: mekkora a valószínűsége annak, hogy a (0…1; 0…1) véletlenszerűen választott pont az egységkörbe esik?

bool egysegkorbe(void) {
    double x = rand()/(double) RAND_MAX;
    double y = rand()/(double) RAND_MAX;
    return x*x + y*y < 1;
}

A montecarlo() hívásai a fenti feladatok megoldására:

printf("fej: %g%%\n", 100.0 * montecarlo(fejvagyiras));
printf("hatos: %g%%\n", 100.0 * montecarlo(hatostdobunk));
printf("korbe: %g%%\n", 100.0 * montecarlo(egysegkorbe));
printf("pi: %g\n", 4 * montecarlo(egysegkorbe));

Az utolsó sor a π becslését adja a Monte-Carlo-módszerrel. A montecarlo(egysegkorbe) hívás megmondja, hogy a (0…1; 0…1) tartományban generált véletlen számpárok hány százaléka esik a körbe. A negyedkör területe r2π/4=π/4, szemben a vizsgált négyzet területével, ami kereken 1, tehát a valószínűség π/4, vagyis a négyszerese π-t kell adja.

10. Az év eleji tételek generikus változata

Tételek a félév eleji anyagból – ezek mind generikus algoritmusok:

  • Számlálás tétele: adott tulajdonságú elemek darabszáma
  • Maximumkeresés tétele: legvalamilyenebb elem megkeresése
generikus
számlálás
int szamlal(long *tomb, int n, bool (*pred)(long)) {
   int i, db;
   db = 0;
   for (i = 0; i < n; ++i)
      if (pred(tomb[i]))     // adott tulajdonságú?
         ++db;
   return db;
}

A program forráskódja is így nagyon szemléletes. Akárhány függvényt írhatunk, amelyek tulajdonságokat vizsgálnak. Ezek a predikátumok:

predikátumok
bool negativ(long x) {
   return x < 0;
}

bool paros(long x) {
   return x%2 == 0;
}

A függvényeket pedig egyszerűen paraméterként átadjuk:

long tomb[10] = {………};
printf("%d negativ van.\n", szamlal(tomb, 10, negativ));
printf("%d   paros van.\n", szamlal(tomb, 10, paros));

Generikus algoritmusok tömbökön

12. Generikus tömb?

Vajon lehet olyan függvényt írni, ami bármilyen tömbön működik?

A pointer aritmetikához ismerni kell a típust. A fordító figyelembe veszi a cím számításánál:

int tomb[] = {9, 3, 5, 76, 1, 45, 87};
int *p;

p = &tomb[3];
p = tomb+3;    // ugyanaz

Azonban ez void * esetén nem működhet:

int szamlal(void *tomb, int n, bool (*pred)(void *));  // ?

Amikor az adatok tömbben vannak, a pointer típusának nem csak egy, hanem két szerepe is van. Azon felül, hogy ez ad információt arról, hogy az adott típust hogyan kell kezelni (nyilván más egy int és egy struct Konyv), a típus ismerete a tömbelemek címének kiszámításakor is fontos. Innen tudja a fordító azt, hogy mekkora egy tömbelem, vagyis a következő elemre lépéshez hány bájtot kell ugrani a memóriában. Ezt az információt mindig figyelembe veszi, amikor egy tömbelemet indexelünk, vagy a címét számítjuk.

Ha a tömb elejére mutató pointert void *-gá konvertáljuk, akkor nem csak a tömb tartalma válik ismeretlenné, hanem az is, hogy az egyes tömbelemek hol helyezkednek el. A tömb elejére mutató void * pointer nem ad semmilyen információt a tömbelemekről. A predikátum paramétere még csak-csak lehet void * (majd a törzsében megfelelő típusú pointerré konvertáljuk), de a tömb elemein nem tudunk lépkedni a típus ismerete nélkül.

Hogy tudjuk ezt a problémát megoldani?

13. Tömbök generikusan – a pointerek kezelése

int tomb[5] = { 11, 22, 33, 44, 55 };
void *ptomb = (void *) tomb;           // így kapja a függvény :(

Egy char* típusú mutatót használva bájtonként lépkedhetünk.
A sizeof pedig megmondja egy típusról, hány bájtos.

typedef char byte;
byte *tomb_bajtjai = (byte *) ptomb;   // a tömb kezdete, bájtok
int i;
for (i = 0; i < 5; ++i) {
    byte *elemcime = tomb_bajtjai + i*sizeof(int);
    int *elem = (int *) elemcime;               // újra int
    printf("%d ", *elem);
}

Ahhoz, hogy a mutató aritmetika működjön, a mutatót típussal kell ellátni, hiszen ilyenkor az adott típus méretével tolja el a címet. Ha char* típusúvá alakítjuk a pointert, akkor bájtonként tudunk lépni, mivel sizeof(char)=1, definíció szerint. A fenti kódban ezért, hogy jobban érthető legyen, mi történik, a typedef segítségével létrehoztunk egy byte nevű típust. Bájtokra mutató pointeren, ha pointer aritmetikát végzünk, bájtonként fogunk ugrani – ezért az elem címének kiszámításakor nem azt kell megadnunk, hogy hányadik egész számra, hanem hogy hányadik bájtra ugrunk. Ez szerencsére egy szorzással könnyen meghatározható: a tömbindexet egyszerűen megszorozzuk egy elem méretével. Az így kapott pointert pedig bátran visszakonvertálhatjuk int *-gá.

Egyes fordítók megengedik azt, hogy void * mutatókon használjunk pointer aritmetikát, de ez nem szabványos, úgyhogy inkább kerüljük az ilyesmit!

14. Tömbök generikusan – a méret átadása

A probléma megoldható, mégpedig úgy, ha egy generikus tömböt feldolgozó algoritmusnak nem csak a tömb kezdőcímét (most void * formában!) és a tömb méretét adjuk át, hanem megmondjuk neki az egyes tömbelemek méretét is! Erre nincsen trükkös megoldás, egyszerűen közölni kell ezt a számot is az algoritmussal.

Nem véletlen, hogy a malloc() függvénynek paraméterként kellett adni a méretet. Ugyanígy, az fread() és fwrite() függvények is meg kell kapják fájlba írt / fájlból olvasott tömb elemszámát és az elemek méretét.

Az algoritmussal közölni kell:

  • a tömb kezdőcímét: void *, a tömb elemeinek a számát: db,
  • és egy elem méretét: meret. !


Ismerős?
fread(void *ptr, size_t meret, size_t db, FILE *fp);

15. Tömbök generikusan – az elemek kezelése

Egy függvény így lépdelhet végig egy void * tömbön:

void for_each_tomb(void *t, int db, int elemmeret, 
                   void (*muvelet)(void *))
{
   int i;
   char *bajtptr = (char *) t;  // csak sizeof(char)=1 miatt!
   for (i = 0; i < db; ++i) {
      muvelet((void *) bajtptr);
      bajtptr += elemmeret;     // léptetés
   }
}

A for_each_tomb() használata egy tömb minden elemének a kiírására.

void int_kiir(void *vp) { printf("%d ", *(int *) vp); }

int tomb[] = { 68, 12, 125, 97, 56 };
for_each_tomb(tomb, 5, sizeof(int), int_kiir);

Komplexebb példa: egy adott feltételt leginkább kielégítő elem keresése. (Legkisebb, legnagyobb, legzöldebb, …)

void *leg_keres(void *tomb, int db, int meret, 
                bool (*kisebb)(void const *, void const *)) {
   int i;
   char *ptr, *eredmeny;         // csak sizeof=1 miatt char!

   eredmeny = (char *)tomb;      // első
   ptr = (char *)tomb + meret;
   for (i = 1; i < db; ++i) {
      if (kisebb((void *) ptr, (void *) eredmeny))
         eredmeny = ptr;         // többi
     ptr += meret;
   }

   return eredmeny;
}

A legkisebb elem megkeresése egy tömbben:

bool kisebb_e(void const *vp1, void const *vp2) {
   int const *psz1 = (int const *)vp1,
             *psz2 = (int const *)vp2;
   return *psz1 < *psz2;
}

int main(void) {
   int tomb[5] = {68, 12, 125, 97, 56};

   lk = *((int*)leg_keres(tomb, 5, sizeof(int), kisebb_e));
   printf("Legkisebb elem: %d", lk);
   return 0;
}
Legkisebb elem: 12

16. Generikus tömbök: stdio, stdlib

A void * technika olyan hasznos, hogy a C könyvtár is alkalmazza:

/* fájlkezelés */
fwrite(void const *ptr, size_t meret, size_t db, FILE *fp);
fread(void *ptr, size_t meret, size_t db, FILE *fp);
/* dinamikus memóriakezelés */
void *malloc(size_t meret);
free(void *ptr);
/* gyorsrendezés, bináris keresés */
void qsort(void *tomb, size_t db, size_t meret,
           int (*hasonlit)(void const *, void const *));
void *bsearch(void const *key, void const *tomb,
              size_t db, size_t meret,
              int (*hasonlit)(void const *, void const *));

17. qsort() és bsearch(): hasonlító függvény

A qsort() és bsearch() utolsó argumentuma egy hasonlító függvény, aminek C-ben szabványos visszatérési értéke van:

mint a
strcmp()
hasonlit(a,b) =
   negatív: ha a < b
     nulla: ha a == b
   pozitív: ha a > b

Például egy hasonlító függvény double típusú elemekre:

int hasonlit_int(void const *vp1, void const *vp2) {
   double const *sz1 = (double const *) vp1;
   double const *sz2 = (double const *) vp2;

   if (*sz1 > *sz2) return 1;
   if (*sz1 < *sz2) return -1;
   return 0;
}

18. qsort() és bsearch(): használatuk

bsearch() használata

Egy tömb rendezése qsort segítségével:

#include <stdlib.h>

int main(void) {
   int t[6] = {23, 119, 47, -2, 54, 86};

   for_each_tomb(t, 6, sizeof(int), int_kiir);
   printf("\n");
   qsort(t, 6, sizeof(int), hasonlit_int);
   for_each_tomb(t, 6, sizeof(int), int_kiir);
   printf("\n");

   return 0;
}
23 119 47 -2 54 86
-2 23 47 54 86 119

A qsort() tehát követi a fent leírtakat: mivel generikus, tömbökön dolgozó algoritmus, ezért meg kell adni neki a tömb elejére mutató pointert (void * típussal), a tömb elemszámát és az egyes elemek méretét is. A negyedik paramétere az összehasonlító függvény, amelyet meg fogja hívni minden elempárra, amit a rendezés közben össze kell hasonlítania.

A void *-ként átadott mutatót lehetne (void *) t formában írni, kiemelve azt, hogy ott egy mutató konvertálásról van szó, de ezt nem szokás megtenni. A pointerek konverziója void *-ra, típus nélküli pointerre a C nyelvben automatikus, éppen ezek miatt az algoritmusok miatt.

bsearch() használata

Keresés a bsearch segítségével:

int t[] = {23, 119, 47, -2, 54, 86};

/* bináris keresés csak rendezett tömbökön */
qsort(t, 6, sizeof(int), hasonlit_int);

int minta = 47;
int *talalt;
talalt = (int *) bsearch(&minta, t, 6, sizeof(int), hasonlit_int);

if (talalt != NULL)
   printf("Megtaláltam, itt van: %p\n", talalt);
else
   printf("Nincs a tömbben.\n");

Adni kell neki egy mintát: hogy néz ki az az elem, amit keresünk.

Hogy ugyanazt a hasonlító függvényt lehessen használni, mint amit a qsort()-hoz is, a bsearch() úgy van megadva, hogy egy mintát is vár tőlünk: első paramétere egy olyan elemre mutató pointer kell legyen, amely egy mintául szolgál a kereséshez. Innen fogja tudni, hogy néz ki az az elem, amit keresnie kell. A hasonlító függvény pedig megmondja neki, hogy a tömbben előre, hátra kell mozogni, esetleg megtalálta az adott elemet. Ne feledjuk, bináris keresésről van szó, és ezért a tömbnek rendezettnek kell lennie!

A visszatérési érték is ahhoz hasonló, mint amit megszoktunk: NULL pointer akkor, ha nincs meg az elem. Ha megvan, akkor pedig egy nem NULL értékű pointer a találatra.

Állapotgépek

20. Szmájlik GTalk-on, Facebookon

SzmájliEzt kell beírni
:) :-)
:D :-D
8-)
:(|)
<3

Feladat: megkeresni a beírt szövegben a szmájlikat, és utána úgy kiírni a szöveget, hogy képek szerepelnek benne helyettük.


Oldjuk meg ezt minél kevesebb memória felhasználásával!

Lehetne működőképes megoldást csinálni úgy, hogy beolvassuk az egész szöveget egy sztringbe. De ez elég rossz ötlet. Ha látunk egy hosszú szöveget, abban rá tudunk mutatni a szmájlikra, anélkül hogy az előttük vagy utánuk lévő részt ismernünk kellene.

A feladatot elképzelhetjük egy adatfolyam (stream) problémaként. Valaki diktálja nekünk a szöveget (bejövő karakterek), nekünk pedig le kell írni azt (kimenő karakterek). A diktálás közben pedig nem szeretnénk a teljes szöveget, vagy hosszú szövegrészletet a fejünkben tartani.

21. Előtte még: karakterek beolvasása, kiírása

Karakterek olvasása: a printf, scanf %c-n kívül használhatóak:

int getchar(void); // beolvas
int putchar(int); // kiír

Ezek gyorsabbak, mint a printf és a scanf, de egyszerre pontosan csak egy karaktert írnak és olvasnak.


Nagyon fontos: a getchar() visszatérési típusa int!

int c;
c = getchar();
if (c == EOF)
   printf("Bemenet vége!");
else
   printf("Karaktert olvastam, kódja: %d", c);

A getchar() függvénynek a visszatérési értéke a fájl vége jelet is tudja jelezni. Ezt úgy oldották meg a C-ben, hogy az stdio.h tartalmaz egy EOF nevű konstanst, amely ezt jelzi. Ennek a konstansnak az értéke szándékosan kívül esik a karakter típus ábrázolási tartományán, hiszen minden olyan szám, ami azon belül van, egy bájt, ami szerepelhet a program bemenetén is. Emiatt a getchar() függvény visszatérési értékét char típusban tárolni hiba!

A getchar() függvény visszatérési típusa int. A visszatérési értéke EOF, ha vége van a bemenetnek, és nem sikerült már beolvasni egy karaktert sem (fájl vége jelnél); és a beolvasott karakter kódja, ha sikerült.

Az elvesző bitek miatt (emlékezzünk: a char kisebb, mint az int) lesz olyan karakter, amelyet a program összekever a fájl vége jellel. Természetesen miután meggyőződtünk róla, hogy nem EOF, már bemásolhatjuk vagy castolhatjuk karakter típusúra. Az EOF konstans számértékét a C fordítók maguk határozhatják meg. Ezért az is hiba, ha valaki azzal a feltételezéssel él a forráskódban, hogy EOF = -1! Egyébként a legtöbb karaktert kezelő függvény, pl. putchar(), toupper(), isdigit(), … is int típusú paraméterrel rendelkezik, de a getchar()-ral ellentétben ez legtöbbször nem lényeges a használatuk közben.

Példa: Blian élete. Az alábbi ploglam minden 'r' betűt 'l' betűle cselél.

#include <stdio.h>

int main(void) {
   int c;   /* kalaktel */

   while ((c = getchar()) != EOF) { // éltékadás is egyben!
      if (c=='r')
         putchar('l');
      else if (c=='R')
         putchar('L');
      else
         putchar(c);
   }

   return 0;                     // letuln zéló
}

A (c=getchar())!=EOF kifejezés működése a következő:

  • Kiértékelődik a getchar() kifejezés. Erre beolvasódik egy karakter vagy az EOF fájl vége jel.
  • Ez bemásolódik a c változóba az értékadás miatt.
  • Az egész zárójelezett kifejezés az értékadás. Ennek értéke a másolt érték, vagyis maga a karakter.
  • Ezt hasonlítjuk össze az EOF konstanssal.
  • Ha nem egyenlő vele, akkor karaktert olvastunk, és mehetünk be a ciklusba.
  • Ha egyenlő, fájl vége jelet, akkor pedig kiléphetünk a ciklusból.

Fontos a zárójel. Ha az nem lenne ott, akkor az = értékadás és != egyenlőségvizsgálat operátorok precedenciája miatt a getchar()!=EOF összehasonlítás eredménye kerülne a c változóba, nem a karakter! (A legkülső zárójelnek természetesen nincs köze a kifejezéshez, mert az a while-hoz tartozik.)

22. Klasszikus állapotgép: az „ly” számláló

Feladat: számoljuk meg a beolvassott szövegben az ly betűket:

  • Az ly 1-nek számít: lyuk,
  • az lly 2-nek: gally,
  • nagybetűkkel most ne foglalkozzunk.

A probléma nehézsége

Önmagában egyik karakternél sem egyértelmű a teendő!

  • l-nél: nem tudjuk, mit kell majd csinálni: alma, lyuk, gally
  • y-nál: a teendő attól függ, előbb mi történt: gy, lyuk

Azt azért sejtjük, hogy a végleges döntés az y karakternél fog megszületni. Az l-nél nem lehet, hiszen a jövőbe nem látunk. Úgyhogy a második gondolatmenet a járható út. Eltárolni a teljes szöveget viszont felesleges, hiszen elég mindig csak egy kis részletet látni belőle. A kidolgozatlan ötlet ezek alapján:

sz = 0;
while ((c=getchar()) != EOF) {
   if (c == 'y') {
      switch (……… ELŐZMÉNYEK ………) {    // !
         case ……… és l volt előtte ………:     // !
            sz += 1;
            break;
         case ……… és ll volt előbb ………:     // !
            sz += 2;
            break;
         default:
            break;
      }
   }
}

printf("%d darab ly szerepelt.\n", sz);

23. Állapotgépek: példák

Állapotgép = véges automata (finite-state machine)

Működése: az eddig kialakult állapottól és az eseménytől függ:

  • az elvégzendő tevékenység,
  • a következő állapot.

Az állapotgép egy olyan gép, program, amely a bemenetei hatására a belső, véges számú állapot között ugrál. Minden bemenet–állapot pároshoz egy, és csakis egy pontosan meghatározott következő állapot (állapotátmenet) tartozik.

Egy állapotgép mindig egy bizonyos állapotban van, és attól függően reagál az eseményekre. Az események hatására állapotátmenet történhet. Az állapotgépet állapotátmeneti gráffal vagy állapotátmeneti táblázattal adjuk meg.

A mostani programjainkban az állapotátmenetekhez tevékenységeket is fogunk társítani.


Példa: italautomata

Az italautomata másképp reagál a sztornó gomb és az italválasztó gomb megnyomására attól függően, hogy be lett-e dobva már a pénz, vagy még nem.


Példa: a Prog1 NZH javításának menete

A megírt ZH-k bekerülnek a javítandók közé. Utána több oktató javítja (mindenki más feladatot). Ha elkészül a javítás, az eredmény pontszám +2 ajándék ponttal rögzítődik az admin portálon. Ezután a ZH-t meg lehet tekinteni. Ha a javításban hiba van, azaz reklamáció esetén a pontszámot újra rögzíteni kell a rendszerben, de ilyenkor az ajándék +2 pont már nem jár. Végül minden ZH dolgozat archiválva van. Itt is látszik, hogy a ZH dolgozattal máshogy kell dolgozni, attól függően, hogy előzőleg mik történtek vele.

24. Állapotgép tervezése

Tervezzük meg az „ly” számláló állapotgépét! Melyik állapotban, milyen esemény hatására, mi a teendő?

Egy állapotgép működése rögzíthető egy állapotátmeneti táblán, pongyolán fogalmazva egy állapottáblán. A táblázat sorai az egyes állapotokat jelentik (amelyekbe valamely régebbi események alapján került az automata). A táblázat oszlopai pedig az eseményeket (ezek most a beérkező karakterek). Minden eseménynél, vagyis minden karakter olvasásánál az aktuális állapottól és az éppen beolvasott karaktertől függően dől el az, hogy mit kell csinálni (tevékenység) és hova kell ugrani (állapot). Gyakran ezt két külön táblázatban adják meg – lentebb az állapot- és tevékenységtábla egy táblázatba összegyúrva szerepel.

Az állapottábla nagyban segíti a tervezést, amelynek menete a következő. Először felvesszük egy táblázat oszlopaiba a számunkra érdekes eseményeket (jelen esetben ezek az l, az y és az összes többi karakterek). Utána az első sorba az alapállapotot, ahonnan indul az automata. Végiggondoljuk, hogy ebben az állapotban mely eseményre (karakterre) minek kell történnie. Ha kell, új állapotokat veszünk föl; és addig folytatjuk, amíg van kitöltetlen sora a táblázatnak.

A konkrét példában: alap állapotban egy l hatására még nem történik semmi, de tudjuk, hogy a következő karakternél figyelni kell, mert az esetleg egy y lehet. Ezért felvesszük az l_volt állapotot. Alap állapotban a másik két karaktertípus hatására semminek nem kell történnie. Ezzel kész az első sor. A második sorban, az l_volt állapotnál y esetén növeljük a számlálót, és visszaugrunk alap állapotba (hiszen a következő karakternél már nem lesz igaz, hogy az ahhoz képest előző l betű volt). Az ll_volt állapotnál viszont egy harmadik l betű esetén maradunk ugyanabban az állapotban, mert a következő karakternél igaz lesz az, hogy az előző kettő l volt. (Ha van ilyen magyar szó egyáltalán.)


Az „ly” számláló állapot- és tevékenységtáblája
lyegyéb
alap→l_volt--
l_volt→ll_voltsz+=1, →alap→alap
ll_volt-sz+=2, →alap→alap

k u l c s l y u k , g a l l y
Számláló: 0

Az „ly” számláló állapottáblája tehát a következőket jelenti:

  • Az alap állapot: semmi, amire figyelni kellene. Ez egyben a kiindulási állapot is.
  • Ha jön egy l betű, átmegyünk l_volt állapotba.
    • Ha ilyenkor jön egy y, akkor a számlálót növelni kell +1-gyel (és → alap!)
    • Ha viszont még egy l, akkor meg ll_volt állapotba. Azért, mert ha harmadikként y érkezik, akkor +2 kell a számlálóba.
    • Ha bármi más, akkor viszont vissza alap állapotba (pl. almafa, az l után m betű jött).

Az állapotgép működését gráffal is megadhatjuk. Ez a megadás teljesen ekvivalens a táblázattal. Minden állapotra (a gráf csúcsai) megadja, hogy az egyes eseményeknél (élekre írt karakterek) mi a teendő. A nyíl az új állapot felé mutat, illetve az elvégzendő tevékenység is a nyíl mellé írva szerepel.

Ly számláló állapotátmeneti gráfja

25. Ly számláló: C kód

Az állapot eltárolásához a legjobb választás egy felsorolt típus, enum. Megtehetnénk, hogy mi magunk számozzuk be az állapotokat, de akkor a programkód követhetetlen lenne. Így viszont olvasható lesz!

typedef enum LyAllapot {
    alap,
    l_volt,
    ll_volt
} LyAllapot;
a teljes
forráskód
letölthető:
lyszaml.c
LyAllapot all = alap;

while ((c = getchar()) != EOF) {
  switch (all) {
    case alap:   // alap állapot
      if (c == 'l')
        all = l_volt;
      break;

    case l_volt: // már volt egy 'l'
      switch (c) {
        case 'l': all = ll_volt; break;
        case 'y': szaml += 1; all = alap; break;
        default:  all = alap; break;
      }
      break;

    case ll_volt:

Minden beérkező karakternél a tevékenység és a következő állapot az függ a beérkező karaktertől és az állapottól. Más például a teendő egy beérkező y karakternél akkor, ha előzőleg l betűt láttunk. Ezért minden karakter feldolgozásánál a táblázat egy cellájából kell kiolvasnunk a teendőket. Ez alapján a kódban egy esetszétválasztást csinálhatunk, ami viszont triviális: a meglévő állapottábla alapján a programkód szisztematikusan, szinte gondolkozás nélkül elkészíthető!

26. Állapotgépek: szmájlik cseréje

A program:
szmajli.c

Az eddigiek alapján a táblázat könnyen elkészíthető, most az egyszerűsítés kedvéért csak két szmájlira:

normál:)<3
alap →alap
c
→kettőspont
(semmi)
→alap
c
→kisebb
(semmi)
→alap
c
kettőspont→alap
:, c
→kettőspont
:
→alap
→kisebb
:
→alap
:, c
kisebb →alap
<, c
→kettőspont
<
→alap
<, c
→kisebb
<
→alap

Itt is az állapotgép táblázatában minden cella tartalmaz egy következő állapotot (fent) és egy tevékenységet (lent). A tevékenység minden esetben valamilyen karakter vagy karakterek kiírását jelenti. c-vel jelöltük az épp beolvasott karakter képernyőre másolását; a többi kiírásnál pedig a megadott jelet kell majd a programnak kiírnia (pl. kisebb jel vagy kettőspont).

Mivel minden oszlopban ugyanaz az állapotátmenet, egyszerűbbnek tűnik az esemény (karakter) szerint csinálni az első esetszétválasztást:

while ((c = getchar()) != EOF) {
    switch (c) {
        default:
            switch (all) {
                case Alap: printf("%c", c); break;
                case Kettospont: printf(":%c", c); break;
                case Kisebb: printf("<%c", c); break;
            }
            all = Alap;
            break;
        case ':':
            switch (all) {
                case Alap: /* semmi */ break;
                case Kettospont: putchar(':'); break;
                case Kisebb: putchar('<'); break;
                }
            all = Kettospont;
            break;

27. Tényleg a switch() a legjobb megoldás?

Az állapot- és tevékenységtábla kézzel történő leprogramozása (ti. a hatalmas switch()-ek) helyett lehet egy sokkal okosabb ötletünk is.

Tábla → táblázat → csináljunk 2D tömböt a kódban!

  • Minden cellában egy tevékenység és egy állapot. Ez azt jelenti, hogy a táblacella egy struktúra.
  • A tevékenységek: mit írunk ki (szöveg + aktuális karakter?)

A tevékenység az ly számláló példájában könnyen leképezhető akár egy egész számra (mennyivel kell növelni a számlálót). Jelen esetben is nagyon hasonlítanak a teendők: vagy kiírjuk az aktuális karaktert, vagy nem; és vagy kiírunk utána még valamit, vagy nem. Összetettebb esetben ún. függvénymutatókat szokás ehhez használni, ez későbbi előadáson szerepel majd.


Az adatszerkezet: struktúrák kétdimenziós tömbje.

typedef struct TablaCella {
   Allapot kovetkezo;
   char szoveg[5];
   bool akt_char_kiir;
} TablaCella;

TablaCella tabla[3][5] = { ... };

Kérdés, hogyan fogjuk ezt a tömböt indexelni.

28. Állapotgép táblázattal – leképezések

Az állapotból és a karakterből is tömbindexet kellene csinálni:

  • A sorokat az állapot szerint indexeljük: tabla[all]
  • Az oszlopot a karakter szerint indexeljük: tabla[all][kar_o]
  • Azon belül pedig pl. a szöveg: tabla[all][kar_o].szoveg

typedef enum SzmajliAllapot { // állapot → 0...2 egész szám
    Alap = 0, Kettospont = 1, Kisebb = 2
} SzmajliAllapot;

int karakterosztaly(char c) { // char fajtája → 0...4 egész szám
   switch (c) {
      default:  return 0;
      case ':': return 1;
      case ')': return 2;
      case '<': return 3;
      case '3': return 4;
   }
}

Az állapotnál legegyszerűbb, ha hagyjuk a fordítónak, a felsorolt típus egyes értékeihez az alapértelmezetteket társítsa. Azok 0, 1 és 2 lesznek. Mivel 0-tól számozódik, pont jó lesz számunkra tömbindexnek is.

A karakter fenti switch() szerkezetében a break utasítások elhagyhatóak, hiszen a return utáni részek úgysem hajtódnak végre a függvényből. Kicsit „sormintás”, de ha nem így lenne, akkor meg egy 256 elemű tömbre lenne szükségünk (ennyiféle bájt van), amiben szinte minden érték nulla, csak néhány másik van – úgyhogy most jó lesz ez a megoldás is.

29. Állapotgép: a táblázat és a kód

A táblázat

A teljes program:
szmajli_tabla.c
TablaCella allapotgep[3][5] = {
   { ... }, { ... },
   { {Alap, "<", true},
     {Kettospont, "<", false},
     {Alap, "<", true},
     {Kisebb, "<", false},
     {Alap, "♥", false} },
};

A táblázatot használó kód

while ((c = getchar()) != EOF) {
    int kar = karakterosztaly(c);
    printf("%s", allapotgep[all][kar].szoveg);  // tevékenység
    if (allapotgep[all][kar].akt_char_kiir)
        putchar(c);
    all = allapotgep[all][kar].kovetkezo;      // állapotátmenet
}

30. Állapotgépek függvényre mutató pointerrel

A tevékenység egy függvény:

typedef struct AllapotPont {
    Allapot kovetkezo;
    void (*tevekenyseg)(void);
} AllapotPont;

Az állapotgépet kezelő program:

Esemeny esemeny;
Allapot allapot;

while ((esemeny = uj_esemenyre_var()) != -1) {
    /* meghívjuk az adott tevékenység függvényét */
    tabla[allapot][esemeny].tevekenyseg();
    /* lépünk a következő állapotba */
    allapot = tabla[allapot][esemeny].kovetkezo;
}

Hogy ne legyen túl sok állapotunk, a tevékenységeket érdemes paraméterezni. Például a tevékenységnek paramétere lehet az aktuálisan beolvasott karakter, vagy egy kiírandó szöveg is. Így egyszerűsödhet az állapotgép.

31. Állapotgépek általában

Digitből
sorrendi hálózatok

Előnyök

  • Tervezésnél: a tervezés eszköze!
  • A felesleges állapotok kiszűrhetők
  • Kódolásnál: mechanikusan kódolható
  • Áttekinthetőbb, érthetőbb a kód, mint egy ad-hoc megoldás

Felhasználásuk

  • Szűrőprogramok (fájlok feldolgozása); fordítóprogramok, nyelvi elemzők (pl. /* kommentek */ kiszűrése)
  • Alkalmazások vezérlése (pl. egérkattintások, mozdulatok)
  • Internetes alkalmazások kommunikációja (protokollok)
  • Hardver: a processzor egy nagy állapotgép!

Hardver oldalról is fontos az állapotgép. A számítógép belseje is tele van ilyenekkel. A processzor működését is egy állapotgép vezérli: utasítás beolvasása, beolvasott utasítás dekódolása, utána további operandusok beolvasása (már a dekódolt utasítás jelentése alapján) stb. Erről a Digit tárgyban van szó.