Ukazatele a odkazy, vyhledávání půlením intervalu

9. díl - Ukazatele a odkazy, vyhledávání půlením intervalu

Petr Sklenička       26.01.2011       C++/C       18300 zobrazení

Tento díl slouží jako stručné seznámení s ukazateli a odkazy. Ukážeme si, jak získat adresu v paměti nějaké proměnné, jak tuto adresu uložit do ukazatele a jak dynamicky alokovat paměť. Také si ukážeme, jak docílíme toho, aby nám funkce "vracela" dvě hodnoty. Nakonec si vysvětlíme a napíšeme algoritmus vyhledavání půlením intervalu.

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
}

Tento kód na první pohled vypadá úplně stejně, jako ten předchozí, drobná změna v něm však je – podívejte se na hlavičku funkce vratDvojnasobek. Před x se objevil znak &. Tento znak (operátor adresy) znamená, že chceme x předat odkazem. A díky tomu si již funkce nebude vytvářet kopii proměnné, ale bude pracovat s proměnnou x, kterou jsme si zavedli ve funkci main. Proto už i poslední výpis hodnoty proměnné x bude jiný než v předchozí ukázce. Hodnota x bude samozřejmě 10, neboť ve funkci vratDvojnasobek se hodnota x změnila.

Nyní si ještě ukážeme, jak to udělat, když potřebujeme, aby nám funkce “vrátila” dvě hodnoty. Píšu to slovo v uvozovkách, protože ve skutečnosti nám funkce nevrátí nic (žádné return), bude pouze měnit hodnoty proměnných, které ji předáme odkazem. Představte si, že chceme napsat banální funkci, která přehodí hodnoty dvou proměnných. Na to, jakým způsobem přehodit hodnoty dvou proměnných, jistě přijdete. Stačí použít třetí pomocnou proměnnou a jde to snadno (hodnoty dvou celočíselných proměnných lze prohodit i bez použití třetí proměnné – můžete si na to zkusit přijít). Napíšeme tedy funkci, která bude mít dva parametry, kterými samozřejmě budou právě ty dvě proměnné, jejichž hodnoty chceme přehodit. Ve funkci hodnoty přehodíme, ale když budeme chtít napsat return, nastane problém. S pomocí slova return dvě hodnoty nevrátíme. My už ale do jisté míry umíme používat odkazy, takže si s problémem poradíme následně:

#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);
}

Jak funguje funkce hledej? Nejprve se ptáme, zda náhodou již levaMez není větší než pravaMez – to je podmínka, kdy skončí rekurze a znamená to, že prvek v poli není. Pokud podmínka není splněná, pokračujeme dále a to tak, že si najdeme “střed” pole. Zeptáme se, zda na pozici mojePole[stred] je hledaný prvek, pokud tam je, našli jsme. V opačném případě se ptáme, zda je hledaný prvek větší nebo menší než prvek na pozici mojePole[stred] a rekurzivně pokračujeme v té či oné části pole. Ještě jednou připomínám, algoritmus funguje pouze na seřazeném poli.

Pokud jste tento algoritmus pochopili a chápete i jeho implementaci pomocí rekurze, můžete si algoritmus zkusit napsat bez použití rekurze – k tomu Vám bude stačit cyklus while a nějaká ta podmínka. Pro tento díl je to vše. Pokud mě do dalšího dílu nic důležitého, co by nemohlo počkat, nenapadne, začneme příště s OOP.

 

hodnocení článku

4 bodů / 4 hlasů       Hodnotit mohou jen registrované uživatelé.

 

Všechny díly tohoto seriálu

13. Virtuální metody 01.02.2012
12. Dědičnost 24.07.2011
11. Konstruktory, destruktory a hrátky s objekty 28.05.2011
10. Úvod do objektově orientovaného programování 10.03.2011
9. Ukazatele a odkazy, vyhledávání půlením intervalu 26.01.2011
8. Funkce 18.12.2010
7. Cykly, neboli smyčky - pokračování 19.11.2010
6. Cykly, neboli smyčky 26.10.2010
5. Pole 13.07.2010
4. Relační operátory a podmínky, příkaz switch 29.06.2010
3. Proměnné a konstanty 22.06.2010
2. První program 15.06.2010
1. Úvod, příprava na psaní aplikací v C++ 08.06.2010

 

Mohlo by vás také zajímat

C++/CLI a interoperabilita managed a unmanaged kódu - díl 1.: Úvod do jazyka a základní konstrukce

V tomto článku je popsána nadstavba C++ pro práci s .NET prostředím zvaná C++/CLI umožňující vytvářed mixed assembly obsahující jak managed tak unmanaged kód. V prvním díle je popsána myšlenka jazyka a základní syntaktické konstrukty (základní typy, podmínky, cykly, pole, namespace a část tříd a objektů). U čtenáře je předpokládána znalost .NET frameworku a nativního programování nejlépe v C++ (alespoň syntaxi a základy).

C++/CLI a interoperabilita managed a unmanaged kódu - díl 2.: Složitější konstrukty, low-level přístup a generické programování

V tomto článku je popsána nadstavba C++ pro práci s .NET prostředím zvaná C++/CLI umožňující vytvářed mixed assembly obsahující jak managed tak unmanaged kód. V tomto díle jsou popsány pokročilejší partie jazyka týkající se hlavně objektů, low-level přístupu k managed objektům a generického programování.

Virtuální souborový systém

Článek pojednává o způsobu návrhu virtuálního souborového systému. Před čtením Vám doporučuji stáhnout si a přečíst zadání, abyste věděli o co vlastně jde. Ke stažení jsou i zdrojové kódy v jazyce C++. Aplikace asi nemá žádné velké využití, nicméně přišlo mi to jako zajímavý problém - jednalo se o semestrální projekt.

 

 

Nový příspěvek

 

Mr.

1'

csharp|

xml|

css|


'

nahlásit spamnahlásit spam -1 / 1 odpovědětodpovědět

Je tam chyba !

Ten algoritmus je chybný. Hodnotu 320 v poli najde, i když tam není ! Chybí ošetření překročení horní hranice pole.

nahlásit spamnahlásit spam 0 / 2 odpovědětodpovědět

Diskuse: Ukazatele a odkazy, vyhledávání půlením intervalu

Dobrý den,

píšete, že toto nejde:

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

void main()
{
    int velikostPole;

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

    int mojePole[velikostPole];
}

Rád bych se zeptal proč? (nijak se o tom napřu, ale vím, že v jiných jazycích toto lze, tak by mne zajímalo, proč toto nejde...)

Díky

nahlásit spamnahlásit spam 2 / 4 odpovědětodpovědět

V kterých jazycích to prosím jde? Nejedná se o interpretované jazyky? Co vím, tak ani ve VB.NET to nejde. Asi ve VBA nebo JavaScriptu by to jít mohlo... Nejsem moc znalý, ale i ve VB.NET se to obchází "ReDim Preserved". V C# to bude myslím podobné...

nahlásit spamnahlásit spam -2 / 2 odpovědětodpovědět

Diskuse: Ukazatele a odkazy, vyhledávání půlením intervalu

Dobrý den,

Prosím Vás, jaký je rozdíl, když napíšete

int main()
{
příkazy
}

a

void main()
{ 
příkazy
}

V tomto díle kde se vysvětlujou ukazatele

je kód

void main()
{
    int a = 27;
	int* p_a = &a;		  
	cout << "Adresa promenne a: " << p_a << "\n";
	cout << "Hodnota promenne a: " << *p_a << "\n";		 
}

mi při spuštění programu vyšlo úplně to stejné, když napíšu místo void main() - int main().

Možná jsem něco ve vysvětlení přehlédl.

nahlásit spamnahlásit spam 0 / 2 odpovědětodpovědět

Klíčovým slovem void říkáme, že funkce (jakákoliv, ne jen main) nebude nic vracet, čili nebude mít žádnou návratovou hodnotu.

Pokud napíšete int, znamená to, že funkce vrací typ int. Pak je nutné mít ve funkci klíčové slovo return, kterým vrátíte hodnotu.

Korektnější zápis funkce main je tento:

int main()
{
   // prikazy
   return 0;
}

Samozřejmě ani zápis s pomocí void a bez slova return není chybný, ale vzpomínám si, že nějakému kompilátoru na Linuxu se to nelíbilo a chtěl int main().

nahlásit spamnahlásit spam 1 / 3 odpovědětodpovědět

Diskuse: Ukazatele a odkazy, vyhledávání půlením intervalu

Dobry den,

jsem pravidelnym ctenarem Vasich clanku a moc se mi libi. Nedavno jsem se zacal zajimat o programovani v C++ a i presto, ze jsem si koupil knihu, velice rad si prectu Vas clanek a priucim se, protoze jsou psany strucne a jasne. Dekuji

nahlásit spamnahlásit spam 1 / 3 odpovědětodpovědět

Díky za pochvalu.

nahlásit spamnahlásit spam 1 / 3 odpovědětodpovědět
                       
Nadpis:
Antispam: Komu se občas házejí perly?
Příspěvek bude publikován pod identitou   anonym.

Nyní zakládáte pod článkem nové diskusní vlákno.
Pokud chcete reagovat na jiný příspěvek, klikněte na tlačítko "Odpovědět" u některého diskusního příspěvku.

Nyní odpovídáte na příspěvek pod článkem. Nebo chcete raději založit nové vlákno?

 

  • Administrátoři si vyhrazují právo komentáře upravovat či mazat bez udání důvodu.
    Mazány budou zejména komentáře obsahující vulgarity nebo porušující pravidla publikování.
  • Pokud nejste zaregistrováni, Vaše IP adresa bude zveřejněna. Pokud s tímto nesouhlasíte, příspěvek neodesílejte.

přihlásit pomocí externího účtu

přihlásit pomocí jména a hesla

Uživatel:  
Heslo:  

zapomenuté heslo

 

založit nový uživatelský účet

zaregistrujte se

 
zavřít

Nahlásit spam

Opravdu chcete tento příspěvek nahlásit pro porušování pravidel fóra?

Nahlásit Zrušit

Chyba

zavřít

feedback