B0B36PRP Webové stránky předmětu

• Řídící struktury – výrazy, funkce, nedefinované chování, kódovací (programovací) styly a čitelnost a srozumitelnost programů.
• Dekompozice programu – do funkcí, předávání argumentů funkcím, návratová hodnota, rekurze a volání funkcí.
• Datové typy – vnitřní reprezentace číselných typů, struktury a uniony v C.
• Pole, ukazatel, textový řetězec – dynamická alokace a paměťové třídy.
• Zpracování vstupů a ošetření chybových stavů – práce se soubory.
• Zápis, překlad a spouštění programu v C – vstup, výstup programu a jeho interakce s operačním systémem.
• Abstraktní datové typy (ADT) – definice, příklady specifikací základní ADT.
• Jednosměrný a obousměrný spojový seznam – implementace zásobníku a fronty.
• Nelineární spojové struktury – binární vyhledávací strom, prioritní fronta a halda.
• Datové struktury reprezentovatelné polem – kruhový buffer, prioritní fronta a halda.
• Využití prioritní fronty – v hledání nejkratší cesty v grafu.

Řídicí struktura

Řídicí struktury umožňují řídit tok vykonávání příkazů v programu.

• Sekvenční struktura – příkazy se vykonávají v pořadí, jak jsou zapsány.
• Větvení – if, if...else, switch.
• Cykly – for (pokud známe počet opakování), while, do...while (provádí tělo alespoň jednou).

Příklad větvení:

if(condition){ //condition is integer where 0 = false, anything else = true 
 // code condition is true
}else{
 // code condition is false
}

Cykly

// může vypadat for(int i = 0; i < 5; i++) nebo také můžeme udělat for(;some_condition;), oboje je valid
for(initialization; condition; increment/decrement)
{
 // code
 break; // lze použít na dostání se z cyklu
 continue; // skočí do na začátek cyklu
}
 
while(condition)
{
 // code
 break; // lze použít na dostání se z cyklu
 continue; // skočí do na začátek cyklu
 
};

Výrazy

Výraz je kombinace operandů (proměnná, konstanta, volání funkce) a operátorů. Výraz má hodnotu a typ.
Pozor: v C není definováno pořadí vyhodnocení podvýrazů! (např. a = a++ + ++a; → nedefinované chování)

Funkce

Blok kódu, který má název, parametry a návratovou hodnotu.
V C každá funkce musí být definována nebo deklarována (prototyp).
Program začíná ve funkci int main(int argc, char* * argv.

Vlastnosti:

• Parametry se předávají hodnotou (call by value), pro předání odkazem se používají ukazatele.
• C dovoluje rekurzi (funkce může volat sama sebe).
• Funkce nemohou být vnořené.
• Funkce s návratovým typem void je procedura.

Příklad funkce:

return_type function_name(parameters)
{
  // code
 
  // for non void functions, we can use `return` to return a value of the return type
}

Příklad běžné funkce:

int max(int a, int b) {
    return (a > b) ? a : b;
}

Nedefinované chování

Nedefinované chování je vlastnost jazyka C, ve výsledky znamená, že výstup chování kódu není definované a může se lišit v závislosti na kompilátoru, operačním systému nebo architektuře. Jedná se například o: dělení nulou, přetečení signed integeru, dereference null pointeru, přístup k paměti mimo alokovanou paměť, použití proměnné bez inicializace, atd. Může se lišit mezi překladači nebo mezi běhy programu.

Příklady:

• Přetečení signed int
• Dělení nulou
• Dereference neplatného ukazatele (NULL)
• Přístup k neinicializované proměnné
• 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). 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 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:

• Používat mezery mezi operátory a operandami
• Používat odsazení pro bloky kódu
• Používat popisné názvy proměnných a funkcí
• Používat komentáře k vysvětlení složitějších částí kódu
• Používat jednotný styl pro pojmenovávání proměnných a funkcí (např. camelCase, snake_case)
• Používat krátké funkce, které dělají jednu věc
• Používat konstanty místo magických čísel
• Používat funkce pro opakující se kód
• Udržovat nejmenší scope proměnných.

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ý.

2. Dekompozice programu

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 programu do funkcí

Dekompozici do funkcí má smysl dělat hlavně ve dvou situacích:

1. Odstranění opakující se logiky

Když se v programu opakuje stejný (nebo hodně podobný) kód, vyplatí se jej extrahovat do samostatné funkce a tu pak volat tam, kde je potřeba. Přináší to několik výhod:

• Čitelnost – program se zkrátí a je hned jasné, co se v jednotlivých částech děje.
• Údržba – změny děláš na jednom místě, takže nehrozí, že zapomeneš upravit některou kopii kódu.
• Potenciální rychlost – menší binárka se lépe vejde do instrukční cache CPU, což může přinést drobný výkonový bonus.

2. Zkrácení přerostlých bloků kódu

Když funkce nabobtná do desítek či stovek řádků, stává se nečitelnou. Řešení:

1. Najdi logické podbloky a každý přesuň do nové, srozumitelně pojmenované funkce.
2. Původní (hlavní) funkce pak slouží jen jako „dirigent“, který volá menší, soustředěné části.

Poznámka k výkonu: Každé volání funkce má overhead. Pokud jde o výkonnostně citlivou část, použít klíčové slovo inline. Překladač vloží kód funkce přímo na místo volání a skok se tím eliminuje.

Dekompozice programu do souborů

V C se zdroják obvykle dělí na implementační soubory (.c) a hlavičkové soubory (.h). Hlavní motivy rozdělení:

1. Logická modularizace

• Doménové vrstvy – např. math.c, io.c, net.c; každá řeší jasně vymezenou oblast.
• Zapouzdření – veřejné rozhraní definuješ v .h, detaily necháš „schované“ v .c.
• Jasné závislosti – co modul nepotřebuje, to ne‐#include-uje.

2. Zrychlení překladů

• Překladač kompiluje každý .c soubor zvlášť do objektu (.o).
• Při drobné změně stačí přeložit jen dotčené moduly a pak je znovu slinkovat, což výrazně šetří čas u větších projektů.

3. Znovupoužití a knihovny

• Dobře navržený modul zabalíš do statické (.a) nebo sdílené (.so, .dll) knihovny a použiješ jinde.
• Hlavička (.h) pak slouží jako kontrakt pro všechny projekty, které knihovnu linkují.

Předávání argumentů funkci

Funkce nemá argumenty

Když chceme vytvořit funkci která nebude mít žádné argumenty je lepší psát:

int nazev_funkce(void) {
  // code
}

než:

int nazev_funkce() {
  // code
}

To je z toho důvodu že když do listu argumentů přímo napíšeme void tak nás compiler zastaví pokud se funkci pokusíme nějaké argumenty předat. Zatímco v druhém případě funkci můžeme zavolat s argumenty a compiler nás ani nemusí varovat.

Funkce s argumenty

Obecně funkce s argumenty vypadá:

return_type function_name(arg1, arg2 .... argn)
{
  // code
}

Argumenty můžeme předávat dvěma způsoby, buď by-value nebo by-reference. Kde V prvním případě zkopírujeme hodnotu proměnné a předáme funkci kopii, v druhém případě předáme funkci odkaz na paměť proměnné. Předávat odkazy v případě větších datových typů může mít rychlostní výhody, ale musíme počítat s tím že jakékoliv změny v promenně ve funkci se propíšou i mimo tuto funkci, takže funkce může mít neočekávané side effects.

Návratová hodnota

Funkce může vracet hodnotu a také nemusí. V přpadě kdy nevrací hodnotu používáme return type void nazev_funkce před jménem funkce, pokud vrací hodnoty použijeme datový typ před názvem proměnné např.: int nazev_funkce.

Rekurzivní funkce

Rekurzivní funkce je taková, která volá sama sebe, dokud se nedostane k základnímu případu (base case).
V matematice se rekurzivní definice vyskytují často, takže pro některé algoritmy bývá rekurzivní zápis přirozenější a srozumitelnější než iterativní varianta. Každé volání funkce ale znamená jistý overhead (uložení návratové adresy a lokálních proměnných na zásobník), takže hluboká rekurze může být pomalejší a náročnější na paměť.

Ukázka — faktoriál

/* Rekurzivní výpočet n!
   base case:      0! = 1
   recursive step: n! = n x (n-1)!
*/
unsigned long long factorial(unsigned int n)
{
    if (n == 0)            // základní případ
        return 1;
 
    return n * factorial(n - 1); // rekurzivní volání
}

3. Datové typy

Datové typy v C jsou:

• _Bool (v c spíše pseudotyp)
• char
• int
• short
• long
• long long
• float
• double

(mají definovanou velikost ve standardu C, kdy short $\leq$ int $\leq$ long, ale závisí na compileru)

Proměnná pak musí mít zadefinovaný typ:

int a = 5;
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.

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.

v knihovně limits.h se dozvíme velikosti, například INT_MIN a INT_MAX, které nám říkají jakých hodnot může nabývat proměnná typu int.

Změna datového typu je možná pomocí cast:

int a = 5;
float b = (float)a; // a je převedeno na float

Pointer je proměnná která obsahuje adresu jiné proměnné.

int a = 5;
int *p = &a; // p je pointer na a
int b = *p; // b je hodnota na kterou p ukazuje
*p = 10; // změní hodnotu a na 10

datový typ void* je speciální typ, který může ukazovat na jakýkoli typ dat.

4. Pole, ukazatel, textový řetězec

Pole v C můžeme definovat dvěma způsoby, statické pole:

int x[5]; // pole of velikosti 5
 
x[0] = 1; // první prvek pole
x[1] = 2; // druhý prvek pole
x[2] = 3; // třetí prvek pole
 
//nebe pomocí pointer aritmetiky:
*(x + 3) = 1 // čtvrtý prvek pole

takto vytvořené pole má statickou velikost a je uloženo na stacku.

a nebo dynamické pole:

int *x = malloc(2 * sizeof(int)); // pole of velikosti 5
x[0] = 1; // první prvek pole
x[1] = 2; // druhý prvek pole
 
free(x); // uvolnění paměti

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.

5. Zpracování vstupů a ošetření chybových stavů

Můžeme použít funkce scanf, fscanf a podobné. Měli bychom sledovat návratovou hodnotu těchto funkcí, abychom věděli jestli nenastala chyba při čtení:

#define ERROR_INPUT -1
int ret = 0;
ret = scanf("%d", &input);
if (ret == EOF){
  return ERROR_INPUT;
}

Pro načítání stringů lze použít funkci fgets pro načtení řetězce o zadané velikosti, abychom předešli přetečení bufferu.

#define BUF_SIZE 256
char buf[BUF_SIZE];
fgets(buf, sizeof(buf), stdin);

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.

Překlad probíhá následujícími kroky:

• Preprocesor: příkazy preprocesoru se zpracují (#include, #define, #ifndef apod.), odstraní se komentáře, výsledek se uloží 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

• 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)

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).

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

Uděláme si ADT Stacku. Nejdříve si vytvoříme hlavičkový soubor kde definujeme interface.

typedef struct Stack Stack;      // neúplný typ
 
Stack *stack_create(void);
bool    stack_push(Stack *, int);
bool    stack_pop (Stack *, int *out);
void    stack_destroy(Stack *);

Tento interface je většinou vše co uživatel vidí, definuje jak vytvoříme datový typ a operace které s ním můžeme dělat. Nemusíme se starat jak funguje push nebo pop a co přesně dělá. Stačí když víme co jednotlivé funkce dělají.

K tomuto interfacu existuje poté specifická implementace. Která může vypadat takhle:

struct Stack { size_t top, cap; int *buf; };
 
Stack *stack_create(void) {
    Stack *s = calloc(1, sizeof *s);
    if (!s) return NULL;
    s->cap = 4;
    s->buf = malloc(s->cap * sizeof *s->buf);
    return s && s->buf ? s : (free(s), NULL);
}
 
static bool grow(Stack *s) {
    size_t n = s->cap * 2;
    int *tmp = realloc(s->buf, n * sizeof *tmp);
    if (!tmp) return false;
    s->buf = tmp;
    s->cap = n;
    return true;
}
 
bool stack_push(Stack *s, int v) {
    if (s->top == s->cap && !grow(s)) return false;
    s->buf[s->top++] = v;
    return true;
}
 
bool stack_pop(Stack *s, int *out) {
    if (!s->top) return false;
    if (out) *out = s->buf[--s->top];
    return true;
}
 
void stack_destroy(Stack *s) {
    if (s) { free(s->buf); free(s); }
}

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:

typedef struct node {
  void* data;
  struct node *next;
} node_t;

a linked list:

typedef struct linked_list {
  node_t *head;
} linked_list_t;

Pro oboustraný linked list, pouze přidáme zpětný pointer do struktry node:

typedef struct node {
  void* data;
  struct node *next;
  struct node *prev;
} node_t;

a poslední prvek do linked listu:

typedef struct linked_list {
  node_t *head;
  node_t *tail;
} 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.

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:

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

Například strom:

typedef struct node {
  void* data;
  struct node *children;
} node_t;

typedef struct tree {
  node_t *root;
} tree_t;

Typy stromů

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

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

    void preorder(node_t *root) {
        if (root) {
            printf("%d ", root->value); // akce
            preorder(root->left);
            preorder(root->right);
        }
    }

  • Inorder

    void inorder(node_t *root) {
        if (root) {
            inorder(root->left);
            printf("%d ", root->value); // akce
            inorder(root->right);
        }
    }

  • Postorder

    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)

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:

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:

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.