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 [2026/06/14 10:34] – [Nedefinované chování] badinmicstatnice:bakalar:b0b36prp [2026/06/14 12:41] (current) – [Indexování:] badinmic
Line 181: Line 181:
 } }
 ``` ```
-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. +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 proměnné ve funkci se propíšou i mimo tuto funkci, takže funkce může mít neočekávané side effects. 
  
 ### Návratová hodnota ### Návratová hodnota
Line 271: Line 271:
 Pole v C můžeme definovat dvěma způsoby, statické pole: Pole v C můžeme definovat dvěma způsoby, statické pole:
 ```c ```c
-int x[5]; // pole of velikosti 5+int x[5]; // pole o velikosti 5
  
 x[0] = 1; // první prvek pole x[0] = 1; // první prvek pole
Line 284: Line 284:
 a nebo dynamické pole: a nebo dynamické pole:
 ```c ```c
-int *x = malloc(2 * sizeof(int)); // pole of velikosti 5+int *x = malloc(2 * sizeof(int)); // pole o velikosti 2
 x[0] = 1; // první prvek pole x[0] = 1; // první prvek pole
 x[1] = 2; // druhý prvek pole x[1] = 2; // druhý prvek pole
Line 313: Line 313:
 fgets(buf, sizeof(buf), stdin); fgets(buf, sizeof(buf), stdin);
 ``` ```
 +v tomto případě fgets načte maximálně `sizeof(buf) - 1 = 255` znaků, protože si poslední místo vždy nechává pro ukončovací znak řetězce `\0`.
  
 # 6. 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říponou `.c` a knihovny do `.h`, includování probíhá pomocí makra `#include`.
  
 Překlad probíhá následujícími kroky: 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ží  +- *Preprocesor*: příkazy preprocesoru se zpracují (`#include`, `#define`, `#ifndef` apod.), odstraní se komentáře, výsledek se uloží  
-o `.i` souborů  +do `.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` souborů. 
 +- *Assembler*: 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 environment 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 
  
- +Soubor lze zkompilovat se statickými (`#include "library.h"`) nebo sdílenými (`#include <library.h>`) knihovnami (staticky například pro lepší 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)+
  
 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 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
Line 333: Line 334:
 # 7. Abstraktní datové typy (ADT) # 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.+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. Stejný ADT může být implementován několika různými způsoby. V jistých aspektech připomínají zapouzdření tříd v objektově orientovaných jazycích. 
 + 
 +Základní typy ADT: 
 +- *Zásobník (Stack)*: funguje na principu LIFO (last in first out), tedy poslední prvek, který je do zásobníku přidán je z něj odebrán jako první (např. nádoba od Pringles). Obsahuje operace push(x) (přidá prvek x na vrchol) a pop() (odebrání a vrácení prvku z vrcholu). 
 +- *Fronta (Queue)*: funguje na principu FIFO (first in first out), tedy první prvek, který je přidán je odebrán jako první (např. fronta v obchodě u pokladny). Obsahuje operace enqueue(x) (vloží prvek x na konec) a dequeue() (odstraní a vrátí první prvek). 
 +- *Seznam (List)*: reprezentuje uspořádanou kolekci prvků. Obsahuje operace insert(x,i) (vloží prvek x na pozici i), delete(i) (odstraní a vrátí prvek na pozici i) a get(i) (vrátí prvek na pozici i). 
 +- *Množina (Set)*: ukládá prvky bez duplicit bez ohledu na pořadí. Obsahuje operace insert(x) (přidá prvek x) a remove(x) (odstraní prvek x), contains(x) (True pokud x je v množině). 
 +- *Slovník (Dictionary)*: ukládá dvojice klíč-hodnota, kde ke každému klíči je přiřazena nanejvýš jedna hodnota. Obsahuje operace put(k,v) (uloží hodnotu v pod klíčem k), get(k) (vrátí hodnotu pod klíčem k) a remove(k) (odstraní klíč k a vrátí jeho příslušnou hodnotu). 
 +- *Prioritní fronta (Priority Queue)*: ukládá prvky do fronty s prioritou. Prvky se odebírají podle priority místo podle pořadí vložení. Obsahuje operace insert(x,p) (vloží prvek x s prioritou p) a extractMin()/extractMax() (odebere a vrátí prvek s nejmenší/největší prioritou).
  
 ## Příklad  ## Příklad 
Line 416: Line 425:
 ``` ```
  
-Pro oboustraný linked list, pouze přidáme zpětný pointer do struktry node:+Pro oboustraný linked list, pouze přidáme zpětný pointer do struktury node:
 ```c ```c
 typedef struct node { typedef struct node {
Line 431: Line 440:
 } linked_list_t; } 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.+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, a v kruhovém má head->prev hodnotu tail a tail->next hodnotu head.
  
  
Line 471: Line 480:
  
 ### Uspořádaný strom ### Uspořádaný strom
-- Potomci každého uzlu jsou uspořádáni (například podle klíče).+- Potomci každého uzlu jsou uspořádáni (například podle klíče), záleží na pořadí potomků. Príklad: Binární vyhledávací strom (vazba "Left - Root - Right" není stejná jako "Right - Root - Left").
  
 ### Neuspořádaný strom ### Neuspořádaný strom
-- Čistě strukturální strom, pořadí potomků není určeno.+- Čistě strukturální strom, nezáleží na pořadí potomků. Příklad: Rodokmen (vazba "Brother - Mother(root) - Sister" je ekvivalentní "Sister - Mother(root) - Brother").
  
 ## Binární vyhledávací strom (BST) ## Binární vyhledávací strom (BST)
Line 483: Line 492:
  
 - Základní typy: - 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.
-  - **Ú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.   - **Vyvážený binární strom** – hloubka listů se liší maximálně o 1.
 +  - **Úplný binární strom** – vyvážený binární strom plněný zleva. Pouze jeden poslední vnitřní uzel může mít jen 1 potomka.
  
 ### Matematické vlastnosti ### Matematické vlastnosti
 - Počet uzlů: `n` - Počet uzlů: `n`
 - Hloubka stromu: `h` - Hloubka stromu: `h`
-- Minimální počet uzlů: `n = 2h + 1` +- Minimální počet uzlů: `n = 2h + 1` *(Platí pouze pro Plný binární strom)* 
-- Maximální počet uzlů: `n = 2(h+1) - 1` +- Maximální počet uzlů: `n = 2^(h+1) - 1` 
-- Počet listů: `ceil(n/2)`+- Počet listů: `ceil(n/2)` *(Platí pouze pro Úplný binární strom)*
  
 ## Implementace binárního stromu v C ## Implementace binárního stromu v C
Line 608: Line 617:
 - levý potomek: $2\cdot i + 1$ - levý potomek: $2\cdot i + 1$
 - pravý potomek: $2\cdot i + 2$ - pravý potomek: $2\cdot i + 2$
-- rodič: $(i - 1) / 2$+- rodič: $(i - 1) / 2$ *(zaokrouhleno dolů)*
  
 ### Základní operace haldy ### Základní operace haldy

Trace: • b0b36prp

Navigation

Playground

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