Algo (les files d'attentes)

LES FILES D’ATTENTE

Introduction

Les files d’attente représentent des structures de données qui fonctionnent avec le principe FIFO. Les files d’attente sont utilisées dans les applications de gestion de réservations. La manipulation d’une file est basée sur l’utilisation de ces primitives lesquelles sont réalisées soit avec les tableaux, soit avec les pointeurs.

Les primitives sont des modules qui permettent d’appliquer des traitements spécifiques à la file. Elles sont :

Initfile ()

Filevide ()

Filepleine () = modules

Enfiler () = ajouterfile ()

Defiler () = Enleverfile ()

La primitive Initfile () : permet d’initialiser les arguments d’une file.

La primitive Filevide () : reçoit les arguments d’une file puis renvoie vrai si la file est vide et faux dans le cas contraire.

La primitive Filepleine () : reçoit les données d’une file puis renvoie vrai si la file est pleine et faux dans le cas contraire.

La primitive Enfiler () : permet d’ajouter une valeur passée en paramètre dans une file. L’ajout se fait que si la file n’est pas pleine, si elle était vide, elle se fait en tête de file sinon en queue de file.

La primitive Defiler () : permet d’enlever la valeur qui est en tête de file et de la sauvegardé dans une variable pour d’éventuel traitement. Toutes valeurs extraites d’une file y sont automatiquement supprimées ce qui signifie que la fille devient vide si elle était composée d’un élément.

Implémentation des files avec les pointeurs

Une file sous forme de pointeur à deux voies d’accès tête et queue ; Tête contient l’adresse du premier élément et queue l’adresse du dernier élément.

Déclaration

Syntaxe : Type nomFile =↑ Structure

DEBUT

Info(s) : type(s)

Suiv : nomFile

FIN

Var tete, queue :nomFile

Ex1 :file d’attente d’entiers réalisée avec les pointeurs

Type File = ↑Structure

DEBUT

Info(s) : entiers

Suiv : File

FIN

Var tete, queue :File

Ex2 : file d’attente de processus. Processeur (id, nom, etat, taille)

Type FileProcessus =↑Structure

DEBUT

Id : entier

Nom : chaine

Taille : reel

Suiv : FileProcessus

FIN

Var tete, queue : FileProcessus

Manipulation des primitives avec les pointeurs

La primitive InitFile ()

Pour initialiser une file réalisée avec les pointeurs, il faut affecter à tête et à queue la valeur NIL quel que soit le type de valeur de la file.

Application

Soit une file d’étudiant un client est caractérisé par son id, son nom, son prénom, son adresse, son capital. Ecrire un module qui réalise la primitive InitFile ().

Type client =↑ Structure

DEBUT

Id : entier

Nom, prenom, adr : chaine

capital : entier

FIN

Type File = ↑ Structure

DEBUT

Info : client

Suiv : File

FIN

Var tete, queue :File

Procedure initFile (D/R tete, queue : file)

DEBUT

TeteNIL

QueueNIL

FIN

La primitive Filevide ()

Une file d’attente sous forme de pointeur est considérée comme vide si tête = queue= NIL, dans ce cas la primitive renvoie la valeur vraie sinon elle renvoie faux

Application

En considérant la même file d’étudiant, écrire un module qui permet de créer la primitive Filevide ()

Fonction Filevide (donnes tete, queue : file) : booleen

DEBUT

Si (tete = NIL et queue=NIL) alors

Retourner (vrai)

Sinon

Retourner (faux)

Finsi

FIN

La primitive Filepleine ()

Une file comme le pointeur est considérée comme telle lorsque toutes les ressources sont occupées cd. Il n’existe plus d’espace mémoire pour ajouter un nouvel élément.

Application

En considérant la même file de clients, écrire le module qui réalise la primitive Filepleine ().

Fonction filepleine(données tete, queue : file) booleen

Var f : file

Debut

Allouer(f)

Si(f= NIL= alors

Retourner(vrai)

Sinon

Retourner(faux)

Finsi

Fin

La primitive Enfiler ()

Enfiler reçoit une valeur et l’ajoute dans la file. Si elle est vide l’élément à ajouter sera premier et dernier sinon l’élément sera placé à la dernière position.

Application

En considérant la même de clients, ecrire le module qui réalise la primitive Enfiler ()

Procedure Enfiler (données val : client D/R tete ;queue : file)

Var pval : file

Debut

Si(filepleine(tete, queue)= vrai) alors

Ecrire ‘la file est pleine donc impossible d’ajouter’

Sinon

Allouer(pval)

Pval ↑.infoval

Pval ↑.suivNIL

Si( filevide(tete,queue)=vrai) alors

Tetepval

Queuepval

Sinon

Queue ↑.suivpval

Queuepval

Finsi

Finsi

Fin

La primitive Defiler ()

Elle permet d’enlever la valeur qui est en tête de file. Ce qui peut la Filevide () si elle avait un élément.

Application

En considérant la même de clients, ecrire le module qui réalise la primitive Defiler ()

Procedure Enfiler (resultat val : client | D/R tete ;queue : file)

Var pval : file

Debut

Si (filevide (tete, queue)= vrai) alors

Ecrire ‘la file est pleine donc impossible d’extraire’

Sinon

Valtete ↑.info

Pval tete

Si( tete= queue) alors

initfile(Tete,queue)

Sinon

tetetete ↑.suiv

Finsi

Liberer(pval)

PvalNIL

Finsi

Fin

Exercice1 :

Soit un tableau de 50 clients, écrire un module qui transfère dans une file d’attente les clients dont le chiffre d’affaire > 150.000.000. Client (id, nom, prenom, adresse,

...