Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
statnice:bakalar:b0b36prp [2026/06/14 11:13] – [6. Zápis, překlad a spouštění programu v C] badinmicstatnice:bakalar:b0b36prp [2026/06/14 12:41] (current) – [Indexování:] badinmic
Line 334: Line 334:
 # 7. Abstraktní datové typy (ADT) # 7. Abstraktní datové typy (ADT)
  
-Abstraktní datové typy (ADT) představují konceptuální model datových struktur, kde je definováno chování (operace) bez ohledu na konkrétní implementaci. V jistých aspektech připomínají zapouzdření tříd v objektově orientovaných jazycích.+Abstraktní datové typy (ADT) představují konceptuální model datových struktur, kde je definováno chování (operace) bez ohledu na konkrétní implementaci. Stejný ADT může být implementován několika různými způsoby. V jistých aspektech připomínají zapouzdření tříd v objektově orientovaných jazycích. 
 + 
 +Základní typy ADT: 
 +- *Zásobník (Stack)*: funguje na principu LIFO (last in first out), tedy poslední prvek, který je do zásobníku přidán je z něj odebrán jako první (např. nádoba od Pringles). Obsahuje operace push(x) (přidá prvek x na vrchol) a pop() (odebrání a vrácení prvku z vrcholu). 
 +- *Fronta (Queue)*: funguje na principu FIFO (first in first out), tedy první prvek, který je přidán je odebrán jako první (např. fronta v obchodě u pokladny). Obsahuje operace enqueue(x) (vloží prvek x na konec) a dequeue() (odstraní a vrátí první prvek). 
 +- *Seznam (List)*: reprezentuje uspořádanou kolekci prvků. Obsahuje operace insert(x,i) (vloží prvek x na pozici i), delete(i) (odstraní a vrátí prvek na pozici i) a get(i) (vrátí prvek na pozici i). 
 +- *Množina (Set)*: ukládá prvky bez duplicit bez ohledu na pořadí. Obsahuje operace insert(x) (přidá prvek x) a remove(x) (odstraní prvek x), contains(x) (True pokud x je v množině). 
 +- *Slovník (Dictionary)*: ukládá dvojice klíč-hodnota, kde ke každému klíči je přiřazena nanejvýš jedna hodnota. Obsahuje operace put(k,v) (uloží hodnotu v pod klíčem k), get(k) (vrátí hodnotu pod klíčem k) a remove(k) (odstraní klíč k a vrátí jeho příslušnou hodnotu). 
 +- *Prioritní fronta (Priority Queue)*: ukládá prvky do fronty s prioritou. Prvky se odebírají podle priority místo podle pořadí vložení. Obsahuje operace insert(x,p) (vloží prvek x s prioritou p) a extractMin()/extractMax() (odebere a vrátí prvek s nejmenší/největší prioritou).
  
 ## Příklad  ## Příklad 
Line 417: Line 425:
 ``` ```
  
-Pro oboustraný linked list, pouze přidáme zpětný pointer do struktry node:+Pro oboustraný linked list, pouze přidáme zpětný pointer do struktury node:
 ```c ```c
 typedef struct node { typedef struct node {
Line 432: Line 440:
 } linked_list_t; } linked_list_t;
 ``` ```
-v normálním spojovém seznamu má poslední prvek hodnotu next NULL, v obousměrném má head->prev NULL a tail->next NULL.+v normálním spojovém seznamu má poslední prvek hodnotu next NULL, v obousměrném má head->prev NULL a tail->next NULL, a v kruhovém má head->prev hodnotu tail a tail->next hodnotu head.
  
  
Line 472: Line 480:
  
 ### Uspořádaný strom ### Uspořádaný strom
-- Potomci každého uzlu jsou uspořádáni (například podle klíče).+- Potomci každého uzlu jsou uspořádáni (například podle klíče), záleží na pořadí potomků. Príklad: Binární vyhledávací strom (vazba "Left - Root - Right" není stejná jako "Right - Root - Left").
  
 ### Neuspořádaný strom ### Neuspořádaný strom
-- Čistě strukturální strom, pořadí potomků není určeno.+- Čistě strukturální strom, nezáleží na pořadí potomků. Příklad: Rodokmen (vazba "Brother - Mother(root) - Sister" je ekvivalentní "Sister - Mother(root) - Brother").
  
 ## Binární vyhledávací strom (BST) ## Binární vyhledávací strom (BST)
Line 484: Line 492:
  
 - Základní typy: - Základní typy:
-  - **Plný binární strom** – všechny listy na stejné hloubce. +  - **Plný binární strom** – každý vnitřní uzel má dva potomky.
-  - **Úplný binární strom** – každý vnitřní uzel má dva potomky.+
   - **Vyvážený binární strom** – hloubka listů se liší maximálně o 1.   - **Vyvážený binární strom** – hloubka listů se liší maximálně o 1.
 +  - **Úplný binární strom** – vyvážený binární strom plněný zleva. Pouze jeden poslední vnitřní uzel může mít jen 1 potomka.
  
 ### Matematické vlastnosti ### Matematické vlastnosti
 - Počet uzlů: `n` - Počet uzlů: `n`
 - Hloubka stromu: `h` - Hloubka stromu: `h`
-- Minimální počet uzlů: `n = 2h + 1` +- Minimální počet uzlů: `n = 2h + 1` *(Platí pouze pro Plný binární strom)* 
-- Maximální počet uzlů: `n = 2(h+1) - 1` +- Maximální počet uzlů: `n = 2^(h+1) - 1` 
-- Počet listů: `ceil(n/2)`+- Počet listů: `ceil(n/2)` *(Platí pouze pro Úplný binární strom)*
  
 ## Implementace binárního stromu v C ## Implementace binárního stromu v C
Line 609: Line 617:
 - levý potomek: $2\cdot i + 1$ - levý potomek: $2\cdot i + 1$
 - pravý potomek: $2\cdot i + 2$ - pravý potomek: $2\cdot i + 2$
-- rodič: $(i - 1) / 2$+- rodič: $(i - 1) / 2$ *(zaokrouhleno dolů)*
  
 ### Základní operace haldy ### Základní operace haldy

Trace: • b0b36prp • b4m36esw

Navigation

Playground

QR Code
QR Code statnice:bakalar:b0b36prp (generated for current page)