TP3 — Listes chaînées, piles et files¶

Objectifs¶

Ce TP prolonge le TP2 consacré aux tableaux dynamiques et prépare le TP4 sur les arbres binaires. Vous allez implémenter une liste simplement chaînée, étudier les piles et les files, puis améliorer une file afin que ses opérations principales aient une complexité constante.

À la fin du TP, vous devrez savoir :

• implémenter et tester une liste simplement chaînée en C ;
• différencier le comportement d'une pile (LIFO) et d'une file (FIFO) ;
• choisir une représentation en fonction des opérations à effectuer ;
• justifier une complexité en comptant les parcours et les décalages nécessaires ;
• implémenter une file réutilisable dans le TP4 pour le parcours en largeur d'un arbre, dont le type de donnée est défini par Elmt_t.

Préparation et méthode de travail¶

Vous pouvez réutiliser les notions et le code du TP2. Gardez un Makefile, compilez après chaque fonction et testez aussi bien les cas limites que les cas courants : structure vide, un élément, plusieurs éléments, élément absent et échec éventuel d'allocation.

Partie 1 — Implémenter une liste simplement chaînée¶

Cette partie construit les opérations nécessaires aux exercices suivants. Les opérations plus avancées (découpage, dédoublonnage, inversion récursive, etc.) peuvent être traitées en bonus : elles ne sont pas le but principal de ce TP.

1.1. Organisation des fichiers¶

Conservez un seul projet C pour l'ensemble du TP3. La liste, la pile et la file partageront le même type Cell, dont le champ de données est typé par Elmt_t *. La file sera réutilisée au TP4. Créez les fichiers suivants :

• cell.h et cell.c : définition d'une cellule contenant un Elmt_t *, création et libération d'une cellule ;
• elmt_t.h et elmt_t.c : définition et fonctions associées aux entiers stockés dans la liste ;
• list.h et list.c : opérations sur les listes simplement chaînées ;
• stack.h et stack.c : interface et implémentation de la pile ;
• fifo.h et fifo.c : interface et implémentation de la file FIFO ;
• test_list.c, test_stack.c et test_fifo.c : programmes de test séparés ;
• Makefile : compilation des trois exécutables de test.

Les trois fichiers de test ont chacun leur propre fonction main. Ils doivent donc être compilés en trois exécutables distincts, en liant à chacun les modules dont il a besoin.

Organisation indicative :

tp3/
├── cell.h          cell.c
├── elmt_t.h        elmt_t.c
├── list.h          list.c
├── stack.h         stack.c
├── fifo.h          fifo.c
├── test_list.c
├── test_stack.c
├── test_fifo.c
└── Makefile

Dans elmt_t.h, définissez Elmt_t comme un alias de int :

typedef int Elmt_t;

Déclarez et implémentez les fonctions suivantes :

• void print_int(Elmt_t *e) : affiche la valeur pointée ;
• int compare_int(Elmt_t *e1, Elmt_t *e2) : renvoie une valeur négative, nulle ou positive selon l'ordre des valeurs ;
• Elmt_t *new_elmt(Elmt_t e) : alloue un élément, initialise sa valeur et renvoie NULL si l'allocation échoue ;
• void free_elmt(Elmt_t *e) : libère un élément alloué dynamiquement.

1.2. Type et fonctions de liste¶

1.2.1. Une cellule typée, partagée avec la file¶

Pour éviter de définir deux types Cell incompatibles — l'un pour les listes et l'autre pour la file du TP4 —, la cellule est définie une seule fois dans cell.h. Son champ data est de type Elmt_t *, et non void * : le type Elmt_t permet de définir explicitement le type des objets stockés.

#ifndef CELL_H
#define CELL_H

#include "elmt_t.h"

typedef struct _cell {
    Elmt_t *data;
    struct _cell *next;
} Cell;

Cell *create_cell(Elmt_t *data); /* alloue une cellule */
void free_cell(Cell *c);          /* libère uniquement la cellule */

#endif

Implémentez create_cell et free_cell une seule fois dans cell.c. create_cell initialise data avec le pointeur reçu et next à NULL, puis renvoie NULL si malloc échoue. free_cell libère uniquement la cellule ; elle ne libère jamais automatiquement data. Le conteneur qui détient l'objet reste responsable de sa libération.

Dans le TP3, Elmt_t est défini comme int dans elmt_t.h, donc Cell.data est un Elmt_t * (un int *). Au TP4, le même module cell / fifo peut être recompilé avec un elmt_t.h adapté au type des nœuds de l'arbre. Il faut alors faire correspondre Elmt_t au type des objets placés dans la file ; les deux TPs étant compilés séparément, chacun peut avoir sa propre définition de Elmt_t.

Dans list.h, incluez cell.h et elmt_t.h sous une garde d'inclusion, puis définissez simplement le type de liste :

#ifndef LIST_H
#define LIST_H

#include "cell.h"
#include "elmt_t.h"

typedef Cell *List;

/* déclarations des fonctions de liste */

#endif

La liste stocke des pointeurs vers des Elmt_t dans le champ typé Cell.data. Vous pouvez donc utiliser directement cell->data dans list.c, sans conversion depuis void *. Une liste vide est représentée par NULL. Dans cette première partie, la liste ne conserve qu'un pointeur vers sa tête : elle ne mémorise pas la dernière cellule.

Déclarez dans list.h et implémentez dans list.c les fonctions suivantes :

• int list_is_empty(List l) : renvoie 1 si la liste est vide, 0 sinon. Le préfixe list_ évite un conflit de nom avec is_empty(Fifo) dans l'interface du TP4 ;
• List create_empty_list(void) ;
• void print_list(List l, void (*print_elmt)(Elmt_t *)) : affiche [] si la liste est vide, sinon les valeurs séparées par des virgules entre crochets ;
• Cell *insert_first(Elmt_t *e, List *l) : crée une cellule avec create_cell(e) puis l'ajoute en tête ;
• Cell *insert_last(Elmt_t *e, List *l) : ajoute une cellule en fin ;
• Cell *search(Elmt_t *e, List l, int (*compare_elmt)(Elmt_t *, Elmt_t *)) : renvoie la première cellule contenant une valeur égale, ou NULL si elle est absente ;
• int length(List l) : renvoie la longueur de la liste ;
• void free_list(List *l) : libère chaque Elmt_t * stocké dans data, puis chaque cellule, et positionne *l à NULL.

create_cell et free_cell sont les fonctions communes de gestion des cellules, implémentées dans cell.c : ne les redéfinissez ni dans list.c, ni dans fifo.c. Vous pouvez écrire une fonction auxiliaire insert_after pour simplifier les insertions. Définissez clairement le comportement en cas d'échec d'allocation : une insertion échouée ne doit pas corrompre la liste.

1.3. Tests et premières complexités¶

Testez au minimum :

1. l'affichage et la destruction d'une liste vide ;
2. l'insertion d'un seul élément en tête ;
3. plusieurs insertions en tête et en fin ;
4. la recherche d'un élément présent et d'un élément absent ;
5. la longueur après plusieurs insertions ;
6. la libération d'une liste non vide et la vérification que la liste vaut ensuite NULL.

Question 1. Quelle est la complexité de insert_first ? Quelle est celle de insert_last dans cette représentation ? Comptez les cellules qu'il faut parcourir.

Question 2. Quelle information supplémentaire permettrait d'insérer en fin sans repartir de la tête à chaque fois ? Gardez cette idée pour la partie 3.

Partie 2 — Pile ou file : choisir une représentation¶

2.1. Deux comportements abstraits¶

Une pile suit la règle LIFO (Last In, First Out) : le dernier élément empilé est le premier dépilé. Exemple : une pile d'assiettes.

• stack_push(e) : ajoute e au sommet ;
• stack_pop(...) : retire le sommet et récupère sa valeur ;
• stack_is_empty(...) : indique si la pile est vide.

Une file suit la règle FIFO (First In, First Out) : le premier élément ajouté est le premier retiré. Exemple : une file d'attente.

• enqueue(e) : ajoute e à la fin de la file ;
• dequeue(...) : retire l'élément le plus ancien ;
• is_empty(...) : indique si la file est vide.

Le comportement abstrait ne détermine pas à lui seul l'implémentation : une pile ou une file peut être construite avec un tableau ou avec une liste chaînée.

2.2. Question ouverte — proposer des implémentations¶

Avant de coder, proposez une représentation pour chacune des structures suivantes. Pour chaque proposition, indiquez l'extrémité d'ajout, l'extrémité de retrait, les décalages ou parcours nécessaires, puis estimez la complexité en fonction du nombre n d'éléments.

• une pile avec un tableau dynamique ;
• une pile avec une liste simplement chaînée ;
• une file avec un tableau dynamique ;
• une file avec une liste simplement chaînée.

Vous pouvez vous aider de ce comparateur interactif. Choisissez les complexités qui vous semblent correctes puis cliquez sur Vérifier mes réponses. Le tableau peut être complété directement dans le navigateur ; il n'est pas nécessaire de l'imprimer.

Vous pouvez aussi manipuler les deux représentations ci-dessous. Chaque représentation possède ses propres données, sa propre position courante et son propre coût cumulé : passer de la liste au tableau ne réinitialise pas les mesures de l'autre représentation.

• Accéder depuis le début : dans une liste, les maillons sont sélectionnés successivement et le compteur augmente à chaque visite ; dans un tableau, la case demandée est sélectionnée directement.
• Ajouter après l'élément courant : dans une liste, suivez les trois étapes de création et de mise à jour des liens ; dans un tableau, observez les déplacements vers la droite nécessaires pour libérer une case.
• Supprimer l'élément courant : dans un tableau, les valeurs suivantes sont déplacées une à une vers la gauche, avec un incrément du compteur à chaque déplacement.
• Ajouter en fin ou suivre next pour comparer d'autres opérations.

L'atelier est un modèle pédagogique du coût algorithmique, pas un chronométrage. Les étapes sont volontairement ralenties afin de rendre les opérations visibles ; aucun calcul n'est exécuté côté serveur.

Pour cette première comparaison, retenez les hypothèses suivantes :

• le tableau dynamique grandit par réallocation géométrique ; une insertion en fin est donc en O(1) amorti ;
• un accès à une case de tableau par son indice est en O(1) ;
• la liste est simplement chaînée et ne mémorise au départ qu'un pointeur vers la tête ;
• on considère les opérations sur une structure contenant n éléments.

Question 3. Donnez un exemple de deux implémentations différentes mais correctes d'une même structure abstraite. Pourquoi leur coût peut-il être différent ?

2.3. Exercice de programmation — utiliser une pile¶

Implémentez une fonction qui vérifie si les parenthèses d'une expression sont correctement équilibrées. Pour cet exercice, prenez en charge les trois couples (), [] et {}. Les autres caractères de la chaîne sont ignorés.

Par exemple :

• a * (b + c) est équilibrée ;
• [(a + b) * {c - d}] est équilibrée ;
• ([)] n'est pas équilibrée : les fermetures sont dans le mauvais ordre ;
• (a + b n'est pas équilibrée ;
• a + b) n'est pas équilibrée.

Définissez et implémentez une pile de caractères. Vous pouvez la construire au-dessus de votre liste de la partie 1 en stockant les caractères sous forme de Elmt_t. Il est aussi possible de proposer une représentation différente, à condition de justifier les choix.

La fonction de vérification doit parcourir la chaîne une seule fois :

1. à l'ouverture d'une parenthèse, d'un crochet ou d'une accolade, empilez le caractère ;
2. à la fermeture, vérifiez que la pile n'est pas vide, dépilez et vérifiez que le type de fermeture correspond à l'ouverture ;
3. à la fin de la chaîne, la pile doit être vide.

Créez stack.h et stack.c. Pour rester cohérent avec la partie 1, vous pouvez représenter Stack par un alias de List et réutiliser les cellules communes typées par Elmt_t : le sommet de pile est alors la tête de la liste. Préfixez les opérations de pile afin que leurs noms ne puissent pas entrer en collision avec ceux des autres modules.

Votre interface doit au minimum proposer les opérations suivantes (vous pouvez adapter les types si vous les justifiez, mais gardez un contrat sans ambiguïté) :

#ifndef STACK_H
#define STACK_H

#include "list.h"

typedef List Stack;

int stack_is_empty(Stack s);
int stack_push(Stack *s, Elmt_t value); /* 1 si succès, 0 si échec d'allocation */
int stack_pop(Stack *s, Elmt_t *value); /* 1 si retrait effectué, 0 si pile vide */
void stack_clear(Stack *s);

#endif

Proposez une signature adaptée, par exemple int balanced(const char *expression), et précisez sa convention de retour. Gérez correctement les erreurs d'allocation et libérez toute mémoire utilisée, y compris lorsqu'une expression est invalide. Pour ne pas confondre une expression invalide et une erreur d'allocation, vous pouvez choisir une convention de retour qui distingue explicitement les trois cas.

Testez au minimum les cinq exemples ci-dessus, une chaîne vide et une expression contenant plusieurs groupes imbriqués. Dans le compte rendu, justifiez la complexité temporelle et la mémoire supplémentaire utilisées.

Partie 3 — Implémenter une file réutilisable au TP4¶

La file réalisée dans cette partie sera réutilisée au TP4 pour effectuer un parcours en largeur d'un arbre binaire. Il est donc important de respecter exactement l'interface demandée et de tester soigneusement les cas limites.

3.1. Pourquoi conserver un pointeur vers la fin ?¶

Une file FIFO peut être représentée par une liste simplement chaînée : on retire en tête et on ajoute en fin. Avec seulement un pointeur vers la tête, le retrait est en O(1), mais l'ajout en fin demande un parcours et coûte O(n).

Comment éviter de parcourir toute la liste lors de chaque ajout ? Conservez dans la structure un pointeur vers la première cellule et un autre vers la dernière cellule. Vous pourrez alors ajouter après la dernière cellule directement, tout en continuant à retirer en tête.

3.2. Interface obligatoire : fifo.h¶

La file doit utiliser le type Cell du module commun cell.h. Le type Cell ne doit surtout pas être redéfini dans fifo.h : ce partage permet de compiler les listes et la file dans un seul projet.

Créez fifo.h avec le contenu suivant :

#ifndef FIFO_H
#define FIFO_H

#include "cell.h"

typedef struct {
    Cell *first;
    Cell *last;
} Fifo;

int is_empty(Fifo);
Fifo create_fifo(void);

/* Return NULL if memory allocation fails. */
Cell *fifo_add(Fifo *, Elmt_t *);
Elmt_t *fifo_get(Fifo *); /* frees the Cell, not the pointed-to object */

#endif

Les noms des fonctions de file restent ceux utilisés au TP4, mais les paramètres liés aux données sont typés avec Elmt_t * plutôt qu'avec void *. create_fifo(void) précise explicitement l'absence de paramètre en C. Gardez exactement ces signatures dans l'en-tête et dans fifo.c, et mettez à jour le fifo.h fourni au TP4 de la même manière.

Le fichier fifo.c inclut fifo.h et implémente les fonctions de file. Il utilise create_cell et free_cell fournies par cell.c. Ne recopiez pas les définitions de Cell, create_cell ou free_cell dans fifo.c.

Après avoir étudié le contrat, complétez ce petit vérificateur pour les deux opérations de la file optimisée :

Dans le TP4, remplacez l'ancien fifo.h par cette version et ajoutez cell.h au projet. Supprimez de l'ancien fifo.c les implémentations de create_cell et free_cell : elles sont désormais fournies par cell.c, qui doit être compilé avec la file. Le code du TP4 qui utilise la file peut continuer à inclure uniquement fifo.h, puisque celui-ci inclut désormais cell.h. Adaptez le type Elmt_t à celui des nœuds d'arbre dans le projet du TP4. Ne conservez pas une seconde définition de Cell ni une seconde implémentation de create_cell / free_cell.

3.3. Contrat des fonctions¶

Respectez précisément les comportements suivants :

• int is_empty(Fifo f) renvoie 1 si la file est vide, 0 sinon. Une file vide doit avoir first == NULL et last == NULL.
• create_cell(Elmt_t *data) est fournie par cell.c : elle alloue une cellule, place le pointeur reçu dans data, initialise next à NULL et renvoie NULL en cas d'échec d'allocation.
• free_cell(Cell *c) est fournie par cell.c : elle libère uniquement la cellule et accepte c == NULL. Elle ne libère jamais c->data.
• Fifo create_fifo(void) renvoie une file vide, avec ses deux pointeurs à NULL.
• Cell *fifo_add(Fifo *f, Elmt_t *data) ajoute une nouvelle cellule en fin de file et renvoie son adresse. En cas d'échec d'allocation, la fonction renvoie NULL et laisse la file inchangée. Si la file était vide, first et last désignent tous deux la nouvelle cellule.
• Elmt_t *fifo_get(Fifo *f) retire la cellule en tête, libère cette cellule avec free_cell, puis renvoie le pointeur data qu'elle contenait. Si la file est vide, la fonction renvoie NULL. Si le retrait vide la file, remettez également last à NULL.

Le contrat utilise NULL comme résultat de fifo_get pour signaler une file vide. Par conséquent, dans cette version, n'enfilez pas la valeur NULL comme donnée : cela rendrait impossible de distinguer une file vide d'une donnée NULL retirée.

Important : fifo_add et fifo_get modifient la file ; elles reçoivent donc un pointeur vers Fifo. En revanche, is_empty reçoit une copie de la structure, car elle ne fait que la consulter.

3.4. Tests obligatoires de la file¶

Dans test_fifo.c, compilé dans le même projet que les modules communs, testez les cas suivants :

1. créer une file vide et vérifier is_empty ;
2. appeler fifo_get sur une file vide et vérifier le résultat NULL ;
3. créer trois objets avec new_elmt, les ajouter à la file et vérifier que les pointeurs ressortent dans le même ordre ;
4. retirer un élément, ajouter un autre élément, puis vérifier l'ordre FIFO ;
5. vider complètement la file et vérifier que first et last valent NULL ;
6. ajouter un élément dans la file redevenue vide et vérifier que cela fonctionne ;
7. contrôler les retours de toutes les allocations.

Pour vider la file, appelez fifo_get jusqu'à ce que is_empty renvoie vrai. Rappelez-vous que fifo_get libère les cellules, mais pas les objets pointés par data. Dans les tests, vérifiez donc aussi que le programme appelant reste responsable des objets renvoyés.

3.5. Lien avec le parcours en largeur du TP4¶

Dans le TP4, la file stockera des pointeurs vers des nœuds d'arbre. Pour conserver le champ typé Elmt_t *, le projet du TP4 devra définir Elmt_t comme alias du type de nœud (par exemple typedef struct Node Elmt_t;, avec une déclaration anticipée compatible dans elmt_t.h). Le TP3 et le TP4 étant des projets compilés séparément, cette définition peut être différente entre les deux sujets. La file ne devra pas libérer les nœuds lorsqu'ils sont retirés : elle libère seulement ses propres cellules. Le code qui possède l'arbre reste responsable de libérer ses nœuds.

Vous n'avez pas à implémenter le parcours en largeur de l'arbre dans ce TP. Vous devez en revanche rendre la file assez fiable pour qu'elle puisse être réutilisée sans modifier son interface.

Question 4. Quelle est désormais la complexité de fifo_add et de fifo_get ? Expliquez pourquoi le pointeur last suffit pour accélérer l'ajout, alors qu'un pointeur vers la fin ne suffirait pas à rendre constant le retrait du dernier élément dans une liste simplement chaînée.

Partie 4 — Synthèse¶

Dans votre compte rendu, répondez brièvement aux questions suivantes :

1. Pour chacune des représentations du tableau interactif, justifiez les complexités par le nombre de décalages ou de cellules parcourues.
2. Pourquoi une pile se représente-t-elle naturellement par une liste simplement chaînée dont le sommet est en tête ?
3. Pourquoi la file implémentée en partie 3 utilise-t-elle deux pointeurs (first et last) ?
4. Quels cas limites faut-il traiter après l'ajout du premier élément ou le retrait du dernier élément ?
5. Pourquoi la liste et la file peuvent-elles partager Cell tout en ayant des politiques de propriété différentes pour data ?

Bonus¶

• Implémenter mirror_it pour inverser une liste simplement chaînée sans recopier les éléments.
• Implémenter une liste doublement chaînée et comparer ses avantages et son coût mémoire.
• Étudier une file à priorités : quel critère de retrait impose-t-elle, et quelle représentation vous semble adaptée ?

Rendu attendu¶

Rendez le code source, le Makefile ou les commandes de compilation, ainsi qu'un court compte rendu contenant les réponses aux questions de complexité, les choix d'implémentation et les tests réalisés. Le compte rendu doit démontrer que les complexités sont comprises et justifiées ; une simple liste de notations O(...) ne suffit pas.

Irruption de l'IA Générative...¶

Comme depuis quelques années il est très facile de demander une correction du code et l'écriture d'un rapport complet à une IA générative, je préfère le faire pour vous afin que vous éconnomisiez des ressources précieuses.

Correction générée par ChatGPT