Warning
This page is located in archive. Go to the latest version of this course pages. Go the latest version of this page.

14 - Spojové seznamy

1. Zásobník

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

2. Fronta

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

3. Binární vyhledávací strom

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

courses/b0b99prpa/solutions/lab14.txt · Last modified: 2020/12/10 09:02 by viteks