1. Rappels de la fiche précédente

Comme dans la fiche précédente, on s'intéresse à une liste chaînée dynamique contenant des éléments de type double, dont voici une représentation après l'ajout de 2 éléments :

Une liste chaînée dynamique contenant 2 éléments, donc avec 2 maillons.

Le type C list_t introduit dans la fiche précédente est donc défini ainsi :

            // 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
          

On connait déjà le code des trois fonctions suivantes, que nous avons construites dans la fiche précédente :

            // 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;
            }

            // 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
            }
          

On construit maintenant les fonctions d'ajout en tête et de suppression en tête de liste.

2. Ajout en tête d'un élément

Maintenant qu'on sait parcourir une liste, voyons comment ajouter un nouvel élément en tête de la liste. On rappelle que le contrat et le prototype de la fonction à écrire est :

          // Ajoute l'élément e en tête de la liste l et retourne la nouvelle liste
          list_t list_add_first(element_t e, list_t l);
        

2.1 Principe de l'ajout en tête d'une liste chaînée dynamique

Pour réfléchir, on suppose qu'on a une liste l contenant déjà un maillon, qui contient l'élement ( 9.0 ) :

La liste initiale ( 9.0 )

Pour ajouter l'élement 8.0 en tête de la liste contenant 9.0, il faut :

2.2 Vers la fonction d'ajout en tête list_t list_add_first( element_t e, list_t l )

Dans cette section, c'est vous qui faites le cours !

Vos profs préférés ont préparé chacun une version de la fonction list_t list_add_first( element_t e, list_t l ), qu'ils croient en situation de révolutionner le Monde des Listes Chaînées.

Le(s)quel(s) de vos profs devrai(en)t retourner à l'école ?

Quelle est la bonne version (si il y en a une)?

A vous de jouer !

            // Dans le fichier list.c
            list_t list_add_first(double val, list_t l) {
              list_t newPtr ;    // On link_t * newPtr, puisque le type liste est défini comme "pointeur sur maillon"
              newPtr->val = val; // On stocke la valeur dans le maillon
              newPtr->suiv = l;  // On pointe sur l'ancien premier maillon
              return newPtr;     // On retourne l'adresse du nouveau maillon.
                                 // newPtr est bien de type "adresse de maillon" : tout va bien !
            }
            // Dans le fichier test.c
            int main() {
              list_t mylist = list_new();
              mylist = list_add_first(9.0, mylist);
              mylist = list_add_first(8.0, mylist);
              list_print(maliste);
            }
            

              // Dans le fichier list.c
              list_t list_add_first(double val, list_t l) {
                link_t m ;    // le nouveau maillon.
                              // Notez bien l'usage de link_t :
                              // cette fois ci, m n'est pas un pointeur, mais bien une structure maillon
                m.val = val;  // on stocke la valeur dans le maillon
                m.suiv = l;   // on pointe sur l'ancien premier maillon
                return &m;    // on retourne l'adresse du nouveau maillon.
                              // &m est bien de type "adresse de maillon",
                              // comme le type de retour de la fonction. Tout va bien... apparemment...
              }

              // Dans le fichier test.c
              int main() {
                list_t mylist;
                mylist = list_new();
                mylist = list_add_first(9.0, mylist);
                mylist = list_add_first(8.0, mylist);
                list_print(maliste);
              }
            

Des deux QCM précédents, on retiendra (outre le fait que vos profs devraient retourner à l'école... ) :

              // Dans le fichier list.c
              list_t list_add_first_v3(double val, list_t l) {
                list_t p;     // pour pointer le nouveau maillon
                // on alloue dyamiquement le nouveau maillon
                p = calloc(1,sizeof(*p));
                if (p==NULL) {
                  // une allocation dynamique peut échouer : on gère ce cas d'erreur !
                  printf("Allocation de mémoire impossible. Aborts.\n");
                  exit(1);
                }
                p->val = val; // on stocke la valeur dans le maillon
                p->suiv = l;  // le maillon suivant le nouveau est l'ancien premier maillon : on pointe dessus
                return p;     // on retourne l'adresse du nouveau maillon alloué dynamiquement
              }

              // Dans le fichier test.c
              int main() {
                list_t mylist;
                mylist = list_new();
                list_add_first_v3(9.0, mylist);
                list_add_first_v3(8.0, mylist);
                list_print(maliste);
              }
            

mylist = list_add_first(9.0, mylist); 

Du QCM précédent, on retiendra (outre le fait que Michel doit aussi retourner en cours... ) :

2.3 Version finale de la fonction list_t list_add_first( double e, list_t l )

Vous devriez avoir compris les points clés permettant d'écrire la fonction list_t list_add_first( double e, list_t l ). En voici la version finale

Liste dynamique : version finale de la foncton d'ajout en tête

              // dans le fichier list.c
              list_t list_add_first( double val, list_t l ) {
                list_t p;

                p = calloc( 1, sizeof( *p ) );
                if ( NULL == p ) {
                  return l;
                  // En cas d'echec de calloc(),
                  // plutôt que de sortir violemment du programme avec exit()
                  // on décide de retourner la liste non modifiée.
                  // Cela permet à la fonction appelante de tester ce cas d'erreur.
                }

                p->val  = val;
                p->next = l;

                return p;
              }

              // dans le fichier test.c
              int main() {
                  list_t maliste;
                  maliste = list_new();
                  maliste = list_add_first(9.0,maliste);
                  maliste = list_add_first(8.0,maliste);
                }
              

Appel de la fonction pour ajouter le second élément.

Déclaration d'un pointeur p, pour le nouveau maillon :

• Allouer dynamiquement un nouveau maillon, pointé par p ;
• Vérifier que l'allocation dynamique s'est bien passée ;
• Mettre 8.0 dans le nouveau maillon.

Le pointeur next de p doit indiquer l'ancienne tête de liste

La tête de la nouvelle liste le nouveau maillon, pointé par p.

On retourne cette nouvelle liste, repérée par p.

Retour au main.

Penser à mettre à a jour la variable liste (ici maliste) pour qu'elle pointe le nouveau maillon !

Il vous appartient de bien comprendre le code de cette fonction, de vous assurer qu'elle se comporte bien dans tous les cas (tracer l'algorithme dans le cas général, le cas liste à 1 élément et le cas liste vide) et de le retenir.

3. Suppression de l'élément de tête

La suppression de l'élément de tête consiste simplement à enlever le premier maillon et retourner le reste de la liste. On rappelle que le contrat et le prototype de la fonction à écrire est :

          // Supprime le maillon en tête de liste et retourne la nouvelle liste
          // PRECONDITION : liste non vide
          list_t list_del_first(list_t l);
        

3.1. Entrainons-nous sur 2 exemples comportant des erreurs courantes

            list_t list_del_first( list_t l ) {
              if(NULL == l) {
                // cas liste vide : Erreur
                fprintf(stderr, "Erreur : liste vide\n");
                exit(EXIT_FAILURE);
              }
              return l->next; // il suffit de retourner l'adresse du maillon suivant, nouveau 1er maillon !
            }
          

            list_t list_del_first( list_t l ) {
              free( l );
              return l->next;
            }
          

3.2. Construisons la fonction list_t list_del_first( list_t l )

On considère une liste contenant 2 éléments ( 8.0 9.0 ) :

Pour supprimer le maillon situé en tête de liste, qui contient l'élément 8.0, il faut :

3.3. Version finale de la fonction list_t list_del_first( list_t l )

Voici le code final de la fonction de suppression en tête de liste :

Liste dynamique : version finale de la fonction de suppression en tête

                // dans le fichier list.c
                list_t list_del_first( list_t l ) {
                  list_t p;
                  // Vérification de la précondition "liste non vide", avec une assertion
                  assert ( ! list_is_empty( l ) ) ;

                  // cas général
                  p = l->next;
                  free( l );
                  return p;
                }

                // dans le fichier test.c
                int main() {
                    list_t maliste;
                    maliste = list_new();
                    maliste = list_add_first(9.0,maliste);
                    maliste = list_add_first(8.0,maliste);
                    maliste = list_del_first(maliste); // On supprime le maillon de tête
                    list_print(maliste);
                }
              

La liste contient 2 éléments ; on appelle la fonction de suppression en tête.

Si la liste est vide, on ne peut pas supprimer le maillon de tête bien sûr. En fait, il est absurde de "supprimer en tête" d'une liste vide. Le contrat de la fonction le précise bien, avec la précondition la liste ne doit pas être vide.

Puisqu'il s'agit d'une précondition, on préfère traiter ce cas particulier absurde avec un appel à assert(), plutôt qu'avec un if( liste vide) et un exit(EXIT_FAILURE); .

Si vous ne savez plus ce qu'est assert(), reportez vous à la fiche Notion de Type Abstrait de Données !

Notre liste n'est pas vide, donc on arrive ici.

On stocke le reste de la liste au moyen d'un pointeur p.

A cette étape, p vaut l'adresse du deuxième maillon ou NULL si on est en fin de liste.

Libération de la mémoire du premier maillon

Pour rappel, il ne faut plus jamais accéder l'adresse pointée par l après l'appel de free() ! Ca tombe bien, on ne le fait pas : on a pris garde mettre de côté l'adresse du 2ème maillon avant de supprimer le premier.

La tête de la nouvelle liste est l'ancien deuxième maillon, ou NULL si jamais la liste n'avait qu'un seul maillon.

On retourne donc l'adresse de la nouvelle tête de liste, c'est à dire la valeur du pointeur p.

Fin de la fonction et retour au main.

Penser à récupérer la valeur de retour de la fonction pour changer l'adresse pointée par la variable liste !

Il vous appartient de bien comprendre le code de cette fonction, de vous assurer qu'elle se comporte bien dans tous les cas (tracer l'algorithme dans le cas général, le cas liste à 1 élément et le cas liste vide) et de la retenir.

4. En conclusion

Cette fiche et la précédente ont 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, et les principales fonctions réalisant les principales opérations sur les listes.

Nous avons ce faisant expliqué comment travailler pour y parvenir.