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