Algoritmy 2 Mgr. Ivana Jelínková

Na konci cvičení odevzdávejte source.c na email ivana.jelinkova01@upol.cz s předmětem ALGO2

Cvičení 6

Opakování na písemku (lineární stuktury, binární stromy)

První zápočtový programovací úkol: Naprogramujte AVL stromy (přidávání, odebírání, vyhledávání)
odevzdávejte do 18. 4. 2025 23:59:59 (CEST) s předmětem ALGO2 - zápočet 1 soubor prijmeni.c na email ivana.jelinkova01@upol.cz

Cvičení 5

Naprogramujte odebírání z binárního stromu a rotace levá a pravá
int remove(tree *t, int data) (vrací 1 pokud prvek odebral, jinak 0)
void rotate_left(tree *t, int data) (data určují vrchol stromu/podstromu, který bude rotován)
void rotate_right(tree *t, int data)

Cvičení 4

Dynamické alokování paměti: struct Node* temp = (struct Node*) malloc(sizeof(struct Node))
https://phoenix.inf.upol.cz/cgi-bin/man/man2html?3+calloc

Vyberte z minulého cvičení 2 funkce např.
node* add_position(node *head, node *insert_node, int position)
a node který se má vložit budete alokovat dynamicky a funkci budete předávat pouze vkládaný klíč typu int
node* add_position(node *head, int insert_key, int position)

Implemetujte struktury pro binární vyhledávací strom (uzel stromu node; strom tree - obsahující ukazatel na kořen). Strom bude obsahovat hodnoty typu int.

Implementujte následující procedury pro práci s BST:
přidání prvku do stromu void add(tree *t, int data)
vypsání prvků ve stromě v sestupném pořadí void print_in_desc_order(tree t)
výpočet hloubky stromu int depth(tree t)
vystisknutí na výstup jak strom vypadá void print_tree(tree t)
nalezení nejmenšího prvku int find_min(tree t)
nalezení největšího prvku int find_max(tree t)

Cvičení 3

Vytvořte strukturu pro uzel (jednosměrného) spojového seznamu (obsahující int data a odkaz na další prvek next) a typ node pro tuto strukturu (typedef).

Funkce, které vrací node ze sekce seznam - vrací počátek seznamu

Seznam

Zjištěte délku seznamu: int length(node head)

Vypište prvky (data struktury node) seznamu oddělených středníkem: void print_data(node head)

Přidejte uzel na začátek seznamu node* add_start(node *head, node *insert_node)

Přidejte uzel na konec seznamu: node* add_end(node *head, node *insert_node)

Přidejte uzel na zadané místo v seznamu (nebo na konec, pokud se daná pozice v seznamu nevyskytuje): node* add_position(node *head, node *insert_node, int position)

Odeberte uzel ze začátku seznamu node* remove_start(node *head)

Odeberte uzel z konce seznamu: node* remove_end(node *head)

Vyhledávání uzlu v seznamu - int search(node *head, node *search_node) - vrátí pozici hledaného uzlu v seznamu, nebo -1 pokud tam není

Odeberte zadaný uzel ze seznamu - node* remove_in(node *head, node *delete_node)

Budete potřebovat další struktury stack a queue pro následující:

Zásobník

Pomocí seznamu naprogramujte zásobník (vkládaná data budou celé uzly; typ pro zásobník stack) a jeho základní operace (void push(stack *zasobnik, node *data) a node* pop(stack *zasobnik)).

Fronta

Pomocí seznamu naprogramujte frontu (vkládaná data budou celé uzly; typ pro frontu queue) a její základní operace (void enqueue(queue *fronta, node *data) a node* dequeue(queue *fronta)).

Cvičení 2

Naprogramujte následující:

Funkci pro třídění zadaného pole

Funkci pro naplnění pole náhodnými hodnotami

Funkci pro sekvenční vyhledávání prvku v poli int sequence_search(int array[], int size, int element)

Funkci pro binární vyhledávání prvku v poli int binary_search(int array[], int size, int element)

Funkci pro interpolační vyhledávání prvku v poli int interpolation_search(int array[], int size, int element)

Vyhledávací funkce vrací index hledaného prvku, pokud nalezen nebyl vrací -1

Vyhledávací funkce porovnejte - kolik muselo proběhnout cyklů před navrácením výsledku? Které vyhledávání je nejlepší? (TIP: naplňte pole druhými mocninami)

Cvičení 1

Následující úkol pokrývá základní znalosti, jenž máte z předmětů Základy programování a Algoritmy 1

1) Vytvořte v C strukturu struct drive pro záznam disku obsahující:
a) Přiřazené písmeno (C, D, Z,...)
b) Celková paměť
c) Využitá paměť
d) Jednotka paměti (b nebo B pro bit a bajt)

2) Vytvořte adresář disků jako pole struktur z předchozího bodu (data si vymyslete; alespoň pět záznamů, různé jednotky).

3) Napište následující funkce (parametr n je vždy velikost pole):
a) pro přístup k údajům o disku (význam je jasný z názvu):
- char drive_name(struct drive d),
- int drive_memory(struct drive d),
- int drive_allocated_memory(struct drive d),
- char drive_memory_unit(struct drive d),
b) vypisující celkovou paměť na standardní výstup pro zadaný adresář, název disku: void print_drive_memory(struct drive drives[], int n, char name)
c) vracející disk s největší celkovou pamětí (celou strukturu) v zadaném adresáři: struct drive max_memory(struct drive drives[], int n)
d) vracející disk s největší přístupnou(využitelnou) pamětí (celou strukturu) v zadaném adresáři: struct drive max_available_memory(struct drive drives[], int n)
e) vracející disk s nejmenší přístupnou pamětí (celou strukturu) v zadaném adresáři: struct drive min_available_memory(struct drive drives[], int n)
f) zvyšující využitou paměť zadaného disku o zadanou hodnotu v zadaném adresáři: void increase_allocated_memory(struct drive drives[], int n, char name, int amount)
g) snižující využitou paměť zadaného disku o zadanou hodnotu v zadaném adresáři: void decrease_allocated_memory(struct drive drives[], int n, char name, int amount)
h) vracející i-tý největší disk v celkové paměti pro zadané i a zadaný adresář: struct drive ith_biggest(struct drive drives[], int i, int n)
i) třídící zadaný adresář sestupně podle celkové paměti disku: void sort_drives(struct drive drives[], int n)