Rozdíly

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

Odkaz na výstup diff

temata:26-datove_a_ridici_struktury:main [2011/02/17 21:22]
sgs
temata:26-datove_a_ridici_struktury:main [2012/05/14 14:34] (aktuální)
conyx [Seznamy]
Řádek 1: Řádek 1:
 +~~ODT~~
 +
 =====Řídící struktury===== =====Řídící struktury=====
 Dělíme na funkce a příkazy Dělíme na funkce a příkazy
Řádek 21: Řádek 23:
 V **bloku** mohou být lokální proměnné, i se stejným jménem jako mimo blok, mají platnost pouze v bloku. Nelze je použít mimo. V **bloku** mohou být lokální proměnné, i se stejným jménem jako mimo blok, mají platnost pouze v bloku. Nelze je použít mimo.
  
-====Podmíněné příkazy====+===Podmíněné příkazy===
 klasické if/else. V některých jazycích lze pouze if, nekdě je nutná i else část. Může být v bloku i bez bloku, pokud je bez bloku, počítá se pouze první příkaz za podmínkou. Ja slovem if následuje **výraz**. Tyto podmínky lze libovolně vnořovat - pozor na správné zavorkovíní. klasické if/else. V některých jazycích lze pouze if, nekdě je nutná i else část. Může být v bloku i bez bloku, pokud je bez bloku, počítá se pouze první příkaz za podmínkou. Ja slovem if následuje **výraz**. Tyto podmínky lze libovolně vnořovat - pozor na správné zavorkovíní.
  
 +===Switch - přepínač===
 +Přepínač slouží k větvenívýpočtu podle hodnoty celočíselného výrazu (v některých jazicích to mohou být i znaky a řetězce).
 +  * Vyhodnotívýraz,hodnotu porovnávás casenávěštími. Pokud nalezne odpovídajícíhodnotu, předářízenína toto návěští.
 +  * Pokudhodnotě výrazu neodpovídá žádné návěští, je řízenípředáno návěští default.
 +  * Pokud default chybí a nevykoná se žádná varianta, řízení se předá bezprostředně za příkaz přepínače.
 +  * V jednom přepínači nelze mít dvě návěští se stejnou hodnotou, může být default nejvýše jednou
 +  * Návěštícaselze ukončit příkazem break. Pokud tomu tak není, program bude pokračovat přes všechna následujícínávěští, dokud nenarazína break, returnnebo konec přepínače.
 +  * Příkaz break může být v rámci přepínače umístěn v libovolně zanořeném bloku.
 +  * Příkaz break se vždy vztahuje k nejbližšímu nadřazenému přepínači nebo cyklu.
 +  * Pro default platí stejná  pravidla jako pro ostatnínávěští. Konvence říká, že by se mělo zapisovat na konec přepínače.
 +
 +===Cykly===
 +Cykly lze take libovolne vnorovat, nebo kombinovat s podminkami a vsim ostatnim.
 +
 +**while**
 +- while (vyraz) {telo}
 +- dopředu neznáme počet iterací, cyklus nemusí proběhnout ani jednou.
 +
 +**do while** 
 +- do {} while (vyraz);
 +- proběhne alespoň jednou
 +
 +**for**
 +for( inicializace ; test podmínky ; zmena ridici promenne) {telo}
 +  * asi není nutné doprodobna vysvetlovat jednotlivé části.
 +  * pokud uvnitr nemanipulujeme s ridící proměnnou, známe dopředu počet opakovaní.
 +  * lze používat více řídících proměnných.
 +
 +**break** - tímto příkazem lze kdykoliv ukončit nejblíže vnořený cyklus
 +
 +**continue** - tímto příkazem lze kdykoliv ukončit aktualní opakování a začít další iteraci.
 +
 +
 +===Skoky===
 +**goto**
 +<code>
 +goto navesti;
 +printf("Toto se nikdy nevytiskne.");
 +navesti: printf("Toto se vytiskne.");
 +</code>
 +- nepoužívá se!
 +- jako příkaz skoku se dá označit i break a continue, protože také přesunou vykonávání na jiné místo.
 +
 +=====Datové struktury=====
 +**Datová struktura** - abstraktní vyjádření zúčastněných vlastností (atributů) prvků (objektů) řešeného problému
 +
 +**Abstraktní datový typ (ADT)**  - je definován množinou hodnot, jichž mohou nabývat prvky tohoto typu a množinou operací definovaných nad tímto typem. 
 +Jeden konkrétní prvek ADT bývá označován jako abstraktní datová struktura (ADS).
 +
 +Základní datové strukuty nám často nabízí samotný programovací jazyk, například strutury, uniony, množiny. O tom ale tato otázka asi být nemá, jde o struktury které si vytváříme sami a musíme pracovat s pamětí.
 +
 +====Seznamy====
 +Seznam je homogenní, lineární, dynamická struktura.
 +
 +**Lineárnost** = každý prvek struktury má právě jednoho předchůdce a jednoho následníka (mimo první a poslední prvek). 
 +
 +Prvkem seznamu může být libovolný datový typ (klidně další seznam). Seznam může být i prázdný. Přístup k prvnímu prvku je přímý, k ostatním sekvenční ve směru průchodu.
 +
 +**Jednosměrný seznam** – průchod jedním směrem.
 +
 +Operace:
 +  * ListInit(L) – vytvoření nového prázdného seznamu
 +  * First(L) – neprázdný seznam → aktivita na prvním prvku
 +  * Succ(L) – aktivní seznam → prvek za aktivním získává aktivitu, v případě posledního seznam ztrácí aktivitu
 +  * Active(L) – aktivní seznam → True, neaktivní → False
 +  * InsertFirst(L, E) – vloží prvek E na začátek seznamu
 +  * CopyFirst(L, E) – operace vrátí do E první prvek seznamu – nutný test na neprázdnost
 +  * DeleteFirst(L, E) – smazání prvního prvku, pokud byl aktivní → ztráta aktivity seznamu
 +  * PostInsert(L, E) – aktivní seznam → vložení prvku E za aktivní prvek
 +  * PostDelete(L) – odstranění prvku za aktivním prvkem
 +  * Copy(L, E) – vrací do E hodnotu aktivního prvku
 +  * Actualize(L, E) – přepíše hodnotu aktivního prvku na E
 +
 +**Dvojsměrný seznam** - průchod oběma směry
 +
 +- doplnění operací jednosměrného First → First, Last; Post → Post, před
 +
 +**Kruhový jednosměrný** – poslední prvek ukazuje na první
 +
 +Typické operace nad seznamem – zjištění délky, ekvivalence dvou seznamů, hledání prvku v seznamu, řazení prvků v seznamu, konkatenace (spojení) seznamů
 +
 +====Zásobník====
 +- homogenní, lineární, dynamická struktura
 +
 +- lze odvodit od seznamu pokud má přístup pouze od začátku
 +
 +- struktura typu lifo
 +
 +- implementace polem, seznamem
 +
 +Operace:
 +  * Init(Z) – inicializace 
 +  * Push(Z, E) – vložení prvku E na vrchol zásobníku
 +  * Pop(Z) – smazání prvku na vrcholu zásobníku
 +  * Top(Z, E) – vrátí do E vrchol zásobníku, nutný test na prázdnost
 +  * Empty(Z) – pokud je prázdný tak True, jinak False
 +
 +====Fronta====
 +- dynamická, homogenní, lineární struktura
 +
 +- struktura typu FIFO
 +
 +Operace:
 +  * Init(F) – inicializace fronty
 +  * QueUp(F, E) – vložení na konec fronty
 +  * Remove(F) – zrušení prvního prvku
 +  * Front(F, E) – do E se uloží první prvek fronty, nutný test na neprázdnost
 +  * Empty(F) - pokud je prázdná tak True, jinak False
 +
 +====Strom====
 +  * kořenový strom je acyklický graf, který má jeden zvláštní uzel, který se nazývá root (kořen)
 +  * kořen je uzel, pro který platí že z každého uzlu stromu vede jedna cesta do kořene.
 +  * z každého uzlu směrem ke kořeni vede pouze jedna hrana do uzlu (otcovský) a libovolný počet hran k uzlům synovským
 +  * výška prázdného stromu je 0
 +  * strom s kořenem má výšku 1
 +  * výška stromu je dána počtem hran k nejvzdálenějšímu uzlu + 1
 +
 +Rekurzivní definice: Binární strom je buď prázdný nebo se sestává z jednoho uzlu zvaného kořen a dvou podstromů – levého a pravého.
 +
 +Binární strom je váhově vyvážený pokud pro všechny jeho uzly platí že počty uzlů jejich levého a pravého podstromu se rovnají nebo se liší právě o 1.
 +
 +Binární strom je výškově vyvážený pokud pro všechny jeho uzly platí že výška levého a pravého podstromu se rovná nebo se liší právě o 1.
 +
 +Absolutně vyvážený strom – n výška stromu n > 0 a 2n – 1 = počet uzlů.
 +
 +Algoritmy nad BS můžou být rekurzivní i nerekurzivní.
 +
 +**Průchod stromem:**
 +  * posloupnost všech uzlů stromu v níž se žádný uzel nevyskytuje dvakrát
 +  * transformace nelineární struktury stromu na lineární 
 +
 +- preorder - jdeme po stromu, kdyz k prvku dorazime zleva, zapiseme ho
 +
 +- inorder - jdeme po stromu, kdyz k prvku dorazime zespodu, zapiseme ho
 +
 +- postorder - jdeme po stromu, kdyz k prvku dorazime zprava, zapiseme ho
 +
 +===== Potvrzení =====
 +
 +<doodle single login|26>
 +^ OK ^ !!! ^
 +</doodle>
 +
 +{{tag>sgs IAL}}
 +
 +~~DISCUSSION~~
temata/26-datove_a_ridici_struktury/main.1297974154.txt.gz · Poslední úprava: 2011/02/17 21:22 autor: sgs
Recent changes RSS feed Debian Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki