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

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

1. Implementujte frontu, která bude obsahovat celá čísla, která bude uživatel zadávat z klávesnice.
   1. Společně s cvičícím navrhněte vhodnou datovou stukturu, na které bude fronta založena.
   2. Společně s cvičícím navrhněte prototypy funkcí, které umožní vkládání dat do fronty (PUSH), odebírání z fronty (POP), dotaz na poslední prvek.
   3. Vytvořte funkci, která vypíše na konzoli obsah celé fronty.
   4. Nezapomeňte implementovat i funkci, která uvolní všechna data spojená s implementovanou frontou.
   5. Kontrolujte správnost dynamické alokace paměti pomocí Valgrindu.
2. Upravte vhodně kód tak, abyste naimplementovali zásobník.
   1. S cvičícím diskutujte změny, které jste v kódu provedli.

1. Implementujte 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.
2. Upravte předchozí seznam tak, aby implementoval prioritní frontu tak, aby funkce PUSH od začátku vytvářela vnitřní stukturu seznamu seřazenou podle priority.

#include <malloc.h>
 
struct polozka
{
	int data;
	struct polozka * dalsi;
};
 
struct polozka * insert (struct polozka * a, int d)
{
	struct polozka * tmp = (struct polozka *) malloc(sizeof(struct polozka));
	tmp->data = d;
	tmp->dalsi = a;
	return tmp;
}
 
int projdi (struct polozka *a)
{
	if (a == NULL) 
		return 0;
	else 
	{
		printf("data: %d\n", a->data);
		projdi (a->dalsi);
	}
}
 
int main()
{
	struct polozka * seznam = NULL;
 
	seznam = insert(seznam, 10);
	seznam = insert(seznam, 20);
	seznam = insert(seznam, 30);
 
	projdi (seznam);
 
	return 0;
}

#include <malloc.h>
 
typedef struct u
{
	int data;
	struct u * predchozi;
} uzel;
 
uzel * push (uzel * a, int data)
{
	uzel * tmp = (uzel *)malloc(sizeof(uzel));
	tmp->data = data;
	tmp->predchozi = a;
	return tmp;
}
 
uzel * pop (uzel * a, int * data)
{
	*data = a->data;
	uzel * tmp = a->predchozi;
	free (a);
	return tmp;
}
 
int main()
{
	int a;
	uzel * zasobnik = NULL;
 
	zasobnik = push (zasobnik, 10);
	zasobnik = push (zasobnik, 33);
	zasobnik = pop (zasobnik, &a);
	printf("pop: %d\n", a);
	zasobnik = pop (zasobnik, &a);
	printf("pop: %d\n", a);
 
	return 0;
}