Chapitre IV – Les files d’attente
- 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
- Spécification d’une file chaînée : fichier file.h
/* fichier file.h */ 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*);
- 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>
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;
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
- 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) enfiler(&f1 , i); else 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
télécharger gratuitement cours algorithmique : Les files d’attente
