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 12:59] – 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 97: Line 96:
 - Vícenásobné změny hodnoty proměnné v jediném výrazu (např. `a = a++ + ++a`) - Vícenásobné změny hodnoty proměnné v jediném výrazu (např. `a = a++ + ++a`)
  
-Jazyk C umí využít nedefinované chování k optimalizaci kódu, protože kompilátor může předpokládat, že se takové chování v programu nikdy nevyskytne. Například pokud přičteme k signed integeru 1 a poté v podmínce zkontrolujeme, zda se proměnná zmenšila, kompilátor může předpokládat, že se nikdy nezmenší, protože by to znamenalo přetečení signed integeru a to je nedefinované chování. Proto může kompilátor optimalizovat kód tak, že podmínku vynechá a kód zrychlí (samozřejmě toto může být velmi problémové, pokud se v programu přetečení signed integeru vyskytuje).+Jazyk C umí využít nedefinované chování k optimalizaci kódu, protože kompilátor může předpokládat, že se takové chování v programu nikdy nevyskytne.  
 +Například pokud přičteme k signed integeru 1 a poté v podmínce zkontrolujeme, zda se proměnná zmenšila, kompilátor může předpokládat, že se nikdy nezmenší, protože by to znamenalo přetečení signed integeru a to je nedefinované chování. Proto může kompilátor optimalizovat kód tak, že podmínku vynechá a kód zrychlí (samozřejmě toto může být velmi problémové, pokud se v programu přetečení signed integeru vyskytuje). 
 +Například u přetečení `signed int` může kompilátor předpokládat, že k tomu nikdy nedojde a podle toho optimalizovat kód.
  
-## Coding style +## Coding style a čitelnost 
-Kódovací styl je způsob, jakým je kód napsán. Existuje mnoho různých stylů, ale většina z nich se snaží o to, aby byl kód čitelný a srozumitelný. Například:+Kódovací styl je způsob, jakým je kód napsán. Existuje mnoho různých stylů, ale většina z nich se snaží o to, aby byl kód čitelný a srozumitelný.  
 + 
 +Například:
 - Používat mezery mezi operátory a operandami - Používat mezery mezi operátory a operandami
 - Používat odsazení pro bloky kódu - Používat odsazení pro bloky kódu
Line 112: Line 115:
  
 Srozumitelnost kódu je důležitá, protože pomáhá ostatním (a i nám) pochopit, co kód dělá. Čitelný kód je také snazší udržovat a opravovat. Je dobré mít jednotný styl v celém projektu, aby byl kód konzistentní a snadno čitelný. Srozumitelnost kódu je důležitá, protože pomáhá ostatním (a i nám) pochopit, co kód dělá. Čitelný kód je také snazší udržovat a opravovat. Je dobré mít jednotný styl v celém projektu, aby byl kód konzistentní a snadno čitelný.
-</markdown> 
  
-===== 2. Dekompozice programu =====+# 2. Dekompozice programu
  
-<markdown> 
 Dekompozice je proces ve kterém se komplexní kus logiky programu rozdělí na menší části pro lepší čitelnost. Většinou se jedná o rozdělení programu do jednotlivých funkcí, rozdělení do více souborů atd...  Dekompozice je proces ve kterém se komplexní kus logiky programu rozdělí na menší části pro lepší čitelnost. Většinou se jedná o rozdělení programu do jednotlivých funkcí, rozdělení do více souborů atd... 
  
Line 174: Line 175:
 ### Funkce s argumenty ### Funkce s argumenty
 Obecně funkce s argumenty vypadá: Obecně funkce s argumenty vypadá:
-```C+```c
 return_type function_name(arg1, arg2 .... argn) return_type function_name(arg1, arg2 .... argn)
 { {
Line 204: Line 205:
     return n * factorial(n - 1); // rekurzivní volání     return n * factorial(n - 1); // rekurzivní volání
 } }
 +```
  
-</markdown> +# 3.  Datové typy
- +
-===== 2.  Datové typy ===== +
- +
-<markdown>+
  
 Datové typy v C jsou: Datové typy v C jsou:
Line 215: Line 213:
 - char - char
 - int - int
 +- short
 - long - long
 - long long - long long
Line 227: 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 248: 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 272: 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 294: 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 321:
 - *Preprocesor*: příkazy preprocesoru se zpracují (`#include`, `#define`, #ifndef` apod.), odstraní se komentáře, výsledek se uloží  - *Preprocesor*: příkazy preprocesoru se zpracují (`#include`, `#define`, #ifndef` apod.), odstraní se komentáře, výsledek se uloží 
 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*: `.s` přeloží se 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
-- objetové soubory se slnkují 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
  
-soubor lze zkompilovat se statickými (`#include "library.h"`) nebo sdílenými (`#include <library.h>`) knihovnami (staticky například prolepší přenositelnost, ale zvětšuje velikost binárního souboru) 
  
 +Soubor lze zkompilovat se statickými (`#include "library.h"`) nebo sdílenými (`#include <library.h>`) knihovnami (staticky například prolepší přenositelnost, ale zvětšuje velikost binárního souboru)
  
-# Abstraktní datové typy (ADT)+Spuštění souboru nezačíná ve funkci `main` ale ve funkci `_start`, která připraví prostředí pro spuštění programu a zavolá funkci main. Funkce main pak vrací hodnotu, která se předává operačnímu systému 
 +jako návratová hodnota programu. (tu můžeme vypsat pomocí `echo $?` v shellu).
  
-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). +# 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.
  
 ## Příklad  ## Příklad 
Line 328: Line 351:
 K tomuto interfacu existuje poté specifická implementace. Která může vypadat takhle: K tomuto interfacu existuje poté specifická implementace. Která může vypadat takhle:
  
-```C+```c
  
 struct Stack { size_t top, cap; int *buf; }; struct Stack { size_t top, cap; int *buf; };
Line 366: 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 400: 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 416: Line 468:
 ``` ```
  
-# Datové struktury reprezentovatelné polem+## Typy stromů
  
-# Využití prioritní fronty+### Uspořádaný strom 
 +- Potomci každého uzlu jsou uspořádáni (například podle klíče).
  
 +### 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.
  
 +### 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)`
  
 +## 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:

Navigation

Playground

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