Cours 4: Le type File.

Voici la signature du type abstrait File .

File creer_file();
Element_file tete_file(File f);
File ajouter_file(File f, Element_file e);
File retirer_file(File f);
unsigned int est_vide_file(File f);
// f: File; e: Element_file;
// préconditions
//  retirer_file(f) est-défini-ssi est_vide_file(f) == 0
//  tete_file(f) est-défini-ssi est_vide_file(f) == 0
// axiomes
//  est_vide_file(f) != 0 =>
//    tete_file(ajouter_file(f, e)) == e
//  est_vide_file(f) == 0 =>
//    tete_file(ajouter_file(f, e)) == tete_file(f)
//  est_vide_file(f) != 0 =>
//    retirer_file(ajouter_file(f, e)) == creer_file()
//  est_vide_file(f) == 0 =>
//    retirer_file(ajouter_file(f, e)) == ajouter_file(retirer_file(f), e)
//  est_vide_file(creer_file()) != 0
//  est_vide_file(ajouter_file(f, e)) == 0

Les préconditions imposent qu'on ne puisse ni retirer, ni consulter la tête d'une file vide.
Le premier axiome indique qu'un élément ajouté a une file vide est placé en tête de file.
Le second axiome montre qu'une file non vide ne change pas de tête après un ajout (l'ajout se fait en queue).
Le troisième axiome affirme qu'un ajout suivi d'un retrait d'une file vide la laissent vide.
Le quatrième axiome précise qu'un ajout d'un élément e suivi d'un retrait d'une file non vide a le même effet qu'un retrait suivi d'un ajout de e .
Le cinquième axiome annonce qu'une file est vide à sa création.
Le sixième axiome dit qu'une file n'est plus vide après un ajout.

Comme dans le cas de la pile, une file est-elle une variété de liste? Dans l'affirmative, on dérive la définition du type File de celui du type Liste.
L'ajout peut s'exprimer comme une écriture en tête et le retrait est alors une suppression de l'élément de queue.
Cela montre qu'une file est une liste dans laquelle on accède à la fois en tête et en queue.
A l'inverse, l'ajout peut être une écriture en queue et le retrait, une suppression de la tête.

Voici une implémentation de file en table (la taille de la file est fixée à sa création), exprimée à partir de la spécification d'une liste en table.

// fichier file_en_table.c
#include <stdio.h>
#include "file_en_table.h"
#include "liste_en_table.h"
File creer_file() {
 Liste l;
 l = creer_liste();
 return (File)l;
}
Element_file tete_file(File f) {
// précondition est_vide_file(f) == 0
 if (est_vide_file(f)) {
   fprintf(stderr, "tete_file: file vide\n");
   exit(1);
 }
 return lire_liste((Liste)f, 0);
}
File ajouter_file(File f, Element_file e) {
// précondition d'implémentation: file non pleine
 if (longueur_liste((Liste)f) == TAILLE_FILE) {
   fprintf(stderr, "ajouter_file: file pleine\n");
   exit(1);
 }
 return (File)inserer_liste((Liste)f, longueur_liste((Liste)f), e);
}
File retirer_file(File f) {
// précondition est_vide_file(f) == 0
 if (est_vide_file(f)) {
   fprintf(stderr, "retirer_file: file vide\n");
   exit(1);
 }
 return (File)supprimer_liste((Liste)f, 0);
}
unsigned int est_vide_file(File f) {
 return (((Liste)f) == NULL);
}

Le code ci-dessus fait apparaître que nous avons privilégié un ajout en queue de liste et un retrait en tête. Dans l'implémentation que nous avons donné pour les listes, une suppression en tête de liste se traduit par un tassement du tableau. Cela n'est pas très efficace.
Nous aurions pu opter pour un retrait en queue et un ajout en tête, mais alors les ajouts auraient provoqués un décalage du tableau d'un cran à droite.
On voit que l'implémentation des listes fournie précédemment ne convient pas pour implanter efficacement les files. Nous allons donc fournir une nouvelle implémentation (sans pour autant revenir sur la signature du type Liste: nous ne devons pas changer liste.h ).
Voici le fichier liste_en_table2.c .

// fichier liste_en_table2.c
#include <stdio.h>
#include "liste_en_table.h"
typedef Element_liste *Table;
typedef struct {unsigned int longueur, premier, dernier; Table t;} St;
Liste creer_liste() {
 St *s;
 s = (St *) malloc(sizeof(St));
 s->t = (Table) malloc(sizeof(Element_liste)*TAILLE_LISTE);
 s->longueur = 0;
 s->premier = s->dernier = 0;
 return (Liste) s;
}
Element_liste lire_liste(Liste l, unsigned int rang) {
// précondition: 0<=rang<=longueur_liste(l)-1
 unsigned int premier = ((St *)l)->premier;
 if (rang >= longueur_liste(l)) {
  fprintf(stderr, "lire_liste: rang %d >= longueur liste %d\n",
    rang, longueur_liste(l));
  exit(1);
 }
 return (((St *)l)->t[(rang+premier)%TAILLE_LISTE]);
}
Liste supprimer_liste(Liste l, unsigned int rang) {
// précondition: 0<=rang<=longueur_liste(l)-1
 unsigned int i;
 unsigned int dernier = ((St *)l)->dernier;
 unsigned int premier = ((St *)l)->premier;
 if (rang >= longueur_liste(l)) {
  fprintf(stderr, "supprimer_liste: rang %d >= longueur liste %d\n",
    rang, longueur_liste(l));
  exit(1);
 }
 if (rang >= longueur_liste(l)/2) {
  for (i=rang+1; i<longueur_liste(l); i++)
   ((St *)l)->t[(i-1+premier)%TAILLE_LISTE] =
     ((St *)l)->t[(i+premier)%TAILLE_LISTE];
  if (dernier == 0)
   ((St *)l)->dernier = TAILLE_LISTE - 1;
  else
   ((St *)l)->dernier = dernier - 1;
 }
 else {
  for (i=rang; i>0; i--) {
   ((St *)l)->t[(i+premier)%TAILLE_LISTE] =
     ((St *)l)->t[(i-1+premier)%TAILLE_LISTE];
  }
  ((St *)l)->premier = (premier + 1) % TAILLE_LISTE;
 }
 ((St *)l)->longueur--;
 return l;
}
Liste inserer_liste(Liste l, unsigned int rang, Element_liste e) {
// précondition: 0<=rang<=longueur_liste(l)
// contrainte d'implémentation: rang<TAILLE_LISTE
 unsigned int i;
 unsigned int dernier = ((St *)l)->dernier;
 unsigned int premier = ((St *)l)->premier;
 if (rang >= TAILLE_LISTE) {
  fprintf(stderr, "inserer_liste: rang %d >= TAILLE liste %d\n",
    rang, TAILLE_LISTE);
  exit(1);
 }
 if (rang > longueur_liste(l)) {
  fprintf(stderr, "inserer_liste: rang %d > longueur liste %d\n",
    rang, longueur_liste(l));
  exit(1);
 }
 if (rang >= longueur_liste(l)/2) {
  for (i=longueur_liste(l); i>rang; i--) {
   ((St *)l)->t[(i+premier)%TAILLE_LISTE] =
     ((St *)l)->t[(i-1+premier)%TAILLE_LISTE];
  }
  ((St *)l)->dernier = (dernier + 1) % TAILLE_LISTE;
 }
 else {
  for (i=0; i<rang; i++) {
   ((St *)l)->t[(i-1+premier)%TAILLE_LISTE] =
     ((St *)l)->t[(i+premier)%TAILLE_LISTE];
  }
  if (premier == 0)
   ((St *)l)->premier = TAILLE_LISTE - 1;
  else
   ((St *)l)->premier = premier - 1;
 }
 ((St *)l)->t[(rang+((St *)l)->premier)%TAILLE_LISTE] = e;
 ((St *)l)->longueur++;
 return l;
}
unsigned int longueur_liste(Liste l) {
 return (((St *)l)->longueur);
}
Position positionner_liste(Liste l, unsigned int rang) {
// précondition: 0<=rang<=longueur_liste(l)-1
 unsigned int premier = ((St *)l)->premier;
 if (rang >= longueur_liste(l)) {
  fprintf(stderr, "positionner_liste: rang %d >= longueur liste %d\n",
    rang, longueur_liste(l));
  exit(1);
 }
 return (Position) &(((St *)l)->t[(rang+premier)%TAILLE_LISTE]);
}
Position suivant_liste(Liste l, Position p) {
// précondition: p!=positionner_liste(l, longueur_liste(l)-1)
 Position q;
 q = positionner_liste(l, longueur_liste(l) - 1);
 if (p == q) {
  fprintf(stderr, "suivant_liste: pas de suivant\n");
  exit(1);
 }
 if ((Table)p == ((St *)l)->t + (TAILLE_LISTE - 1))
  return (Position)((St *)l)->t;
 else
  return (Position) ((Table) p + 1);
}
Element_liste lire_courant_liste(Liste l, Position p) {
// précondition: longueur_liste(l)>0
 if (longueur_liste(l) == 0) {
  fprintf(stderr, "lire_courant_liste: liste vide\n");
  exit(1);
 }
 return ((Element_liste) *((Element_liste *)p));
}

On constate que la liste est toujours représentée par un tableau et sa longueur mais qu'on a ajouté les rangs du premier et du dernier élément (dans l'implémentation précédente, le premier était toujours en 0 et le dernier, en longueur(l) - 1 ).
Ainsi, une insertion dans la première moitié du tableau se fait en décalant vers la gauche (circulairement sur le tableau) tous les éléments depuis le premier jusqu'à celui qui précède le rang d'insertion. Le premier recule d'un rang circulairement.
Une insertion dans la seconde moitié décale vers la droite (circulairement) tous les éléments depuis le rang d'insertion jusqu'au dernier. Le dernier avance d'un rang circulairement.
Une suppression dans la première moitié décale un préfixe à droite et le premier avance d'un rang. Une suppression dans la seconde moitié décale un suffixe à gauche et le dernier recule d'un rang.
Cette implémentation des listes en table est plus efficace que la précédente parce que la complexité moyenne des insertions et des suppressions est proportionnelle à n/4 , n étant le nombre d'éléments de la liste, alors que dans l'implémentation précédente, les insertions et les suppressions avaient une complexité en moyenne de n/2 .
Notons que les suppressions et les insertions en queue et en tête se font sans décalages (dans l'implémentation précédente, cela ne concernait que les insertions et suppressions en queue).

Revenons à l'implémentation des files en table. En la liant à celle des listes en table que nous venons de voir, nous pouvons ajouter et retirer sans décalage du tableau représentant la file.
Voici le fichier file.h .

// fichier file.h
#include "file_def.h"
#include "element_file_def.h"
File creer_file();
Element_file tete_file(File f);
File ajouter_file(File f, Element_file e);
File retirer_file(File f);
unsigned int est_vide_file(File f);
// f: File; e: Element_file;
// préconditions
//  retirer_file(f) est-défini-ssi est_vide_file(f) == 0
//  tete_file(f) est-défini-ssi est_vide_file(f) == 0
// axiomes
//  est_vide_file(f) != 0 =>
//    tete_file(ajouter_file(f, e)) == e
//  est_vide_file(f) == 0 =>
//    tete_file(ajouter_file(f, e)) == tete_file(f)
//  est_vide_file(f) != 0 =>
//    retirer_file(ajouter_file(f, e)) == creer_file()
//  est_vide_file(f) == 0 =>
//    retirer_file(ajouter_file(f, e)) == ajouter_file(retirer_file(f), e)
//  est_vide_file(creer_file()) != 0
//  est_vide_file(ajouter_file(f, e)) == 0

Voici le fichier file_def.h

// fichier file_def.h
typedef void *File;

Voici le fichier main_table.c qui met en œuvre le type file en table.
On peut remarquer la façon dont on s'assure que la file n'est pas pleine avant de tenter un empilement. La constante TAILLE_FILE est définie et rendue visible par le fichier file_en_table.h . Comme on ne dispose d'aucune fonction donnant le nombre d'éléments de la file (cela ne fait pas partie de notre spécification d'une file), on tient à jour un compteur de la longueur de la file.

// fichier main_table.c
#include <stdio.h>
#include "element_int_file.h"
#include "file_en_table.h"
#define TAILLE_REP 128
main() {
 File f;
 Element_file e;
 int i;
 unsigned int longueur;
 char rep[TAILLE_REP];
 f = creer_file();
 longueur = 0;
 do {
  afficher_menu();
  fgets(rep, TAILLE_REP, stdin);
  if (rep[0] == 'q') exit(0);
  switch (rep[0]) {
   case 'r':
     if (est_vide_file(f)) printf("file vide\n");
     else {
      f = retirer_file(f);
      longueur--;
     }
     break;
   case 'a':
     if (longueur == TAILLE_FILE) printf("file pleine\n");
     else {
      sscanf(&rep[1], "%d", &i);
      e = creer_element_file();
      e = ecrire_element_file(e, i);
      f = ajouter_file(f, e);
      longueur++;
     }
     break;
   case 't':
     if (est_vide_file(f)) printf("file vide\n");
     else printf("%d\n", lire_element_file(tete_file(f)));
     break;
   case 'v':
     if (est_vide_file(f)) printf("vrai\n");
     else printf("faux\n");
     break;
  }
 } while (1);
}
afficher_menu() {
 printf("menu:\n");
 printf("  (q)uitter\n");
 printf("  (a)jouter (i)\n");
 printf("  (r)etirer\n");
 printf("  la file est-elle (v)ide?\n");
 printf("  afficher la (t)ete de file\n");
}

Voici le makefile. On peut constater qu'au lieu d'employer liste_en_table.c qui correspond à notre première implémentation des listes, on emploie liste_en_table2.c qui est l'implémentation donnée ci-dessus.

# fichier make_file_en_table
main_table: main_table.o liste_en_table2.o file_en_table.o element_int_file.o
        cc -o main_table main_table.o liste_en_table2.o file_en_table.o element_int_file.o
main_table.o: main_table.c file_en_table.h file.h file_def.h element_file_def.h element_int_file.h
        cc -c main_table.c
file_en_table.o: file_en_table.c file_en_table.h file.h file_def.h liste_en_table.h liste.h liste_def.h element_file_def.h
        cc -c file_en_table.c
liste_en_table2.o: liste_en_table2.c liste.h liste_en_table.h liste_def.h element_file_def.h
        cc -c liste_en_table2.c
element_int_file.o: element_int_file.c element_int_file.h element_file_def.h
        cc -c element_int_file.c

Tentons maintenant une implémentation de file en liste chaînée. La même remarque s'applique à l'implémentation des listes en liste chaînée. L'implémentation vue jusqu'ici ne permet que des accès en tête sans parcours de la liste. Les accès en queue sont les plus coûteux puisqu'ils nécessitent le parcours séquentiel de toute la liste.
Pour accélérer les accès en queue, il nous faut repérer le dernier élément de la liste. On représente la liste par un pointeur sur son dernier élément, celui-ci pointant sur le premier (une liste vide est toujours représentée par un pointeur NULL).
L'accès direct au dernier élément de la liste ne suffit pas. En effet, les opérations supprimer_liste(l, r) et inserer_liste(l, r, e) sont implémentées en parcourant la liste jusqu'à atteindre le rang r . S'il est le dernier, l'opération parcourt toute la liste plutôt que de directement agir sur le premier élément pointé (qui est le dernier élément de la liste). On ne peut faire autrement puisque le rang r n'indique pas qu'il est le dernier.
Pour autoriser une insertion directe d'un élément en queue de liste sans parcours, il faut ajouter une opération spécifique à la nouvelle implémentation de liste en chaîne. C'est l'opération suffixer_liste(l, e) .
Voici la nouvelle implémentation des listes en liste chaînée (fichier liste_en_chaine2.c ). Le fichier liste_dernier.h est l'extension de la spécification de liste à laquelle on a ajouté la fonction suffixer_liste .

// fichier liste_en_chaine2.c
#include <stdio.h>
#include "liste_dernier.h"
typedef struct C {Element_liste e; struct C *s;} Cellule;
typedef Cellule *Chaine;
Liste creer_liste() {
 Chaine l;
 l = NULL;
 return (Liste) l;
}
Element_liste lire_liste(Liste l, unsigned int rang) {
// précondition: 0<=rang<=longueur_liste(l)-1
 Chaine c;
 unsigned int i;
 if (rang >= longueur_liste(l)) {
  fprintf(stderr, "lire_liste: rang %d >= longueur liste %d\n",
    rang, longueur_liste(l));
  exit(1);
 }
 c = (Chaine)l;
 for (i=0; i<=rang; i++) c = c->s;
 return c->e;
}
Liste supprimer_liste(Liste l, unsigned int rang) {
// précondition: 0<=rang<=longueur_liste(l)-1
 Chaine c, p;
 unsigned int i;
 if (rang >= longueur_liste(l)) {
  fprintf(stderr, "supprimer_liste: rang %d >= longueur liste %d\n",
    rang, longueur_liste(l));
  exit(1);
 }
 c = (Chaine)l;
 if (c == c->s) {
  free(c);
  return NULL;
 }
 for (i=0; i<=rang; i++) {
  p = c;
  c = c->s;
 }
 p->s = c->s;
 free(c);
 if (rang > 0 && c == (Chaine)l) return (Liste)p;
 else return l;
}
Liste suffixer_liste(Liste l, Element_liste e) {
 Chaine c, p;
 c = (Chaine)l;
 p = (Chaine) malloc(sizeof(Cellule));
 p->e = e;
 if (c == NULL) {
  p->s = p;
 }
 else {
  p->s = c->s;
  c->s = p;
 }
 return (Liste)p;
}
Liste inserer_liste(Liste l, unsigned int rang, Element_liste e) {
// précondition: 0<=rang<=longueur_liste(l)
 Chaine c, p, q;
 unsigned int i;
 if (rang > longueur_liste(l)) {
  fprintf(stderr, "inserer_liste: rang %d > longueur liste %d\n",
    rang, longueur_liste(l));
  exit(1);
 }
 c = (Chaine)l;
 q = (Chaine) malloc(sizeof(Cellule));
 q->e = e;
 if (c == NULL) {
  q->s = p;
  return (Liste)q;
 }
 for (i=0; i<=rang; i++) {
  p = c;
  c = c->s;
 }
 q->s = c;
 p->s = q;
 if (rang > 0 && p == (Chaine)l) return (Liste)q;
 else return l;
}
unsigned int longueur_liste(Liste l) {
 unsigned int i = 0;
 Chaine c;
 if (l == NULL) return 0;
 c = (Chaine)l;
 do {
  i++;
  c = c->s;
 } while (c != (Chaine)l);
 return i;
}
Position positionner_liste(Liste l, unsigned int rang) {
// précondition: 0<=rang<=longueur_liste(l)-1
 Chaine c;
 unsigned int i;
 if (rang >= longueur_liste(l)) {
  fprintf(stderr, "positionner_liste: rang %d >= longueur liste %d\n",
    rang, longueur_liste(l));
  exit(1);
 }
 c = (Chaine)l;
 for (i=0; i<=rang; i++) c = c->s;
 return (Position)c;
}
Position suivant_liste(Liste l, Position p) {
// précondition: p!=positionner_liste(l, longueur_liste(l)-1)
 Chaine c;
 Position q;
 q = positionner_liste(l, longueur_liste(l) - 1);
 if (p == q) {
  fprintf(stderr, "suivant_liste: pas de suivant\n");
  exit(1);
 }
 c = ((Chaine)p)->s;
 return (Position)c;
}
Element_liste lire_courant_liste(Liste l, Position p) {
// précondition: longueur_liste(l)>0
 if (longueur_liste(l) == 0) {
  fprintf(stderr, "lire_courant_liste: liste vide\n");
  exit(1);
 }
 return ((Chaine)p)->e;
}

Voici le fichier liste_dernier.h

// fichier liste_dernier.h
#include "liste.h"
Liste suffixer_liste(Liste l, Element_liste e);
// l: Liste; e: Element_liste; i: unsigned int;
// axiomes:
//   0<=i<longueur_liste(l) =>
//     lire_liste(suffixer_liste(l, e), i) == lire_liste(l, i)
//   lire_liste(suffixer_liste(l, e), longueur(l)) == e

Nous pouvons maintenant donner l'implémentation des files en liste chaînée.

// fichier file_en_chaine.c
#include <stdio.h>
#include "file.h"
#include "liste_dernier.h"
File creer_file() {
 Liste l;
 l = creer_liste();
 return (File)l;
}
Element_file tete_file(File f) {
// précondition est_vide_file(f) == 0
 if (est_vide_file(f)) {
   fprintf(stderr, "tete_file: file vide\n");
   exit(1);
 }
 return lire_liste((Liste)f, 0);
}
File ajouter_file(File f, Element_file e) {
 return (File)suffixer_liste((Liste)f, e);
}
File retirer_file(File f) {
// précondition est_vide_file(f) == 0
 if (est_vide_file(f)) {
   fprintf(stderr, "retirer_file: file vide\n");
   exit(1);
 }
 return (File)supprimer_liste((Liste)f, 0);
}
unsigned int est_vide_file(File f) {
 return (((Liste)f) == NULL);
}

Voici le fichier main_chaine.c de mise en œuvre.

// fichier main_chaine.c
#include <stdio.h>
#include "element_int_file.h"
#include "file.h"
#define TAILLE_REP 128
main() {
 File f;
 Element_file e;
 int i;
 char rep[TAILLE_REP];
 f = creer_file();
 do {
  afficher_menu();
  fgets(rep, TAILLE_REP, stdin);
  if (rep[0] == 'q') exit(0);
  switch (rep[0]) {
   case 'r':
     if (est_vide_file(f)) printf("file vide\n");
     else f = retirer_file(f);
     break;
   case 'a':
     sscanf(&rep[1], "%d", &i);
     e = creer_element_file();
     e = ecrire_element_file(e, i);
     f = ajouter_file(f, e);
     break;
   case 't':
     if (est_vide_file(f)) printf("file vide\n");
     else printf("%d\n", lire_element_file(tete_file(f)));
     break;
   case 'v':
     if (est_vide_file(f)) printf("vrai\n");
     else printf("faux\n");
     break;
  }
 } while (1);
}
afficher_menu() {
 printf("menu:\n");
 printf("  (q)uitter\n");
 printf("  (a)jouter (i)\n");
 printf("  (r)etirer\n");
 printf("  la file est-elle (v)ide?\n");
 printf("  afficher la (t)ete de file\n");
}

Voici le fichier make_file_en_chaine .

# fichier make_file_en_chaine
main_chaine: main_chaine.o liste_en_chaine2.o file_en_chaine.o element_int_file.o
        cc -o main_chaine main_chaine.o liste_en_chaine2.o file_en_chaine.o element_int_file.o
main_chaine.o: main_chaine.c file.h file_def.h element_file_def.h element_int_file.h
        cc -c main_chaine.c
file_en_chaine.o: file_en_chaine.c file.h file_def.h liste_dernier.h liste.h liste_def.h element_file_def.h
        cc -c file_en_chaine.c
liste_en_chaine2.o: liste_en_chaine2.c liste.h liste_dernier.h liste_def.h element_file_def.h
        cc -c liste_en_chaine2.c
element_int_file.o: element_int_file.c element_int_file.h element_file_def.h
        cc -c element_int_file.c