On appelle liste une suite finie d'éléments repérés par leur rang (premier, second, etc..., nième). L'ajout et la suppression d'un élément peut se faire à n'importequel rang valide de la liste. Dans la suite et pour cet exercice les éléments listés seront des entiers, mais de façon générale une liste peut lister tout type d'éléments.

En langage C, les tableaux sont une première façon spontanée de représenter une liste. Les opérations d'insertion et de suppression d'éléments y sont toutefois malaisés. Elles nécessitent des redimensionnements du tableau et des recopies multiples. Nous allons voir une autre façon de représenter une liste, à l'aide de données dynamiques et de pointeurs : les listes chainées.

Les listes chainées

Une liste chainée est une structure dynamique formée de noeuds reliés par des liens. La figure ci dessous illustre ces concepts.

En C, un noeud sera représenté sous la forme d'une structure contenant une ou plusieurs informations et un pointeur (le lien) vers le noeud suivant dans la liste. Nous souhaitons donc déclarer une structure Noeud dont un des champs est un pointeur... sur un Noeud. Il est nécessaire de savoir ce qu'est un Noeud pour définir un pointeur de Noeud. Cette difficulté est contournée par l'écriture suivante :



typedef struct Noeud
{ 
  int donnée;
  struct Noeud * suivant;
} Noeud;

Une liste peut ensuite être déclarée comme étant un simple lien (c'est à dire un pointeur) sur le premier noeud :

Noeud * liste;

Ce pointeur vaut NULL si la liste est vide et ne contient aucun élément. Il vaut l'adresse du premier noeud si la liste n'est pas vide. Les noeuds sont créés dynamiquement (avec la fonction malloc) au fur et à mesure des besoins. Ils sont détruits (avec la fonction free) s'ils ne sont plus utilisés. Il faut faire attention à bien renseigner la valeur du pointeur suivant dans chaque noeud afin qu'il ait toujours soit la valeur NULL (fin de liste), soit l'adresse du noeud suivant.

Ecrire un programme qui va utiliser des listes chaînées et offrir les fonctions suivantes pour les manipuler :

Création d'une liste vide : Noeud * cree_liste_vide();
Afficher les éléments contenus dans la liste (ici il s'agit donc des entiers contenus dans chaque noeud) : void afficher(Noeud * liste);
Ajouter un élément (un entier) en début de liste : Noeud * ajout_debut(Noeud * liste, int e);
Suppression d'un élément (un entier) en début de liste : Noeud * supprime_debut(Noeud * liste);
Taille de la liste : int taille(Noeud * liste);
Renvoyer le Jème élément de la liste (un entier ici) : int jieme(Noeud * liste, int j);
Ajouter un élément (un entier) en position j : Noeud * ajout_jieme(Noeud * liste, int j, int e);
Supprimer un élément (un entier) en position j : Noeud * supprime_jieme(Noeud * liste, int j);

Corrections

TP 7 : Listes