tl;dr

Czirkos Zoltán, Csendes Dávid · 2019.10.08.

Összefoglalók néhány témakörhöz: vezérlési szerkezetek, függvények, pointerek, sztringek, sztringkezelő függvények, rekurzió, rendezések.

1. A vezérlési szerkezetek

A három alapvető vezérlési szerkezet a C programozási nyelvben a következőképpen írható le:

  • Szekvencia – az utasításokat és kifejezéseket pontosvessző választja el.
    utasítás1;
    utasítás2;
    utasítás3;
  • Feltétel – az if kulcsszó után a kifejezést zárójelbe tesszük; az else (egyébként) ág elhagyható.
    if (feltétel)
        utasítás;       /* ha teljesül, ezt */
    else
        másik_utasítás; /* ha pedig nem, akkor ezt */
  • Ciklus – a belépés és bentmaradás feltétele úgyszint zárójelben, a kulcsszó pedig a while.
    while (feltétel)
        utasítás;       /* amíg teljesül, ezt újra és újra */

A ciklusok magjába és a feltétel után nem csak egyetlen egy utasítás vagy kifejezés írható, hanem több is. Ilyenkor az egymás utáni utasításokat kapcsos zárójelbe kell tenni. Például egy cikluson belüli utasítássorozat a következőképpen néz ki:

while (feltétel) {
    utasítás1;
    utasítás2;
    utasítás3;
}                   /* ide, a } után NEM kell pontosvessző */

Az utasítások mellett a C-ben írt program ún. változódeklarációs sorokat is tartalmaz. Ezek azok, amelyben megadjuk a gépnek, hogy milyen nevű változóink vannak, és hogy mi azoknak a típusa (pl. egész vagy valós szám, karakter stb.)

int oszto, szam;
double hanyados;

Nem teljesen tartozik ide logikailag, de nagyon fontos megemlíteni a programozásban használatos egyenlőségvizsgálatot és értékadást; illetve ezek először furcsa C szintaktikáját. Nagyon fontos nem összekeverni őket!

Értékadás
Egy változó értékét megváltoztatjuk vele; a régi értékét elfelejti, és helyette újat jegyez meg a gép. Jele C-ben egy egyenlőségjel: =.
i = 5;            /* i értéke 5 lesz */
szam = szam+1;    /* a számot eggyel növeljük */
Összehasonlítás
Két változó, konstans vagy kifejezés egyenlőségének vizsgálata. Jele C-ben két egymás utáni egyenlőségjel: ==.
if (x == 7)
    printf("x értéke most épp hét.");

2. Függvények

Sok programban egy bizonyos művelet, műveletsor többször fordul elő. Ahelyett, hogy minden helyre leírnánk ugyanazt a kódrészletet, az ilyenekből szubrutinokat (függvényeket) hozunk létre, amelyek a program többi részéből elérhetőek. Ezek végrehajtása után ott folytathatódik a végrehajtás, ahonnan jöttünk.

/* parameter (bemenet): sugar,
   visszateresi ertek (kimenet): kerulet */
double kor_kerulete(double r) {
    return 2 * 3.14159 * r;
}

C-ben a szubrutinokat függvényeknek nevezzük. A már eddig is használt printf() is egy ilyen függvény, amelyet nem nekünk kell megírni, hanem a nyelv beépített eleme. A main() is egy ilyen függvény – a main névvel jelezzük a fordítónak, hogy ez legyen az a függvény a sok közül, ahol a program elindul.

A C-s függvények a matematikai függvények általánosításai; egyrészt nem feltétlenül rendelkeznek paraméterrel, másrészt visszatérési értékük sem feltétlenül van.

#include <stdio.h>

/* ennek a fuggvenynek se parametere, se visszateresi erteke */
void szorzotabla_rajzol(void) {
    for (int y = 1; y <= 10; y += 1) {
        for (int x = 1; x <= 10; x += 1)
            printf("%5d", x*y);
        printf("\n");
    }
}

int main(void) {
    szorzotabla_rajzol();
    return 0;
}

3. Pointerek – emlékeztető

Az alábbi program a pointerek használatát és a tömb-pointer kapcsolatot mutatja be.

#include <stdio.h>

int main(void) {
    int tprim[6]={2, 3, 5, 7, 11, 13};
    int a=1, b=2;
    int i;

    int *p;

    /* EGYETLEN VÁLTOZÓVAL */
    p=0; p=NULL;   /* nem mutat sehova. */
    
    printf("a=%d, b=%d\n", a, b);
    p=&a;          /* most a-ra mutat */
    *p=5;
    printf("a=%d, b=%d\n", a, b);
    p=&b;          /* most b-ra mutat */
    *p=9;
    printf("a=%d, b=%d\n", a, b);

    /* TÖMBBEL - tömb elejére mutat, indexelhető */
    p=tprim;
    for (i=0; i<6; i++)
        printf("tprim[%d]=%d, p[%d]=%d\n", i, tprim[i], i, p[i]);
    /* a pointerrel végigmegyünk a tömbön */
    /* p++: a következő elem, nem a következő bájt! */
    for (i=0, p=tprim; i<6; i++, p++)
        printf("*p=%d\n", *p);

    return 0;
}

Pointer aritmetika: egy pointerhez, pl. int *p hozzáadhatunk egy egész számot. p+1 azt jelenti, hogy a memóriában a *p után következő int változó címe. p-3 az őt hárommal megelőző int címe. int *p1, *p2 esetén pedig p2-p1 azt adja meg, hogy *p2 hány elemmel van arrébb, mint *p1. Ezek alapján egy tömböt, amelynek az elejére egy p pointer mutat, így is indexelhetünk: *(p+2), és ez teljesen ekvivalens p[2]-vel. Tömböknél általában az utóbbi formát érdemes használni, mert sokkal olvashatóbb, az előbbiért meg úgyis pontlevonás járhat a ZH-ban.

4. Tömbök és pointerek - az automatikus konverzió segít!

Mint láthattátok, ha definiálunk egy tömböt, akkor annak kezdőcímét át tudjuk passzolni egy függvénynek, mely így hozzáférhet a tömbhöz.

void kiir(int* tomb, int meret){
    for(int i = 0; i < meret; i++)
        printf("%d ", tomb[i]);
}

int main(void) {
    int tomb[3] = { 5, 7, 6 };
    kiir(tomb, 3);
}

De ez hogy történhet? Most akkor a tömböt tekinthetem pointernek, vagy fordítva, vagy mi engedi ezt meg? A megoldás roppant egyszerű, de jobb letisztázni.

*A tömbként definiált változók NEM pointerek.* Azonban gondoljunk bele, mit kéne ahhoz tenni, hogy egy tömböt elérhetővé tegyünk egy függvény számára: *át kéne adnunk a kezdőcímét manuálisan*:

int main(void) {
    int tomb[3] = { 5, 7, 6 };
    kiir(&tomb[0], 3);
}

De miért kéne nekem minden egyes alkalommal leírnom az *&* jelet, a *szögletes nyitó-zárójelet* és még ráadásul azt, hogy *0*, mikor *a tömböt láthatóvá szeretném tenni a legelejétől a függvény számára* - egyszerűen adja magát, hogy legyen egy lehetőségem arra, hogy leírhassam egyszerűen azt, hogy *tomb*, mint az első példában. Ez csak egy kényelmi funkció, amit a fordító biztosít, hogy könnyebb legyen írni a programot, illetve így olvasni is egyszerűbb a kódot. Ami itt történik, nevezzük *automatikus konverziónak*.

Automatikus konverzióba belefuthattatok már korábban is: nézzük meg, mi történik az alábbi kódban!

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

int main(void) {
    int a = 2;
    double d = sqrt(a);
    printf("%f", d);
    return 0;
}

Látszólag semmi különleges nincs a kódban - egy számnak szeretném tudni a gyökét. Igen ám, de a fejléce az *sqrt* függvénynek így néz ki:

double sqrt(double);

Azaz egy double-t kér be paraméterül, mi viszont egy int-et adtunk meg! Ha megpróbáljuk lefordítani, nem fog azonban elhasalni, sőt - helyes eredményt ad vissza. Ilyenkor is automatikus konverzió történik - az egész számot a háttrében *átcastolja* a fordító double értékké. Ha ti magatok írtok egy hasonló fejlécű függvényt, és annak egész számot adtok be paraméterül, szintén helyesen futhat le a program, ennek köszönhetően.

/* a háttérben ez történik */
double d = sqrt( (double) a);

Mikor történhet ezzel baj? Akkor, *ha valamilyen információvesztés történik emiatt*. Egy olyan típusra akarunk castolni, amely valamit nem tud az előző típushoz képest. Egy példa erre az, ha float-ot kér a függvény, de mi double-t adunk be neki - a függvényen belül nem biztos, hogy ugyanazt az értéket fogjuk látni, mint kívül, hiszen a float fele annyi bitet tárol, mint a double! (Hence the name, double.) Vagy egy nagyon jellegzetes másik példa az, ha int paraméter helyére adunk be double-t - ekkor nyilván a tizedesjegyek el fognak veszni.

#include <stdio.h>

void kiiregesz(int szam){
    printf("%d ", szam);
}

void kiirfloat(float szam){
    printf("%f", szam);
}

int main(void) {
    double ertek = -1554.654184;
    kiiregesz(ertek);
    /* eredmény: -1554 */
    kiirfloat(ertek);
    /* eredmény: -1554.654175 */
    return 0;
}

És végül akkor mi történik a tömbből pointer esetben? Az eredeti példakódban a tomb változó típusa int[3] - azaz egy 3 elemű egészekből álló tömb. Ez automatikusan castolásra kerül int*-gá, amely pointer a kezdőcímre fog mutatni. Ha azt szeretnénk, hogy máshova mutasson, akkor manipulálnunk kell az értékét a kezdőcímnek egy hozzáadással.

int main(void){
    int tomb[3] = { 5, 7, 6 };
    kiir(tomb+1, 3);
}

Na de mi a helyzet ezzel, hogy int[3] a típusa a változónak? Ennek van értelme? Van, de csak ritkán kerül elő. Egy példa erre az, ha többdimenziós tömböt szeretnénk láthatóvá tenni egy függvénynek - ekkor muszáj megadni, hogy a tömbökben (mint sorok) lévő tömbökben (sorokon belüli oszlopok) hány elem van. (Erre azért van szükség egyébként, hogy ki tudja számolni a fordító, hova kell ugrani a kettős megindexeléskor a memóriában.)

/* ha nincs ott a 3-as, fordítási hiba!
 * int* tomb[]-ként csak figyelmeztetés lesz, de el fog szállni a program */
void kiirtwod(int tomb[][3], int meret){
    for(int i = 0; i < meret; i++){
        for(int j = 0; j < 3; j++){
            printf("%d ", tomb[i][j]);
        }
        printf("\n");
    }
}

int main(void) {
    int twod[2][3] = {
        { 1, 2, 3 },
        { 4, 5, 6 }
    };
    kiirtwod(twod, 2);
}

5. Sztringek

Amit fejben kell tartanunk:

  • Sztring típus mint olyan, C-ben nem létezik.
  • Helyette karaktertömböt használunk.
  • Hogy a hossza változó lehessen, nullával lezárjuk.
  • Olyan nullával, ami NEM ugyanaz, mint a nullás számjegy! '\0' vagy 0 formában írható. (A '0' és a NULL mást jelent!)
  • Maximum annyi karakter lehet benne, amennyi a tömb mérete mínusz egy: a lezáró nulla miatt.
  • A tömb mérete nem ugyanaz, mint a benne lévő sztring hossza!

Függvényeknél, amelyek sztringeket dolgoznak fel, a következő dolgokra kell figyelni:

  • Ha a függvény csak olvassa a sztringet, a lezáró nullából tudni fogja, hol a vége. Ezért nem kell átadni a méretet. Elég egy pointer a tömb elejére.
  • Ha a függvény ír is egy sztringbe, akkor észnél kell lenni – vajon belefér a cél tömbbe, amit oda akarunk tenni? A függvény erről csak akkor tud gondoskodni, ha külön megadjuk neki a rendelkezésre álló terület méretét. Ez viszont nem az írt sztring hosszával egyenlő, hanem a tömb méretével!
  • Ha sztringet állítunk elő, mindig gondolni kell a lezáró nullára!

Ennek megfelelően egy sztring hosszát meghatározó függvény a következőképpen nézhet ki. A két változat teljesen ugyanúgy működik, csak a for ciklusosban kihasználjuk, hogy a C bármit megenged a ciklus fejlécébe írni.

int sztringhossz(char *sz) {
   int i;

   i=0;
   while (sz[i]!='\0') ++i;

   return i;
}
int sztringhossz(char *sz) {
   int i;

   for (i=0; sz[i]!='\0'; ++i)
      ;

   return i;
}

Egy sztring másolása pedig:

void sztringmasol(char *ide, char *honnan) {
   int i;

   for (i=0; honnan[i]!='\0'; ++i)
      ide[i]=honnan[i];    /* ugyanannyiadik karakter */
   ide[i]='\0';            /* a lezaro nulla: "i" pont annyi */
}

Itt a for ciklus átmásolja az összes „értékes” karaktert, vagyis mindent a lezáró nullán kívül. A lezáró nullát már nem másolja, hiszen ha elérte, a honnan[i]!='\0' feltétel már nem teljesül. Ezért azt külön kell odatenni a másolat sztring végére az ide[i]='\0' utasítással. Pont az i-edik indexre kell írni a nullát, ugyanis a forrás sztringben is pont ezen az indexen volt.

6. Szabványos sztringkezelő függvények és buktatók

Legalapvetőbb sztringkezelő függvényeket a string.h-ból. A használható puskán ezek mind rajta vannak! Itt egy rövid, nem teljes lista a használható függvényekről, hogy néhány buktatót meg lehessen említeni:

  • strcpy(ide, innen) Sztring másolása. Miért létezik ilyen? Mert tömb értékadás nem létezik.
  • strcat(mihez, mit) – hozzáfűzés.
  • strlen(s) – méret lekérdezése.
  • strcmp(mit, mivel) – összehasonlítás. Ennek a visszatérési értékére figyelni kell! Ami igazra értékelődik ki (nem nulla), az pont a nem egyenlőség.
  • sprintf(s, fmt, ...) sztringbe printfelés, sscanf(s, fmt, ...) sztringből scanfelés.
  • scanf("%s", ide) ez csak szóközig olvas! Mivel ide egy tömb, nem kell elé a címképző & operátor.
  • gets(ide) ez beolvas egy egész sort (enterig, amit nem rak bele). Mivel nem lehet tudni, a bemenetről hány karakter jön, túlírhat. Ez nagyon gáz!
  • fgets(ide, max, file) fájlból olvas egy sort (enterig, amit belerak). A max-ba a rendelkezésre álló tömb mérete kell.
  • strncpy(ide, innen, max) maximum annyi karaktert másol. Nem biztos, hogy lezárja nullával, vagyis önmagában használhatatlan… Pl. utána kell írni, hogy ide[max-1]=0, és akkor már jó. De azt meg könnyű elfelejteni.
  • strncat(ide, innen, max) maximum annyi karaktert másol. Vigyázat, a max-ban nem az ide[] méretét kell megadni!

7. Rekurzió iskolapélda: Fibonacci

Fibonacci számsor: olyan sorozat, amelynek minden eleme az őt megelőző két elem összege. Hogy ne a végtelenségig hivatkozzunk az előző elemekre, az első kettőt külön meg kell adni, vagyis:

  • Fib0=0,
  • Fib1=1, és
  • Fibn=Fibn-1+Fibn-2.

Ez egy rekurzív definíció – a sorozat n. elemét önmagát felhasználva, az n-1. és n-2. elem segítségével definiáljuk. C-ben a verem miatt lehetőség van arra, hogy egy függvény meghívja saját magát. Ez a rekurzió. A rekurzió mélységében az egyes hívásokhoz tartozó paraméterek és lokális változók egymástól függetlenek.

A rekurzió lényege, hogy a megoldandó problémát saját magára vezetjük vissza, egy egyszerűbb részfeladatra.

#include <stdio.h>

/* a Fibonacci feladat rekurziv megoldasa. */
int fib(int n) {
   if (n<2)
      return n;
   else
      return fib(n-2)+fib(n-1);
}

/* az iterativ megoldas */
int fib_it(int n) {
   int eloz=1, f=0, kov, i;

   for (i=0; i<n; ++i) {
      kov=f+eloz;
      eloz=f; f=kov;
   }
   return f;
}

int main(void) {
    int i;

    for (i=0; i<40; i++) {
        printf("%d ", fib(i));
        fflush(stdout);             /* ezt azert, hogy egybol megjelenjen */
    }
    printf("\n");
    for (i=0; i<40; i++) {
        printf("%d ", fib_it(i));
        fflush(stdout);
    }
    printf("\n");

    return 0;
}

Minden rekurzív problémának létezik iteratív megoldása is; amely azonban sokszor nem olyan triviális, mint a fenti. Ebben az esetben a rekurzív megoldás szép, de haszontalan, mert nagyon lassú tud lenni. Pl. a 4. fibonacci számhoz a függvény kiszámolja a 2.-at és a 3.-at. A 3. számhoz pedig kiszámolja a 1.-t és a 2.-at; nem véve figyelembe, hogy a 2-es már egyszer ki lett számolva.

A rekurzív fib() függvény által végzett számítás

8. Rendezés közvetlen kiválasztással

Egyik legegyszerűbb rendező algoritmus a kiválasztásos rendezés. Lényege az ábrán látható.

  1. Megkeressük a legkisebb elemet a tömbből.
  2. Megcseréljük azt a tömb legelső elemével.
  3. Innentől kezdve a tömb első eleme a legkisebb; ahhoz már nem kell nyúlni.
  4. Tekintjük a tömböt a második elemétől a végéig, és megcsináljuk rá ugyanezt.
  5. Az első két elem a helyén van.
  6. Tekintjük a tömböt a harmadik elemtől a végéig stb.
Rendezés közvetlen kiválasztással

A példaprogram feltölt egy tömböt véletlenszámokkal, rendezi és végül kiírja őket növekvő sorrendben. Szándékosan mindent külön függvénybe írtam; sőt, a főprogramban dinamikus memóriakezelést használok (a függvények egyébként nem tudják, hogy dinamikus memóriáról van-e szó). Ezek természetesen nem részei az algoritmusnak, hanem csakis az első függvény.

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

/* KIVALASZTASOS RENDEZES - EZ ITT A FENTI ALGORITMUS */
void rendez(int *tomb, int meret) {
    int i, j;
    for (i=0; i<meret-1; ++i) {
        int temp;
        int minindex=i;        /* ez a legkisebb :) */

        /* vagy megis van kisebb? */
        for (j=i+1; j<meret; ++j)
            if (tomb[j]<tomb[minindex])
                minindex=j;
        /* csere 3 lepesben */
        temp=tomb[minindex];
        tomb[minindex]=tomb[i];
        tomb[i]=temp;
    }
}

/* randommal feltolt */
void feltolt(int *tomb, int meret) {
    int i;
    for (i=0; i<meret; ++i)
        tomb[i]=rand()%100;
}

/* kiirja mindet */
void kiir(int *tomb, int meret) {
    int i;
    for (i=0; i<meret; ++i)
        printf("%5d", tomb[i]);
}

int main(void) {
    int *t;
    int meret;

    srand(time(0));

    printf("meret? "); scanf("%d", &meret);

    t=(int *) malloc(sizeof(int)*meret);
    feltolt(t, meret);
    rendez(t, meret);
    kiir(t, meret);
    free(t);

    return 0;
}

9. Buborékrendezés

A buborékrendezés egymás melletti elemeket cserél:

  1. Hasonlítsuk össze az első két elemet. Ha nincsenek jó sorrendben, cseréljük meg.
  2. Hasonlítsuk össze a második párt (második és harmadik elem). Esetleg csere.
  3. Folytassuk így a tömb végéig.
  4. Így, ha a legnagyobb elem a tömb elején is volt akár, akkor a végére került: azzal már a végleges helye.
  5. Csináljuk meg ugyanezt még egyszer, a tömb elejétől az utolsó előttiig. Az utolsóhoz már nem nyúlunk.
  6. Aztán ugyanezt megint, de az utolsó kettőhöz már nem nyúlunk stb.
Buborékrendezés

A buborékrendezés hatékonysága javítható azzal, ha megjegyezzük, hogy a vizsgált tömbrészletnél volt-e csere. Ha nem volt, akkor minden pár jó sorrendben van. Akkor a rövidebb részt vizsgálva ugyanerre az eredményre fogunk jutni, vagyis a külső ciklust már nem kell folytatni.

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

void buborek(int *tomb, int meret) {
    int i, j;

    /* egyre kisebb tombbel dolgozunk */
    for (j=meret-1; j>0; j--) {
        int voltcsere;

        voltcsere=0;
        /* belso ciklus, egymas mellettieket nezi */
        for (i=0; i<j; i++)
            /* ha az egymas mellettiek nem jok, csere */
            if (tomb[i]>tomb[i+1]) {
                int temp=tomb[i];
                tomb[i]=tomb[i+1];
                tomb[i+1]=temp;
                /* jegyezzuk meg, hogy volt dolgunk */
                voltcsere=1;
            }

        /* ha sehol nem csereltunk meg elemet, akkor
         * le lehet loni a ciklust */
        if (!voltcsere)
            break;
    }
}

#define MERET 15
int main(void) {
    int tomb[MERET];
    int i;

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

    /* rendezes es kiiras */
    buborek(tomb, MERET);
    for (i=0; i<MERET; i++)
        printf("%d ", tomb[i]);
    printf("\n");

    return 0;
}

A fenti kódban a break utasítás egy kulturált használata látható. A két egymásba ágyazott ciklus a buborékrendezés; for (j...j--) az egyre rövidebb részletek ciklusa, és for (i...i++) az egymás melletti párok ciklusa. Ezeknek a feltételeibe nem írjuk bele a „volt-e csere” feltételt. Helyette ha egy tömbrészlet vizsgálata után kiderül, hogy nem volt csere, akkor megszakítjuk a ciklust. Érezhető, hogy ez egy különleges körülmény, ami menet közben derül ki, és nem kapcsolódik semmilyen módon az „egyre rövidebb részletek” gondolathoz.