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. //            concernant des personnes
  10. //
  11. // Spécificité : On passe en paramètre des sous-programmes qui
  12. // agissent sur les listes, la liste à modifier. Pour les sous-
  13. // programmes qui modifie la liste (comme l'ajout d'un élément)
  14. // on retourne la tête de la nouvelle liste modifiée.
  15. //
  16. // Lors de l'appel de ces sous-programmes il faut donc passer
  17. // la liste en paramètre mais éventuellement récupérer la liste
  18. // modifiée
  19. //
  20. // L'implantation donnée ici utilise des macro-instructions afin
  21. // de rendre la lecture du code plus aisée.
  22. // ==================================================================
  23. #include <iostream>
  24. #include <vector>
  25. #include <string>
  26.  
  27. using namespace std;
  28.  
  29. // ==================================================================
  30. // structures communes
  31. // ==================================================================
  32.  
  33. struct personne
  34. {
  35.     string nom, prenom;
  36. };
  37.  
  38. // Instanciation d'une personne
  39. void personne_initialiser(personne &p, string nom, string prenom)
  40. {
  41.     p.nom = nom;
  42.     p.prenom = prenom;
  43. }
  44.  
  45. // Redéfinition de l'opérateur de sortie sur un flux : il est nécessaire
  46. // de redéfinir cet opérateur car il est utilisé pour l'affichage
  47. ostream &operator<<(ostream &out, personne &p)
  48. {
  49.     out << "(" << p.nom << ", " << p.prenom << ")";
  50.     return out;
  51. }
  52.  
  53. // Redéfinition de l'opérateur de comparison > : il est nécessaire
  54. // de redéfinir cet opérateur car il est utilisé pour le tri
  55. // Note : on compare les personnes suivant leur nom uniquement
  56. bool operator>(const personne &p1, const personne &p2)
  57. {
  58.     return p1.nom > p2.nom;
  59. }
  60.  
  61. // définition du type de la valeur stockée par un élément de la liste
  62. using type_valeur = personne;
  63.  
  64. // définition d'un élément (maillon) de la liste
  65. struct type_element_de_liste
  66. {
  67.     // pointeur sur l'élément suivant
  68.     type_element_de_liste *suivant;
  69.     // valeur stockée par cet élément
  70.     type_valeur valeur;
  71. };
  72.  
  73. // définition d'une liste comme un pointeur sur un élément
  74. using liste = type_element_de_liste *;
  75.  
  76. // définition de la liste vide
  77. const liste liste_vide = nullptr;
  78.  
  79. // ==================================================================
  80. // structures spécifiques à cette implantation
  81. // ==================================================================
  82.  
  83. #define le_suivant_de(l) l->suivant
  84. #define la_valeur_de(l) l->valeur
  85.  
  86. // ==================================================================
  87. // Sous-programmes qui agissent sur une liste
  88. // ==================================================================
  89.  
  90. // Initialisation de la liste
  91. liste liste_initialiser()
  92. {
  93.     return liste_vide;
  94. }
  95.  
  96. // Ajout en tête de la liste
  97. liste liste_ajouter_en_tete(liste l, type_valeur valeur)
  98. {
  99.     type_element_de_liste *nouvel_element = new type_element_de_liste;
  100.     le_suivant_de(nouvel_element) = l;
  101.     la_valeur_de(nouvel_element) = valeur;
  102.  
  103.     return nouvel_element;
  104. }
  105.  
  106. // Ajout en queue de la liste
  107. liste liste_ajouter_en_queue(liste l, type_valeur valeur)
  108. {
  109.  
  110.     type_element_de_liste *nouvel_element = new type_element_de_liste;
  111.     le_suivant_de(nouvel_element) = liste_vide;
  112.     la_valeur_de(nouvel_element) = valeur;
  113.  
  114.     if (l == liste_vide)
  115.     {
  116.         return nouvel_element;
  117.     }
  118.     else
  119.     {
  120.         // rechercher le dernier élément
  121.         liste dernier = l;
  122.         while (le_suivant_de(dernier) != liste_vide)
  123.         {
  124.             dernier = le_suivant_de(dernier);
  125.         }
  126.  
  127.         le_suivant_de(dernier) = nouvel_element;
  128.  
  129.         return l;
  130.     }
  131. }
  132.  
  133. // Affichage de la liste
  134. void liste_afficher(liste l)
  135. {
  136.  
  137.     liste courant = l;
  138.     while (courant != liste_vide)
  139.     {
  140.         cout << la_valeur_de(courant) << " ";
  141.         courant = le_suivant_de(courant);
  142.     }
  143.     cout << endl;
  144. }
  145.  
  146. // Tri de la liste sous forme de tri à bulle
  147. void liste_trier(liste l)
  148. {
  149.  
  150.     liste courant1 = l;
  151.     while (courant1 != liste_vide)
  152.     {
  153.         liste courant2 = le_suivant_de(courant1);
  154.         while (courant2 != liste_vide)
  155.         {
  156.             if (la_valeur_de(courant1) > la_valeur_de(courant2))
  157.             {
  158.                 swap(la_valeur_de(courant1), la_valeur_de(courant2));
  159.             }
  160.             courant2 = le_suivant_de(courant2);
  161.         }
  162.         courant1 = le_suivant_de(courant1);
  163.     }
  164. }
  165.  
  166. // ==================================================================
  167. // Programme principal
  168. // ==================================================================
  169. // On insère des élément dans la liste (en tête, puis en queue) et
  170. // on affiche le résultat : 11 4 3 2 1 5 6 7 8 9 10 -1
  171. // on tri ensuite la liste : -1 1 2 3 4 5 6 7 8 9 10 11
  172. // ==================================================================
  173.  
  174. int main()
  175. {
  176.     liste l;
  177.     personne p;
  178.  
  179.     l = liste_initialiser();
  180.  
  181.     std::vector<pair<string, string>> identites = {
  182.         {"dupond", "jean"},
  183.         {"dupont", "jean"},
  184.         {"decafer", "marc"},
  185.         {"naymar", "jean"},
  186.         {"nade", "marie"},
  187.         {"estone", "charles"}};
  188.  
  189.     for (auto paire : identites)
  190.     {
  191.         personne_initialiser(p, paire.first, paire.second);
  192.         l = liste_ajouter_en_tete(l, p);
  193.     }
  194.  
  195.     cout << "liste initiale = ";
  196.     liste_afficher(l);
  197.  
  198.     liste_trier(l);
  199.  
  200.     cout << "liste triée = ";
  201.     liste_afficher(l);
  202.  
  203.     return EXIT_SUCCESS;
  204. }
  205.