Chapitre 5

Chapitre 5
Structure de données :
Files
1. Définition et types
La file d’attente est une structure qui permet de stocker des éléments dans un ordre donné et
de les retirer dans le même ordre, c’est à dire selon le protocole FIFO ’first in first out’.
« On ajoute toujours un élément en queue de liste et on retire celui qui est en tête ».
Selon le type d’implémentation, on distingue deux types de files:
▪ File statique (contiguë): Implémentation par un tableau.

▪ File dynamique: Implémentation par une liste chainée
2. Files statiques
2.1. Définition de type :

La définition du type File (statique) est comme suit :
Type Structure Pile

début
Tab: Tableau[MAX] d'Éléments ;
Tête : entier ; // indice de premier de la File.

Queue: entier ; // indice de dernier élément inséré dans la File.
Fin
L’implémentation de files statiques peut être réalisée par décalage en utilisant un tableau
avec une tête fixe, toujours à 1, et une queue variable. Elle peut être aussi réalisée par flot en
utilisant un tableau circulaire où la tête et la queue sont toutes les deux variables
2.2. Implémentation par tableau (Par décalage)

Tête fixe et queue variable. Elle souffre du problème de décalage à chaque défilement.
- La file est vide si Queue = 0
- La file est pleine si Queue = Max
- La file est vide si Tète = Queue
2.3. Opérations usuelles sur les files statiques
Dans cette section nous présentons les opérations primitives sur les files statiques.
1) La procédure initialiser :
En C :
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
typedef struct {
int tableau[MAX];
int tete;
int queue;
} File;
void initialiser(File *file) {

file->tete = 0;
file->queue = 0;
}
2) La fonction EstPleine :
En C :
int EstPleine (File *file) {
return file->queue == MAX;
}
3) La fonction EstVide :
En C :
int estVide(File *file) {
return file->tete == file->queue;
}
4) La procédure Enfiler :
En C :
void enfiler(File *file, int element) {
if (estPleine(file)) {
printf("Erreur : La file est pleine\n");
return;
}
file->tableau[file->queue] = element;
file->queue ++;
}
5) La fonction Défiler :
En C :
int defiler(File *file) {
if (estVide(file)) {
printf("Erreur : La file est vide\n");
return -1; // Valeur d'erreur
}
int element = file->tableau[file->tete];

file->tete = (file->tete + 1) % MAX;
return element;
}
6) La procédure Afficher :
En C :
void afficher(File *file) {
printf("La file est vide\n");
return;
}
int i = file->tete;
while (i != file->queue) {
printf("%d ", file->tableau[i]);
i = (i + 1) % MAX;
}
printf("\n");
}
3. Files dynamiques
C’est une Liste chainée où le défilement se fait seulement à la tête et l’enfilement se fait
seulement à la queue de la liste.
3.1. Définition de type File dynamique
La définition du type File (dynamique) est comme suit :
Type
Structure Maillion
Ele : typeq;
suivant: * Maillion;
fin
Type Structure File
Début
Tête : *Maillon ; // Gade l’adresse de la tête de la File.
Queue: *Maillon; // Gade l’adresse ddernier élément inséré dans la File.
Fin
Dans le langage C, on définira le type File (dynamique) comme suit :
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {

int valeur;
struct Node *suivant;
} Node;
typedef struct {
Node *tete;
Node *queue;
} File;
3.2. Opérations primitives

1) La procédure Initialiser :
En C :
void initialiser(File *file) {
file->tete = NULL;
file->queue = NULL;
}
2) La Fonction EstVide :
En C :
int estVide(File *file) {
return file->tete == NULL;

}
3) La Procédure Enfiler:
En C :
void enfiler(File *file, int valeur) {
Node *nouveauNode = (Node *)malloc(sizeof(Node));
if (nouveauNode == NULL) {
printf("Erreur d'allocation mémoire\n");
return;
}
nouveauNode->valeur = valeur;
nouveauNode->suivant = NULL;
file->tete = nouveauNode;
file->queue = nouveauNode;
} else {
file->queue->suivant = nouveauNode;
file->queue = nouveauNode;
}
}
4) La Fonction Défiler :
En C :
int defiler(File *file) {
}
Node *ancienTete = file->tete;

int valeur = ancienTete->valeur;
file->tete = file->tete->suivant;
if (file->tete == NULL) {
file->queue = NULL;
}
free(ancienTete);
return valeur;
}
5) La procédure Afficher :
En C :
void afficher(File *file) {
printf("La file est vide\n");
return;
}
Node *courant = file->tete;

while (courant != NULL) {
printf("%d ", courant->valeur);
courant = courant->suivant;
}
printf("\n");
}
6) La Fonction Taille :
En C :
int taille(File *file) {
int compteur = 0;
Node *courant = file->tete;
while (courant != NULL) {

compteur++;
courant = courant->suivant;
}
return compteur;
}
7) La Fonction tête : Qui retourne l’élément en tête de la file.

En C :
int tete(File *file) {
}
return file->tete->valeur;
}
TD5
Exercice 1:
Nous considérons des files d’attente représentant des nombres entiers sous forme de chiffres. Les chiffres
composant le nombre sont enfilés dans la file du droit vers la gauche. Dans l’exemple sous-dessous la file
F contient la représentation du nombre entier 942537 sous forme de chiffres.
F 7 3 5 2 4 9
On vous demande de :
1. Ecrire la fonction egale (F1, F2) : permettant de vérifier si la file F1 et la file F2 représentent le même
nombre.
2. Ecrire la fonction inverse (F) qui retourne une file F1 contenant le nombre inverse du nombre
représenté par la file F. L’inverse d’un nombre est le nombre composé de mêmes chiffres mais dans
l’ordre inverse.
3. Ecrire la procédure decomposer (F) permettant de décomposer le nombre représenté par la file F en
deux nombre N1 et N2 composés du même nombre de chiffres. La procédure affiche N1 et N2 si la
décomposition est possible, sinon elle affiche un message d’erreur.
Exemple : La décomposition du nombre (942 537) donne N1= 942 et N2 =537.
Exercice 2:
Contexte :
Une banque utilise un système de gestion des clients pour optimiser son service au guichet. Les clients
arrivent les uns après les autres et doivent être servis dans l'ordre d'arrivée. Chaque client a un numéro
unique et un temps estimé de service.
Consignes
1. Structure des données :

o Chaque client est représenté par une structure contenant:
▪ Numéro de client (entier).
▪ Temps estimé de service (entier en minutes).
o Utilisez une file dynamique pour gérer les clients.
2. Fonctions principales : Implémentez les fonctions suivantes :
o ajouterClient : Ajouter un nouveau client à la file d'attente avec un numéro unique et un
temps de service.
o servirClient : Retirer le client en tête de la file et afficher son numéro et son temps de
service.
o afficherClients : Afficher tous les clients encore en attente, avec leur numéro et leur temps
de service.
o estVide : Vérifier si la file est vide.
o taille : Retourner le nombre de clients dans la file.
o tempsTotalAttente : Calculer le temps total estimé pour servir tous les clients encore dans
la file.
3. Simulation :
o Simulez l'arrivée de 5 clients avec des temps de service aléatoires entre 2 et 10 minutes.
o Affichez la file après l'arrivée de chaque client.
o Servez les clients un par un en affichant leurs informations.
o Affichez la file restante et le temps total d'attente après chaque service.

Chapitre 5

Transféré par

Droits d'auteur :

Formats disponibles

Chapitre 5

Transféré par

Informations du document

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Chapitre 5

Transféré par

Droits d'auteur :

Formats disponibles

Chapitre 5

Selon le type d’implémentation, on distingue deux types de files:

▪ File statique (contiguë): Implémentation par un tableau.

2.1. Définition de type :

Type Structure Pile

Tête : entier ; // indice de premier de la File.

2.2. Implémentation par tableau (Par décalage)

2.3. Opérations usuelles sur les files statiques

void initialiser(File *file) {

int element = file->tableau[file->tete];

typedef struct Node {

3.2. Opérations primitives

return file->tete == NULL;

Node *ancienTete = file->tete;

Node *courant = file->tete;

while (courant != NULL) {

7) La Fonction tête : Qui retourne l’élément en tête de la file.

1. Structure des données :

Vous aimerez peut-être aussi