Chapitre IV - Les files d’attente
1. Définition d’une file
La file est une structure de donnée, qui permet de stocker les données dans l'ordre FIFO
(First In First Out) - en français Premier Entré Premier Sorti).
La récupération des données sera faite dans l'ordre d'insertion.
L'implémentation des files en représentation chaînée est analogue à la SDA liste
simplement chaînée.
Pour simplifier l'accès à la queue de la file, nous allons opter pour un procédé de
mémorisation pour repérer la cellule queue (et non pas un procédé de calcul par
parcours comme pour les listes vues en cours). Ainsi une file est un enregistrement
contenant deux pointeurs, le premier vers la tête de la file d'attente et le deuxième vers
la queue de la file.
L'insertion dans la file se fera dans l'ordre normal, le 1er élément de la file sera le
premier élément saisi, donc sa position est au début de la file.
Le dernier élément aura la référence NULL comme élément suivant.
Une file vide admettra la constante NULL comme tête et queue.
Les opérations standard sur les files (en anglais Queue) sont :
Opération de création : creer_file
Opérations de consultation : vide_file et premier_file
Opérations de modification : enfiler (en anglais queue) et defiler (dequeue)
ASD2 – TI1-7 – Les files
1/5
2. Spécification d’une file chaînée : fichier file.h
/ fichier file.h /
Advertisement
typedef int element;
typedef struct cellule{
element information;
struct cellule * suivant;
} cellule;
typedef struct file{
cellule * tete;
cellule * queue;
} file;
void creer_file(file*);
int vide_file(file);
element premier_file(file);
void enfiler(file* , element);
void defiler(file*);
3. Implémentation d’une file chaînée : fichier file.c
NB : Les schémas ci-dessous sont donnés à titre indicatif, des corrections sur ces
schémas seront faites en classe.
ASD2 – TI1-7 – Les files
2/5
ASD2 – TI1-7 – Les files
3/5
/ fichier file.c /
#include "file.h"
#include <stdlib.h>
Advertisement
void creer_file(file * f){
f->tete = NULL;
f->queue = NULL;
}
int vide_file(file f){
return (f.tete == NULL) && (f.queue == NULL);
}
element premier_file(file f){
return f.tete->information;
}
void enfiler(file * f , element e){
cellule * n;
n = (cellule*)malloc(sizeof(cellule));
n->information = e;
n->suivant = NULL;
if(vide_file(*f))
f->tete = n;
else
f->queue->suivant = n;
f->queue = n;
}
void defiler(file * f){
cellule * p;
p = f->tete;
Advertisement
if(p->suivant == NULL){
f->tete = NULL;
f->queue = NULL;
free(p);
}
else{
f->tete = p->suivant;
free(p);
}
}
ASD2 – TI1-7 – Les files
4/5
4. Exercice : Utilisation du module file.h
Ecrire un programme principal qui utilise et teste efficacement le module file.h
/ fichier main.c /
#include <stdio.h>
#include "file.h"
void main() {
file f1, f2;
int i;
creer_file(&f1);
creer_file(&f2);
for(i = 0 ; i < 10 ; i++){
if(i%2 == 0)
Advertisement
else
enfiler(&f1 , i);
enfiler(&f2 , i);
}
printf("f1 : ");
while(!vide_file(f1)){
printf("%d\t" , premier_file(f1));
defiler(&f1);
}
printf("\nf2 : ");
while(!vide_file(f2)){
printf("%d\t" , premier_file(f2));
defiler(&f2);
}
}
Résultat de l’exécution
f1 : 0 2 4 6 8
f2 : 1 3 5 7 9
ASD2 – TI1-7 – Les files
5/5