Kurz C++ (4.)

Vφtejte u dalÜφho serißlu v∞novanΘmu programovßnφ, ve kterΘm se v n∞kolika pokraΦovßnφch budeme v∞novat datov²m strukturßm a n∞kter²m algoritm∙m pro prßci s t∞mito strukturami. DneÜnφ dφl bude z velkΘ Φßsti opakovacφ.

1.1 ┌vod

Proto₧e v∞tÜina program∙, tedy snad vÜechny krom∞ typick²ch "Hello world!" program∙, pracuje s daty, je nutnΘ se krom∞ n∞kterΘho programovacφho jazyka seznßmit i se strukturami, do kter²ch m∙₧eme uklßdat svß data. V naÜem serißlu se nejprve podφvßme na zßkladnφ typy prom∞nn²ch a zopakujeme si n∞co o ukazatelφch. PotΘ p°ejdeme k polφm a to jak staticky, tak i dynamicky alokovan²m. Nßsledovn∞ se budeme zab²vat odvozen²mi datov²mi strukturami jako jsou zßsobnφk a fronta, kterΘ budeme implementovat pomocφ polφ. Dßle bude na °ad∞ struktura, jejφ₧ jednoduchou implementaci jsme si ukßzali ji₧ v kurzu jazyka C++ - lineßrnφ spojov² seznam. PotΘ se p°esuneme na strom, a budeme se zab²vat jeho velice pou₧φvanou mutacφ - binßrnφm stromem. Krom∞ datov²ch struktur se budeme zab²vat i algoritmy pracujφcφmi s t∞mito strukturami - p°edevÜφm t°φdφcφmi algoritmy. P°φklady k tomuto Φlßnku budou v jazycφch C nebo C++.

1.2. Zßkladnφ prom∞nnΘ

Mezi zßkladnφ prom∞nnΘ °adφme jednoduchΘ prom∞nnΘ (int, char, double apod.), v²Φtov² typ, struktury, unie, objekty a ukazatele. Jako poslednφ to budou pole, kter²mi se budeme zab²vat detailn∞ji. To by m∞ly b²t vÜechny zßkladnφ typy, kterΘ nßm nyn∞jÜφ p°ekladaΦe nabφzejφ.

1.2.1. JednoduchΘ prom∞nnΘ

Prom∞nnΘ jsou ulo₧eny v pam∞ti poΦφtaΦe na jistΘ adrese, abychom si nemuseli pamatovat adresu, na kterΘ se naÜe prom∞nnß nachßzφ, umo₧≥ujφ nßm p°ekladaΦe pojmenovßnφ prom∞nnΘ jmΘny - identifikßtory. Prom∞nnΘ vytvß°φme deklarovßnφm, p°i kterΘm specifikujeme jmΘno a typ prom∞nnΘ. Typ urΦuje, jakΘ hodnoty budeme moci do prom∞nnΘ ulo₧it a tedy i mφsto v pam∞ti, kterΘ prom∞nnß zabere. V nßsledujφcφ tabulce je uvedeno, kolik vybranΘ prom∞nnΘ zabφrajφ v pam∞ti:

Typ prom∞nnΘ	Velikost v Byte
char	1
short	2
int	4
float	4
double	8

Pozn.: m∙₧e se liÜit pro r∙znΘ operaΦnφ systΘmy a p°ekladaΦe, toto platφ pro p°ekladaΦ Microsoft Visual C++ 6.0

Prom∞nnΘ mohou mφt r∙zn² v²znam, podle toho na jakΘ stran∞ rovnφtka stojφ. Pokud prom∞nnß stojφ na levΘ stran∞, je tedy l-hodnotou, p°edstavuje mφsto v pam∞ti (adresu, kam se ulo₧φ v²sledek za rovnφtkem). Pokud stojφ na pravΘ stran∞ p°i°azenφ, pak je to hodnota prom∞nnΘ (nap°. typu int), kam ukazuje identifikßtor.

Vφme, ₧e prom∞nnΘ mohou existovat po cel² b∞h programu nebo jen v urΦitΘm bloku. Prom∞nnΘ proto d∞lφme na globßlnφ a lokßlnφ:

K t∞mto prom∞nn²m m∙₧eme p°idat jeÜt∞ prom∞nnΘ, kterΘ si m∙₧eme vytvo°it sami:

Pokud p°edßme funkci jako parametr jednoduchou prom∞nnou (tedy p°edßvßme parametr hodnotou), nem∙₧eme ji v t∞le funkce zm∞nit, proto₧e si p°ekladaΦ vytvo°φ kopii tΘto prom∞nnΘ a s nφ pak v t∞le funkce pracuje:

int prom = 5;

void ZmenProm(int i)
{
i = 66;
}

cout << "Promenna pred : " << prom << endl;
ZmenProm(prom); // predame hodnotou -> po vystupu z funkce bude prom nezmenena
cout << "Promenna po : " << prom << endl;

V odstavci o ukazatelφch si jeÜt∞ p°ipomeneme p°edßnφ parametru odkazem.

1.2.2. V²Φtov² typ

V²Φtov² typ lze s v²hodou pou₧φt k definovßnφ spolu souvisejφcφch konstant. Nap°. ve v∞tÜin∞ RPG her mßme postaviΦku, kterß mß vlastnosti jako je sφla, obratnost a inteligence. M∙₧eme tedy definovat v²Φtov² typ nßsledujφcφm zp∙sobem:

enum E_Vysledek { CHYBA = 0, OK };

enum E_Vlastnosti { Vl_Sila = 0, Vl_Obratnost, Vl_Inteligence, Vl_PocetVlastnosti } ;

int Vlastnosti[Vl_PocetVlastnosti];

StaΦφ definovat pevnou hodnotou jen prvnφ z konstant pat°φcφ do v²ΦtovΘho typu, p°ekladaΦ pak p°idßvß k dalÜφm jedniΦku. Pokud jako poslednφ nechßme Vl_PocetVlastnosti, mßme definovßnu velikost pole pro vÜechny vlastnosti. Funkce pro nastavenφ hodnoty n∞jakΘ vlastnosti pak mß nßsledujφcφ tvar:

E_Vysledek NastavVlastnost(E_Vlastnosti _vl, int _iHodnota)
{
    if(_vl < Vl_PocetVlastnosti)
    {
        Vlastnosti[_vl] = _iHodnota;

        return OK;
    }

    return CHYBA;
}

1.2.3. Struktury, unie a t°φdy

Struktura nßm umo₧≥uje slouΦit vφce datov²ch prvk∙ dohromady. Deklarujeme ji nßsledovn∞:

Pokud bychom v jazyce C cht∞li vytvo°it prom∞nnou typu Test, napφÜeme nßsledujφcφ:

Struktura m∙₧e obsahovat prvky r∙zn²ch typ∙. K p°φstupu k prvk∙m uvnit° struktury pou₧φvßme teΦkovΘ notace. Prom∞nnΘ le₧φ v pam∞ti v∞tÜinou za sebou v po°adφ, jak jsme je deklarovali, ale n∞kterΘ p°ekladaΦe mohou toto uspo°ßdßnφ m∞nit. Prom∞nnΘ ale nemusφ le₧et t∞sn∞ za sebou, p°ekladaΦ m∙₧e vklßdat r∙zn∞ dlouhΘ mezery, aby optimalizoval p°φstup do pam∞ti (nap°. zarovnßnφ na sudΘ adresy). V p°ekladaΦi Microsoft Visual C++ 6.0 m∙₧eme urΦit, jakΘ zarovnßnφ chceme pomocφ #pragma pack(cislo), kde cislo m∙₧e b²t 1,2,4,8 nebo 16. Velikost struktury tedy nemusφ odpovφdat souΦtu prvk∙ v nφ obsa₧en²ch. Nelze tedy takΘ spolΘhat na p°φstup do struktury p°es ukazatel a p°iΦφtßnφ velikosti prom∞nn²ch, kterΘ chceme p°eskoΦit.

Unie jsou zvlßÜtnφm p°φpadem struktury, kdy vÜechny prom∞nnΘ zaΦφnajφ na jednΘ adrese, sdφlejφ tedy pam∞¥. Nap°.:

union Test {
int a;
char c[4];
};

Test unie;
unie.a = 0x4A4F4841;
cout << unie.c << endl;

Objekty jsme se zab²vali v kurzu o C++ velice detailn∞, tak₧e jen p°ipomeneme, ₧e t°φda m∙₧e obsahovat metody a atributy.

V jazyce C++ je struktura vlastn∞ t°φdou, kterß mß implicitn∞ p°φstupovß prßva public a navφc pokud d∞dφme od struktury, tak implicitn∞ d∞dφme op∞t jako bychom pou₧ili public. Strukturu m∙₧eme pou₧φt jako rodiΦe pro t°φdu nebo struktura m∙₧e b²t potomkem t°φdy, ale unie pou₧φvat v d∞dickΘ hierarchii nesmφme. TakΘ nelze v unii mφt virtußlnφ metody. Pokud nenφ unie anonymnφ (bez specifikovanΘho jmΘna), pak m∙₧e obsahovat metody vΦetn∞ konstruktor∙ a destruktor∙.

1.2.4. Ukazatele

Ukazatele jsou zvlßÜtnφ druh prom∞nnΘ, kterΘ nesou adresu mφsta v pam∞ti, kde se nachßzφ pro nßs zajφmavß hodnota. Pokud chceme dostat hodnotu, na kterou ukazatel ukazuje, pak pou₧ijeme referenΦnφho operßtoru *. Pokud chceme zφskat adresu ji₧ existujφcφ prom∞nnΘ, pak pou₧ijeme operßtor dereferencovßnφ &:

int *p_i, i = 5;

p_i = &i; // ziskame adresu promenne i
cout << "Hodnota p_i : " << p_i << endl << "Hodnota na kterou ukazuje p_i : " << *p_i << endl;

Pokud p°i°adφme n∞jakou pevnou hodnotu p°φmo ukazateli p_i, pak si koledujeme o problΘmy, proto₧e se s nejv∞tÜφ pravd∞podobnostφ jednß o pam∞¥, kterß nßm nepat°φ. Nßsledn²m p°i°azenφm hodnoty na adresu, na kterou ukazuje p_i m∙₧e dojφt k chyb∞ p°φstupu do pam∞ti, program bude p°episovat cizφ data apod. Nßsledujφcφ k≤d je tedy Üpatn²:

int *p_i, i = 5;

p_i = (int *)(107); // nastavime pevne adresu
cout << "Hodnota p_i : " << p_i << endl << "Hodnota na kterou ukazuje p_i : " << *p_i << endl;

Po p°φstupu na tuto adresu dojde k chyb∞. NaÜt∞stφ je nutnΘ p°etypovßnφ, tak₧e k t∞mto problΘm∙m nem∙₧e dojφt ·plnou nßhodou.

Pokud pot°ebujeme mφsto v pam∞ti, pak si o n∞j m∙₧eme °φct prßv∞ za pou₧itφ ukazatel∙:

int *p_i;

p_i = new int; // ziskame adresu pridelene pameti

if(p_i)    // pokud nam byla pamet pridelena
{
    *p_i = 0;    // vynulujeme pridelenou pamet

    delete p_i; // a uvolnime pamet
}

JeÜt∞ si p°ipomeneme metodu p°edßvßnφ parametr∙ odkazem, kdy m∙₧eme zm∞nit uvnit° funkce vn∞jÜφ prom∞nnou:

int prom = 5;

void ZmenProm(int *p_i)    // pouzijeme ukazatel -> predani odkazem
{
    *p_i = 66;
}

cout << "Promenna pred : " << prom << endl;
ZmenProm(&prom);    // predame adresu promenne prom
cout << "Promenna po : " << prom << endl;

S ukazateli se setkßme i v nßsledujφcφch odstavcφch, kde si jeÜt∞ povφme n∞co o pointerovΘ aritmetice.

1.2.5. Pole

1.2.5.1. Jednorozm∞rnß pole

Pole nßm umo₧≥ujφ sdru₧it vφce hodnot stejnΘho typu a potΘ k nim p°istupovat pomocφ indexace. Jsou to tedy homogennφ datovΘ struktury, vÜechny prvky tedy majφ stejn² typ. Zopakujeme si deklaraci jednorozm∞rn²ch a vφcerozm∞rn²ch polφ. Nejprve jednorozm∞rnß:

V prvnφm p°φpad∞ je v²sledkem jednorozm∞rnΘ pole obsahujφcφ 20 prvk∙ typu int. Velikost pole m∙₧eme urΦit pomocφ operßtoru sizeof() nßsledujφcφm zp∙sobem:

Pokud pot°ebujeme znßt poΦet prvk∙ v poli m∙₧eme vyd∞lit velikost pole velikostφ prvnφho prvku. Zde je k≤d:

cout << "Pocet prvku pole je: " << sizeof(statPole1D)/sizeof(statPole1D[0]) << endl;

Jednorozm∞rnß pole jsou v pam∞ti reprezentovßna jako souvisl² ·sek prom∞nn²ch urΦitΘho typu. Pokud pou₧ijeme identifikßtor pro pole bez hranat²ch zßvorek urΦujφcφch index, pak mßme ukazatel a k jednotliv²m prvk∙m m∙₧eme p°istupovat i podle nßsledujφcφho vzoreΦku:

Pokud chceme deklarovat jednorozm∞rnΘ pole dynamicky, pak pou₧ijeme nßsledujφcφ:

K prvk∙m pole pak zase p°istupujeme pomocφ hranat²ch zßvorek a index∙. Pokud nßm to vyhovuje vφce, pak m∙₧eme pou₧φt pointerovΘ aritmetiky a v²Üe uvedenΘho vzoreΦku. Po pou₧itφ pole nezapomeneme pam∞¥ uvolnit:

if(dynPole1D)    // nezpominame pri pristupu overit, ze pole existuje
{
    // prace s polem

    delete dynPole1D;
}

1.2.5.2. Vφcerozm∞rnß pole

Vφcerozm∞rnß pole jsou vlastn∞ pole slo₧enß z polφ, ve dvourozm∞rnΘm p°φpad∞ je to tabulka:

	0	1	2	3
0	statPole2D[0][0]	statPole2D[0][1]	statPole2D[0][2]	statPole2D[0][3]
1	statPole2D[1][0]	statPole2D[1][1]	statPole2D[1][2]	statPole2D[1][3]
2	statPole2D[2][0]	statPole2D[2][1]	statPole2D[2][2]	statPole2D[2][3]

Pokud bychom cht∞li zjistit velikost tohoto dvourozm∞rnΘho pole, pak pou₧ijeme nßsledujφcφ:

Pokud pot°ebujeme znßt poΦet prvk∙ v poli m∙₧eme vyd∞lit velikost pole velikostφ prvnφho prvku. Zde je k≤d:

cout << "Pocet prvku pole je: " << sizeof(statPole2D)/sizeof(statPole2D[0][0]) << endl;

cout << "Pocet radku pole je: " << sizeof(statPole2D)/sizeof(statPole2D[0]) << endl;

cout << "Pocet sloupcu pole je: " << sizeof(statPole2D[0])/sizeof(statPole2D[0][0]) << endl;

Vφcerozm∞rnß pole jsou v pam∞ti uklßdßna po °ßdcφch. Pro p°φstup k prvk∙m m∙₧eme op∞t pou₧φvat pointerovΘ aritmetiky:

Vφcerozm∞rnß pole se dajφ samoz°ejm∞ deklarovat i jako pole jednorozm∞rnß, nap°. v²Üe uvedenΘ dvourozm∞rnΘ pole o rozm∞rech 3x4 lze stejn∞ dob°e zobrazit pomocφ jednorozm∞rnΘho pole, kterΘ bude mφt 12 prvk∙.

#include <iostream>

using namespace std;

typedef int *PINT;    // definujeme typ ukazatel na int

int main()
{
    int **dynPole2D;    // ukazatel na ukazatel

    dynPole2D = new PINT[3];    // vytvorime radky

    for(int i = 0; i < 3; i++)
    {
        dynPole2D[i] = new int[4];    // do radku pak vlozime 4 sloupce
    }

    int k = 0;

    for(i = 0; i < 3; i++)
        for(int j = 0; j < 4; j++)
        {
            dynPole2D[i][j] = k++;    // naplnime hodnotami
        }

    // vypis pole
    for(i = 0; i < 3; i++)
    {
        for(int j = 0; j < 4; j++)
        {
            cout << dynPole2D[i][j] << " ";
        }
        cout << endl;
    }

    for(i = 0; i < 3; i++)
    {
        delete(dynPole2D[i]);    // !!!nejdrive!!! smazeme sloupecky
    }

    delete [] dynPole2D;    // smazeme radky

    char c;
    cin >> c;
    return 0;
}

Programovacφ jazyk C++ nßs neomezuje maximßlnφm poΦtem dimenzφ, tak₧e je to vÜe doslova na naÜφ fantazii a pam∞ti poΦφtaΦe.

1.3. Co bude p°φÜt∞

DneÜnφ lekce byla zopakovßnφm zßkladnφch typ∙ prom∞nn²ch. V p°φÜtφm pokraΦovßnφ se podφvßme na vyhledßvßnφ hodnoty v poli a pak na t°φd∞nφ jednorozm∞rnΘho pole n∞kolika metodami - bublinkovΘ t°φd∞nφ, quicksort a dalÜφ. Potom budou nßsledovat odvozenΘ datovΘ struktury zalo₧enΘ na polφch - fronta a zßsobnφk.

DatovΘ struktury a algoritmy (1.)