TP5/exo_c6/file_chaine_correction.c

   1 /**************************************************************************
   2  Implantation d'un type File d'entiers sous forme chaînée
   3
   4    La file est représentée par un doublet tête-queue de pointeurs
   5    vers une cellule.
   6         Le pointeur "tête"  contient l'adresse de la tête  de la file.
   7         Le pointeur "queue" contient l'adresse de la queue de la file.
   8
   9         La file vide est représentée par le doublet NULL-NULL
  10
  11         Chaque cellule pointe vers la cellule suivante de la file
  12 ou vers NULL si on est en queue de file.
  13
  14 **************************************************************************/
  15 #include <stdio.h>
  16 #include <stdlib.h>
  17
  18 typedef int element;
  19 typedef struct cellule {
  20         element valeur;
  21         struct cellule *suivant;
  22 } Cellule;
  23
  24 typedef struct file {
  25         Cellule *t, *q;
  26 } File;                         /* tête queue */
  27
  28 File file_vide(void)
  29 {
  30         File f = { NULL, NULL };
  31         return f;
  32 }
  33
  34 int est_vide(File f)
  35 {
  36         return !f.t;
  37 }
  38
  39 element tete(File f)
  40 /* ATTENTION: consulter la tête d'une File vide n'a pas de sens */
  41 {
  42         if (est_vide(f)) {
  43                 printf("Erreur - file vide\n");
  44                 exit(-1);
  45         }
  46         return f.t->valeur;     /* la File n'est pas modifiée */
  47 }
  48
  49 File enfiler(element e, File f)
  50 {
  51         Cellule *pc = (Cellule *) malloc(sizeof(Cellule));
  52         pc->valeur = e;
  53         pc->suivant = NULL;
  54
  55         if (est_vide(f))
  56                 f.t = f.q = pc; /* la cellule créée est à la fois tête et queue */
  57         else
  58                 f.q = f.q->suivant = pc;        /* la cellule créée est la nouvelle queue */
  59         return f;
  60 }
  61
  62 File defiler(File f)
  63 /* ATTENTION: supprimer la tête d'une File vide n'a pas de sens */
  64 {
  65         Cellule *pc = f.t;
  66         if (est_vide(f)) {
  67                 printf("Erreur - file vide\n");
  68                 exit(-1);
  69         }
  70         if (f.t == f.q)
  71                 f = file_vide();        /* la File n'avait plus qu'une seule cellule */
  72         else
  73                 f.t = f.t->suivant;     /* la queue ne change pas */
  74         free(pc);
  75         return f;
  76 }
  77
  78 element defiler2(File * f)
  79 {
  80         /* ATTENTION: la File est modifiée */
  81         /* ATTENTION: supprimer la tête d'une File vide n'a pas de sens */
  82         Cellule *pc = f->t;
  83         element e;
  84         if (est_vide(*f)) {
  85                 printf("Erreur - file vide\n");
  86                 exit(-1);
  87         }
  88         e = f->t->valeur;
  89         if (f->t == f->q)
  90                 *f = file_vide();       /* la File n'avait plus qu'une seule cellule */
  91         else
  92                 f->t = f->t->suivant;   /* la queue ne change pas */
  93         free(pc);
  94         return e;
  95 }
  96
  97 /********************************************************************/
  98 int main()
  99 {
 100         File p;
 101         int i;
 102         p = file_vide();
 103         for (i = 0; i < 20; i++)
 104                 p = enfiler(i, p);
 105         for (i = 0; i < 25; i++)
 106                 printf("%d\n", defiler2(&p));
 107 }
 108
 109 /********************************************************************/