====== Datové a řídicí struktury ====== ===== Datové struktury ===== [[wp>Data structure]] **Strukturovaný datový typ** sestává z komponent jiného (dříve definovaného) typu, kterému říkáme **kompoziční typ**. Pokud jsou všechny komponenty strukturovaného typu stejného kompozičního typu, říkáme, že strukturovaný typ je **homogenní**. Komponentám homogenního typu se někdy říká **položky** (//item//), zatím co komponentám heterogenního typu se říká **složky** (//component//). Strukturovaný typ má **strukturovanou hodnotu**. Tato hodnota je definovaná tehdy, když jsou definované hodnoty všech jejích komponent. ==== Pole ==== [[wp>Array data structure]], [[wp>String (computer science)]] **Pole** (//array//) je homogenní ortogonální (pravoúhlý) datový typ. Jednorozměrnému poli říkáme **vektor**, dvojrozměrnému poli říkáme **matice**. Lze vytvářet pole s neomezenou vícerozměrnou hierarchickou strukturou. Prvek vektoru je zpřístupňován jedním, prvek matice dvojicí indexů. Indexem může být libovolný ordinální typ. Pro svou homogenitu říkáme prvkům pole také **položky**. Typ pole je specifikován **rozsahem svých dimenzí** (rozměrů) a komponentním typem. Pole, jehož jméno a velikost dimenzí je pevně dána deklarací a nemohou se měnit v průběhu programu, se nazývá **statické** (vs **dynamické**). Pokus o přístup k prvku pole, jehož index je mimo specifikovaný rozsah, způsobí chybu. **Řetězec** (//string//) je strukturovaný homogenní datový typ. Položkami řetězce je typ znak a řetězec má vlastnosti podobné jednorozměrnému poli znaků. ==== Seznam ==== [[wp>List (computing)]], [[wp>Linked list]] Seznam je homogenní, lineární, dynamická struktura. * Lineárnost znamená, že každý prvek struktury má právě jednoho předchůdce (predecessor) a jednoho následníka (successor). Výjimku tvoří první a poslední prvek. * Prvkem seznamu může být libovolný jiný datový typ -- také strukturovaný. Např. seznam seznamů. * Seznam může být prázdný. * Přístup k prvnímu (okrajovému) prvku je přímý, přístup k ostatním prvkům seznamu je sekvenční ve směru průchodu. Seznam, který lze procházet jen jedním směrem se nazývá "jednosměrně vázaný" zkráceně "jednosměrný", Seznam u něhož lze procházet oběma směry je "dvousměrně vázaný" -- "dvousměrný". {{ http://upload.wikimedia.org/wikipedia/commons/thumb/6/6d/Singly-linked-list.svg/500px-Singly-linked-list.svg.png |Singly-linked list}} {{ http://upload.wikimedia.org/wikipedia/commons/thumb/5/5e/Doubly-linked-list.svg/500px-Doubly-linked-list.svg.png |Doubly-linked list}} ==== Zásobník ==== {{ http://upload.wikimedia.org/wikipedia/commons/thumb/2/29/Data_stack.svg/200px-Data_stack.svg.png|Zásobník}} [[wp>Stack (data structure)]] Zásobník je homogenní, lineární, dynamická struktura. Zásobníku se také říká struktura typu **LIFO** z anglického "Last-In-First-Out". Základní operace jsou: * **Push** -- přidání pvku na vrchol zásobníku * **Pop** -- vyzvednutí pvku z vrchol zásobníku ==== Fronta ==== {{ http://upload.wikimedia.org/wikipedia/commons/thumb/5/52/Data_Queue.svg/200px-Data_Queue.svg.png|Fronta}} [[wp>Queue (data structure)]] Fronta je dynamická, homogenní a lineární struktura. Někdy se jí říká struktura typu "FIFO". Operace: * **Enqueue** -- zařazení prvku na konec fronty * **Dequeue** -- vyzvednutí prvku ze začítku fronty ==== Binární strom ==== {{ http://upload.wikimedia.org/wikipedia/commons/thumb/f/f7/Binary_tree.svg/200px-Binary_tree.svg.png|Binární strom}} [[wp>Binary tree]] Binární strom je buď prázdný, nebo sestává z jednoho uzlu zvaného kořen a dvou podstromů -- levého a pravého. Oba podstromy mají vlastnosti stromu. Binární strom je váhově vyvážený (weight balanced), když pro všechny jeho uzly platí, že počty uzlů jejich levého podstromu a pravého podstromu se rovnají, nebo se liší právě o 1. Stromu, počet jehož uzlů je 2//n// − 1, pro //n// > 0 a jehož výška je právě n říkáme absolutně váhově vyvážený strom. Binární strom je výškově vyvážený (height balanced) , když pro jeho všechny uzly platí, že výška levého podstromu se rovná výšce pravého podstromu, nebo se liší právě o 1. === Průchody stromem === [[wp>Tree traversal]] Existují 3 způsoby průchodů: Preorder, Inorder a Postorder. Předpony pre, in a post určují kdy přijde na řadu kořenový uzel. Dále vždy projdeme nejdříve levý podstrom a poté pravý. Inverzní varianty průchodů obrací pouze pořadí větví. ===== Řídicí struktury ===== ==== Funkce ==== [[wp>Subroutine]] int soucet(int x, int y); int soucet(int x, int y) { return x + y; } printf("%d\n", soucet(10, 20)); //30 Funkce umožňují rozložit složitější problémy na jednodušší podproblémy. **Deklarace** funkce (někdy také prototyp, v ukázce na začátku) se skládá z návratového typu, názvy funkce a seznamu parametrů. Ve většině případů ji lze vynechat, a použít rovnou definici. **Definice** funkce rozšiřuje deklaraci o blok těla funkce. Tělo funkce by mělo obsahovat příkaz ''return'' za kterým by měla následovat vracená hodnota jejíž typ se musí shodovat s návratovým typem funkce. Pokud má funkce návratový typ ''void'', za ''return''em nic nenásleduje. Příkaz ''return'' přeruší další provádění. Někdy se funkce s typem ''void'' označuje jako procedura. Funkce se volá jejím názvem a zadanými prarametry. ==== Složený příkaz (blok) ==== Složený příkaz je posloupnost libovolných příkazů (včetně dalších složených). Většinou se syntakticky odlišuje, například ''{}'' (C, Java, ...) nebo odsazením (Python). Proměnné mají většinou omezenou platnost jen pro blok (a podbloky) ve kterých byly deklarováný. ==== Výraz – příkaz ==== Výrazem je nejen aritmetický výraz, prostý výskyt konstanty (literálu) či proměnné, ale i funkční volání a přiřazení. Jestliže výraz ukončíme symbolem ; (středník), získáme výrazový příkaz. Zvláštním případem je prázdný příkaz. ==== Podmíněný příkaz ==== [[wp>Conditional_(programming)]], [[wp>Switch statement]] if (/*podmínka*/) { /*příkazy*/ } if (/*podmínka*/) { /*příkazy*/ } else { /*příkazy*/ } switch (/*proměnná*/) { case /*stav*/: /*příkazy*/ break; case /*stav*/: /*příkazy*/ break; /*...*/ default: /*příkazy*/ } **''If''** je nejtypičtější podmíněný příkaz. Podmínka má vždy výsledek ''true'' nebo ''false''. Je-li ''true'', provede se příkaz za ''if''em. Pokračuje-li navíc ''else'', jeho tělo se provede v případě že je výsledek podmínky ''false''. Složené závorky nejsou nutné, pokud se provede pouze jeden příkaz, společně s odsazením ale zvyšují přehlednost kódu a usnadňují doplnění dalšího kódu. **''Switch''** se používá pokud se rozhodujeme podle různých pevných hodnot jedné proměnně, například barva něčeho. Podmíněné příkazy je samozřejmě možné do sebe zanořovat. ==== Cykly ==== Slouží k několikanásobnému opakování stejného bloku kódu. Cykly je možné přerušit dvěma způsoby: * **''continue''** -- přestane provádět tělo smyčky a začne další iteraci * **''break''** -- úplně přestane smyčku provádět a dál pokračuje v běhu programu === while === [[wp>While loop]], [[wp>Do while loop]] while (/*podmínka*/) { /*příkazy*/ } do { /*příkazy*/ } while (/*podmínka*/); **''While''** se používá pokud předem neznáme počet opakování. Pokud je ''while'' uveden na začátku, nejdříve se vyhodnotí podmínka a až pak se připadně provede tělo. Je tedy možné, že se tělo neprovede vůbec. Při použití varianty ''do while'' se tělo provede nejméně jednou. === for === [[wp>For loop]] for (/*inicializace*/; /*test podmínky*/; /*inkrementace*/) { /*příkazy*/ } Tělo smyčky se provede tolikrát, dokud platí test podmínky. V těle je možné použít proměnnou inicializovanou v hlavičce smyčky.