Objectifs
- Savoir déclarer et construire des listes chaînées en C.
- Savoir reconnaître et implémenter les algorithmes classiques de listes
chaînées à l’aide de fonctions itératives.
Contexte et préparation: Nous allons utiliser les listes chaînées (non
ordonnées, puis ordonnées) pour représenter des ensembles d’entiers. Les
opérations classiques sur les ensembles d’entiers seront réalisées à l’aide
d’algorithmes classiques sur les listes, en version itérative.
- IMPORTANT les 2 principales causes de segmentation fault avec les listes
- chaînées
- une liste non-initialisée
- un accès aux champs d’une cellule vide (ex: accès à
P->val ou P->suivant
avec P=NULL).
Question du TP
Toutes les questions seront testées au fur et à mesure (appels dans le main),
comme d’habitude !
En direct du cours (Listes non triées)
- Déclarer une liste chaînée.
- Écrire la fonction de création d’une liste chaînée par ajout en tête.
- Écrire une fonction d’impression d’une liste chaînée.
- Écrire une fonction qui teste si une liste chaînée est triée.
- Écrire une fonction de suppression de la cellule de tête d’une liste chaînée.
- Écrire une fonction de désallocation d’une liste.
- Tester les fonctions précédentes. Vérifier avec valgrind l’absence de fuite
mémoire à l’exécution.
Listes triées
On va maintenant faire en sorte de maintenir une liste triée sans doublons.
- Écrire un algorithme d’insertion d’un entier dans une liste triée par ordre
croissant. On ne fera l’insertion que si l’élément n’existe pas déjà dans la
liste.
- Écrire une fonction qui permet de créer une liste d’entiers triée par lecture
dans un fichier. Les entiers contenus sur le fichier peuvent être négatifs et
dans n’importe quel ordre.
Tests sur les ensembles
Écrire des fonctions pour :
- Tester si une liste quelconque ne contient pas de doublons.
- Faire l’union de deux ensembles (c.a.d., l’union de deux listes sans
doublon).
- Faire l’intersection de deux ensembles.
- Transformer une liste quelconque en un ensemble (supprimer les doublons).