Cvičení 3 - lineární datové struktury II

Témata

• seznam,
• zásobník
• fronta

Úkoly

Protože 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ý uzel se v seznamu/frontě/zásobníku nebude vyskytovat vícekrát (tj toto nemusíte ošetřovat).

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 tyto struktury (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)?

Úkoly označené (*) nejsou povinné (nemusíte je odevzdávat).