The wiki page is under active construction, expect bugs.

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 [2025/05/11 13:08] – external edit 127.0.0.1statnice:bakalar:b0b36prp [2025/05/11 15:17] (current) – external edit 127.0.0.1
Line 19: Line 19:
  
 ## Řídicí struktura ## Řídicí struktura
-Řídicí struktura je konstrukce, která určuje pořadí a podmínky vykonávání příkazů v programu.+Řídicí struktury umožňují řídit tok vykonávání příkazů v programu.
  
-Tři základní druhy: +- **Sekvenční struktura** – příkazy se vykonávají v pořadí, jak jsou zapsány. 
-- **Posloupnost** – příkazy se vykonávají sekvenčně. +- **Větvení** – `if`, `if...else`, `switch`. 
-- **Větvení** – rozhodování na základě podmínky (if, switch). +- **Cykly** – `for` (pokud známe počet opakování), `while`, `do...while` (provádí tělo alespoň jednou).
-- **Cyklus** – opakování příkazů dokud je splněna podmínka (for, while, do-while).+
  
 Příklad větvení: Příklad větvení:
Line 214: Line 213:
 - char - char
 - int - int
 +- short
 - long - long
 - long long - long long
Line 226: Line 226:
 char b = 'a'; char b = 'a';
 ``` ```
 +
 +proměnné dále můžou mít modifikátory jako:
 +- `signed` - má jak kladné tak záporné hodnoty
 +- `unsigned` - má pouze kladné hodnoty
 +- `static` - hodnota se uchovává mezi voláním funkce, je uložena ve static data
 +- `const` - hodnota se nemění
 +- `volatile` - hodnota se může měnit mimo program (např. hardware)
 +- `extern` - proměnná je definována v jiném souboru
 +
 +V C není datový typ string. Textové řetězce se reprezentují jako pole znaků zakončené `\0`.
 +
 +```c
 +char text[] = "Ahoj";
 +char *text2 = "Ahoj"; // konstanta
 +```
 +
 +pozor na rozdíl mezi `const int *` - konstantní hodnota, `const int * const` - konstantní pointer na konstantní hodnotu, a `int * const` - konstantní pointer na proměnnou, v C lze ale vše přetypovat, takže to není nutně konstantní
 +- konstantní pointer nelze přesměrovat na jinou proměnnou, ale hodnota na kterou ukazuje se může měnit
 +- konstantní hodnota se nemění, ale pointer se může přesměrovat na jinou proměnnou
 +- konstantní pointer na konstantní hodnotu se nemění, ani hodnota na kterou ukazuje
  
 můžeme includovat knihovnu `inttypes.h` která nám umožní používat typy se specifickou velikostí, jako například `uint8_t`, pro 8 bit unsigned integer. můžeme includovat knihovnu `inttypes.h` která nám umožní používat typy se specifickou velikostí, jako například `uint8_t`, pro 8 bit unsigned integer.
Line 247: Line 267:
 datový typ `void*` je speciální typ, který může ukazovat na jakýkoli typ dat. datový typ `void*` je speciální typ, který může ukazovat na jakýkoli typ dat.
  
-# Pole, ukazatel, textový řetězec+# 4. Pole, ukazatel, textový řetězec
  
 Pole v C můžeme definovat dvěma způsoby, statické pole: Pole v C můžeme definovat dvěma způsoby, statické pole:
Line 271: Line 291:
 ``` ```
 takto vytvořené pole je umístěno na haldě, pro získání místa na haldě musíme o místo zažádat pomocí `malloc` a pak je správné ho na konci uvolnit pomocí `free`. takto vytvořené pole je umístěno na haldě, pro získání místa na haldě musíme o místo zažádat pomocí `malloc` a pak je správné ho na konci uvolnit pomocí `free`.
 +void* je speciální ukazatel, který může ukazovat na libovolný typ dat a je běžně používán pro obecné funkce pracující s různými datovými typy.
  
-# Zpracování vstupů a ošetření chybových stavů+# 5. Zpracování vstupů a ošetření chybových stavů
  
 Můžeme použít funkce `scanf`, `fscanf` a podobné. Můžeme použít funkce `scanf`, `fscanf` a podobné.
Line 293: Line 314:
 ``` ```
  
-# Zápis, překlad a spouštění programu v C+# 6. Zápis, překlad a spouštění programu v C
  
 Soubory píšeme do souborů s příponom `.c` a knihovny do `.h`, includování probíhá pomocí makra `#include`. Soubory píšeme do souborů s příponom `.c` a knihovny do `.h`, includování probíhá pomocí makra `#include`.
Line 301: Line 322:
 o `.i` souborů  o `.i` souborů 
 - *Kompilátor*: `.i` soubory se přeloží z C kódu do assembleru a výsledek se uloží do `.s` souboru.- *Asembler*: přeloží `.s` soubory do objektových souborů `.o`, zatím bez absolutních adres - *Kompilátor*: `.i` soubory se přeloží z C kódu do assembleru a výsledek se uloží do `.s` souboru.- *Asembler*: přeloží `.s` soubory do objektových souborů `.o`, zatím bez absolutních adres
 +
 - *Linker*: objektové soubory se slinkují (přeloží se adresy pro volání funkcí, nastavuje enviroment pro předávání argumentů, atd...) do spustitelného souboru - *Linker*: objektové soubory se slinkují (přeloží se adresy pro volání funkcí, nastavuje enviroment pro předávání argumentů, atd...) do spustitelného souboru
  
Line 309: Line 331:
 jako návratová hodnota programu. (tu můžeme vypsat pomocí `echo $?` v shellu). jako návratová hodnota programu. (tu můžeme vypsat pomocí `echo $?` v shellu).
  
-# Abstraktní datové typy (ADT)+# 7. Abstraktní datové typy (ADT)
  
-Abstraktní datové typy jsou přístup k programování datových struktur, (technicky vzato je to konceptuální model) který velmi připomíná třídy v objektově orientovaných jazycích. ADT umožňuje udělat zapouzdření, modularitu a abstrakci (uživatel ADT se nestará o implementaci ale jen o interface). +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.
  
 ## Příklad  ## Příklad 
Line 367: Line 389:
 ``` ```
  
-# Jednosměrný a obousměrný spojový seznam+# 8. Jednosměrný a obousměrný spojový seznam 
 + 
 +## Spojové seznamy 
 + 
 +Dynamická struktura, kde každý prvek obsahuje hodnotu a odkaz na další prvek. 
 + 
 +- **Jednosměrný** – každý prvek ukazuje na následující. 
 +- **Obousměrný** – prvky obsahují odkazy na předchozí i následující prvek. 
 +- **Kruhový** – poslední prvek ukazuje zpět na první. 
 + 
 +Výhoda: **flexibilní velikost**. Nevýhoda: **vyšší paměťová režie**
  
 Může být jednoduše naimplementován pomocí dvou struktur, node: Může být jednoduše naimplementován pomocí dvou struktur, node:
Line 401: Line 433:
 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.
  
-# Nelineární spojové struktury+ 
 +# 9. Nelineární spojové struktury 
 + 
 +## Stromy – základní pojmy 
 + 
 +- **Cesta** – posloupnost uzlů od kořene k uzlu. 
 +- **Délka cesty** – počet hran mezi kořenem a uzlem. 
 +- **Hloubka uzlu** – délka cesty od kořene. 
 +- **Výška stromu** – maximální hloubka uzlu ve stromu. 
 +- **Šířka stromu** – počet uzlů na stejné úrovni. 
 +- **Vyvážený strom** – uzly rovnoměrně rozložené, nejmenší možná výška. 
 + 
 +Příklad uzlu v C: 
 +```c 
 +typedef struct Node { 
 +    int data; 
 +    struct Node* left; 
 +    struct Node* right; 
 +} Node; 
 +```
  
 Například strom: Například strom:
Line 417: Line 468:
 ``` ```
  
 +## Typy stromů
  
-# Datové struktury reprezentovatelné polem+### Uspořádaný strom 
 +- Potomci každého uzlu jsou uspořádáni (například podle klíče).
  
-Fronta, stack, priority queue+### Neuspořádaný strom 
 +- Čistě strukturální strom, pořadí potomků není určeno.
  
 +## Binární vyhledávací strom (BST)
 +- Každý uzel má maximálně 2 potomky (levý a pravý podstrom).
 +- Levý potomek obsahuje menší hodnotu, pravý potomek větší hodnotu než rodič.
 +- Slouží k rychlému vyhledávání, vkládání a mazání dat (průměrně O(log n), v nejhorším O(n) u nevyváženého stromu).
 +- Implementace je většinou rekurzivní.
  
 +- 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.
 +  - **Vyvážený binární strom** – hloubka listů se liší maximálně o 1.
  
-# Využití prioritní fronty+### Matematické vlastnosti 
 +- Počet uzlů: `n` 
 +- Hloubka stromu: `h` 
 +- Minimální počet uzlů: `n = 2h + 1` 
 +- Maximální počet uzlů: `n = 2(h+1) - 1` 
 +- Počet listů: `ceil(n/2)`
  
-helo+## Implementace binárního stromu v C 
 +```c 
 +typedef struct node { 
 +    int value; 
 +    struct node *left; 
 +    struct node *right; 
 +} node_t;
  
 +node_t *tree = NULL;
 +```
  
 +## Procházení stromu
  
 +### BFS (do šířky)
 +- Prochází se úrovně stromu po vrstvách.
  
 +### DFS (do hloubky)
 +- Existují 3 základní metody:
 +  - **Preorder**
 +    ```c
 +    void preorder(node_t *root) {
 +        if (root) {
 +            printf("%d ", root->value); // akce
 +            preorder(root->left);
 +            preorder(root->right);
 +        }
 +    }
 +    ```
 +  - **Inorder**
 +    ```c
 +    void inorder(node_t *root) {
 +        if (root) {
 +            inorder(root->left);
 +            printf("%d ", root->value); // akce
 +            inorder(root->right);
 +        }
 +    }
 +    ```
 +  - **Postorder**
 +    ```c
 +    void postorder(node_t *root) {
 +        if (root) {
 +            postorder(root->left);
 +            postorder(root->right);
 +            printf("%d ", root->value); // akce
 +        }
 +    }
 +    ```
  
 +## Vyhledávání v binárním vyhledávacím stromu (BST)
 +```c
 +node_t* search(node_t* root, int key) {
 +    if (!root || root->value == key)
 +        return root;
 +    if (key < root->value)
 +        return search(root->left, key);
 +    else
 +        return search(root->right, key);
 +}
 +```
  
 +# 10. Datové struktury reprezentovatelné polem
  
 +## Zásobník (Stack)
  
 +Zásobník je lineární datová struktura pracující na principu **LIFO (Last In, First Out)** – poslední prvek vložený do zásobníku je první, který se odebere.
  
 +### Základní operace:
 +- **push**: vloží prvek na vrchol zásobníku.
 +- **pop**: odebere a vrátí prvek z vrcholu zásobníku.
 +- **peek** (top): vrátí hodnotu vrcholu zásobníku, aniž by ji odebral.
 +- **isEmpty**: zjistí, zda je zásobník prázdný.
  
 +Zásobník lze implementovat pomocí pole nebo spojového seznamu. Používá se například při rekurzi, parsování výrazů nebo při realizaci funkcí volání v programech.
  
  
 +## Fronta (Queue)
  
 +Fronta je lineární datová struktura pracující na principu **FIFO (First In, First Out)** – první prvek vložený do fronty je první, který se odebere.
  
 +### Základní operace:
 +- **enqueue**: vloží prvek na konec fronty.
 +- **dequeue**: odebere a vrátí prvek z čela fronty.
 +- **peek** (front): vrátí hodnotu na čele fronty, aniž by ji odebral.
 +- **isEmpty**: zjistí, zda je fronta prázdná.
  
 +Fronta se používá například při plánování procesů, správě úloh, nebo v simulacích, kde je potřeba zachovat pořadí požadavků.
 +
 +## Prioritní fronta – spojový seznam nebo pole
 +- Každý prvek má přiřazenou prioritu. Při vybírání se vždy vybere prvek s nejvyšší nebo nejnižší prioritou (dle implementace).
 +- Prioritní frontu lze implementovat jako:
 +  - **spojový seznam** (pomalé vybírání O(n), rychlé vkládání O(1)),
 +  - **pole** (pomalé vybírání O(n)),
 +  - **haldu (heap)** (rychlé vybírání i vkládání O(log n)).
 +
 +Příklad struktury polem:
 +```c
 +typedef struct {
 +    void **queue;
 +    int *priorities;
 +    int count;
 +    int head;
 +    int tail;
 +} queue_t;
 +```
 +
 +## Halda (heap)
 +- Binární plný strom s vlastností haldy:
 +  - Rodič ≤ potomci (min-heap) nebo rodič ≥ potomci (max-heap).
 +- Prvky jsou uloženy v poli.
 +
 +### Indexování:
 +- levý potomek: $2\cdot i + 1$
 +- pravý potomek: $2\cdot i + 2$
 +- rodič: $(i - 1) / 2$
 +
 +### Základní operace haldy
 +
 +#### Insert / Push
 +- Přidá prvek na konec pole (na první volné místo).
 +- Prvek se **"bublá nahoru"** (heapify-up), dokud není splněna vlastnost haldy (porovnává se s rodičem).
 +- Složitost: **O(log n)**.
 +
 +#### Pop
 +- Odebere prvek z kořene (index 0 = minimum/min-heap).
 +- Poslední prvek se přesune na kořen a **"bublá dolů"** (heapify-down), dokud není splněna vlastnost haldy.
 +- Složitost: **O(log n)**.
 +
 +#### Peek
 +- Vrátí hodnotu na kořeni (nejmenší / největší prvek podle typu haldy), aniž by prvek odstranila.
 +- Složitost: **O(1)**.
 +
 +### Výhody haldy
 +- V porovnání s prostou prioritní frontou v poli má halda efektivní složitost operací.
 +- Halda je ideální pro implementaci **prioritní fronty**, například pro algoritmy hledání nejkratší cesty (Dijkstra, A*).
 +
 +# 11. Využití prioritní fronty – hledání nejkratší cesty v grafu
 +
 +## Dijkstrův algoritmus
 +1. Nastavíme vzdálenosti všech uzlů na nekonečno (`INT_MAX`), startovací uzel na 0.
 +2. Vložíme startovací uzel do prioritní fronty (haldy).
 +3. Dokud fronta není prázdná:
 +   - Vybereme uzel s nejmenší vzdáleností.
 +   - Aktualizujeme vzdálenosti sousedů.
 +   - Přidáme sousedy do fronty, pokud se vzdálenost zmenšila.
 +
 +Příklad:
 +```c
 +typedef struct {
 +    int vertex;
 +    int distance;
 +} PriorityQueueNode;
 +```
  
 +Složitost: $O((V + E) \cdot log V)$
 +Dijkstra algoritmus předpokládá, že všechny hrany mají nezáporné váhy. Pro grafy s negativními hranami je vhodnější algoritmus Bellman-Ford.
  
 +## A* algoritmus
 +- Modifikace Dijkstra s heuristikou (odhadem vzdálenosti do cíle).
 +- Heuristika snižuje počet prozkoumaných uzlů → rychlejší hledání.
 +- Nejčastější použití v herní AI, robotice, mapových aplikacích.
  
 </markdown> </markdown>

Trace: • b0b36dbs

Navigation

Playground

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