====== 10 - Spojové seznamy, fronta, zásobník ======


===== Procvičované témata =====

  * Dynamická alokace
  * Rekurze
  * Valgrind
  * Spojový seznam
  * Zásobník vs. fronta


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

  - Implementujte spojový seznam, který bude obsahovat celá čísla
    - Společně s cvičícím navrhněte vhodnou datovou stukturu, na které bude seznam založen.
    - Společně s cvičícím navrhněte prototypy funkcí, které umožní vkládání dat do seznamu. 
    - Zamyslete se nad tím, jak vložit nový prvek na libovolné místo seznamu.
    - Vytvořte funkci, která vypíše na konzoli obsah celého seznamu.
    - Nezapomeňte implementovat i funkci, která uvolní všechna data spojená se seznamem.
    - Kontrolujte správnost dynamické alokace paměti pomocí Valgrindu.




===== Příklad implementace spojového seznamu =====


<code c>
#include <stdio.h>
#include <stdlib.h>

/** 
 * @brief uzel spojoveho seznamu 
 */
struct uzel
{
    int data;               /**< datova polozka         */
    struct uzel * dalsi;    /**< ukazatel na dalsi uzel */
};

/** 
 * @brief funkce, ktera vlozi data na konec spojoveho seznamu
 * 
 * @param a ukazatel na aktualni zacatek seznamu
 * @param data datova polozka uzlu
 * @return novy zacatek spojoveho seznamu
 */
struct uzel * add (struct uzel * a, int data)
{
    struct uzel * tmp = malloc(sizeof(struct uzel));
    tmp->data = data;
    tmp->dalsi = a;
    return tmp;
}

/** 
 * @brief vklada data do seznamu podle velikosti
 * 
 * @param a
 * @param data 
 */
void insert (struct uzel * a, int data)
{
    while (a != NULL)
    {
        printf("a: %p a->dalsi: %p\n", a, a->dalsi); 
        if (a->data > data && a->dalsi->data < data && a->dalsi != NULL)
        {
            struct uzel * tmp = malloc (sizeof(struct uzel));
            tmp->data = data;
            tmp->dalsi = a->dalsi;
            printf("tmp: %p %p\n", tmp, a->dalsi);
            a->dalsi = tmp;
            return;
        }     
        a = a->dalsi;
    }
}

/**
 * @brief funkce, ktera rekurzivne projde cely spojovy seznam
 * 
 * @param a  
 */
void print (struct uzel * a)
{
    if (a == NULL)
        return;
    else
    {
        if (a->dalsi != NULL)
            printf("%i %p %p\n", a->data, a->dalsi, a->dalsi->dalsi);
        else
            printf("%i %p\n", a->data, a->dalsi);
        print (a->dalsi);
    }
}

/**
 * @brief funkce na dealokaci spojoveho seznamu
 * 
 * @param a zacatek spojoveho seznamu
 */
void destroy (struct uzel * a)
{
    while (a != NULL)
    {
        struct uzel * b = a;
        a = a->dalsi;
        free(b);
    }
}

int main()
{
    struct uzel * seznam = NULL;

    seznam = add (seznam, 10);
    seznam = add (seznam, 20);
    seznam = add (seznam, 30);
    seznam = add (seznam, 40);

    insert (seznam, 25);

    printf("--------------------\n");
    print (seznam);

    destroy (seznam);

    return 0;
}
</code>


===== Další úkoly na procvičení =====
  - Upravte vhodně kód tak, abyste naimplementovali zásobník.
    - S cvičícím diskutujte změny, které jste v kódu provedli.
  - Upravte kód vhoddně tak, abyste naimplementovali frontu
    - S cvičícím diskutujte změny, které jste v kódu provedli. 
    - Zajímavou variantou je 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. Pomocí takového seznamu lze implementovat prioritní frontu tak, aby funkce PUSH od začátku vytvářela vnitřní stukturu seznamu seřazenou podle priority.
  - Implementujte binární vyhledávací strom 

<note tip>Příklady implementace najdete v sekci řešených příkladů.</note>