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

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

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

#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;
}

1. Upravte vhodně kód tak, abyste naimplementovali zásobník.
   1. S cvičícím diskutujte změny, které jste v kódu provedli.
2. Upravte kód vhoddně tak, abyste naimplementovali frontu
   1. S cvičícím diskutujte změny, které jste v kódu provedli.
   2. 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.
3. Implementujte binární vyhledávací strom