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.