[code] listes chaînées, piles, files

, par Pierre

Un exemple d’utilisation des listes simplement chaînées pour implémenter les piles et les files (cours du 22 mars 2010). Les choix d’implémentation et des alternatives (parfois meilleures) ont été discutées pendant le cours. L’objectif était surtout de montrer les difficultés concrètes et l’importance de faire un croquis avant de coder.

  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <errno.h>
  4.  
  5. /* Definir le type des listes chainees */
  6.  
  7. typedef int element_t;
  8.  
  9. typedef struct cellule_s {
  10.     element_t e;
  11.     struct cellule_s *suivant;
  12. } cellule_t, *liste_t;
  13.  
  14. typedef liste_t pile_t;
  15.  
  16. typedef struct {
  17.     liste_t debut;
  18.     liste_t fin;
  19. } *file_t;
  20.  
  21. /* fonctions de base sur les listes */
  22. liste_t nouvelleListe() {
  23.     return NULL;
  24. }
  25.  
  26.  
  27. liste_t ajouterListe(element_t e, liste_t l) {
  28.     liste_t y;
  29.     /* creer cellule pour e*/
  30.     y = malloc(sizeof(*y));
  31.     if (y == NULL) {
  32.         perror("plus de memoire ??");
  33.     }
  34.     /* mettre la cellule en tete de l */
  35.     y->e = e;
  36.     y->suivant = l;
  37.     /* retourner la nouvelle liste */
  38.     return y;
  39. }
  40.  
  41. int estVideListe(liste_t l) {
  42.     return (l == NULL);
  43. }
  44.  
  45. element_t teteListe(liste_t l) {
  46.     if (estVideListe(l)) {
  47.         perror("Exception : tete sur liste vide");
  48.     }
  49.     return l->e;
  50. }
  51.  
  52. liste_t retirerTeteListe(liste_t l) {
  53.     liste_t garbage;
  54.     if (estVideListe(l)) {
  55.         perror("Exception : retirer tete sur liste vide");
  56.     }
  57.     /* effacer la premier cellule */
  58.     garbage = l;
  59.     l = l->suivant;
  60.     free(garbage);
  61.     return l;
  62. }
  63.  
  64. liste_t rechercherListe(element_t a, liste_t l) {
  65.     while ((!estVideListe(l)) && (teteListe(l) != a)) {
  66.         l = l->suivant;
  67.     }
  68.     return l;
  69. }
  70.  
  71. /* les piles */
  72.  
  73. pile_t nouvellePile() {
  74.     return nouvelleListe();
  75. }
  76.  
  77. int estVidePile(pile_t p) {
  78.     return estVideListe(p);
  79. }
  80.  
  81. void empiler(element_t e, pile_t *pp) {
  82.     *pp = ajouterListe(e, *pp);
  83. }
  84.  
  85. element_t depiler(pile_t *pp) {
  86.     element_t e;
  87.     e = teteListe(*pp);
  88.     *pp = retirerTeteListe(*pp);
  89.      return e;
  90. }
  91.  
  92. element_t sommet(pile_t p) {
  93.     return teteListe(p);
  94. }
  95.  
  96. /* Files */
  97.  
  98. file_t nouvelleFile() {
  99.     file_t f;
  100.     f = malloc(sizeof(*f));
  101.     if (f == NULL) {
  102.         perror("Memoire !");
  103.     }
  104.     f->debut = nouvelleListe();
  105.     f->fin = f->debut;
  106.     return f;
  107. }
  108.  
  109. int estVideFile(file_t f) {
  110.     return estVideListe(f->debut);
  111. }
  112.  
  113. element_t teteFile(file_t f) {
  114.     if (estVideFile(f)) {
  115.         perror("Exception: tete sur file vide");      
  116.     }
  117.     return teteListe(f->debut);
  118. }
  119.  
  120. void insererFile(element_t e, file_t f) {
  121.     liste_t x;
  122.     x = malloc(sizeof(*x));
  123.     if (x == NULL) {
  124.         perror("Memoire.. pas content");
  125.     }
  126.     x->e = e;
  127.     x->suivant = NULL;
  128.     if (estVideFile(f)) {
  129.         f->debut = x;
  130.         f->fin = x;
  131.     } else {
  132.         (f->fin)->suivant = x;
  133.         f->fin = x;
  134.     }
  135. }
  136.  
  137. element_t retirerFile(file_t f) {
  138.     element_t e;
  139.     if (estVideFile(f)) {
  140.         perror("Exception: retrait dans une file vide");
  141.     }
  142.     e = (f->debut)->e;
  143.     if (f->debut == f->fin) {/* un seul element dans la file */
  144.         free(f->debut);
  145.         f->debut = NULL;
  146.         f->fin = NULL;
  147.     } else {
  148.         liste_t x;
  149.         x = f->debut;
  150.         f->debut = x->suivant;
  151.         free(x);
  152.     }
  153.     return e;
  154. }
  155.  
  156. /* afficher */
  157. void afficherListe(liste_t l) {
  158.     while (!estVideListe(l)) {
  159.         printf("%d::", l->e);
  160.         l = l->suivant;
  161.     }
  162.     printf("\n");
  163. }
  164.  
  165. void afficherPile(pile_t p) {
  166.     afficherListe(p);
  167. }
  168.  
  169. void afficherFile(file_t f) {
  170.     afficherListe(f->debut);
  171. }
  172.  
  173. int main() {
  174.     liste_t l;
  175.     pile_t p;
  176.     file_t f;
  177.     l = nouvelleListe();
  178.     l = ajouterListe(100, l);
  179.     l = ajouterListe(200, l);
  180.     l = ajouterListe(300, l);
  181.     l = ajouterListe(400, l);
  182.     afficherListe(l);
  183.     l = retirerTeteListe(l);
  184.     afficherListe(l);
  185.     p = nouvellePile();
  186.     empiler(100, &p);
  187.     empiler(200, &p);
  188.     empiler(300, &p);
  189.     empiler(400, &p);
  190.     afficherPile(p);
  191.     depiler(&p);
  192.     afficherPile(p);
  193.     f = nouvelleFile();
  194.     insererFile(100, f);
  195.     insererFile(200, f);
  196.     insererFile(300, f);
  197.     insererFile(400, f);
  198.     afficherFile(f);
  199.     retirerFile(f);
  200.     afficherFile(f);
  201.     return EXIT_SUCCESS;
  202. }

Télécharger

Recherche

Enseignement

Administration

Curriculum Vitæ [pdf]
Comment me contacter

Autres réalisations (logiciels, etc.)

Thymio, Python et Asebamedulla
des QCM en ligne grâce à org-mode (et jQuery, et MathJax), org-mode [org, html, css]

Café

Enseigner la programmation
Revenu et logement, Je livre ici quelques éléments de comparaison concernant mon niveau de vie, pour couper court à quelques idées reçues, et un condensé de nombreuses (...)
Revenu et travail d’un enseignant-chercheur, Cet article complète l'article Revenu et logement, en détaillant un peu le budget de mon ménage, mon parcours d'enseignant-chercheur en terme de (...)
Paris 13 Villetaneuse, pas encore la vélorution !
Cybersyn (el systemo synco), Au café, mardi 5 avril 2011, j'ai bien vu que, mis à part Antoine Allombert, personne ne connaissait l'histoire de l'extraordinaire projet chilien (...) [jpg, jpg, png]

Divers

Affiche CiE 2016
Augmenter l’espace de stockage d’un hote GNU/Linux (VirtualBox etc.)
AperoTIC sur les réseaux sociaux
ADULLACT, Pour être un peu moins seul à défendre l'usage et le développement de logiciels libres dans mon travail (et autour), j'ai adhéré à l'ADULLACT en tant (...)
Hacker l’éducation (Open bidouille camp 2 // Fac lab de Gennevilliers)
Expo : et l’Homme… créa le robot
MathJax
Onglets dans un rapport $\LaTeX$ [gz, png, pdf, gz]
Logo LIPN et accessoires [svg, svg, png, tex, pdf, tif, zip, png, eps, svg]
Ventilo pour ibook (retrouvé) [jpg]