Cvičení 3

Témata

• seznam,
• zásobník
• fronta

Úkoly

Pokud zatím neumíte alokovat paměť dynamicky, tak všechny použité uzly můžete vytvořit s předstihem v mainu (pomocí pole obsahujícího všechny používané uzly). Žádný z takových uzlů se v seznamu/frontě/zásobníku nebude vyskytovat vícekrát (tj. toto nemusíte ošetřovat). Pokud už dynamické alokace ovládáte, můžete ve všech procedurách v úkolech 3,4 a 5 přijímat místo přidáváného uzlu rovnou hodnotu a uzel vytvořit dynamicky v rámci procedury.

1. 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).

2. Vytvořte strukturu pro jednosměrný spojový seznam (tj. struktura obsahujicí začátek seznamu - první uzel) a typ list pro tyto struktury (typedef).

3. Použijte struktury z úkolů 1 a 2 k implementaci následujících procedur:

   • zjištění délky seznamu: int length(list seznam)
   • výpis prvků (tj složka data struktury node) seznamu oddělených čárkou: void print_list(list seznam)
   • přidávání uzlu na začátek seznamu: void add_start(list *seznam, node *uzel)
   • přidávání uzlu na konec seznamu: void add_end(list *seznam, node *uzel)
   • přidávání uzlu na zadané místo v seznamu (nebo na konec, pokud se daná pozice v seznamu nevyskytuje): void add_position(list *seznam, node *uzel, int position)
   • odebírání uzlu ze začátku seznamu: int remove_start(list *seznam) - vrátí 0, pokud se něco smazalo, a -1 jinak
   • odebírání uzlu z konce seznamu: int remove_end(list *seznam) - vrátí 0, pokud se něco smazalo, a -1 jinak
   • vyhledávání uzlu v seznamu - int search(list *seznam, node *uzel) - vrátí pozici hledaného uzlu v seznamu, nebo -1 pokud tam není
   • odebírání zadaného uzlu ze seznamu - int remove(list *seznam, node *uzel) - vrátí 0, pokud uzel byl odebrán, a -1 jinak

4. 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)).

5. 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)). Co byste museli upravit, aby obě operace byly v O(1)?

6. Implementujte obousměrný spojový seznam.

Poznámky - Pokud chcete, můžete seznam reprezentovat dvojitým ukazatelem na uzel **node místo struktury list. Proč nestačí jednoduchý ukazatel?