Version sans JavaScript, en lecture seule : les ateliers, les quiz et l’exécution du code n’y sont pas. Version complète · Catalogue · Se connecter
Feuille d'exercices 4
Structures de données Lire des signatures, écrire des fonctions sur les listes avec un pointeur sur pointeur, trouver les bogues d'un module, une pile et un arbre binaire de recherche en types abstraits. Chapitre 4.
Sauf mention contraire, les listes sont celles du chapitre 4 :
typedef struct s_liste *t_liste;
struct s_liste
{
int val;
t_liste suivant;
};
t_liste ajouter(int x, t_liste l); /* ajoute x en tête */
void detruire(t_liste l);Tous les programmes se compilent avec gcc -std=c11 -Wall -Wextra -Werror, et doivent passer valgrind --leak-check=full sans erreur ni fuite.
Exercice · Lire des signatures
Pour chaque prototype, dire ce que fait sans doute la fonction, ce qu'elle peut modifier chez l'appelant, et écrire un appel. On suppose que les conventions du chapitre 4 sont respectées.
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);Exercice · Fonctions sur les listes
Écrire :
int somme(t_liste l).void ajouter_fin(int x, t_liste *l), qui ajoute x en fin de liste.void supprimer(int x, t_liste *l), qui supprime la première occurrence de x, s'il y en a une, et libère le maillon.t_liste copier(t_liste l), qui rend une copie de la liste, dans le même ordre, sans la renverser.t_liste renverser(t_liste l), qui renverse la liste en place , sans allouer un seul maillon, et rend son nouveau début.Les questions 2 à 4 s'écrivent sans cas particulier pour la liste vide, avec un pointeur sur pointeur.
Exercice · Trouver les bogues
Ce module compile. Il contient pourtant quatre erreurs.
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);
}Trouver les quatre erreurs, et dire pour chacune ce qui se passe à l'exécution. Compiler avec gcc -std=c11 -Wall -Wextra -g : lesquelles sont signalées ? Puis lancer sous valgrind un main qui s'en sert : lesquelles apparaissent ? Corriger. Exercice · Une pile en type abstrait
Une pile est une structure où l'on retire en premier le dernier élément ajouté. On la représente par un tableau qui s'agrandit, comme le vecteur du chapitre 4.
Écrire l'en-tête pile.h : le type abstrait t_pile, et les opérations pile_nouvelle, pile_est_vide, empiler, depiler (qui rend l'élément retiré) et pile_detruire. Écrire pile.c. depiler sur une pile vide affiche un message sur la sortie d'erreur et arrête le programme. Pourquoi empiler n'a-t-elle pas besoin de recevoir la pile par adresse, alors que inserer recevait la liste par adresse ? Exercice · Un arbre binaire de recherche
Dans un arbre binaire de recherche , les clés du sous-arbre gauche d'un nœud sont strictement plus petites que la sienne, celles du sous-arbre droit plus grandes ou égales.
typedef struct s_abr *t_abr;
struct s_abr
{
int cle;
t_abr g, d;
};Écrire void abr_inserer(int x, t_abr *a), sans récursivité et sans cas particulier pour l'arbre vide. Écrire int abr_contient(int x, t_abr a). Écrire void abr_afficher(t_abr a), qui affiche les clés dans l'ordre croissant. Quel parcours faut-il ? Écrire void abr_detruire(t_abr a). On insère 50, 30, 70, 20, 40, 60, 80, 30. Dessiner l'arbre. Qu'obtient-on si l'on insère 10, 20, 30, 40, 50 ?