Spojové seznamy, ukazatele, stromy (binární strom)

Formát: 30 min praktická úloha, 15 min obhajoba + teorie. Teorie pokrývá linked listy, BST a tree traversals. U téhle otázky malujte jako diví: diagramy stromů jsou klíčové.

Část 1: Teorie

K čemu spojové struktury

Klasické pole má pevnou velikost a vkládání/mazání je drahé (musí se přesouvat prvky). Spojové struktury řeší:

Neznáme velikost dopředu
Často vkládáme a mažeme prvky
Potřebujeme hierarchickou strukturu (stromy)

Datové struktury
   ├─ Lineární
   │   ├─ Pole (array) ........... pevná velikost, indexový přístup
   │   ├─ Spojový seznam ......... dynamická velikost, sekvenční přístup
   │   └─ Fronta, zásobník ....... omezený přístup (FIFO, LIFO)
   ├─ Hierarchické
   │   ├─ Strom (Tree)
   │   ├─ Binární strom
   │   └─ BST (Binary Search Tree)
   └─ Síťové
       └─ Graf

Ukazatele a reference

Ukazatel v C (klasický pointer)

int a = 10;
int* p = &a;       // p drží ADRESU proměnné a
printf("%d", *p);  // dereference: vypíše 10

Symbol	Význam
`&a`	Adresa proměnné `a` v paměti
`*p`	Dereference: co je na adrese, kterou drží `p`

Výhody C pointerů: přímá práce s pamětí, výkon. Nevýhody: segfault, memory leaks, neintuitivní.

Reference v C# (bezpečná alternativa)

C# pointery běžně nepoužívá, místo nich má reference, které jsou součástí jazyka pro každý class.

class Person { public string Name; }

Person p1 = new Person();
Person p2 = p1;               // p2 ukazuje na STEJNÝ objekt
p2.Name = "axo";
Console.WriteLine(p1.Name);   // "axo": obě ukazují na totéž

   STACK              HEAP
  ┌──────┐           ┌──────────────────┐
  │ p1 → ●──────────▶│ Person {axo}     │
  │ p2 → ●──────────▶│                  │
  └──────┘           └──────────────────┘
       Obě reference ukazují na 1 objekt