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;

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.)