Prednáška 13

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 = 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 = new int[a[1]];  // b teraz ukazuje na nové pole dĺžky 4 
delete[] b;         // uvoľníme pamäť alokovanú pre nové pole

Dvojrozmerné polia

• Doteraz sme stále pracovali s jednorozmerným poľom, čo však ak potrebujeme dvojrozmerné pole, maticu?
  • Napríklad na matice z algebry, alebo na dvojrozmerné tabuľky napr. body študentov z domácich úloh
• Podobne môžeme potrebovať aj polia väčších rozmerov, pracuje sa s nimi analogicky ako s dvojrozmenrný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 <iostream>
using namespace std;

int main() {
    /* Vytvorime pole s dvoma riadkami a piatimi stlpcami 
     * a rovno ho aj inicializujeme: */ 
    int a[2][5] = {{1,2,3,4,5},{6,7,8,9,10}}; 

    /* Vypiseme pole ako tabulku: */
    for (int i = 0; i <= 1; i++) {
        for (int j = 0; j <= 4; j++) {
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
}

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 slpcami bude v pamäti uložená nejako takto:

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

#include <iostream>
using namespace std;

int main() {
    int m, n;
    cout << "Zadaj pocet riadkov: ";
    cin >> m;
    cout << "Zadaj pocet stlpcov: ";
    cin >> n;
    
    /* Alokuj pole smernikov na riadky: */
    int **a;
    a = new int *[m];
    
    /* Alokuj jednotlive riadky: */
    for (int i = 0; i <= m-1; i++) {
        // a[i] je smernik na i-ty riadok 
        a[i] = new int[n];           
    }
    
    /* Nacitanie prvkov tabulky: */
    cout << "Zadaj cisla tabulky:" << endl;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            // nacitaj j-ty prvok i-teho riadku 
            cin >> a[i][j];          
        }
    }
    
    /* Spocitaj a vypis priemery jednotlivych stlpcov: */
    for (int j = 0; j < n; j++) {
        int sum = 0;
        for (int i = 0; i < m; i++) {
            sum += a[i][j];
        }
        cout << "Priemer hodnot v stlpci " << j 
             << " je " << (sum * 1.0)/m << endl;
    } 
    
    /* Uvolnenie pamate: */
    for (int i = 0; i <= m-1; i++) {
        delete[] a[i];
    }
    delete[] 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?

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 s m riadkami a n stĺpcami a vyplní ju číslami načítanými zo vstupu

Všimnite si, že funkciám potrebujeme dávať aj rozmery matice. Namiesto toho by sme si mohli spraviť štruktúru podobne ako pri dynamickom poli:

struct matica {
  int m, n;
  int **a;
}

Cieľ programu

Náš program bude v obdĺžnikovej tabuľke celých čísel uchovávať výškovú mapu nejakého územia, v ktorom nadmorská výška nadobúda hodnoty medzi 0 a 2000 metrami nad morom.

Program na vstupe najprv dostane dvojicu prirodzených čísel m a n. Výškovou mapou potom bude obdĺžnik pozostávajúci z m krát n štvorčekov, kde každý zo štvorčekov bude mať danú nejakú nadmorskú výšku od 0 po 2000 metrov nad morom (nadmorská výška 0 znamená more a kladná nadmorská výška znamená pevninu). Následne program postupne prečíta zo vstupu 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:

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

Program výšková mapa

#include <iostream>
#include "SVGdraw.h"
using namespace std;

/* velkost stvorceka mapy v pixeloch */
const int stvorcek = 15;

int **vytvorMapu(int m, int n) {
    /* Vytvori a vrati na vystupe mapu (obdlznikovu tabulku) s m riadkami a n stlpcami. */
    int **a;
    a = new int *[m];
    for (int i = 0; i <= m-1; i++) {
        a[i] = new int[n];
    }
    return a;
}

void zmazMapu(int m, int n, int **a) {
    /* Uvolni z pamate mapu s m riadkami a n stlpcami.
       Parameter n je nadbytocny, ale mohol by sa zist, keby napriklad 
       bolo treba z pamate uvolnovat aj jednotlive prvky matice a. */
    for (int i = 0; i <= m-1; i++) {
        delete[] a[i];
    }
    delete[] a;
}

void nacitajMapu(int m, int n, int **a) {
    /* Nacita hodnoty (nadmorske vysky) do uz vytvorenej mapy velkosti m krat n. */
    for (int i = 0; i <= m-1; i++) {
        for (int j = 0; j <= n-1; j++) {
            cin >> a[i][j];
        }
    }
}

void farba(SVGdraw &drawing, int r, int g, int b) {
    /* Nastavi farbu ciary aj vyplne na dane hodnoty. */
    drawing.setLineColor(r, g, b);
    drawing.setFillColor(r, g, b);
}

void vykresliMapu(int m, int n, int **a, SVGdraw &drawing) {
    /* Ofarbi jednotlive stvorceky mapy podla ich nadmorskej vysky:
     * modra -- more (nadmorska vyska 0)
     * zelena -- niziny (nadmorska vyska 1,...,200)
     * hneda -- "pohoria" (nadmorska vyska 200,...,2000) */
    for (int i = 0; i <= m-1; i++) {
        for (int j = 0; j <= n-1; j++) {
            /* nastavenie farby podla hodnoty */
            if (a[i][j] == 0) {
                farba(drawing, 0, 0, 255);
            } else if (a[i][j] <= 200) {
                double x = a[i][j] / 200.0;
                farba(drawing, x * 255, 127 + x * 127, 0);
            } else {
                double x = (a[i][j] - 200) / 1800.0;
                farba(drawing, 255 - x * 150, 255 - x * 200, 0);
            }
            /* Vykreslenie stvorceka; POZOR: vymena suradnic */
            drawing.drawRectangle(j * stvorcek, i * stvorcek, stvorcek, stvorcek);
        }
    }
}

void najvyssiVrch(int m, int n, int **a, int &riadok, int &stlpec) {
    /* Najde v mape a o rozmeroch m krat n stvorcek s najvyssou nadmorskou vyskou
       a jeho suradnice ulozi do premennych riadok resp. stlpec. */
    riadok = 0;
    stlpec = 0;
    for (int i = 0; i <= m-1; i++) {
        for (int j = 0; j <= n-1; j++) {
            if (a[i][j] > a[riadok][stlpec]) {
                riadok = i;
                stlpec = j;
            }
        }
    }
}

int main(void) {
    /* nacitaj rozmery matice */
    int m, n;
    cin >> m >> n;

    /* vytvor a nacitaj maticu */
    int **a = vytvorMapu(m, n);

    nacitajMapu(m, n, a);

    /* zobraz maticu */
    SVGdraw drawing(n * stvorcek, m * stvorcek, "mapa.svg"); // POZOR: vymena suradnic
    vykresliMapu(m, n, a, drawing);

    /* najdi najvyssi vrch a zvyrazni ho stvorcekom */
    int riadok, stlpec;
    najvyssiVrch(m, n, a, riadok, stlpec);

    drawing.setLineColor("black");
    drawing.setLineWidth(3);
    drawing.setNoFill();
    drawing.drawRectangle(stlpec * stvorcek, riadok * stvorcek, stvorcek, stvorcek); // POZOR: vymena suradnic

    /* ukonci vykreslovanie */
    drawing.finish();

    /* uvolni pamat matice */
    zmazMapu(m, n, a);
    
    return 0;
}

Polia reťazcov

Každý reťazec je pole znakov, ktoré možno interpretovať aj ako smerník na char. Pole reťazcov teda možno implementovať ako pole smerníkov na char. Keďže sa vo väčšine aplikácií môžu vyskytovať reťazce rôznych dĺžok, ukazuje sa tu byť užitočná vlastnosť polí smerníkov spomínaná vyššie – jednotlivé ich riadky môžu mať rôzne dĺžky.

Nasledujúci jednoduchý program je ukážkou použitia takto implementovaných polí reťazcov. Zo vstupu postupne načítava riadky, až kým je zadaný prázdny riadok. Tie postupne ukladá do poľa. Na záver sa všetky tieto reťazce vypíšu na výstup, oddelené medzerami.

#include <iostream>
#include <cstring>
using namespace std;

const int maxN = 1000;
const int maxRiadok = 1000;

int main(void) {
    char *a[maxN];
    char riadok[maxRiadok];
    int N = 0;
    while (N <= maxN-1) {                 
        cin.getline(riadok, maxRiadok);      // nacitame jeden riadok zo vstupu
        if (strcmp(riadok, "") == 0) {       // v pripade prazdneho riadku ukoncime nacitavanie
            break;
        }
        /* 
           Alokujeme pamat pre N-ty retazec pola a.
           (Musi byt o 1 vacsia, nez jeho dlzka -- dovodom je znak \0 na konci).
        */
        a[N] = new char[strlen(riadok) + 1]; 
        strcpy(a[N], riadok);
        N++;
    }
    // Vypiseme jednotlive riadky oddelene medzerami:
    for (int i = 0; i <= N-1; i++) {
        cout << a[i] << " ";
    }
    // Uvolnime pamat:
    for (int i = 0; i <= N-1; i++) {
        delete[] a[i];
    }

    return 0;
}

Cvičenie: prerobte tento program tak, aby namiesto poľa a fixnej veľkosti maxN používal dynamické pole.

Zadávanie argumentov programu z príkazového riadku

Polia reťazcov umožňujú okrem iného aj napísať program, ktorý dostane a spracuje jeden alebo viacero argumentov z príkazového riadku a na základe nich prípadne „upraví svoje správanie”. Príkladom programu využívajúcim túto funkcionalitu je aj samotný kompilátor g++. Jeho najjednoduchšie volanie

g++ program.cpp

obsahuje okrem názvu programu g++ aj argument program.cpp – ten dáva kompilátoru informáciu o tom, ktorý zdrojový súbor má kompilovať.

Na písanie programov umožňujúcich spracovanie takýchto argumentov je potrebné využiť „jemne pokročilejšiu” verziu funkcie main s hlavičkou

int main(int argc, char **argv)

– tú automaticky generujú viaceré pokročilejšie textové editory alebo IDE (napríklad NetBeans). Význam parametrov argc a argv je nasledovný:

• argv je pole reťazcov (resp. pole smerníkov na char) a argc je počet reťazcov v tomto poli.
• Reťazec argv[0] je vždy názov programu.
• Reťazce argv[1],...,argv[argc-1] sú jednotlivé argumenty.

Nasledujúci jednoduchý program postupne vypíše všetky argumenty, ktoré dostal z príkazového riadku.

#include <iostream>
using namespace std;

int main(int argc, char **argv) {
    for (int i = 0; i <= argc-1; i++) {
        cout << argv[i] << endl;
    }
    return 0;
}

Deklarácie so smerníkmi a poľami

Na dnešnej prednáške budeme kombinovať smerníky a polia, vytvoríme napríklad pole smerníkov. Môže sa vám hodiť nasledujúce:

• Operátor [ ] má vyššiu prioritu ako *. Napríklad zápis *a[10] teda treba chápať ako *(a[10]). To znamená, že vezmeme pole a, pozrieme sa na jeho desiaty prvok a následne na tento desiaty prvok aplikujeme dereferenciu. Prvky poľa a sú teda (v prípade, že robíme niečo zmysluplné) smerníky. Naopak (*p)[10] znamená nasledovné: vezmeme p, aplikujeme dereferenciu (p je teda smerník), ktorej výsledkom je pole a pozrieme sa na desiaty prvok tohto poľa.
• Operátor [ ] je zľava asociatívny a operátor * je sprava asociatívny. To znamená, že napríklad a[2][3] je to isté ako (a[2])[3] a **p je to isté ako *(*p).

Napríklad deklaráciu

int *a[10]; // t. j. *(a[10])

teraz treba chápať takto: ak vezmeme a, pozrieme sa na niektorý z desiatich prvkov tohto poľa a nakoniec aplikujeme dereferenciu, dostaneme hodnotu typu int. Zadeklarovali sme teda desaťprvkové pole smerníkov na int. Rovnako možno intepretovať aj nasledujúce deklarácie:

int **a;         // a je smernik na smernik na int; kazde pole smernikov na int tak mozno priradit do a (ale nie opacne)
int (*a)[10];    // a je smernik na pole desiatich celych cisel
int *(*(a[10])); // a je desatprvkove pole smernikov na smerniky na int
int **a[10];     // to iste, ako na predchadzajucom riadku

Smerníková aritmetika

Na smerníkoch možno vykonávať určité operácie, súhrn ktorých býva honosne nazývaný smerníkovou aritmetikou. Nech p, p1, p2 sú smerníky definované ako

T *p;
T *p1;
T *p2;

kde T označuje nejaký typ. Nech n je typu int. Potom:

• p + n označuje smerník na n-tý pamäťový úsek (postačujúci práve na uchovanie hodnoty typu T) za adresou p.
  • Napríklad p+n je to isté ako &p[n] a *(p+n) je to isté ako p[n].
  • p++ je skratkou pre p = p+1, ...
• Operátor [ ] je teda nadbytočný – p[n] je len skratkou pre často používaný výraz *(p+n).
• p - n označuje smerník na n-tý pamäťový úsek (postačujúci práve na uchovanie hodnoty typu T) pred adresou p.
• p1 - p2 je celé číslo k také, že p1 == p2 + k. Zmysluplný výsledok možno očakávať len vtedy, keď p1 a p2 sú adresami prvkov v tom istom poli (v jedinom súvislom kuse pamäte).
• Smerníky tiež možno prirodzene porovnávať relačnými operátormi ==, <, >, <=, >=, !=. Výsledok je zmysluplný opäť len vtedy, keď p1 a p2 sú adresami prvkov v tom istom poli.

Program, ktorý najprv načíta pole a následne prvky tohto poľa vypíše od konca, tak možno napísať napríklad aj takto:

#include <iostream>
using namespace std;

const int maxN = 1000;

int main(void) {
    int a[maxN];
    int N;
    cout << "Zadaj pocet cisel: ";
    cin >> N;
    for (int i = 0; i <= N-1; i++) {
        cout << "Zadaj cislo " << i + 1 << ": ";
        cin >> *(a + i);    
    }
    for (int i = N-1; i >= 0; i--) {
        cout << *(a + i) << " ";
    }
    cout << endl;
    return 0;
}