B0B36PRP Webové stránky předmětu
Řídicí struktury umožňují řídit tok vykonávání příkazů v programu.
if, if...else, switch.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 }
// 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ý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í)
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:
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í 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:
signed intNULL)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.
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:
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ý.
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...
Dekompozici do funkcí má smysl dělat hlavně ve dvou situacích:
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:
Když funkce nabobtná do desítek či stovek řádků, stává se nečitelnou. Řešení:
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.
V C se zdroják obvykle dělí na implementační soubory (.c) a hlavičkové soubory (.h). Hlavní motivy rozdělení:
math.c, io.c, net.c; každá řeší jasně vymezenou oblast. .h, detaily necháš „schované“ v .c. #include-uje..c soubor zvlášť do objektu (.o). .a) nebo sdílené (.so, .dll) knihovny a použiješ jinde. .h) pak slouží jako kontrakt pro všechny projekty, které knihovnu linkují.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.
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.
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 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ěť.
/* 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í }
Datové typy v C jsou:
(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é hodnotyunsigned - má pouze kladné hodnotystatic - hodnota se uchovává mezi voláním funkce, je uložena ve static dataconst - 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í
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 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.
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);
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:
#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) 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.
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); } }
Dynamická struktura, kde každý prvek obsahuje hodnotu a odkaz na další prvek.
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.
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;
Implementace je většinou rekurzivní.
Základní typy:
nhn = 2h + 1n = 2(h+1) - 1ceil(n/2)typedef struct node { int value; struct node *left; struct node *right; } node_t; node_t *tree = NULL;
void preorder(node_t *root) { if (root) { printf("%d ", root->value); // akce preorder(root->left); preorder(root->right); } }
void inorder(node_t *root) { if (root) { inorder(root->left); printf("%d ", root->value); // akce inorder(root->right); } }
void postorder(node_t *root) { if (root) { postorder(root->left); postorder(root->right); printf("%d ", root->value); // akce } }
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); }
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á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 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.
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ů.
Příklad struktury polem:
typedef struct { void **queue; int *priorities; int count; int head; int tail; } queue_t;
INT_MAX), startovací uzel na 0.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.