====== 14 - Spojové seznamy ======

===== 1. Zásobník =====

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

typedef struct u
{
    int data;
    struct u * dalsi;
} uzel; 

uzel * push (uzel * a, int data)
{
    uzel * tmp = malloc (sizeof(uzel));
    tmp->data = data;
    tmp->dalsi = a;
    return tmp;
}

uzel * pop (uzel * a, int *data)
{
    *data = a->data;
    uzel * tmp = a->dalsi;
    free(a);
    return tmp;
}

int main()
{
    uzel * zasobnik = NULL;
    int b;

    zasobnik = push (zasobnik, 10);
    zasobnik = push (zasobnik, 20);
    zasobnik = push (zasobnik, 30);

    zasobnik = pop (zasobnik, &b);
    printf("%i\n", b);
}
</code>

===== 2. Fronta =====

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

typedef struct u
{
    int data;
    struct u * dalsi;
} uzel;

typedef struct q
{
    uzel * zacatek;
    uzel * konec;
} fronta;

void queue_init (fronta ** a)
{
    *a = malloc (sizeof(fronta *));
    (*a)->zacatek = NULL;
    (*a)->konec = NULL;
}

void queue_push (fronta * a, int data)
{
    uzel * novy = malloc (sizeof(uzel));

    novy->data = data;
    novy->dalsi = NULL;

    // jsou ve fronte nejaka data?
    if (a->konec)   // a->konec != NULL 
    {
        a->konec->dalsi = novy;
    }
    else            // fronta je prazdna 
    {
        a->zacatek = novy;
    }

    a->konec = novy;   
}

void queue_pop (fronta * a, int * data)
{
    if (a->zacatek) // ve fronte je alespon jedna polozka
    {
        *data = a->zacatek->data;
        uzel *tmp = a->zacatek;
        a->zacatek = a->zacatek->dalsi;
        free(tmp);
        if (a->zacatek == NULL)
        {
            a->konec = NULL;
        }
    }
}

int main()
{
    fronta * a;
    int b;

    queue_init (&a);

    queue_push (a, 10);
    queue_push (a, 20);
    queue_push (a, 30);
    queue_push (a, 40);

    queue_pop(a, &b);
    printf("%i\n", b);
    queue_pop(a, &b);
    printf("%i\n", b);
    queue_pop(a, &b);
    printf("%i\n", b);
    queue_pop(a, &b);
    printf("%i\n", b);
}
</code>

===== 3. Binární vyhledávací strom =====

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

typedef struct u
{
    int data;   // hodnota uzlu
    struct u *levy, *pravy;
} uzel;

uzel * novy (int data)
{
    uzel * tmp = malloc (sizeof(uzel));
    tmp->data = data;
    tmp->levy = NULL;
    tmp->pravy = NULL;
    return tmp;
}

uzel * pridej (uzel * a, int data)
{
    if (a == NULL)
    {
        return novy (data);
    }

    if (data < a->data)
    {
        a->levy = pridej(a->levy, data);
    }
    else
    {
        a->pravy = pridej(a->pravy, data);
    }
    
    return a;
}

void print (uzel * a)
{
    if (a != NULL)
    {
        print(a->levy);
        printf("%i\n", a->data);
        print(a->pravy);
    }
}

int main ()
{
    uzel * strom = NULL;

    strom = pridej (strom, 50);
    strom = pridej (strom, 30);
    strom = pridej (strom, 60);
    strom = pridej (strom, 20);
    strom = pridej (strom, 45);
    strom = pridej (strom, 55);
    strom = pridej (strom, 70);

    print(strom);
}
</code>
</code>