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.