dotNETportal.cz

Co je to ukazatel

Ukazatel, nebo též pointer, je proměnná, která uchovává paměťovou adresu. Je to velmi silný nástroj jazyka C++, neboť ukazatele umožňují přímou manipulaci s pamětí počítače. Předem podotýkám, že je dost možné, že po přečtení tohoto dílu asi plně neuvidíte, jaký je přínos ukazatelů, nicméně postupem času (a čtením dalších dílů) budete zjišťovat, že nějaký přínos opravdu mají.

Paměť počítače je rozdělena do sekvenčně číslovaných paměťových buněk, přičemž každá proměnná je umístěna na jedinečném místě. Toto místo se označuje jako adresa v paměti. Obvykle není nutné znát adresu nějaké proměnné, neboť to je starost kompilátoru. Kdybychom ale chtěli přece jen adresu proměnné zjistit, stačí použít operátor adresy (&) – ten vrací adresu objektu.

#include <iostream>
using namespace std;

void main()
{
    int a = 27;

    cout << &a << "\n";
}

Pokud si zkompilujete tento kratičký kousek kódu, výstupem Vám bude adresa proměnné a. Nyní tedy víme, že každá proměnná má svou adresu. Aniž bychom tuto adresu museli znát, je možné ji uložit do ukazatele. Kdybychom tedy chtěli adresu naší celočíselné proměnné a uložit do ukazatele, provedli bychom to tímto způsobem:

int* p_a = &a;

Tímto zápisem vzniká proměnná p_a jako ukazatel na typ int. Znamená to, že p_a bude uchovávat adresu celého čísla. Určitě jste si všimli, jak se zápis liší od normální proměnné – za slovem int je hvězdička. S pomocí tohoto ukazatele je možné získat hodnotu proměnné a. To nazýváme nepřímým přístupem, protože my prostřednictvím ukazatele nepřímo přistupujeme k proměnné a.

Operátor nepřímého přístupu ( * ) se také nazývá dereference, neboli zrušení odkazu. Zrušení odkazu ukazatele neznamená nic jiného, než to, že získáme hodnotu uloženou na adrese, jejíž hodnota je v ukazateli.

cout << "Adresa promenne a: " <<  p_a << "\n";
cout << "Hodnota promenne a: " << *p_a << "\n";

Dynamická alokace paměti

Vzhledem k tomu, že ukazatele se hojně používají ve spojení s OOP, které jsme zatím neprobírali, ukážeme si využití ukazatelů na příkladu, kde OOP nepotřebujete. Určitě si vzpomenete na díl, ve kterém jsme probírali pole. Když jsme chtěli vytvořit pole např. 20 prvků typu int, stačilo napsat toto:

int mojePole[20];

To je asi jasné. Co kdybychom ale chtěli velikost pole určit podle zadání uživatele, čili velikost pole by se určovala za běhu programu? Pozornějšího čtenáře by možná mohlo napadnout toto řešení:

// Tento priklad NELZE ZKOMPILOVAT!
#include <iostream>
using namespace std;

void main()
{
    int velikostPole;

    cout << "Zadejte velikost pole: ";
    cin >> velikostPole;

    int mojePole[velikostPole];
}

Takovým způsobem to ale nejde. Kompilátor Vám vypíše chybu. V tomto případě je nutné pole vytvořit jinak – s pomocí ukazatele.

#include <iostream>
using namespace std;

void main()
{
    int velikostPole;

    cout << "Zadejte velikost pole: ";
    cin >> velikostPole;

    int* mojePole = new int [velikostPole];
}

Nyní je třeba si kód trochu vysvětlit, nebo spíš poslední řádek kódu. My vlastně deklarujeme mojePole jako ukazatel na první položku v poli. Jinak řečeno, mojePole ukazuje (neboli má adresu) na mojePole[0]. Poté už s polem můžeme pracovat jak to známe z minulých dílů.

for (int i = 0; i < velikostPole; i++)
        mojePole[i] = i * i;        // 0, 1, 4, 9, 16 ...

Takto například pole naplníme druhými mocninami čísel 0, 1, 2…velikostPole – 1.

Když jsme si velikost pole určili až za běhu programu, neudělali jsme nic jiného, než že jsme si přiřadili nějakou část paměti našemu poli. V případě, že zjistíme, že v programu již pole nepotřebujeme, je dobré paměť opět uvolnit – k tomu slouží klíčové slovo delete.

delete [] mojePole;

Na hranaté závorky nesmíme zapomenout, říkáme tím, že uvolňujeme z paměti pole.

Předávání argumentů funkci odkazem

Jak víme, každá funkce v jazyce C++ buď nevrací nic, nebo vrací právě jednu hodnotu. Toto mírné omezení lze obejít předáváním argumentů odkazem. Když budeme funkci předávat argument tak, jako jsme se to naučili v minulém díle, tak se v oboru platnosti funkce vytvoří kopie argumentu. Abyste přesně pochopili předchozí větu, podívejte se na následující kus kódu.

#include <iostream>
using namespace std;

int vratDvojnasobek(int x)
{
    x = 2 * x;
    return x;
}

void main()
{
    int x = 5;
    cout << "Promenna x: " << x << "\n";            // Vystup: Promenna x: 5
    cout << "Hodnota, vracena funkci: " << vratDvojnasobek(x) << "\n";
    cout << "Promenna x: " << x << "\n";            // Vystup: Promenna x: 5
}

Nejprve vypisujeme hodnotu proměnné x, která je 5. Poté voláme funkci, která hodnotu x zdvojnásobí. Zde je ale velmi nutné si uvědomit, že funkce nemanipuluje s proměnnou x, kterou jsme si zavedli ve funkci main. Funkce si ve svém oboru platnosti vytvoří kopii této proměnné, čili na posledním řádku programu, kde se opět vypisuje hodnota x, se také vypíše hodnota 5.

#include <iostream>
using namespace std;

int vratDvojnasobek(int &x)
{
    x = 2 * x;
    return x;
}

void main()
{
    int x = 5;
    cout << "Promenna x: " << x << "\n";            // Vystup: Promenna x: 5
    cout << "Hodnota, vracena funkci: " << vratDvojnasobek(x) << "\n";
    cout << "Promenna x: " << x << "\n";            // Vystup: Promenna x: 10
}

#include <iostream>
using namespace std;

void vymenit(int &a, int &b);

void main()
{
    int x = 3, y = 5;

    cout << "Pred zamenou: x = " << x << " y = " << y << "\n";
    vymenit(x, y);
    cout << "Po zamene: x = " << x << " y = " << y << "\n";
}

void vymenit(int &a, int &b)
{
    int pom;
    pom = a;
    a = b;
    b = pom;
}

Ještě jednou podotýkám, že my funkci vymenit nepředáváme hodnoty proměnných, ale místa v paměti, kde jsou proměnné uložené – funkce pak pracuje s touto částí paměti.

O ukazatelích a odkazech by se ještě dalo napsat více věcí, nicméně jejich větší uplatnění je při objektově orientovaném programování, které jsme zatím neprobírali, čili zatím jenom vezměte na vědomí, že ukazatelé a odkazy v C++ existují, zatím přibližně víte, jak fungují, ale dál se s nimi zatím netrapte. Až se plně ponoříme do OOP, ukazatelé se vrátí a tam uvidíme jejich sílu.

V tomto díle jste se tedy vlastně až tam moc nenaučili. Proto si nyní vysvětlíme jeden algoritmus, konkrétně vyhledávání půlením intervalu (ten nemá s ukazateli ani odkazy nic společného), ale určitě byste jej měli znát.

Vyhledávání půlením intervalu

Představte si, že máme pole celých čísel. My chceme zjistit, zda je v tomto poli obsažen nějaký prvek, čili jej budeme hledat. Jeden ze způsobu, jak to udělat, je postupně procházet celé pole a ptát se, zda prvek, na kterém se právě nacházíme, je roven prvku, který hledáme. Tímto způsobem bychom jej určitě našli (nebo nenašli), ale co když se bude jednat o velmi velké pole a prvek bude až na konci pole? Krom toho, že ztratíme spoustu času, než jej najdeme, se nestane nic. Mnohem lepší způsob je však použít algoritmus vyhledávání půlením intervalu. Tento algoritmus však funguje pouze na seřazeném poli. Říkáme, že pole celých čísel je seřazené, pokud jsou v něm prvky uspořádané od nejmenšího k největšímu (nebo naopak). V našem příkladu budeme uvažovat, že pole již setříděné máme. Algoritmů, jak seřadit pole, je celá řada, od těch banálních až po ty složitější. Pokud Vás to zajímá, podívejte se zde: http://vbnet.cz/clanek--97-naucte_se_programatorsky_myslet_dil_1_algoritmy_pro_trideni_1.aspx Jedná se o pěkný článek od pana Hercega, ve kterém popisuje dva jednoduché algoritmy pro třídění – třídění výběrem a bublinkové třídění. Pokud si článek přečtete, nemělo by Vám dělat problém algoritmy přepsat do C++.

Dejme tomu tedy, že máme pole velikosti n, které je seřazené (od nejmenšího prvku po největší). Vyhledávání půlením intervalu pak funguje takto: Nejprve se podíváme na prvek mojePole[n / 2], čili “doprostřed” pole. Zeptáme se, zda prvek, který hledáme, je na této pozici. Pokud ano, prvek jsme našli. Pokud ne, ptáme se, zda prvek na pozici n / 2 je menší, nebo větší než prvek, který hledáme. Pokud je menší, budeme hledáním pokračovat v levé části pole, jinak v pravém. Uvědomme si, že jedním porovnáním jsme eliminovali n / 2 prvků v poli. Algoritmus pak pokračuje stejným způsobem ve zbylé půlce pole. Opět se tato půlka “rozpůlí” a ptáme se na to samé. Celé se to opakuje tak dlouho, dokud prvek nenajdeme, nebo pokud zjistíme, že tam prvek není.

Celý algoritmus je možné implementovat dvěma způsoby. Buď rekurzivně (to si ukážeme), nebo s pomocí cyklů (to nechám na Vás).

#include <iostream>
using namespace std;

bool hledej(int mojePole[], const int x, const int levaMez, const int pravaMez);

int main()
{
    const int N = 10;            // velikost pole
    int mojePole[N] = {3, 7, 10, 11, 15, 20, 30, 48, 99, 102};
    const int x = 320;

    if (hledej(mojePole, x, 0, N) == true)
        cout << "Prvek " << x << " byl nalezen.\n";
    else
        cout << "Prvek " << x << " nenalezen.\n";

    return 0;
}

/*
 * mojePole - pole, ve kterem hledame
 * x - prvek, ktery hledame
 * levaMez, pravaMez - urcuji, v jake oblastni pole budeme hledat
 */
bool hledej(int mojePole[], const int x, const int levaMez, const int pravaMez)
{
    if (levaMez > pravaMez)
        return false;                        // prvek nenalezen
    int stred = (levaMez + pravaMez) / 2;
    if (mojePole[stred] == x)
        return true;
    if (x < mojePole[stred])                // hledani bude pokracovat v leve casti pole
        return hledej(mojePole, x, levaMez, stred - 1);
    else                                    // jinak pokracujeme v prave casti
        return hledej(mojePole, x, stred + 1, pravaMez);
}