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.