| Szmájli | Ezt 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.
Á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.
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.
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. Az l_volt állapotban viszont
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 állapotátmeneti gráf sokszor kevésbé áttekinthető, mint a táblázat – ha abból kell kódolni, akkor nehéz lehet követni a nyilakat. Az sem látszik rajta, hogy teljesen definiált-e, szemben a táblázattal, ahol látjuk, hogy minden cellája ki van-e töltve.
Viszont tervezésre, ötletelésre kiválóan alkalmas. Az állapotgép által felismert jelsorozatokat (eseménysorozatokat) is könnyebb ezen felismerni, egyszerűen csak követni kell az átmenetekre (nyilakra, élekre) írt feliratokat.
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;A függvényhívás menetéről már volt szó régebben. Ismétlésként foglaljuk ezt össze!
#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;
}
Minden függvényhíváskor lefoglalódik egy terület a veremben, amely az adott híváshoz tartozik, és visszatéréskor megszűnik: ez a keret (stack frame).
A függvényhívás előtt a fenti példában a következő történik:
- A hívó, azaz a
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).
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?
A rendezés megvalósítására a C szabványos könyvtára tartalmaz egy qsort() nevű generikus
algoritmust. Ennek az összehasonlítás kritériuma, azaz a rendezési reláció megadható. Ha sztringeket szeretnénk rendezni, könnyű a
dolgunk: az szintén szabványos strcmp() függvény lehet a paraméter:
alma barack korte szilva
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
int main(void) {
char szavak[4][20] = {
"barack", "alma", "szilva", "korte",
};
qsort(szavak, 4, 20, strcmp); // db = 4, meret = 20
for (int i = 0; i < 4; ++i)
printf("%s ", szavak[i]);
return 0;
}Vegyük észre, hogy itt a függvénynek két paramétert is kell adni a tömbhöz. Egyrészt tudnia kell,
hány eleme van (hány sztringet kell sorbaraknia). Ez itt db = 4. Másrészt pedig azt is látnia kell, hogy
egy elem mekkora, vagyis hogy hány karakterből álló sztringeket kell cserélgetni. Ez meg meret = 20.
Tehát „mindkét irányban” változhat a méret, az elemszám és a sztringek hossza is tetszőleges. A
qsort() paramétere ezért nem két dimenziós tömbre mutató pointer (amelybe bele kellene írni a tömb méretét is, pl.
int (*p)[20]), hanem inkább egy void *. A void *-ként átadott mutatót lehetne (void*)
szavak 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.
A qsort() 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 probléma tehát 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.
Egy függvény így lépdelhet végig egy void * tömbön:
void for_each_tomb(void *t, int db, size_t meret,
void (*muvelet)(void *))
{
char *pbyte = (char *) t; // sizeof(char) = 1 miatt
for (int i = 0; i < db; ++i)
muvelet((void *) (pbyte + i * meret));
}Tehát ebben a char * csak azért szerepel, mert tudjuk, hogy sizeof(char) = 1, és
a pointer aritmetika esetén bájtokkal dolgozunk.
A for_each_tomb() használata egy tömb minden elemének a kiírására:
void kiir_int(void *vp) {
printf("%d ", *(int *) vp);
}
int tomb[] = { 68, 12, 125, 97, 56 };
for_each_tomb(tomb, 5, sizeof(int), kiir_int);