Prednáška 15 - Programovanie

Oznamy
Opakovanie smerníkov
Dvojrozmerné polia
- Dvojrozmerné polia s konštantnou veľkosťou
- Dvojrozmerné pole pomocou poľa smerníkov
Príklad: výšková mapa
- Cieľ programu
- Program výšková mapa
Hra life
Polia reťazcov
Vstupy do funkcie main
Deklarácie so smerníkmi a poľami
Zhrnutie

Oznamy

Prednáška budúci pondelok 16.11. bude mimoriadne v učebni M-IV (v F2 sa koná vedecká konferencia).

Opakovanie smerníkov

Smerníky na jednoduché premenné:

int n = 7;         // premenná typu int 
int *p = NULL;     // smerník na premennú typu int 
p = &n;            // p ukazuje na n, *p a n sú zhruba to isté 
*p = 8;            // v premennej n je teraz 8 
n = (*p)+1;        // v premennej n je teraz 9

Smerníky a polia, alokovanie poľa:

int a[3];
int * b = a; // a,b sú teraz takmer rovnocenné premenné 
*b = 3;
b[1] = 4;
a[2] = 5;   // v poli sú teraz čísla 3,4,5 
b = malloc(sizeof(int) * a[1]);  
// b teraz ukazuje na nové pole dĺžky 4
free(b);  // uvoľníme pamäť alokovanú pre nové pole

Dvojrozmerné polia

Doteraz sme pracovali s jednorozmerným poľom, čo však ak potrebujeme dvojrozmerné pole, maticu?
Príklady dvojrozmerných polí:
- dvojrozmerné tabuľky napr. body študentov z domácich úloh,
- matice z algebry (budúci semester),
- rastrové obrázky.
Podobne môžeme potrebovať aj polia väčších rozmerov, pracuje sa s nimi analogicky ako s dvojrozmernými.

Dvojrozmerné polia s konštantnou veľkosťou

Ak je veľkosť dvojrozmerného poľa vopred známa konštanta, môžeme ho vytvoriť veľmi jednoducho
- napr. int a[2][5] vytvorí tabuľku s dvomi riadkami a piatimi stĺpcami
- a[i][j] je potom prvok na riadku i a stĺpci j
- Rozmery poľa musíme uviesť aj ak pole posielame do funkcie, napr. void vypis(int a[2][5])
Tento spôsob však nebudeme ďalej používať, lebo väčšinou chceme rozmery prispôsobiť potrebám daného vstupu.

#include <stdio.h>
int main(void) {
    /* Vytvoríme pole s dvoma riadkami a piatimi stľpcami 
     * a rovno ho aj inicializujeme: */ 
    int a[2][5] = { {1,2,3,4,5}, {6,7,8,9,10} };

    /* Vypíšeme pole ako tabuľku: */
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 5; j++) {
            printf("%d ", a[i][j]);
        }
        printf("\n");
    }
}

Dvojrozmerné pole pomocou poľa smerníkov

Omnoho flexibilnejšou alternatívou sú polia smerníkov.
Každý riadok tabuľky bude jedno dynamicky alokované pole a smerník na jeho začiatok si uložíme do poľa smerníkov.
Tabuľka s m riadkami a n sĺpcami bude v pamäti uložená nejako takto:

Nasledujúci program načíta rozmery dvojrozmernej tabuľky, potom jej prvky a spočíta priemer čísel v každom stĺpci.

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

int main(void) {
    int m, n;
    printf("Zadaj pocet riadkov: ");
    scanf("%d", &m);
    printf("Zadaj pocet stlpcov: ");
    scanf("%d", &n);
    
    /* Alokuj pole smerníkov na riadky: */
    int **a;
    a = malloc(sizeof(int *) * m);
    
    /* Alokuj jednotlivé riadky: */
    for (int i = 0; i < m; i++) {
        // a[i] je smerník na i-ty riadok
        a[i] = malloc(sizeof(int) * n);
    }
    
    /* Načítanie prvkov tabuľky: */
    printf("Zadaj cisla tabulky:\n");
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            // načítaj j-ty prvok i-teho riadku
            scanf("%d", &a[i][j]);
        }
    }
    
    /* Spočítaj a vypíš priemery jednotlivých stĺpcov: */
    for (int j = 0; j < n; j++) {
        int sum = 0;
        for (int i = 0; i < m; i++) {
            sum += a[i][j];
        }
        printf("Priemer hodnot v stlpci %d je %f\n", j, ((double)sum) / m);
    }
    
    /* Uvoľnenie pamäte: */
    for (int i = 0; i < m; i++) {
        free(a[i]);
    }
    free(a);
}

Cvičenie:

Ako by ste spočítali priemery stĺpcov vstupnej tabuľky s využitím iba jednorozmerného poľa? (Celú tabuľku teda nechceme ukladať.)
Ako by vyzeralo vytvorenie a použitie trojrozmernej tabuľky?
Ako by sme navzájom vymenili prvý a druhý riadok tabuľky? Ako prvý a druhý stĺpec?

Príklad: výšková mapa

Pokračujme ukážkou o niečo väčšieho programu využívajúceho dvojrozmerné tabuľky (matice).

Maticu uložíme ako dynamicky alokované pole smerníkov.
V programe je niekoľko funkcií, ktoré sa môžu zísť aj v iných programoch na prácu s maticami.
int **vytvorMaticu(int m, int n) alokuje pamäť pre maticu s m riadkami a n stĺpcami a vráti smerník na pole smerníkov.
void zmazMaticu(int **a, int m) uvolní pamäť alokovanú pre maticu a s m riadkami (počet stĺpcov nepotrebujeme).
void nacitajMaticu(int **a, int m, int n) dostane už alokovanú maticu a s m riadkami a n stĺpcami a vyplní ju číslami načítanými zo vstupu.

Cieľ programu

Náš program bude v obdĺžnikovej tabuľke celých čísel uchovávať výškovú mapu.

Bude to obdĺžniková tabuľka s m riadkami a n stĺpcami.
Každé políčko obsahovať nadmorskú výšku od 0 po 2000 metrov nad morom (nadmorská výška 0 znamená more a kladná nadmorská výška znamená pevninu).
Program na vstupe najprv dostane rozmery tabuľky m a n a následne nadmorské výšky všetkých štvorčekov.
Takto zadanú mapu program vykreslí pomocou knižnice SVGdraw, pričom každý štvorček dostane určitú farbu podľa svojej nadmorskej výšky.
Následne zavolá funkciu najvyssiVrch, ktorá nájde najvyšší bod (resp. jeden z najvyšších bodov) vykresľovaného územia a v mape ho zvýrazní rámikom.

Príklad vstupu a výstupu:

 11
  0    0    0    0    0    0    0    0    0    0
  0    0   40   80  100  120  140  120    0    0
 40   80  120  160  200  240  280  190  100    0
 60  120  180  240  300  360  420  260  100    0
 80  160  240  320  400  480  560  160    0    0
 80  120  300  400  500  600    0    0    0    0
  0   80  160  180  600    0    0    0    0    0
  0    0    0    0    0    0    0   70    0    0
  0    0    0    0  800  960  700  200    0    0
  0    0  540  420  900  700  500    0    0    0
  0  220  600  800 1000 1200 1400  680    0    0
 20  240  660  880 1100 1320 1540  750  100    0
 40  280  720  960 1200 1440 1680  820  100    0
 60  420  780 1040 1300 1560 1820 1200  400    0
 80  360  840 1120 1400 1680 1960 1500  600    0
 40  280  720  960 1200 1440 1680 1000  400    0
100  220  600  800 1000 1200 1400  680  100    0
 60  120  480  640  800  960 1120  540  100    0
 20    0    0  480  600  720  840  400  100    0
  0    0  240  320  400  480  560  260  100    0
  0    0    0  160  200  240  280    0    0    0
  0    0    0    0    0    0    0    0    0    0

Program výšková mapa

#include <stdio.h>
#include <stdlib.h>
#include "SVGdraw.h"

/* veľkosť štvorčeka mapy v pixeloch */
#define SIZE 15

int **vytvorMaticu(int m, int n) {
    /* Vytvorí a vráti maticu (obdĺžnikovú tabuľku)
     * s m riadkami a n stĺpcami. */
    int **a;
    a = malloc(sizeof(int *) * m);
    for (int i = 0; i < m; i++) {
        a[i] = malloc(sizeof(int) * n);
    }
    return a;
}

void zmazMaticu(int **a, int m) {
    /* Uvoľní z pamäte maticu s m riadkami. */
    for (int i = 0; i < m; i++) {
        free(a[i]);
    }
    free(a);
}

void nacitajMaticu(int **a, int m, int n) {
    /* Načíta hodnoty do už vytvorenej matice
     * veľkosti m krát n. */
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &a[i][j]);
        }
    }
}

void nastavFarbu(int vyska, Drawing drawing) {
    /* podľa nadmorskej výšky nastaví farbu čiary
     * aj výplne
     * modrá -- more (nadmorská výška 0)
     * zelená -- nížiny (nadmorská výška 1,...,200)
     * hnedá -- "pohoria" (nadmorská výška 200,...,2000) */

    // premenné pre červenú, zelenú a modrú zložku farby
    int r, g, b;
    // nastavenie farby podľa hodnoty
    if (vyska == 0) { // modré more
        r = 0;
        g = 0;
        b = 255;
    } else if (vyska <= 200) { // zelené nížiny
        double x = vyska / 200.0;
        r = x * 255;
        g = 127 + x * 127;
        b = 0;
    } else {  // žlto-hnedé hory
        double x = (vyska - 200) / 1800.0;
        r = 255 - x * 150;
        g = 255 - x * 200;
        b = 0;
    }

    /* Nastaví farbu čiary aj výplne na dané hodnoty. */
    setLineColorRGB(drawing, r, g, b);
    setFillColorRGB(drawing, r, g, b);
}

void vykresliStvorcek(int riadok, int stlpec, Drawing drawing) {
    /* Vykresli štvorcek pre daný riadok a stĺpec mapy.
     * Použije pri tom aktuálne nastavené farby.
     * Pozor, pri vykresľovaní
     * uvádzame najskôr x (stĺpec), potom y (riadok) */
    drawRectangle(drawing, stlpec * SIZE,
                  riadok * SIZE,
                  SIZE, SIZE);
}

void vykresliMapu(int **a, int m, int n, Drawing drawing) {
    /* Vykresli mapu rozmerov m krát n do obrázku.
     * Jednotlivé štvorčeky mapy ofarbi podľa ich nadmorskej výšky */
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            nastavFarbu(a[i][j], drawing);
            vykresliStvorcek(i, j, drawing);
        }
    }
}

void maximumMatice(int **a, int m, int n, int *riadok, int *stlpec) {
    /* Nájde v matici a s rozmermi m krát n
     * políčko s maximálnou hodnotou
       a jeho súradnice uloží do premenných *riadok, *stlpec. */
    *riadok = 0;
    *stlpec = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i][j] > a[*riadok][*stlpec]) {
                *riadok = i;
                *stlpec = j;
            }
        }
    }
}

int main(void) {
    /* načítaj rozmery matice */
    int m, n;
    scanf("%d %d", &m, &n);

    /* vytvor a načítaj maticu */
    int **a = vytvorMaticu(m, n);
    nacitajMaticu(a, m, n);

    /* zobraz maticu, pozor výmena súradnice */
    Drawing drawing = drawingInit(n * SIZE, m * SIZE,
                                  "mapa.svg");
    vykresliMapu(a, m, n, drawing);

    /* nájdi najvyšší vrch a zvýrazni ho štvorčekom */
    int riadok, stlpec;
    maximumMatice(a, m, n, &riadok, &stlpec);

    setLineColor(drawing, "black");
    setLineWidth(drawing, 3);
    setNoFill(drawing);
    vykresliStvorcek(riadok, stlpec, drawing);

    /* ukonči vykresľovanie */
    drawingFinish(drawing);

    /* uvoľni pamäť matice */
    zmazMaticu(a, m);
}

Hra life

Hra life je jednoduchá simulácia kolónie buniek, ktorá má zaujímavé teoretické vlastnosti.

Máme mriežku m x n štvorčekov, v každom žije najviac 1 bunka.
Bunky sa rodia a umierajú podľa toho, koľko majú susedov v ôsmych okolitých políčkach.
- Ak v čase t má bunka 2 alebo 3 susedov, zostane žiť aj v čase t+1, inak zomiera.
- Ak v čase t má prázdne políčko presne 3 susedov, narodí sa tam v čase t+1 nová bunka.

Stav hry si môžeme pamätať v matici boolovských hodnôt.

Príklad vstupu

Pre jednoduchosť vstup uvádzame ako nuly a jednotky bez medzier (1=živá bunka). Výslednú animáciu nájdete tu.

20 20
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000111111111100000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000

Rátanie zmeny v matici

Stav v čase t máme v matici a, do matice b chceme dať stav v čase t+1.

int zratajOkolie(int m, int n, bool **a, int riadok, int stlpec) {
    /* počet zivých prvkov v okolí */
    int sucet = 0;
    for (int i = riadok - 1; i <= riadok + 1; i++) {
        for (int j = stlpec - 1; j <= stlpec + 1; j++) {
            /* treba ošetriť okraje matice */
            if (i >= 0 && i < m && j >= 0 && j < n && a[i][j]) {
                sucet++;
            }
        }
    }
    /* samotný štvorček nechceme zarátať */
    if (a[riadok][stlpec]) {
        sucet--;
    }
    return sucet;
}

void prepocitajMaticu(int m, int n, bool **a, bool **b) {
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            /* spočítaj počet živých prvkov v okolí */
            int pocet = zratajOkolie(m, n, a, i, j);
            /* priraď do b[i][j] hodnotu podľa okolia a[i][j] */
            b[i][j] = (pocet == 3 || (pocet == 2 && a[i][j]));
        }
    }
}

Ďalšie detaily programu

Celý program, ktorý načíta vstup a simuluje 10 krokov hry Life aj s vytvorením animácie: Program Life
Prepočítavanie chceme opakovať v cykle pre viacero časových intervalov.
Môžeme prekopírovať celú maticu z b späť do a, ale rýchlejšie je len vymeniť smerníky.

    for (int i = 0; i < 10; i++) {
        /* podľa a spočítaj maticu do b */
        prepocitajMaticu(m, n, a, b);
        /* vymeň smerníky, aby v a bola nová matica */
        bool **tmp = b;
        b = a;
        a = tmp;
    }

vytvorMaticu, zmazMaticu a pod. prepíšeme tak, aby robili s maticou boolovských hodnôt namiesto intov.
V animácii na začiatku vykreslíme celú maticu, potom prekreslíme vždy len tie bunky, ktoré sa zmenili.

Polia reťazcov

Dvojrozmerné polia v C nemusia mať všetky riadky rovnako dlhé. To sa hodí napríklad na ukladanie viacerých reťazcov.
Spomeňte si, že v C je reťazec jednoducho pole char-ov, kde za posledným znakom ide špeciálny znak 0.
Pole reťazcov bude teda dvojrozmerné pole char-ov.
Môžeme načítavať napr. vstup po riadkoch, pričom každý riadok načítame do dlhého poľa, ktoré by malo stačiť a potom do prekopírujeme do akurát veľkého riadku v poli.
Nakoniec program riadky vypíše odzadu.
Ak by sme vopred alokovali NMAX riadkov, každý veľkosti MAXRIADKOV, vyšlo by potenciálne na zmar oveľa viac pamäte.

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

#define NMAX 1000
#define MAXRIADOK 1000

int main(void) {
    char *a[NMAX];   // pole smerníkov na char
    char riadok[MAXRIADOK];  // pole pre načítavanie riadkov
    int n = 0;
    while (true) {
        // načítame jeden riadok
        char *result = fgets(riadok, MAXRIADOK, stdin);
        // ak je koniec súboru alebo sa minuli položky poľa a,
        // končíme načítavanie
        if (result == NULL || n == NMAX) {
            break;
        }
        // alokujeme pamäť pre n-tý reťazec poľa a
        // pozor, k strlen pridáme 1 kvôli 0 na konci
        a[n] = malloc(sizeof(char) * (strlen(riadok) + 1));
        // prekopírujeme riadok
        strcpy(a[n], riadok);
        n++;
    }

    // vypíšeme riadky odzadu
    for (int i = n - 1; i >= 0; i--) {
        fputs(a[i], stdout);
    }

    // uvoľníme pamäť
    for (int i = 0; i < n; i++) {
        free(a[i]);
    }
}

Cvičenia:

Prečo nemáme na konci programu free(a)?
Čo by sa stalo, ak by sme namiesto a[n] = malloc(sizeof(char) * (strlen(riadok) + 1)); strcpy(a[n], riadok) dali a[n] = riadok?
Prerobte program tak, aby namiesto poľa a fixnej veľkosti NMAX používal dynamické pole.
Vedeli by sme dynamické polia nejako použiť aj na načítavanie jednotlivých riadkov?

Vstupy do funkcie main

Často vidíte v programoch funkciu main s nasledujúcou hlavičkou:

int main(int argc, char ** argv) {

Vstupné argumenty argc a argv sa používajú pri spúšťaní programu na príkazovom riadku.

argv je pole C-čkových reťazcov a argc je počet reťazcov v tomto poli
Prvý reťazec, argv[0], je meno samotného programu a ostatné sú argumenty programu
Videli sme napríklad spúšťanie kompilátora na príkazovom riadku:

gcc program.c -o program

Tu gcc je meno programu, ktoré je nasledované tromi argumentami "program.c", "-o" a "program". Tieto argumenty dávajú kompilátoru informáciu o tom, ktorý zdrojový súbor má kompilovať a kam má uložiť spustiteľný program.

Nasledujúci jednoduchý program vypíše všetky argumenty, ktoré dostal z príkazového riadku, vrátane mena programu.

#include <stdio.h>

int main(int argc, char ** argv) {
    for (int i = 0; i < argc; i++) {
        printf("%s\n", argv[i]);
    }
}

Deklarácie so smerníkmi a poľami

Príklady na prácu s maticami uvedené vyššie môžete modifikovať vo vlastných programoch, ale je dobré trochu lepšie rozumieť logike práce so smerníkmi v C/C++.

Operátor [ ] je zľava asociatívny, t.j. a[2][3] je to isté ako (a[2])[3]
Operátor * je sprava asociatívny, t.j. **p je to isté ako *(*p).
Operátor [ ] má vyššiu prioritu ako *, t.j. *a[2] je to isté ako *(a[2]).
Ak x je pole smerníkov na int, tak *(x[2]) znamená, že vezmeme pole x, pozrieme sa na jeho druhý prvok a následne na tento druhý prvok aplikujeme dereferenciu, čím dostaneme int.
Ak x je smerník na pole int-ov, (*x)[2] znamená, že vezmeme x, aplikujeme dereferenciu, ktorej výsledkom je pole int-ov a pozrieme sa na druhý prvok tohto poľa.

Cvičenie:

Premennú x sme vytvorili príkazom int **x = vytvorMaticu(4,4). S ktorými prvkami tabuľky potom pracujú výrazy *(x[2]) a (*x)[2]?

Komplikácie nastávajú aj pri pochopení typov premenných. Pomôžu nasledujúce rady.

Deklaráciu premennej int *p môžeme čítať takto: Ak vezmeme smerník p a aplikujeme na neho operátor *, získame hodnotu typu int.
Deklarácia int *a[4] je to isté ako int *(a[4]) a znamená: Ak vezmeme a, pozrieme sa na niektorý zo štyroch prvkov tohto poľa a nakoniec aplikujeme dereferenciu, dostaneme hodnotu typu int. Vytvorili sme teda štvorprvkové pole smerníkov na int. Jednotlivé smerníky v poli zatiaľ nie sú inicializované.
Deklarácia int (*a)[4] znamená: Ak vezmeme a, aplikujeme dereferenciu, dostaneme pole a keď sa pozrieme na niektorý prvok tohto poľa, dostaneme int. Riadok teda vytvorí smerník na pole štyroch celých čísel. Tento smerník však zatiaľ ukazuje na náhodné miesto pamäte, žiadne nové pole nevzniklo. To sa nám málokedy zíde, premennú a môžeme zadefinovať radšej ako int **a.
Deklarácia int *(*(a[4])) vytvorí štvorprvkové pole smerníkov na smerníky na int. Dá sa zapísať aj bez zátvoriek int **a[4].

Zhrnutie

Hlavnou náplňou dnešnej prednášky bolo vytvorenie a používanie dvojrozmerných polí pomocou poľa smerníkov na riadky.
Môžete používať a podľa potreby upravovať funkcie int ** vytvorMaticu(int m, int n), void zmazMaticu(int **a, int m) a void nacitajMaticu(int **a, int m, int n) z programu s výškovou mapou.
Pole reťazcov je vlastne dvojrozmerná tabuľka znakov, ktorej riadky môžu mať rôznu dĺžku (a každý je správne ukončený nulou).
Pozor na správnu alokáciu a dealokáciu. Pri práci so smerníkmi sa oplatí nakresliť si obrázok, čo kam ukazuje.