{{indexmenu_n>09}}

====== Lab 09 - Struktury a spojové seznamy ======

/*
  * [[courses:b3b36prg:internal:tutorialinstruction:09|pro vyučující]]
*/


===== Cíle cvičení =====

  * Implementovat jednosměrný spojový seznam, procvičit si obsah ([[courses:b3b36prg:lectures:lec08|přednášky 8 Spojové struktury]].
  * Zásobník a fronta.


===== Úkoly na cvičení =====

  - Navrhněte složený datový typ (''struct'') **jednosměrného spojového seznamu**, ve kterém budeme ukládat celá čísla.
  - Navrhněte vhodné funkce (dekompozice) knihovny spojového senznamu a programu, který načte celá čísla ze ''stdin'' a uloží je do seznamu (**zásobník** a/nebo **fronta**).
    - Definujte chování programu, pokud na vstupu nebude celé číslo.
  - Implementujete funkce pro práci se spojovým seznamem. //Uvažujte, že budou tvořit knihovnu, ale pro jednoduchost budeme nejdříve implementovat v jediném souboru.//
  - Funkce otestujte programem, který vypíše vstupní čísla na ''stdout''. 
  - Program rozšiřte o funkce, které vypíši pouze lichá a pouze sudá čísla a to v pořadí, v jakém byla načtena.
  - Knihovní funkce práce se spojovým seznamem rozšiřte o implementace **fronty**. 
    * Upravte datovou strukturu a implementaci funkcí.
    * Zvažte rozšíření strukturu o informaci, zdali spojový seznam implementujete **zásobník** nebo **frontu**, například ukazatel na funkci, který bude nastaven na push_front() nebo push_back() při inicializaci struktury spojového seznamu jako zásobníku nebo fronty, např. ''create_stack()'' a ''create_queue()''.


  * Kontrolujte správnost dynamické alokace paměti a realizujte uvolnění alokované paměti.
  * Program otestujete nástrojem ''valgrind''.
  * Implementaci rozdělte do samostatné knihovny, např. ''ll-int.h'' a ''ll-int.c'' a vyzkoušejte si kompilaci a linkování  (případně i dynamické linkování) a použití ''Makefile''.

  * S cvičícím diskutujte změny, které jste v kódu provedli.

===== Další úkoly na procvičení =====

  - Implementujte spojový seznam, který v sobě bude obsahovat vždy dvojici dat - dvě celá čísla - první bude datová složka a druhé bude představovat prioritu.
  - Upravte předchozí seznam tak, aby implementoval prioritní frontu tak, aby funkce PUSH od začátku vytvářela vnitřní stukturu seznamu seřazenou podle priority.

===== Odkazy =====

[[http://seredlad.pages.fel.cvut.cz/slides/prp.html?10|Prezentace ke cvičení]]