Kalábovi

Kalábovic wikina

Uživatelské nástroje

Nástroje pro tento web


pitel:isz:datove_ridici_struktury

Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

Odkaz na výstup diff

pitel:isz:datove_ridici_struktury [03. 07. 2012, 13.53:45] (aktuální)
Řádek 1: Řádek 1:
 +====== 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<​sup>//​n//</​sup>​ − 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]]
 +<code c>int soucet(int x, int y);
 +
 +int soucet(int x, int y) {
 +    return x + y;
 +}
 +
 +printf("​%d\n",​ soucet(10, 20)); //30
 +</​code>​
 +
 +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]]
 +<code c>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*/​
 +}</​code>​
 +
 +**''​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]]
 +<code c>while (/​*podmínka*/​) {
 +    /​*příkazy*/​
 +}
 +
 +do {
 +    /​*příkazy*/​
 +} while (/​*podmínka*/​);</​code>​
 +
 +**''​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]]
 +<code c>for (/​*inicializace*/;​ /*test podmínky*/;​ /​*inkrementace*/​) {
 +    /​*příkazy*/​
 +}</​code>​
 +
 +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.
/var/www/wiki/data/pages/pitel/isz/datove_ridici_struktury.txt · Poslední úprava: 03. 07. 2012, 13.53:45 (upraveno mimo DokuWiki)