Version without JavaScript, read-only: workshops, quizzes and running code are not available here. Full version · Catalogue · Sign in
Exercise sheet 4
Data structures Read signatures, write list functions with a pointer to a pointer, find the bugs in a module, a stack and a binary search tree as abstract types. Chapter 4.
Unless stated otherwise, the lists are those of chapter 4:
typedef struct s_liste *t_liste;
struct s_liste
{
int val;
t_liste suivant;
};
t_liste ajouter(int x, t_liste l); /* adds x at the head */
void detruire(t_liste l);All programs are compiled with gcc -std=c11 -Wall -Wextra -Werror, and must pass valgrind --leak-check=full with no error and no leak.
Exercise · Reading signatures
For each prototype, say what the function probably does, what it can modify on the caller's side, and write a call. We assume the conventions of chapter 4 are followed.
size_t compter(const char s[], char c);void trier(int t[], size_t n);int retirer_tete(t_liste *l);t_liste concatener(t_liste a, t_liste b);int diviser(int a, int b, int *reste);void liberer_tout(char *mots[], size_t n);Exercise · Functions on lists
Write:
int somme(t_liste l).void ajouter_fin(int x, t_liste *l), which adds x at the end of the list.void supprimer(int x, t_liste *l), which removes the first occurrence of x, if there is one, and frees the node.t_liste copier(t_liste l), which returns a copy of the list, in the same order, without reversing it.t_liste renverser(t_liste l), which reverses the list in place , without allocating a single node, and returns its new start.Questions 2 to 4 can be written without a special case for the empty list, using a pointer to a pointer.
Exercise · Find the bugs
This module compiles. Yet it contains four errors.
t_liste ajouter(int x, t_liste l)
{
t_liste t = malloc(sizeof (t_liste));
t->val = x;
t->suivant = l;
return t;
}
void ajouter_fin(int x, t_liste l)
{
if (l == NULL )
l = ajouter(x, NULL );
else
{
while (l->suivant != NULL )
l = l->suivant;
l->suivant = ajouter(x, NULL );
}
}
void detruire(t_liste l)
{
for (; l != NULL ; l = l->suivant)
free(l);
}Find the four errors, and say for each what happens at run time. Compile with gcc -std=c11 -Wall -Wextra -g: which ones are reported? Then run a main that uses it under valgrind: which ones show up? Fix them. Exercise · A stack as an abstract type
A stack is a structure from which the last element added is the first removed. We represent it by an array that grows, like the vector of chapter 4.
Write the header pile.h: the abstract type t_pile, and the operations pile_nouvelle, pile_est_vide, empiler, depiler (which returns the removed element) and pile_detruire. Write pile.c. depiler on an empty stack prints a message on the error output and stops the program. Why does empiler not need to receive the stack by address, whereas inserer received the list by address? Exercise · A binary search tree
In a binary search tree , the keys of a node's left subtree are strictly smaller than its own, those of the right subtree greater or equal.
typedef struct s_abr *t_abr;
struct s_abr
{
int cle;
t_abr g, d;
};Write void abr_inserer(int x, t_abr *a), without recursion and without a special case for the empty tree. Write int abr_contient(int x, t_abr a). Write void abr_afficher(t_abr a), which prints the keys in increasing order. Which traversal is needed? Write void abr_detruire(t_abr a). We insert 50, 30, 70, 20, 40, 60, 80, 30. Draw the tree. What do we get if we insert 10, 20, 30, 40, 50?