InfoCo je PDA
Co je PDA
PDA BE300
Seznámení
Výbava
Obsah CD
Hardware
Tipy & Triky
Manuály
Hardware
Operační systémy
Hry
Programy
Programování
HP Jornada 720
Info
Výbava
Software
Hry
ActiveSync
E-knihy
.
Prohlížeče
Tvorba e-Knih
LOG-in/outInformace
|
Zimního času |
| Dnes je: 23. 11. 2024 |
| Internetový čas
@ 728 |
9. díl - Ukazatele a odkazy, vyhledávání půlením intervalu
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.
|
|
... pokračování zde ...
|
Stránka byla už zobrazena: 206 ×
