2. Algorithmique 4 - Listes

2.1. Qu'est-ce qu'une liste ?

Une liste pour laquelle tout nouvel élément est ajouté en tête et tout élément est retiré en fin est appelée une file (queue en anglais), c'est une structure FIFO (First In, First Out).

Une liste pour laquelle tout nouvel élément est ajouté en queue et tout élément est retiré également en queue est appelée une pile (stack en anglais), c'est une structure LIFO (Last In, First Out).

2.2. Implantation d'une liste

On peut donner plusieurs implantation des listes :

• sous forme de tableau extensible
• sous forme de liste simplement chaînée
• sous forme de liste doublement chaînée
• sous forme de liste doublement chaînée circulaire

Une liste possède plusieurs avantages :

• on peut retirer ou supprimer des élements n'importe où dans la liste
• elle n'est pas de taille fixe

Elle possède également des inconvénients :

• pour les listes chaînées : accéder au $n$-ième élément requiert de parcourir $n$ éléments (maillons)
• pour les listes implantées par un tableau, insérer un nouvel élément requiert de déplacer d'un rang vers la droite tous les éléments qui suivent

2.3. Cas des listes simplement chaînées

On va utiliser la structure de données suivante pour implanter une liste simplement chaînée :

Une liste peut se réduire à l'utilisation d'éléments (maillons) chaînés entre eux, mais il est généralement préférable de définir un autre type liste qui stocke un pointeur sur le premier élément et le nombre d'éléments de la liste.

2.4. Variations sur les listes

Voici six exemples de l'implantation des listes sur le même thème issu du cours.

2.4.1. Implantation à base de pointeurs de pointeurs

• il s'agit d'une implantation itérative utilisant des pointeurs et la synatxe du C/C++. On passe en paramètre de chaque sous-programme un pointeur sur la liste pour gérer les modifications (ajout, suppression) :
  
  Afficher le code    ens/l1/algo4/v0_le_itr.cpp

  1. // ==================================================================
  2. //      Auteur : Jean-Michel RICHER
  3. //      Email  : jean-michel.richer@univ-angers.fr
  4. // Institution : Université d'Angers, Faculté des Sciences
  5. // Département : Informatique
  6. // ==================================================================
  7. //
  8. // Objectif : Implantation itérative de liste simplement chaînée
  9. //
  10. // Spécificité : On passe en paramètre des sous-programmes qui
  11. // agissent sur les listes, un pointeur sur la liste à modifier
  12. //
  13. // Lors de l'appel de ces sous-programmes il faut donc passer
  14. // l'adresse de la liste
  15. //
  16. // L'implantation donnée ici utilise la syntaxe du langage C
  17. // ==================================================================
  18.  
  19. #include <iostream>
  20. #include <sstream>
  21. using namespace std;
  22.  
  23. // ==================================================================
  24. // structures communes
  25. // ==================================================================
  26.  
  27. // définition du type de la valeur stockée par un élément de la liste
  28. using type_valeur = int;
  29.  
  30. // définition d'un élément (maillon) de la liste
  31. struct type_element_de_liste
  32. {
  33.     // pointeur sur l'élément suivant
  34.     type_element_de_liste *suivant;
  35.     // valeur stockée par cet élément
  36.     type_valeur valeur;
  37. };
  38.  
  39. // définition d'une liste comme un pointeur sur un élément
  40. using liste = type_element_de_liste *;
  41.  
  42. // définition de la liste vide
  43. const liste liste_vide = nullptr;
  44.  
  45. // ==================================================================
  46. // Sous-programmes qui agissent sur une liste
  47. //
  48. // Implantation itérative
  49. // ==================================================================
  50.  
  51. // Initialisation d'une liste
  52. void liste_initialiser(liste *l)
  53. {
  54.     *l = liste_vide;
  55. }
  56.  
  57. // Ajout en tete de la liste
  58. void liste_ajouter_en_tete(liste *l, int valeur)
  59. {
  60.  
  61.     type_element_de_liste *nouvel_element = new type_element_de_liste;
  62.     nouvel_element->suivant = *l;
  63.     nouvel_element->valeur = valeur;
  64.  
  65.     *l = nouvel_element;
  66. }
  67.  
  68. // Ajout en queue de la liste
  69. void liste_ajouter_en_queue(liste *l, int valeur)
  70. {
  71.  
  72.     type_element_de_liste *nouvel_element = new type_element_de_liste;
  73.     nouvel_element->suivant = liste_vide;
  74.     nouvel_element->valeur = valeur;
  75.  
  76.     if (*l == liste_vide)
  77.     {
  78.         *l = nouvel_element;
  79.     }
  80.     else
  81.     {
  82.         // rechercher le dernier élément
  83.         liste dernier = *l;
  84.         while (dernier->suivant != liste_vide)
  85.         {
  86.             dernier = dernier->suivant;
  87.         }
  88.  
  89.         dernier->suivant = nouvel_element;
  90.     }
  91. }
  92.  
  93. // créer une liste à partir de données stokées
  94. // dans une chaîne de caractères
  95. void liste_creer(liste *l, string data)
  96. {
  97.  
  98.     istringstream iss(data);
  99.     type_valeur valeur;
  100.  
  101.     while (iss >> valeur)
  102.     {
  103.         liste_ajouter_en_queue(l, valeur);
  104.     }
  105. }
  106.  
  107. // Vider une liste : supprimer tous ses éléments
  108. void liste_vider(liste *l)
  109. {
  110.  
  111.     liste courant = *l;
  112.     liste suivant;
  113.  
  114.     while (courant != liste_vide)
  115.     {
  116.         suivant = courant->suivant;
  117.         delete courant;
  118.         courant = suivant;
  119.     }
  120.  
  121.     *l = liste_vide;
  122. }
  123.  
  124. // Affichage de la liste
  125. void liste_afficher(liste *l)
  126. {
  127.  
  128.     liste courant = *l;
  129.     while (courant != liste_vide)
  130.     {
  131.         cout << courant->valeur << " ";
  132.         courant = courant->suivant;
  133.     }
  134.     cout << endl;
  135. }
  136.  
  137. // Tri de la liste sous forme de tri à bulle
  138. void liste_trier(liste *l)
  139. {
  140.  
  141.     liste courant1 = *l;
  142.     while (courant1 != liste_vide)
  143.     {
  144.         liste courant2 = courant1->suivant;
  145.         while (courant2 != liste_vide)
  146.         {
  147.             if (courant1->valeur > courant2->valeur)
  148.             {
  149.                 swap(courant1->valeur, courant2->valeur);
  150.             }
  151.             courant2 = courant2->suivant;
  152.         }
  153.         courant1 = courant1->suivant;
  154.     }
  155. }
  156.  
  157. void liste_supprimer_doublons(liste *l)
  158. {
  159.  
  160.     liste courant = *l;
  161.  
  162.     // on parcourt la liste initiale à la recherche d'un doublon
  163.     // pour chaque élément
  164.     while (courant != liste_vide)
  165.     {
  166.         liste doublon = courant->suivant;
  167.  
  168.         // parcours des éléments restants dans la liste
  169.         liste precedent_doublon = courant;
  170.         while (doublon != liste_vide)
  171.         {
  172.  
  173.             // a t-on trouvé un doublon ?
  174.             if (courant->valeur == doublon->valeur)
  175.             {
  176.                 // si oui, supprimer le doublon
  177.                 liste suivant_doublon = doublon->suivant;
  178.                 delete doublon;
  179.                 precedent_doublon->suivant = suivant_doublon;
  180.  
  181.                 doublon = suivant_doublon;
  182.             }
  183.             else
  184.             {
  185.                 // sinon, passer à l'élément suivant
  186.                 precedent_doublon = doublon;
  187.                 doublon = doublon->suivant;
  188.             }
  189.         }
  190.  
  191.         courant = courant->suivant;
  192.     }
  193. }
  194.  
  195. // ==================================================================
  196. // Programme principal
  197. // ==================================================================
  198. // On insère des élément dans la liste (en tête, puis en queue) et
  199. // on affiche le résultat : 11 4 3 2 1 5 6 7 8 9 10 -1
  200. // on tri ensuite la liste : -1 1 2 3 4 5 6 7 8 9 10 11
  201. // ==================================================================
  202.  
  203. int main()
  204. {
  205.     liste l;
  206.  
  207.     liste_initialiser(&l);
  208.  
  209.     for (int i = 1; i < 5; ++i)
  210.     {
  211.         liste_ajouter_en_tete(&l, i);
  212.     }
  213.  
  214.     for (int i = 5; i < 11; ++i)
  215.     {
  216.         liste_ajouter_en_queue(&l, i);
  217.     }
  218.  
  219.     liste_ajouter_en_tete(&l, 11);
  220.     liste_ajouter_en_queue(&l, -1);
  221.  
  222.     cout << "liste initiale = ";
  223.     liste_afficher(&l);
  224.  
  225.     liste_trier(&l);
  226.  
  227.     cout << "liste triée = ";
  228.     liste_afficher(&l);
  229.  
  230.     liste_vider(&l);
  231.  
  232.     liste_creer(&l, "1 2 1 2 2 3 2 1");
  233.  
  234.     cout << "liste avec doublons = ";
  235.     liste_afficher(&l);
  236.  
  237.     liste_supprimer_doublons(&l);
  238.  
  239.     cout << "liste sans doublons = ";
  240.     liste_afficher(&l);
  241.  
  242.     liste_vider(&l);
  243.  
  244.     return EXIT_SUCCESS;
  245. }
  246.  
• il s'agit de l'implantation récursive de la première version :
  
  Afficher le code    ens/l1/algo4/v0_le_rec.cpp

  1. // ==================================================================
  2. //      Auteur : Jean-Michel RICHER
  3. //      Email  : jean-michel.richer@univ-angers.fr
  4. // Institution : Université d'Angers, Faculté des Sciences
  5. // Département : Informatique
  6. // ==================================================================
  7. //
  8. // Objectif : Implantation récursive de liste simplement chaînée
  9. //
  10. // Spécificité : On passe en paramètre des sous-programmes qui
  11. // agissent sur les listes, un pointeur sur la liste à modifier
  12. //
  13. // Lors de l'appel de ces sous-programmes il faut donc passer
  14. // l'adresse de la liste
  15. //
  16. // L'implantation donnée ici utilise la syntaxe du langage C
  17. // ==================================================================
  18.  
  19. #include <iostream>
  20. using namespace std;
  21.  
  22. // ==================================================================
  23. // structures communes
  24. // ==================================================================
  25.  
  26. // définition du type de la valeur stockée par un élément de la liste
  27. using type_valeur = int;
  28.  
  29. // définition d'un élément (maillon) de la liste
  30. struct type_element_de_liste
  31. {
  32.     // pointeur sur l'élément suivant
  33.     type_element_de_liste *suivant;
  34.     // valeur stockée par cet élément
  35.     type_valeur valeur;
  36. };
  37.  
  38. // définition d'une liste comme un pointeur sur un élément
  39. using liste = type_element_de_liste *;
  40.  
  41. // définition de la liste vide
  42. const liste liste_vide = nullptr;
  43.  
  44. // ==================================================================
  45. // Sous-programmes qui agissent sur une liste
  46. //
  47. // Implantation récursive
  48. // ==================================================================
  49.  
  50. // Initialisation d'une liste
  51. void liste_initialiser(liste *l)
  52. {
  53.     *l = liste_vide;
  54. }
  55.  
  56. // Ajout en tete de la liste
  57. void liste_ajouter_en_tete(liste *l, int valeur)
  58. {
  59.  
  60.     type_element_de_liste *nouvel_element = new type_element_de_liste;
  61.     nouvel_element->suivant = *l;
  62.     nouvel_element->valeur = valeur;
  63.  
  64.     *l = nouvel_element;
  65. }
  66.  
  67. // Ajout en queue de la liste
  68. void liste_ajouter_en_queue(liste *l, int valeur)
  69. {
  70.  
  71.     if (*l == liste_vide)
  72.     {
  73.         type_element_de_liste *nouvel_element = new type_element_de_liste;
  74.         nouvel_element->suivant = liste_vide;
  75.         nouvel_element->valeur = valeur;
  76.         *l = nouvel_element;
  77.     }
  78.     else
  79.     {
  80.         liste_ajouter_en_queue(&(*l)->suivant, valeur);
  81.     }
  82. }
  83.  
  84. // Affichage de la liste
  85. void liste_afficher(liste *l)
  86. {
  87.     if (*l != liste_vide)
  88.     {
  89.  
  90.         cout << (*l)->valeur << " ";
  91.         liste_afficher(&(*l)->suivant);
  92.     }
  93.     else
  94.     {
  95.         cout << endl;
  96.     }
  97. }
  98.  
  99. // ==================================================================
  100. // Programme principal
  101. // ==================================================================
  102. // On insère des élément dans la liste (en tête, puis en queue) et
  103. // on affiche le résultat : 4 3 2 1 5 6 7 8 9 10
  104. // ==================================================================
  105.  
  106. int main()
  107. {
  108.     liste l;
  109.  
  110.     liste_initialiser(&l);
  111.  
  112.     for (int i = 1; i < 5; ++i)
  113.     {
  114.         liste_ajouter_en_tete(&l, i);
  115.     }
  116.  
  117.     for (int i = 5; i < 11; ++i)
  118.     {
  119.         liste_ajouter_en_queue(&l, i);
  120.     }
  121.  
  122.     liste_afficher(&l);
  123.  
  124.     return EXIT_SUCCESS;
  125. }
  126.  
• amélioration de la première version en utilisant un type 'pointeur_sur_liste' et des macro-instructions afin de rendre le code plus lisible :
  
  Afficher le code    ens/l1/algo4/v1_le_itr.cpp

  1. // ==================================================================
  2. //      Auteur : Jean-Michel RICHER
  3. //      Email  : jean-michel.richer@univ-angers.fr
  4. // Institution : Université d'Angers, Faculté des Sciences
  5. // Département : Informatique
  6. // ==================================================================
  7. //
  8. // Objectif : Implantation itérative de liste simplement chaînée
  9. //
  10. // Spécificité : On passe en paramètre des sous-programmes qui
  11. // agissent sur les listes, un pointeur sur la liste à modifier
  12. //
  13. // Lors de l'appel de ces sous-programmes il faut donc passer
  14. // l'adresse de la liste
  15. //
  16. // L'implantation donnée ici utilise des macro-instructions afin
  17. // de rendre la lecture du code plus aisée. On utilise également
  18. // le type 'pointeur_sur_liste' plutôt que 'liste *' afin de
  19. // spécifier le passage en paramètre de la liste dans les sous-
  20. // programmes de manipulation
  21. // ==================================================================
  22.  
  23. #include <iostream>
  24. #include <sstream>
  25. using namespace std;
  26.  
  27. // ==================================================================
  28. // structures communes
  29. // ==================================================================
  30.  
  31. // définition du type de la valeur stockée par un élément de la liste
  32. using type_valeur = int;
  33.  
  34. // définition d'un élément (maillon) de la liste
  35. struct type_element_de_liste
  36. {
  37.     // pointeur sur l'élément suivant
  38.     type_element_de_liste *suivant;
  39.     // valeur stockée par cet élément
  40.     type_valeur valeur;
  41. };
  42.  
  43. // définition d'une liste comme un pointeur sur un élément
  44. using liste = type_element_de_liste *;
  45.  
  46. // définition de la liste vide
  47. const liste liste_vide = nullptr;
  48.  
  49. // ==================================================================
  50. // structures spécifiques à cette implantation
  51. // ==================================================================
  52.  
  53. // l'accès à la tête de la liste se fait par pointeur
  54. using pointeur_sur_liste = liste *;
  55.  
  56. // définition de macro-instructions qui permettent de rendre le
  57. // code plus lisible
  58.  
  59. // contenu du pointeur
  60. #define le_contenu_du_pointeur(l) (*l)
  61.  
  62. // élément suivant
  63. #define le_suivant_de(l) l->suivant
  64.  
  65. // valeur d'un élément
  66. #define la_valeur_de(l) l->valeur
  67.  
  68. // ==================================================================
  69. // Sous-programmes qui agissent sur une liste
  70. // ==================================================================
  71.  
  72. // Initialisation d'une liste
  73. void liste_initialiser(pointeur_sur_liste l)
  74. {
  75.     le_contenu_du_pointeur(l) = liste_vide;
  76. }
  77.  
  78. // Ajout en tete de la liste
  79. void liste_ajouter_en_tete(pointeur_sur_liste l, int valeur)
  80. {
  81.  
  82.     type_element_de_liste *nouvel_element = new type_element_de_liste;
  83.     le_suivant_de(nouvel_element) = le_contenu_du_pointeur(l);
  84.     la_valeur_de(nouvel_element) = valeur;
  85.  
  86.     le_contenu_du_pointeur(l) = nouvel_element;
  87. }
  88.  
  89. // Ajout en queue de la liste
  90. void liste_ajouter_en_queue(pointeur_sur_liste l, int valeur)
  91. {
  92.  
  93.     type_element_de_liste *nouvel_element = new type_element_de_liste;
  94.     le_suivant_de(nouvel_element) = liste_vide;
  95.     la_valeur_de(nouvel_element) = valeur;
  96.  
  97.     if (le_contenu_du_pointeur(l) == liste_vide)
  98.     {
  99.         le_contenu_du_pointeur(l) = nouvel_element;
  100.     }
  101.     else
  102.     {
  103.         // rechercher le dernier élément
  104.         liste dernier = le_contenu_du_pointeur(l);
  105.         while (le_suivant_de(dernier) != liste_vide)
  106.         {
  107.             dernier = le_suivant_de(dernier);
  108.         }
  109.  
  110.         le_suivant_de(dernier) = nouvel_element;
  111.     }
  112. }
  113.  
  114. // créer une liste à partir de données stokées
  115. // dans une chaîne de caractères
  116. void liste_creer(pointeur_sur_liste l, string data)
  117. {
  118.  
  119.     istringstream iss(data);
  120.     type_valeur valeur;
  121.  
  122.     while (iss >> valeur)
  123.     {
  124.         liste_ajouter_en_queue(l, valeur);
  125.     }
  126. }
  127.  
  128. // Vider une liste : supprimer tous ses éléments
  129. void liste_vider(pointeur_sur_liste l)
  130. {
  131.  
  132.     liste courant = le_contenu_du_pointeur(l);
  133.     liste suivant;
  134.  
  135.     while (courant != liste_vide)
  136.     {
  137.         suivant = le_suivant_de(courant);
  138.         delete courant;
  139.         courant = suivant;
  140.     }
  141.  
  142.     le_contenu_du_pointeur(l) = liste_vide;
  143. }
  144.  
  145. // Affichage de la liste
  146. void liste_afficher(pointeur_sur_liste l)
  147. {
  148.  
  149.     liste courant = le_contenu_du_pointeur(l);
  150.     while (courant != liste_vide)
  151.     {
  152.         cout << la_valeur_de(courant) << " ";
  153.         courant = le_suivant_de(courant);
  154.     }
  155.     cout << endl;
  156. }
  157.  
  158. // Tri de la liste sous forme de tri à bulle
  159. void liste_trier(pointeur_sur_liste l)
  160. {
  161.  
  162.     liste courant1 = le_contenu_du_pointeur(l);
  163.     while (courant1 != liste_vide)
  164.     {
  165.         liste courant2 = le_suivant_de(courant1);
  166.         while (courant2 != liste_vide)
  167.         {
  168.             if (la_valeur_de(courant1) > la_valeur_de(courant2))
  169.             {
  170.                 swap(la_valeur_de(courant1), la_valeur_de(courant2));
  171.             }
  172.             courant2 = le_suivant_de(courant2);
  173.         }
  174.         courant1 = le_suivant_de(courant1);
  175.     }
  176. }
  177.  
  178. void liste_supprimer_doublons(pointeur_sur_liste l)
  179. {
  180.  
  181.     liste courant = le_contenu_du_pointeur(l);
  182.  
  183.     // on parcourt la liste initiale à la recherche d'un doublon
  184.     // pour chaque élément
  185.     while (courant != liste_vide)
  186.     {
  187.         liste doublon = le_suivant_de(courant);
  188.  
  189.         // parcours des éléments restants dans la liste
  190.         liste precedent_doublon = courant;
  191.         while (doublon != liste_vide)
  192.         {
  193.  
  194.             // a t-on trouvé un doublon ?
  195.             if (la_valeur_de(courant) == la_valeur_de(doublon))
  196.             {
  197.                 // si oui, supprimer le doublon
  198.                 liste suivant_doublon = le_suivant_de(doublon);
  199.                 delete doublon;
  200.                 le_suivant_de(precedent_doublon) = suivant_doublon;
  201.  
  202.                 doublon = suivant_doublon;
  203.             }
  204.             else
  205.             {
  206.                 // sinon, passer à l'élément suivant
  207.                 precedent_doublon = doublon;
  208.                 doublon = le_suivant_de(doublon);
  209.             }
  210.         }
  211.  
  212.         courant = le_suivant_de(courant);
  213.     }
  214. }
  215.  
  216. // ==================================================================
  217. // Programme principal
  218. // ==================================================================
  219. // On insère des élément dans la liste (en tête, puis en queue) et
  220. // on affiche le résultat : 11 4 3 2 1 5 6 7 8 9 10 -1
  221. // on tri ensuite la liste : -1 1 2 3 4 5 6 7 8 9 10 11
  222. // ==================================================================
  223.  
  224. int main()
  225. {
  226.     liste l;
  227.  
  228.     liste_initialiser(&l);
  229.  
  230.     for (int i = 1; i < 5; ++i)
  231.     {
  232.         liste_ajouter_en_tete(&l, i);
  233.     }
  234.  
  235.     for (int i = 5; i < 11; ++i)
  236.     {
  237.         liste_ajouter_en_queue(&l, i);
  238.     }
  239.  
  240.     liste_ajouter_en_tete(&l, 11);
  241.     liste_ajouter_en_queue(&l, -1);
  242.  
  243.     cout << "liste initiale = ";
  244.     liste_afficher(&l);
  245.  
  246.     liste_trier(&l);
  247.  
  248.     cout << "liste triée = ";
  249.     liste_afficher(&l);
  250.  
  251.     liste_vider(&l);
  252.  
  253.     liste_creer(&l, "1 2 1 2 2 3 2 1");
  254.  
  255.     cout << "liste avec doublons = ";
  256.     liste_afficher(&l);
  257.  
  258.     liste_supprimer_doublons(&l);
  259.  
  260.     cout << "liste sans doublons = ";
  261.     liste_afficher(&l);
  262.  
  263.     liste_vider(&l);
  264.  
  265.     return EXIT_SUCCESS;
  266. }
  267.  
• amélioration de la version précédente mais en utilisant l'opérateur de référence :
  
  Afficher le code    ens/l1/algo4/v2_le_itr.cpp

  1. // ==================================================================
  2. //      Auteur : Jean-Michel RICHER
  3. //      Email  : jean-michel.richer@univ-angers.fr
  4. // Institution : Université d'Angers, Faculté des Sciences
  5. // Département : Informatique
  6. // ==================================================================
  7. //
  8. // Objectif : Implantation itérative de liste simplement chaînée
  9. //
  10. // Spécificité : On passe en paramètre des sous-programmes qui
  11. // agissent sur les listes, une référence sur la liste à modifier
  12. //
  13. // Lors de l'appel de ces sous-programmes il faut donc passer
  14. // la liste (et non pas son adresse)
  15. //
  16. // L'implantation donnée ici utilise des macro-instructions afin
  17. // de rendre la lecture du code plus aisée. On utilise également
  18. // le type 'reference_sur_liste' plutôt que 'liste&' afin de
  19. // spécifier le passage en paramètre de la liste dans les sous-
  20. // programmes de manipulation
  21. // ==================================================================
  22.  
  23. #include <iostream>
  24. #include <sstream>
  25. using namespace std;
  26.  
  27. // ==================================================================
  28. // structures communes
  29. // ==================================================================
  30.  
  31. // définition du type de la valeur stockée par un élément de la liste
  32. using type_valeur = int;
  33.  
  34. // définition d'un élément (maillon) de la liste
  35. struct type_element_de_liste
  36. {
  37.     // pointeur sur l'élément suivant
  38.     type_element_de_liste *suivant;
  39.     // valeur stockée par cet élément
  40.     type_valeur valeur;
  41. };
  42.  
  43. // définition d'une liste comme un pointeur sur un élément
  44. using liste = type_element_de_liste *;
  45.  
  46. // définition de la liste vide
  47. const liste liste_vide = nullptr;
  48.  
  49. // ==================================================================
  50. // structures spécifiques à cette implantation
  51. // ==================================================================
  52.  
  53. // l'accès à la tête de la liste se fait par pointeur
  54. using reference_sur_liste = liste &;
  55.  
  56. // définition de macro-instructions qui permettent de rendre le
  57. // code plus lisible
  58.  
  59. // contenu du pointeur
  60. #define le_contenu_de(l) l
  61.  
  62. // élément suivant
  63. #define le_suivant_de(l) l->suivant
  64.  
  65. // valeur d'un élément
  66. #define la_valeur_de(l) l->valeur
  67.  
  68. // ==================================================================
  69. // Sous-programmes qui agissent sur une liste
  70. // ==================================================================
  71.  
  72. // Initialisation d'une liste
  73. void liste_initialiser(reference_sur_liste l)
  74. {
  75.     le_contenu_de(l) = liste_vide;
  76. }
  77.  
  78. // Ajout en tete de la liste
  79. void liste_ajouter_en_tete(reference_sur_liste l, int valeur)
  80. {
  81.     type_element_de_liste *nouvel_element = new type_element_de_liste;
  82.     le_suivant_de(nouvel_element) = le_contenu_de(l);
  83.     la_valeur_de(nouvel_element) = valeur;
  84.  
  85.     le_contenu_de(l) = nouvel_element;
  86. }
  87.  
  88. // Ajout en queue de la liste
  89. void liste_ajouter_en_queue(reference_sur_liste l, int valeur)
  90. {
  91.  
  92.     type_element_de_liste *nouvel_element = new type_element_de_liste;
  93.     le_suivant_de(nouvel_element) = liste_vide;
  94.     la_valeur_de(nouvel_element) = valeur;
  95.  
  96.     if (le_contenu_de(l) == liste_vide)
  97.     {
  98.         le_contenu_de(l) = nouvel_element;
  99.     }
  100.     else
  101.     {
  102.         // rechercher le dernier élément
  103.         liste dernier = le_contenu_de(l);
  104.         while (le_suivant_de(dernier) != liste_vide)
  105.         {
  106.             dernier = le_suivant_de(dernier);
  107.         }
  108.  
  109.         le_suivant_de(dernier) = nouvel_element;
  110.     }
  111. }
  112.  
  113. // créer une liste à partir de données stokées
  114. // dans une chaîne de caractères
  115. void liste_creer(reference_sur_liste l, string data)
  116. {
  117.  
  118.     istringstream iss(data);
  119.     type_valeur valeur;
  120.  
  121.     while (iss >> valeur)
  122.     {
  123.         liste_ajouter_en_queue(l, valeur);
  124.     }
  125. }
  126.  
  127. // Vider une liste : supprimer tous ses éléments
  128. void liste_vider(reference_sur_liste l)
  129. {
  130.  
  131.     liste courant = le_contenu_de(l);
  132.     liste suivant;
  133.  
  134.     while (courant != liste_vide)
  135.     {
  136.         suivant = le_suivant_de(courant);
  137.         delete courant;
  138.         courant = suivant;
  139.     }
  140.  
  141.     le_contenu_de(l) = liste_vide;
  142. }
  143.  
  144. // Affichage de la liste
  145. void liste_afficher(reference_sur_liste l)
  146. {
  147.  
  148.     liste courant = le_contenu_de(l);
  149.     while (courant != liste_vide)
  150.     {
  151.         cout << la_valeur_de(courant) << " ";
  152.         courant = le_suivant_de(courant);
  153.     }
  154.     cout << endl;
  155. }
  156.  
  157. void liste_supprimer_doublons(reference_sur_liste l)
  158. {
  159.  
  160.     liste courant = le_contenu_de(l);
  161.  
  162.     // on parcourt la liste initiale à la recherche d'un doublon
  163.     // pour chaque élément
  164.     while (courant != liste_vide)
  165.     {
  166.         liste doublon = le_suivant_de(courant);
  167.  
  168.         // parcours des éléments restants dans la liste
  169.         liste precedent_doublon = courant;
  170.         while (doublon != liste_vide)
  171.         {
  172.  
  173.             // a t-on trouvé un doublon ?
  174.             if (la_valeur_de(courant) == la_valeur_de(doublon))
  175.             {
  176.                 // si oui, supprimer le doublon
  177.                 liste suivant_doublon = le_suivant_de(doublon);
  178.                 delete doublon;
  179.                 le_suivant_de(precedent_doublon) = suivant_doublon;
  180.  
  181.                 doublon = suivant_doublon;
  182.             }
  183.             else
  184.             {
  185.                 // sinon, passer à l'élément suivant
  186.                 precedent_doublon = doublon;
  187.                 doublon = le_suivant_de(doublon);
  188.             }
  189.         }
  190.  
  191.         courant = le_suivant_de(courant);
  192.     }
  193. }
  194.  
  195. // Tri de la liste sous forme de tri à bulle
  196. void liste_trier(reference_sur_liste l)
  197. {
  198.  
  199.     liste courant1 = le_contenu_de(l);
  200.     while (courant1 != liste_vide)
  201.     {
  202.         liste courant2 = le_suivant_de(courant1);
  203.         while (courant2 != liste_vide)
  204.         {
  205.             if (la_valeur_de(courant1) > la_valeur_de(courant2))
  206.             {
  207.                 swap(la_valeur_de(courant1), la_valeur_de(courant2));
  208.             }
  209.             courant2 = le_suivant_de(courant2);
  210.         }
  211.         courant1 = le_suivant_de(courant1);
  212.     }
  213. }
  214.  
  215. // ==================================================================
  216. // Programme principal
  217. // ==================================================================
  218. // On insère des élément dans la liste (en tête, puis en queue) et
  219. // on affiche le résultat : 11 4 3 2 1 5 6 7 8 9 10 -1
  220. // on tri ensuite la liste : -1 1 2 3 4 5 6 7 8 9 10 11
  221. // ==================================================================
  222.  
  223. int main()
  224. {
  225.     liste l;
  226.  
  227.     liste_initialiser(l);
  228.  
  229.     for (int i = 1; i < 5; ++i)
  230.     {
  231.         liste_ajouter_en_tete(l, i);
  232.     }
  233.  
  234.     for (int i = 5; i < 11; ++i)
  235.     {
  236.         liste_ajouter_en_queue(l, i);
  237.     }
  238.  
  239.     liste_ajouter_en_tete(l, 11);
  240.     liste_ajouter_en_queue(l, -1);
  241.  
  242.     cout << "liste initiale = ";
  243.     liste_afficher(l);
  244.  
  245.     liste_trier(l);
  246.  
  247.     cout << "liste triée = ";
  248.     liste_afficher(l);
  249.  
  250.     liste_vider(l);
  251.  
  252.     liste_creer(l, "1 2 1 2 2 3 2 1");
  253.  
  254.     cout << "liste avec doublons = ";
  255.     liste_afficher(l);
  256.  
  257.     liste_supprimer_doublons(l);
  258.  
  259.     cout << "liste sans doublons = ";
  260.     liste_afficher(l);
  261.  
  262.     liste_vider(l);
  263.  
  264.     return EXIT_SUCCESS;
  265. }
  266.  

2.4.2. Implantation à base de pointeurs

• amélioration de la première version mais qui n'utilise pas de pointeur de pointeur pour passer une liste en paramètre. On passe la liste en paramètre et si on la modifie à l'intérieur du sous-programme, on retourne la nouvelle tête de liste :
  
  Afficher le code    ens/l1/algo4/v3_le_itr.cpp

  1. // ==================================================================
  2. //      Auteur : Jean-Michel RICHER
  3. //      Email  : jean-michel.richer@univ-angers.fr
  4. // Institution : Université d'Angers, Faculté des Sciences
  5. // Département : Informatique
  6. // ==================================================================
  7. //
  8. // Objectif : Implantation itérative de liste simplement chaînée
  9. //
  10. // Spécificité : On passe en paramètre des sous-programmes qui
  11. // agissent sur les listes, la liste à modifier. Pour les sous-
  12. // programmes qui modifie la liste (comme l'ajout d'un élément)
  13. // on retourne la tête de la nouvelle liste modifiée.
  14. //
  15. // Lors de l'appel de ces sous-programmes il faut donc passer
  16. // la liste en paramètre mais éventuellement récupérer la liste
  17. // modifiée
  18. //
  19. // L'implantation donnée ici utilise des macro-instructions afin
  20. // de rendre la lecture du code plus aisée.
  21. // ==================================================================
  22. #include <iostream>
  23. #include <sstream>
  24. using namespace std;
  25.  
  26. // ==================================================================
  27. // structures communes
  28. // ==================================================================
  29.  
  30. // définition du type de la valeur stockée par un élément de la liste
  31. using type_valeur = int;
  32.  
  33. // définition d'un élément (maillon) de la liste
  34. struct type_element_de_liste
  35. {
  36.     // pointeur sur l'élément suivant
  37.     type_element_de_liste *suivant;
  38.     // valeur stockée par cet élément
  39.     type_valeur valeur;
  40. };
  41.  
  42. // définition d'une liste comme un pointeur sur un élément
  43. using liste = type_element_de_liste *;
  44.  
  45. // définition de la liste vide
  46. const liste liste_vide = nullptr;
  47.  
  48. // ==================================================================
  49. // structures spécifiques à cette implantation
  50. // ==================================================================
  51.  
  52. #define le_suivant_de(l) l->suivant
  53. #define la_valeur_de(l) l->valeur
  54.  
  55. // ==================================================================
  56. // Sous-programmes qui agissent sur une liste
  57. // ==================================================================
  58.  
  59. // Initialisation de la liste
  60. liste liste_initialiser()
  61. {
  62.     return liste_vide;
  63. }
  64.  
  65. // Ajout en tête de la liste
  66. liste liste_ajouter_en_tete(liste l, int valeur)
  67. {
  68.     type_element_de_liste *nouvel_element = new type_element_de_liste;
  69.     le_suivant_de(nouvel_element) = l;
  70.     la_valeur_de(nouvel_element) = valeur;
  71.  
  72.     return nouvel_element;
  73. }
  74.  
  75. // Ajout en queue de la liste
  76. liste liste_ajouter_en_queue(liste l, int valeur)
  77. {
  78.  
  79.     type_element_de_liste *nouvel_element = new type_element_de_liste;
  80.     le_suivant_de(nouvel_element) = liste_vide;
  81.     la_valeur_de(nouvel_element) = valeur;
  82.  
  83.     if (l == liste_vide)
  84.     {
  85.         return nouvel_element;
  86.     }
  87.     else
  88.     {
  89.         // rechercher le dernier élément
  90.         liste dernier = l;
  91.         while (le_suivant_de(dernier) != liste_vide)
  92.         {
  93.             dernier = le_suivant_de(dernier);
  94.         }
  95.  
  96.         le_suivant_de(dernier) = nouvel_element;
  97.  
  98.         return l;
  99.     }
  100. }
  101.  
  102. // créer une liste à partir de données stokées
  103. // dans une chaîne de caractères
  104. liste liste_creer(string data)
  105. {
  106.     liste l = liste_vide;
  107.     istringstream iss(data);
  108.     type_valeur valeur;
  109.  
  110.     while (iss >> valeur)
  111.     {
  112.         l = liste_ajouter_en_queue(l, valeur);
  113.     }
  114.  
  115.     return l;
  116. }
  117.  
  118. // Vider une liste : supprimer tous ses éléments
  119. liste liste_vider(liste l)
  120. {
  121.  
  122.     liste courant = l;
  123.     liste suivant;
  124.  
  125.     while (courant != liste_vide)
  126.     {
  127.         suivant = le_suivant_de(courant);
  128.         delete courant;
  129.         courant = suivant;
  130.     }
  131.  
  132.     return liste_vide;
  133. }
  134.  
  135. // Affichage de la liste
  136. void liste_afficher(liste l)
  137. {
  138.  
  139.     liste courant = l;
  140.     while (courant != liste_vide)
  141.     {
  142.         cout << la_valeur_de(courant) << " ";
  143.         courant = le_suivant_de(courant);
  144.     }
  145.     cout << endl;
  146. }
  147.  
  148. // Tri de la liste sous forme de tri à bulle
  149. void liste_trier(liste l)
  150. {
  151.  
  152.     liste courant1 = l;
  153.     while (courant1 != liste_vide)
  154.     {
  155.         liste courant2 = le_suivant_de(courant1);
  156.         while (courant2 != liste_vide)
  157.         {
  158.             if (la_valeur_de(courant1) > la_valeur_de(courant2))
  159.             {
  160.                 swap(la_valeur_de(courant1), la_valeur_de(courant2));
  161.             }
  162.             courant2 = le_suivant_de(courant2);
  163.         }
  164.         courant1 = le_suivant_de(courant1);
  165.     }
  166. }
  167.  
  168. liste liste_supprimer_doublons(liste l)
  169. {
  170.  
  171.     liste courant = l;
  172.  
  173.     // on parcourt la liste initiale à la recherche d'un doublon
  174.     // pour chaque élément
  175.     while (courant != liste_vide)
  176.     {
  177.         liste doublon = le_suivant_de(courant);
  178.  
  179.         // parcours des éléments restants dans la liste
  180.         liste precedent_doublon = courant;
  181.         while (doublon != liste_vide)
  182.         {
  183.  
  184.             // a t-on trouvé un doublon ?
  185.             if (la_valeur_de(courant) == la_valeur_de(doublon))
  186.             {
  187.                 // si oui, supprimer le doublon
  188.                 liste suivant_doublon = le_suivant_de(doublon);
  189.                 delete doublon;
  190.                 le_suivant_de(precedent_doublon) = suivant_doublon;
  191.  
  192.                 doublon = suivant_doublon;
  193.             }
  194.             else
  195.             {
  196.                 // sinon, passer à l'élément suivant
  197.                 precedent_doublon = doublon;
  198.                 doublon = le_suivant_de(doublon);
  199.             }
  200.         }
  201.  
  202.         courant = le_suivant_de(courant);
  203.     }
  204.  
  205.     return l;
  206. }
  207.  
  208. // ==================================================================
  209. // Programme principal
  210. // ==================================================================
  211. // On insère des élément dans la liste (en tête, puis en queue) et
  212. // on affiche le résultat : 11 4 3 2 1 5 6 7 8 9 10 -1
  213. // on tri ensuite la liste : -1 1 2 3 4 5 6 7 8 9 10 11
  214. // ==================================================================
  215.  
  216. int main()
  217. {
  218.     liste l;
  219.  
  220.     l = liste_initialiser();
  221.  
  222.     for (int i = 1; i < 5; ++i)
  223.     {
  224.         l = liste_ajouter_en_tete(l, i);
  225.     }
  226.  
  227.     for (int i = 5; i < 11; ++i)
  228.     {
  229.         liste_ajouter_en_queue(l, i);
  230.     }
  231.  
  232.     l = liste_ajouter_en_tete(l, 11);
  233.     l = liste_ajouter_en_queue(l, -1);
  234.  
  235.     cout << "liste initiale = ";
  236.     liste_afficher(l);
  237.  
  238.     liste_trier(l);
  239.  
  240.     cout << "liste triée = ";
  241.     liste_afficher(l);
  242.  
  243.     l = liste_vider(l);
  244.  
  245.     l = liste_creer("1 2 1 2 2 3 2 1");
  246.  
  247.     cout << "liste avec doublons = ";
  248.     liste_afficher(l);
  249.  
  250.     l = liste_supprimer_doublons(l);
  251.  
  252.     cout << "liste sans doublons = ";
  253.     liste_afficher(l);
  254.  
  255.     l = liste_vider(l);
  256.  
  257.     return EXIT_SUCCESS;
  258. }
  259.  
• amélioration de la première version mais qui n'utilise pas de pointeur de pointeur pour passer une liste en paramètre. On passe la liste en paramètre et si on la modifie à l'intérieur du sous-programme, on retourne la nouvelle tête de liste :
  
  Afficher le code    ens/l1/algo4/v3_le_rec.cpp

  1. // ==================================================================
  2. //      Auteur : Jean-Michel RICHER
  3. //      Email  : jean-michel.richer@univ-angers.fr
  4. // Institution : Université d'Angers, Faculté des Sciences
  5. // Département : Informatique
  6. // ==================================================================
  7. //
  8. // Objectif : Implantation récursive de liste simplement chaînée
  9. //
  10. // Spécificité : On passe en paramètre des sous-programmes qui
  11. // agissent sur les listes, la liste à modifier. Pour les sous-
  12. // programmes qui modifie la liste (comme l'ajout d'un élément)
  13. // on retourne la tête de la nouvelle liste modifiée.
  14. //
  15. // Lors de l'appel de ces sous-programmes il faut donc passer
  16. // la liste en paramètre mais éventuellement récupérer la liste
  17. // modifiée
  18. //
  19. // L'implantation donnée ici utilise des macro-instructions afin
  20. // de rendre la lecture du code plus aisée.
  21. // ==================================================================
  22. #include <iostream>
  23. using namespace std;
  24.  
  25. // ==================================================================
  26. // structures communes
  27. // ==================================================================
  28.  
  29. // définition du type de la valeur stockée par un élément de la liste
  30. using type_valeur = int;
  31.  
  32. // définition d'un élément (maillon) de la liste
  33. struct type_element_de_liste
  34. {
  35.     // pointeur sur l'élément suivant
  36.     type_element_de_liste *suivant;
  37.     // valeur stockée par cet élément
  38.     type_valeur valeur;
  39. };
  40.  
  41. // définition d'une liste comme un pointeur sur un élément
  42. using liste = type_element_de_liste *;
  43.  
  44. // définition de la liste vide
  45. const liste liste_vide = nullptr;
  46.  
  47. // ==================================================================
  48. // structures spécifiques à cette implantation
  49. // ==================================================================
  50.  
  51. #define le_suivant_de(l) l->suivant
  52. #define la_valeur_de(l) l->valeur
  53.  
  54. // ==================================================================
  55. // Sous-programmes qui agissent sur une liste
  56. // ==================================================================
  57.  
  58. // Initialisation de la liste
  59. liste liste_initialiser()
  60. {
  61.     return liste_vide;
  62. }
  63.  
  64. // Ajout en tête de la liste
  65. liste liste_ajouter_en_tete(liste l, int valeur)
  66. {
  67.     type_element_de_liste *nouvel_element = new type_element_de_liste;
  68.     le_suivant_de(nouvel_element) = l;
  69.     la_valeur_de(nouvel_element) = valeur;
  70.  
  71.     return nouvel_element;
  72. }
  73.  
  74. // Ajout en queue de la liste
  75. liste liste_ajouter_en_queue(liste l, int valeur)
  76. {
  77.  
  78.     if (l == liste_vide)
  79.     {
  80.         type_element_de_liste *nouvel_element = new type_element_de_liste;
  81.         le_suivant_de(nouvel_element) = liste_vide;
  82.         la_valeur_de(nouvel_element) = valeur;
  83.         return nouvel_element;
  84.     }
  85.     else
  86.     {
  87.         // rechercher le dernier élément
  88.         le_suivant_de(l) = liste_ajouter_en_queue(le_suivant_de(l), valeur);
  89.         return l;
  90.     }
  91. }
  92.  
  93. // Affichage de la liste
  94. void liste_afficher(liste l)
  95. {
  96.  
  97.     if (l == liste_vide)
  98.     {
  99.         cout << endl;
  100.     }
  101.     else
  102.     {
  103.         cout << la_valeur_de(l) << " ";
  104.         liste_afficher(le_suivant_de(l));
  105.     }
  106. }
  107.  
  108. // Tri de la liste sous forme de tri à bulle
  109. // !!! Implantation itérative !!!
  110. void liste_trier(liste l)
  111. {
  112.  
  113.     liste courant1 = l;
  114.     while (courant1 != liste_vide)
  115.     {
  116.         liste courant2 = le_suivant_de(courant1);
  117.         while (courant2 != liste_vide)
  118.         {
  119.             if (la_valeur_de(courant1) > la_valeur_de(courant2))
  120.             {
  121.                 swap(la_valeur_de(courant1), la_valeur_de(courant2));
  122.             }
  123.             courant2 = le_suivant_de(courant2);
  124.         }
  125.         courant1 = le_suivant_de(courant1);
  126.     }
  127. }
  128.  
  129. // ==================================================================
  130. // Programme principal
  131. // ==================================================================
  132. // On insère des élément dans la liste (en tête, puis en queue) et
  133. // on affiche le résultat : 11 4 3 2 1 5 6 7 8 9 10 -1
  134. // on tri ensuite la liste : -1 1 2 3 4 5 6 7 8 9 10 11
  135. // ==================================================================
  136.  
  137. int main()
  138. {
  139.     liste l;
  140.  
  141.     l = liste_initialiser();
  142.  
  143.     for (int i = 1; i < 5; ++i)
  144.     {
  145.         l = liste_ajouter_en_tete(l, i);
  146.     }
  147.  
  148.     for (int i = 5; i < 11; ++i)
  149.     {
  150.         liste_ajouter_en_queue(l, i);
  151.     }
  152.  
  153.     l = liste_ajouter_en_tete(l, 11);
  154.     l = liste_ajouter_en_queue(l, -1);
  155.  
  156.     cout << "liste initiale = ";
  157.     liste_afficher(l);
  158.  
  159.     liste_trier(l);
  160.  
  161.     cout << "liste triée = ";
  162.     liste_afficher(l);
  163.  
  164.     return EXIT_SUCCESS;
  165. }
  166.  

Les deux dernières versions sont probablement les plus sympathiques ;-) car :

1. on n'utilise que des pointeurs et non des pointeurs de pointeurs ou des références sur pointeur
2. on n'a les mêmes prototypes (signatures) de sous-programme en itératif ou en récursif

2.4.3. Application

Voici un exemple qui reprend l'implantation itérative avec des listes pour une personne qui est un struct composé de deux chaînes : nom et prénom.

Il est nécessaire de redéfinir deux opérateurs pour une personne :

• l'opérateur de sortie << pour l'affichage
• l'opérateur de comparaison > pour le tri

Voir le code :

2.4.4. Listes et récursion

Heureusement, le compilateur gcc/g++ dérécursive la grande majorité des sous-programmes récursifs. Un simple test montre par exemple que sur AMD Ryzen 5600 G, si on utilise effectivement la récursion (il faut compiler avec g++ -O1), l'ajout en queue de $200\_000$ entiers dans une liste prend $50$ secondes alors que sans récursion on ne met plus que $18$ secondes.

Un autre test montre que si on utilise une structure de personne (nom, prénom et téléphone sous forme de string, comme en TP), l'ajout de la 43662 ième personne provoque une erreur de segmentation car la pile est saturée. En effet, on passe en paramètres de la fonction nom, prénom et téléphone à chaque appel de fonction.

En architecture 64 bits, la pile est initialement dans la méthode main à la valeur 238024d0_h . Elle descend jusqu'à 230047d0_h, soit une différence de 7fdd00_h $= 8\_379\_648_{10}$. Or la pile occupe 8 Mo soit $8\_388\_608$ octets, et, une fois dans la méthode main, on a déjà utilisé une partie de la pile. On a donc bien saturé la pile avec ces nombreux appels récursifs.