OBSAH WEBU
ČTĚTE!
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/19 10:42] 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 68: | Řádek 70: | ||
| =====Datové struktury===== | =====Datové struktury===== | ||
| - | Dělíme na funkce a příkazy | + | **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~~ | ||
