Cvičení 4 - BST I; dynamické alokace v seznamu

Informatici (cvičení v C)

Témata

• fronta a zásobník
• implementace seznamu s dynamickou alokací uzlů
• binární vyhledávací stromy (BST)

Úkoly

• Úkol 1 už někteří možná mají z minula, pro ostatní by to měla být snadná úprava.
  1. Z minula máte implementovány struktury a základní procedury pro práci se seznamem. Modifikujte je tak, abyste uzly vytvářeli a rušili dle potřeby dynamicky. Tj. všechny procedury budou místo uzlů k přidání/odebrání dostávat jen hodnoty k přidání/odebrání a potřebné uzly budou vytvářeny/rušeny dynamicky. Seznam bude obsahovat hodnoty typu int. Napište takto následující procedury:
     • zjištění délky seznamu: int length(list seznam)
     • výpis prvků (tj složka s daty struktury node) seznamu oddělených čárkou: void print_list(list seznam)
     • přidávání hodnoty na začátek seznamu: void add_start(list *seznam, int data)
     • přidávání hodnoty na konec seznamu: void add_end(list *seznam, int data)
     • přidávání hodnoty na zadané místo v seznamu (nebo na konec, pokud se daná pozice v seznamu nevyskytuje): void add_position(list *seznam, int data, int position)
     • odebírání hodnoty ze začátku seznamu: int remove_start(list *seznam) - vrátí 0, pokud se něco smazalo, a -1 jinak
     • odebírání hodnoty z konce seznamu: int remove_end(list *seznam) - vrátí 0, pokud se něco smazalo, a -1 jinak
     • vyhledávání hodnoty v seznamu - int search(list seznam, int data) - vrátí (první) pozici hledané hodnoty v seznamu, nebo -1 pokud tam není
     • odebírání zadané hodnoty (prvního výskytu) ze seznamu - int remove(list *seznam, int data) - vrátí 0, pokud hodnota byla odebrána, a -1 jinak

2. Pomocí seznamu naprogramujte zásobník (typ pro zásobník stack) a jeho základní operace (void push(stack *zasobnik, int data) a int pop(stack *zasobnik)).
3. Pomocí seznamu naprogramujte frontu (typ pro frontu queue) a její základní operace (void enqueue(queue *fronta, int data) a int dequeue(queue *fronta)). Co byste museli upravit, aby obě operace byly v O(1)?
4. Implementujte obousměrný spojový seznam.
5. Implementujte vhodné struktury pro binární vyhledávací strom (uzel stromu node; strom tree - obsahující ukazatel na kořen). Strom bude obsahovat hodnoty typu int.
6. 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ě ve vzestupném pořadí void print_in_order(tree t)
   • výpočet hloubky stromu int depth(tree t)

Učitelé (cvičení v Pythonu)

Témata

• spojový seznam podruhé
• obousměrný spojový seznam
• fronta a zásobník

Společně implementujeme spojový seznam a základní operace na něm (vyhledávání, přidávání, mazání). Projdeme si další lineární datové struktury.

Úkoly

1. Pomocí spojového seznamu naprogramujte zásobník.
2. Pomocí spojového seznamu naprogramujte frontu.
3. Implementujte obousměrný spojový seznam.