====== 14 - Spojové seznamy ======
===== 1. Zásobník =====
#include
#include
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
#include
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
#include
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);
}