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 {element   valeur;
  20          struct cellule *suivant; } Cellule;
  21
  22 typedef struct file { Cellule *t, *q; } File;   /* tête queue */
  23
  24 File file_vide(void)
  25 {
  26  File f={NULL,NULL};
  27  return f;
  28 }
  29
  30 int est_vide(File f)
  31 {
  32  return !f.t;
  33 }
  34
  35 element tete(File f)
  36 /* ATTENTION: consulter la tête d'une File vide n'a pas de sens */
  37 {
  38  if (est_vide(f)) {printf("Erreur - file vide\n"); exit(-1); }
  39  return f.t->valeur; /* la File n'est pas modifiée */
  40 }
  41
  42 File enfiler(element e,File f)
  43 {
  44  Cellule *pc=(Cellule *)malloc(sizeof(Cellule));
  45  pc->valeur=e;pc->suivant=NULL;
  46
  47  if (est_vide(f))
  48         f.t=f.q=pc; /* la cellule créée est à la fois tête et queue */
  49  else
  50         f.q=f.q->suivant=pc; /* la cellule créée est la nouvelle queue */
  51  return f;
  52 }
  53
  54 File defiler(File f)
  55 /* ATTENTION: supprimer la tête d'une File vide n'a pas de sens */
  56 {
  57  Cellule *pc=f.t;
  58  if (est_vide(f))
  59  {
  60   printf("Erreur - file vide\n");
  61   exit(-1);
  62  }
  63  if (f.t==f.q) f=file_vide();   /* la File n'avait plus qu'une seule cellule */
  64  else f.t=f.t->suivant; /* la queue ne change pas */
  65  free(pc);
  66  return f;
  67 }
  68
  69 element defiler2(File *f)       /* ATTENTION: la File est modifiée */
  70 /* ATTENTION: supprimer la tête d'une File vide n'a pas de sens */
  71 {
  72  Cellule *pc=f->t;
  73  element e;
  74  if (est_vide(*f))
  75  {
  76   printf("Erreur - file vide\n");
  77   exit(-1);
  78  }
  79  e=f->t->valeur;
  80  if (f->t==f->q) *f=file_vide(); /* la File n'avait plus qu'une seule cellule */
  81  else f->t=f->t->suivant; /* la queue ne change pas */
  82  free(pc);
  83  return e;
  84 }
  85
  86
  87 /********************************************************************/
  88 int main()
  89 {
  90  File p;
  91  int i;
  92  p=file_vide();
  93  for (i=0; i<20; i++) p=enfiler(i,p);
  94  for (i=0; i<25; i++) printf("%d\n",defiler2(&p));
  95 }
  96 /********************************************************************/
  97