====== 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 =====
#include
#include
/**
* @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;
}
===== 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
Příklady implementace najdete v sekci řešených příkladů.