Rozdíly

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

--- temata:26-datove_a_ridici_struktury:main [2011/02/17 21:53]
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ělíme na funkce a příkazy
@@ Řádek 36: / Řádek 38: @@
 ===Cykly===
+Cykly lze take libovolne vnorovat, nebo kombinovat s podminkami a vsim ostatnim.
 **while**
 - while (vyraz) {telo}
@@ Řádek 45: / Řádek 49: @@
 **for**
-for( inicializace ; test podmínky ; inkrementace ) {telo}
+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.1297976026.txt.gz · Poslední úprava: 2011/02/17 21:53 autor: sgs

Zobrazit stránku Starší verze

Zpětné odkazy Nahoru