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í struktura je konstrukce, která určuje pořadí a podmínky vykonávání příkazů v programu.

Tři základní druhy:

• Posloupnost – příkazy se vykonávají sekvenčně.
• Větvení – rozhodování na základě podmínky (if, switch).
• Cyklus – opakování příkazů dokud je splněna podmínka (for, while, do-while).

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
• 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';

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.

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.

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

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

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

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); }
}

Jednosměrný a obousměrný spojový seznam

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.

Nelineární spojové struktury

Například strom:

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

typedef struct tree {
  node_t *root;
} tree_t;

Datové struktury reprezentovatelné polem

Fronta, stack, priority queue

Využití prioritní fronty

helo