Cette fiche et la suivante introduisent la réalisation du type abstrait Liste appelée "listes chaînées dynamiques". Il s'agit de la réalisation la plus courante, et probablement la plus utilisée, du concept de liste.

  • Cette fiche est dédiée à la déclaration du type C et aux algorithmes de parcours de liste.
  • La fiche suivante construira les fonctions d'ajout en tête et de suppression en tête de liste.

Avec ces 2 fiches, on construit donc pas à pas le l'implantation "liste chaînée dynamique" du TAD liste. Vous allez ainsi comprendre comment passer du concept d'un type abtrait à sa réalisation ; et repérer quelques questions à se poser au fur et à mesure.

Pour simplifier notre propos, on ne s'intéresse dans cette fiche qu'à une liste contenant des valeurs de type double.

1. Les principes

Les objectifs poursuivi avec les "listes chaînées dynamiques" sont les suivants :

  • La liste doit pouvoir contenir autant d'éléments que l'on veut. Seule la quantité de mémoire disponible doit limiter le nombre d'éléments maximum de la liste.
  • Pour cela, plutôt que d'allouer toute la mémoire pour la liste dès sa création, on va allouer des maillons un à un, à la demande. Chaque maillon contiendra un élément. C'est donc le programmeur qui, lors de l'ajout/suppression de maillons, va prendre en charge la gestion mémoire (allocation et libération des maillons).

Les maillons vont donc être alloués un à un, à divers endroits de la mémoire.

Avec les listes chaînées dynamiques, le chaînage d'un maillon sur le suivant est réalisé au moyen d'un pointeur de type pointeur - sur - maillon qui pointe le maillon suivant, c'est à dire un pointeur dont la valeur est l'adresse mémoire où est placé maillon suivant.

Les maillons d'une liste chaînée dynamique sont alloués au fur et à mesure et répartis à divers endroits de la mémoire.

Chaque maillon contient donc deux choses :

  • L'élément stocké dans le maillon, (un double pour nous) - en vert sur la figure.
  • Un pointeur qui pointe le maillon suivant (donc de type "pointeur - sur - maillon") - en orange sur la figure.

Enfin :

  • Le dernier maillon de la liste n'a pas de suivant. Son pointeur sur le maillon suivant ne pointe aucun maillon. Il doit donc valoir donc NULL - en noir sur la figure.
  • La variable qui permet de manipuler la liste est un simple pointeur sur le premier maillon de la liste - à gauche sur la figure.

2. Le type maillon link_t

La définition du type "maillon" (link_t en anglais) doit donc contenir une valeur, mais aussi un pointeur sur une variable de ce même type "maillon", pour accéder au maillon suivant. On dit que le type maillon est un type récursif.

On pourrait penser définir le type maillon comme suit : 


          // !! ATTENTION : CE QUI SUIT PROVOQUE UNE ERREUR DE COMPILATION !!
          // Définition (fausse) du type maillon
          typdef struct {
            double val;     /* un élément de la liste*/
            link_t * next;  /* un pointeur sur le maillon suivant de la liste */
          } link_t ;

Seulement voila : ce code est refusé par le compilateur car, à la ligne 5, on utilise le type link_t n'est pas encore connu par le compilateur !

En langage C est donc conduit à définir le type maillon comme suit : 


          // 1. Pré-définition du type maillon :
          //     On prédéfinit un type "struct quelquechose" (ici : struct _link)
          //     qui ne sert à qu'à déclarer le type structuré récursif.
          struct _link {
            double val;          /* un élément de la liste*/
            struct _link * next; /* un pointeur sur le maillon suivant de la liste */
          };

          // 2. Maintenant, on peut définir le type link_t avec typedef :
          typedef  struct _link  link_t; // link_t est type synonyme de "struct _link"

En fait, il est possible de déclarer le type link_t de façon un peu plus condensée.

Voici la déclaration que nous retiendrons pour le type maillon link_t dans le fichier header list.h : 


            // Fichier list.h
            #ifndef _LIST_H
            #define _LIST_H
              typedef struct _link {
                double val;          /* élément placé dans le maillon */
                struct _link * next; /* pointeur sur le maillon suivant de la liste */
              } link_t;
            #endif

3. Le type liste list_t

Plusieurs choix s'offrent à nous pour définir en C le type liste chainée dynamique. Le plus simple, que nous utiliserons durant tout ce semestre, consiste à dire qu'une variable "liste chaînée dynamique" est tout simplement un pointeur sur le premier maillon de la liste. Ainsi :

  • Si la liste n'est pas vide, notre variable vaudra l'adresse du premier maillon : cela permettra d'accéder à ce premier maillon, puis de proche en proche à tous les maillons de la liste.
  • Le cas liste vide est simplement repéré par la valeur NULL : la variable liste ne pointe sur aucun maillon.

On peut donc définir le type liste ainsi : 


          // Fichier list.h
          #ifndef _LIST_H
          #define _LIST_H

          // Définition du type maillon
          typedef struct _link {
            double val;          /* un élément de la liste*/
            struct _link * next; /* un pointeur sur le maillon suivant de la liste */
          } link_t;

          // Définition du type liste :
          // une variable liste est un simple pointeur - sur - maillon
          typedef link_t * list_t;

          #endif

On retiendra, de façon un condensée : 


            // Fichier list.h
            #ifndef _LIST_H
            #define _LIST_H
            // définition des types maillon link_t et liste list_t
            typedef struct _link {
              double val;          /* un élément de la liste*/
              struct _link * next; /* un pointeur sur le maillon suivant de la liste */
            } link_t, * list_t;
            #endif

Comme pour les variables classiques de type pointeur, déclarer list_t l; définit une variable qui contient une adresse.

Cela ne réserve pas la mémoire pour la structure pointée, en l'occurence le maillon, qui doit devra donc être allouée dynamiquement.

4. Création d'une liste vide et prédicat liste vide

Une liste chainée dynamique vide est simplement repérée par un pointeur NULL. Nos fonctions list_new() list_is_empty() sont donc très simples : 


              // Fichier list.c
              #include <stdlib.h>
              #include "list.h"

              // retourne une liste vide
              list_t list_new() {
                return NULL;
              }

              // predicat : retourne VRAI si la liste l est vide
              int list_is_empty( list_t l ) {
                return NULL == l;
              }

Et voici un programme de test de ces 2 premières fonctions : 


            // Fichier test_list.c
            #include <stdlib.h>
            #include <stdio.h>
            #include "list.h"

            int main() {
              list_t l;           // une variable liste, pas encore initialisée
              l = list_new();  // bah... on initialise la liste à "vide" (le pointeur l vaut NULL)

              if( list_is_empty(l) ) {
                printf("La liste est vide !\n");
              }
              // Rq : le prédicat list_is_empty(l) retourne une valeur booléenne...
              // ... c'est à dire précisément ce qu'attend l'instruction conditionnelle if( ... ).
              // Il serait donc absurde d'écrire :
              //    if( list_is_empty(l) == 1)
              // Et on écrit :
              //    if( list_is_empty(l) ) <=> "si la valeur booléenne retournée par la fonction est VRAI" ...


            }
            // ce programme affiche, bien sur "La liste est vide".

5. Parcours itératif d'une liste

En toute logique, il faudrait maintenant écrire les fonctions d'ajout ou de suppression d'un élément en tête de liste, list_add_first() et list_del_first(). Mais ces fonctions sont un peu complexes. Dans un but pédagogique, nous supposerons qu'elle existent et nous intéresserons d'abord aux parcours de liste, plus simples.

Parcourir une liste, c'est visiter tous ses maillons pour faire quelque chose, par exemple :

  • Afficher la valeur stockée dans chaque maillon (un double dans notre cas) ;
  • Compter le nombre d'éléments ;
  • Compter le nombre de maillon dont les éléments valent une certaine valeur ;
  • etc.

Le parcours d'une liste est bien sûr séquentiel, en partant de la tête de la liste.

Tous les fonctions de parcours se ressemblent. Intéressons-nous à la fonction d'affichage de tous les maillons.

5.1 Elaboration de la fonction d'affichage void list_print( list_t l )

Pour réfléchir, on suppose qu'il existe une liste contenant déjà quelques éléments, que l'on veut afficher. Par exemple :

Pour afficher cette liste, dans la fonction void list_print( list_t l), il va nous faloir :

  • Une boucle pour parcourir la liste, jusqu'à ce qu'on arrive à la fin ;
  • Et donc une "variable de boucle" qui, à chaque tour de boucle, permet de manipuler le maillon courant. Puisque les maillons sont connus par leur adresse dans le cas des listes chaînées dynamiques, cette variable de boucle sera un pointeur - sur - maillon.

Avant le premier passage dans la boucle, la variable de boucle doit pointer le premier maillon.

A chaque tour de boucle :

  • Il faut afficher la valeur du maillon courant ;
  • Il faut passer au maillon suivant, en faisant pointer notre variable de boucle sur le maillon suivant.

Bien sûr, le corps de boucle ne doit être exécuté que tant qu'il y a un maillon.

Après avoir beaucoup réfléchi, mettons que vous proposiez le code du prochain encart pour votre fonction list_print(). Vous en êtes plutôt content, mais comment faire pour vous assurer qu'il est correct ? Il vous faut tracer cet algorithme.

Tracer une fonction, c'est suivre pas à pas son exécution. Pour cela :

  • On considère un état particulier pour les paramètres de la fonction ;
  • On se munit d'un papier et d'un stylo ;
  • A chaque étape de l'algorithme, on dessine l'état de la mémoire et on note les valeurs des variables.

Pour vous assurer que votre fonction est correcte, il faut faire cela sur plusieurs cas :

  • Un "cas général" usuel ;
  • ET un ou plusieurs "cas particuliers", pour vérifier que l'algorithme est bien robuste à ces cas.

Dans le cas des listes (et plus tard des autres types abstraits), pensez à toujours considérer les quelques cas suivants :

  • le cas général où la liste contient 2 ou 3 éléments quelconques, par exemple 8. et 9. ;
  • le cas particulier où la liste est vide ;
  • le cas particulier où la liste ne contient qu'un seul élément.

Traçons, donc, notre fonction void list_print( ) dans un "cas général" et plusieurs "cas particuliers".

Trace de la fonction list_print dans le cas général
d'une liste contenant 2 éléments 

                // dans le fichier list.c
                ...
                void list_print( list_t l ) {
                  link_t * p ;
                  p = l;
                  while ( NULL != p ) {
                    printf(" %lf ", p->val);
                    p  = p->next;
                  }
                }


                // dans le fichier main.c
                ...
                int main() {
                  list_t mylist = list_new();
                  mylist = list_add_first( 9.0, mylist ); // on suppose que
                  mylist = list_add_first( 8.0, mylist ); // cette fonction existe

                  list_print(mylist);
                }

Ligne 17 et 18 du main, on ajoute en tête 9.0 puis 8.0

A ligne 19, la liste contient
( 8.0 9.0 ).

Notez que les éléments sont dans l'ordre inverse de l'ajout.

C'est normal, puisque list_add_first() ajoute le nouvel élément en tête de liste (au début).

Appel, dans le main(), de la fonction list_print() sur la liste ( 8.0 9.0 )

Voici une représentation de l'état de la mémoire :

Exécution de la fonction.

Création de la variable paramètre l qui est initialisée avec la valeur passée à la fonction, c'est à dire la valeur de la variable mylist du main().

l vaut donc l'adresse 0x1600. Autrement dit, l pointe le premier maillon de la liste ; c'est bien ce qu'on veut !

Création de la variable locale p de la fonction list_print(). p n'est pas encore initialisée (aléatoire).

Initialisation de p avec la tête de la liste, soit 0x1600

p regarde le premier maillon

p est-il en fin de liste ? Si oui, on arrête la boucle.

Dans notre cas, p ne vaut pas NULL. On rentre donc dans le corps de boucle.

On affiche p->val, c'est à dire l'élément stocké dans le premier maillon pointé par p.

Cette ligne affiche donc 8.0 dans le terminal. Ce qui est bien la valeur du premier maillon de la liste. Bravo !

Passage au maillon suivant.

Avant l'exécution de cette ligne, l'adresse du maillon suivant est stockée dans p->next :

Après l'exécution de cette ligne, p va donc contenir donc l'adresse du 2ième maillon.

Voici l'état de toute notre mémoire après cette étape :

On a donc bien avancé d'un maillon !

Retour au test de sortie de boucle.

p est-il en fin de liste ? Si oui, on arrête

Dans notre cas, on continue !

Affichage de l'élément du maillon pointé par p, c'est à dire p->val.

Cette ligne affiche donc 9.0 dans le terminal. Ce qui est bien la valeur du 2ième maillon de la liste. Bravo !

Passage au maillon suivant.

Avant l'exécution de cette ligne, l'adresse du maillon suivant est stockée dans p->next :

Mais p pointe le dernier maillon. Donc p->next vaut NULL.

Cette ligne affecte donc NULL à p :

Et voici l'état de toutes notre mémoire après cette étape :

Retour au test de sortie de boucle.

Comme p vaut NULL, la boucle s'arrête.

Fin de la fonction. Destruction des variables locales p et l et retour au main().

Globalemenent, notre code a affiché : 

8.0 9.0

C'est tout à fait ce qu'on voulait. Bravo !

Trace de la fonction list_print dans le cas particulier "liste vide" 

                // dans le fichier list.c
                ...
                void list_print( list_t l ) {
                  link_t * p ;
                  p = l;
                  while ( NULL != p ) {
                    printf(" %lf ", p->val);
                    p  = p->next;
                  }
                }


                // dans le fichier main.c
                ...
                int main() {
                  list_t mylist = list_new(); // une liste vide
                  list_print(mylist);
                  ...
                }

"La liste est vide"
<=>
"la variable mylist du main vaut NULL"".

Exécution de la fonction.

Le paramètre l vaut NULL.

p est donc également initialisé à NULL.

Test de sortie de boucle.

Comme p vaut NULL, on ne rentre pas dans la boucle.

Fin de la fonction. Destruction des variables locales p et l et retour au main().

Notre fonction n'a rien affiché dans le Terminal. Pour une liste vide, c'est une bonne nouvelle.

Bravo !

Pour vous entrainer, tracer la fonction dans le cas où la liste n'a qu'un unique élément et vérifiez que son comportement est correct.

En traçant notre fonction, on s'est donc assuré qu'elle est correcte dans le "cas général" et dans les cas particuliers "liste vide" et "liste à un élément".

Toutefois, on peut améliorer un peu, car :

  • Dans le cas où la liste n'est pas vide, on a bien affiché les éléments, mais on a pas terminé la ligne avec un retour chariot. C'est souhaitable, pour 'nettoyer' le terminal avant un éventuel futur printf.
  • Et dans le cas où la liste est vide, il serait pertinent de le signaler à l'utilisateur.

5.2 Version finale de la fonction void list_print( list_t l )

In fine on retiendra la version suivante pour la fonction list_print() : 


              /**
              * Affiche les éléments de la liste - Version finale
              */
              void list_print( list_t l ) {
                link_t * p = l;

                // traitement du cas particulier "liste vide"
                if(list_is_empty(p)) {
                  printf("La liste est vide\n");
                  return ; // plus rien à faire : on arrête la fonction
                }

                // cas général
                while ( NULL != p ) {       // "tant que p pointe un maillon"
                  printf(" %lf ;", p->val); // on affiche la valeur stockée dans le maillon
                  p  = p->next;             // on affecte à p l'adresse du maillon suivant
                }
                printf("\n"); // fin de la liste. Retour à la ligne pour terminer proprement
              }

Vous remarquerez qu'il ne faut pas allouer de mémoire pour le pointeur p dans les algorithme de parcours de liste !

Le maillon pointé existe déjà : il a évidemment été alloué lors de l'ajout d'un élément à la liste...

5.3 Autres parcours de liste

Pour vous entrainez, faite les QCM suivants :

Exemple de parcous de liste #1 On suppose qu'on dispose d'une implantation des listes chaînées dynamiques et on considère code suivant : 

          #include "list.h"

          int mystere1(list_t l) {
            link_t * p = l;
            int n = 0;
            while ( NULL != p ) {
              n ++ ;
              p  = p->next;
            }
            return n;
          }

          int main() {
            list_t mylist = list_new();
            int tmp;
            mylist = list_add_first( 9.0, mylist );
            mylist = list_add_first( 8.0, mylist );
            tmp = mystere1(mylist);
            printf("tmp vaut %d\n", tmp);
            ...
          }
Que fait ce code ? Erreur à la compilation Non, le code est syntaxiquement correct A l'exécution, il y a une erreur. Le code affiche tmp vaut 2 L'affichage est imprévisible Pour comprendre : un papier, un crayon, et tracez l'algorithme ! Exemple de parcous de liste #2 On suppose qu'on dispose d'une implantation des listes chaînées dynamiques et on considère code suivant : 

            #include "list.h"

            double mystere2(list_t l) {
              link_t * p = l;
              double x ;
              while ( NULL != p ) {
                if(p->val != 0.) {
                  x = x * val ;
                }
                p  = p->next;
              }
              return x;
            }

            int main() {
              list_t mylist = list_new();
              double tmp;
              mylist = list_add_first( 3.0, mylist );
              mylist = list_add_first( 0.0, mylist );
              mylist = list_add_first( 2.0, mylist );
              tmp = mystere2(mylist);
              printf("tmp vaut %lf\n", tmp);
            }
Que fait le code ? Erreur à la compilation Non, le code est syntaxiquement correct A l'exécution, il y a une erreur. L'affichage est imprévisible ("aléatoire") Le code affiche tmp vaut 6 Le code affiche tmp vaut 0

Vous l'aurez sans doute compris, la fonction est censée retourner le produit de tous les éléments non nuls de la liste.

Mais... n'y aurait-il pas une variable locale non initialisée dans la fonction, dont la valeur est donc aléatorie à la création ?

Rationnel : pensez à initialiser vos variables en C ! Notamment lorsqu'il s'agit d'un accumulateur !

6. En conclusion

Cette fiche a progressivement mis en place la structure de donnée "liste chaînée dynamique" : la définition des types C supportant cete structure de donnée, puis, supposant qu'on dispose d'une liste déjà créée avec quelques maillons, les algorithmes de parcours de liste.

La fiche suivante construit pas à pas les fonctions d'ajout en tête de liste puis de suppression en tête de liste.