9 - 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í

  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.

Další úkoly na procvičení

  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.

Ukázkové příklady

1. Lineární seznam

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

2. Zásobník

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

courses/b0b99prpa/labs/lab09.txt · Last modified: 2019/11/19 12:57 by viteks