Suivez-nous sur X
|
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z,
ALL
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z
|
|
A propos d'Obligement
|
|
David Brunet
|
|
|
|
En pratique : Algorithmes et structures de données - Les files
(Article écrit par Lucien Turski-Marcon et Bruno Bailluet et extrait d'Amiga News Tech - mars 1992)
|
|
Petite définition : une file est une structure de données représentée par un vecteur, où tout ajout d'élément
se fait en queue de file et tout retrait, en tête de file.
Nous avons donc affaire à une structure de données de type FIFO (First In, First Out), contrairement à
la pile qui, comme nous l'avons vu précédemment, est de type LIFO.
La file peut être représentée soit par un tableau, soit par une liste chaînée. Sa gestion n'est pas aussi
simple que celle de la pile, pour la bonne et simple raison qu'il existe plusieurs méthodes d'implantation :
la gestion contiguë, la gestion contiguë avec décalage et la gestion circulaire.
Nous allons donc étudier successivement ces trois méthodes, en décrivant pour chacune d'elles ses primitives :
initialisation de la file, ajout d'un élément (enfiler), retrait d'un élément (défiler), ainsi que les
grandes classiques booléennes que nous ne présentons plus : file_vide et file_pleine. Toutes les primitives
sont données pour les tableaux, afin que nous puissions effectuer des comparaisons valables entre les différentes méthodes.
Commençons par la plus simple : la gestion contiguë de la file. Partant d'une file vide nous devons déterminer
une valeur pour chacune de nos bornes (TETE et QUEUE). Ces valeurs ne peuvent pas être choisies au hasard,
puisqu'elles doivent vérifier le test file_vide. Il est hors de question de les initialiser n'importe comment
et d'utiliser une variable booléenne qui nous indiquerait l'état de la file. Dans ce premier cas, TETE vaut
1 et QUEUE vaut 0 : la file est vide si TETE = QUEUE + 1, ou plus simplement si TETE>QUEUE.
Si nous exécutons manuellement les différentes procédures et fonctions, nous constatons que les deux bornes
sont constamment incrémentées. Et je vous assure qu'il n'y a pas d'erreur : en effet, lorsque l'on enfile un
nouvel élément, il est tout à fait légitime de voir la QUEUE s'éloigner de la TETE. Il en est de même lorsque
l'on défile un élément : la TETE doit pointer sur la case suivant l'élément défilé. En fait, ce phénomène est
tout à fait normal. Lorsque nous posons un livre sur une pile, il ne bouge pas. Maintenant, si nous retirons celui qui se
trouve tout en dessous, les autres ne vont pas rester en suspension, ils vont descendre.
Le problème ne vient pas de la file mais du tableau. De ce fait, si nous n'opérons pas le décalage nous-mêmes,
nous risquons d'atteindre très rapidement les limites que nous nous étions fixées pour le tableau. Cette méthode a
le seul mérite d'être pédagogique, car elle permet d'aborder les files de manière simple et naturelle, et de
soulever quelques problèmes d'implantation. En pratique, elle est à proscrire !
Algorithme Recherche_Occurence ;
(* version pour les tableaux *)
Constante
Tete <- 1 ;
Max_Tableau <- 3 ;
Declaration
mafile : Tableau [1..3] De Caractere ;
motif : Chaine [3] ;
Trouve : Booleen ;
Phrase : Tableau [1..100] De Caractere ;
Sert_A_Rien : Caractere ;
Queue, Indice, Defil_NbFois, Defil_Cpt, Position : Entier ;
Fonction Cherche : Booleen
Debut
Si (mafile = motif) Alors
Cherche <- Vrai ;
Sinon
Cherche <- Faux ;
Fsi ;
Fin ;
Fonction File_Pleine : Booleen
Debut
Si (Queue = Max_Tableau) Alors
File_Pleine <- Vrai ;
Sinon
File_Pleine <- Faux ;
Fsi ;
Fin ;
Fonction File_Vide : Booleen
Debut
Si (Tete = (Queue + 1)) Alors
File_Vide <- Vrai ;
Sinon
File_Vide <- Faux ;
Fsi ;
Fin ;
Procedure Enfiler (lettre : Caractere)
Debut
Si non (File_Pleine) Alors
Queue <- Queue + 1 ;
mafile [Queue] <- lettre ;
Sinon
Afficher ("File Pleine") ;
Quitter () ;
Fsi ;
Fin ;
Fonction Defiler : Caractere
Declaration
compteur : Entier ;
Debut
Si non (File_Vide) Alors
Defiler <- mafile [Queue] ;
compteur <- 1 ;
Tant Que (compteur < Queue) Faire
mafile [compteur] <- mafile[compteur + 1] ;
compteur <- compteur + 1 ;
Ftq ;
Queue <- Queue - 1 ;
Sinon
Afficher ("File Vide") ;
Quitter () ;
Fsi ;
Fin ;
Debut
(* nous aurions pu aussi saisir cette phrase ainsi que *)
(* le motif a rechercher. Encore un bon petit exercice *)
Phrase = "Only AMIGA makes it possible !!!" ;
motif = "le " ;
(* ces 2 lignes font office de Procedure Init *)
Queue = 0 ;
Indice = 1 ;
Tant Que non(File_Pleine) Faire
Enfiler (Phrase [Indice]) ;
Indice <- Indice + 1 ;
Ftq ;
Trouve <- Cherche() ;
Tant Que non(Trouve) Et (Indice < Longueur(Phrase)) Faire
(* Cette fonction Emplacement a pour but de renvoyer *)
(* la position de motif[1] dans la file en ignorant *)
(* le premier element de celle-ci. Si cet element *)
(* n'est pas trouve la fonction renvoie 0. *)
Position <- Emplacement (mafile + 1, motif[1]);
Si (Position = 0) Alors
Defil_NbFois <- Max_Tableau ;
Sinon
Defile_NbFois <- Position - 1 ;
Fsi ;
(* pour une fois nous n'utilisons pas les elements que *)
(* nous retourne la fonction defile car nous n'avons nul *)
(* besoin des caracteres qui n'appartiennent pas au motif. *)
Defil_Cpt <- 0 ;
Tant Que (Defil_Cpt < Defil_NbFois) Faire
Sert_A_Rien <- Defiler () ;
Defile_Cpt <- Defile_Cpt + 1 ;
Ftq ;
(* et l'on recommence en enfilant de nouveau autant de *)
(* caracteres qu'il en a ete precedemment defiles *)
Tant Que non(File_Pleine) Faire
Enfiler (Phrase [Indice]) ;
Indice <- Indice + 1 ;
Ftq ;
Trouve <- Cherche() ;
Ftq ;
Si (Trouve = Vrai) Alors
Afficher ("Trouve\n") ;
Sinon
Afficher ("Non trouve\n") ;
Fsi ;
Fin ;
|
Listing 2 : l'implémentation en C
/* Compile avec LC -L -O */
/* Quelques mots sur le programme qui suit. */
/* Le but est de rechercher une sous-chaine dans une chaine
plus grande. Ici, la longueur de la sous-chaine est 3
et elle contient "le ".
Vous pouvez modifier la sous-chaine a travers la variable
motif (N'OUBLIEZ PAS DE MODIFIER LA CONSTANTE MAX QUI DOIT
ETRE EGALE A LA LONGUEUR DE motif).
*/
/* Je vais maintenant vous exposer l'algorithme retenu pour
effectuer cette recherche.
L'algorithme est extremement simple comme vous allez pouvoir
le constater et ceci pour deux raisons :
1. Le but de l'article n'etant pas axe sur l'apparition
de motif mais sur la file, il fallait que l'exemple
soit a la portee de chacun (tout en n'etant pas
totalement inutile)
2. La seconde raison est que cet algorithme sort tout
droit de nos cerveaux embrumes.
Pour nous simplifier la tache nous avons pris une file de meme
taille que notre motif.
Algo :
On commence par remplir la file puis tant que la sous-chaine
n'est pas trouvee on regarde dans la file si on trouve la
premiere lettre de la sous-chaine recherchee.
Si cette lettre n'est pas dans la file, on n'a aucune chance
de trouver notre sous-chaine donc on vide la file et on la
remplit de nouveau puis on recommence au debut.
Si cette lettre existe dans notre file, elle est susceptible
d'etre suivie par les autres lettres de notre motif. Pour le
savoir, il suffit de defiler jusqu'a ce que cette lettre se
trouve en premiere position dans notre file et de remplir la
file.
Apres cela, il nous reste a tester si la file contient la
sous-chaine.
Si c'est le cas, c'est GAGNE !!!.
Sinon on recommence au debut.
*/
/* Bon assez parle, voila qui devrait regaler votre compilateur
prefere. Si vous avez des questions, n'hesitez pas nous ferons
de notre mieux pour vous repondre.
*/
#include <stdio.h>
#include <string.h>
#define TETE 0
/* L'indice TETE est une constante initialisee a 0
car en C les tableaux commencent a l'indice 0
*/
#define MAX 3 /* On indique ici la taille de notre file */
int cherche (void);
void enfiler (char);
char defiler (void);
int file_pleine (void);
int file_vide (void);
char *mafile = NULL, *motif = "le ";
/* La variable motif contient la sous-chaine a rechercher
Le pointeur mafile contient l'adresse de base de notre file
*/
int trouve, queue; /* Declaration d'une sentinelle (trouve) nous
indiquant si la sous-chaine a ete trouvee
ou pas, et de la variable queue nous
permettant de savoir ou se trouve la fin
de notre file dans notre tableau
*/
void main()
{
char *chaine = "Only AMIGA makes it possible !!!", *courant;
/* Le pointeur chaine contient l'adresse de base de la chaine
dans laquelle doit s'effectuer la recherche
*/
char *adr_a;
int j, compteur;
courant = chaine;
queue = -1; /* Initialisation de notre queue de file */
/* Allocation de MAX elements pour notre file */
mafile = (char *) malloc (MAX);
if (mafile == NULL)
{
puts ("Probleme d'allocation memoire !!!");
exit (5);
}
/* Remplissage de notre file */
while (file_pleine() == 0)
{
enfiler (*courant);
courant++;
}
trouve = cherche(); /* Test si le contenu de notre file est
le meme que celui de la sous-chaine
recherchee
*/
/* Tant que la sous-chaine n'est pas trouvee et que l'on n'a
pas atteint la fin de la chaine
*/
while ((trouve == 0) && ((courant-chaine) < strlen(chaine)))
{
/* Recherche dans la file (en ignorant le premier element
sinon si l'occurrence existe bien en premiere position
dans notre file mais que la sous-chaine n'est pas
trouvee ON BOUCLE)
si une occurrence du premier caractere de notre
sous-chaine existe et si c'est le cas, on stocke son
adresse dans adr_a
*/
adr_a = strchr (mafile+1,*motif);
if (adr_a == NULL)
/* Si adr_a = NULL alors notre file ne contient pas
le premier caractere de notre sous-chaine.
Par consequent, nous pouvons vider la file
completement
*/
compteur = MAX;
else
/* Si, au contraire, le premier caractere de notre
sous-chaine est trouve dans notre file, il faut
defiler jusqu'a ce caractere
*/
compteur = adr_a - mafile;
for (j = 0; j < compteur; j++)
defiler();
/* Remplissage de la file afin de pouvoir tester a
nouveau si la sous-chaine a ete trouvee
*/
while (file_pleine() == 0)
{
enfiler (*courant);
courant++;
}
trouve = cherche();
}
/* Ce test parle de lui-meme */
if (trouve == 1)
printf ("Trouve\n");
else
printf ("Non trouve\n");
free (mafile); /* Soyons franc-jeu, liberons la memoire */
}
int cherche (void)
{
/* Si la file contient la sous-chaine recherchee
renvoie 1
Sinon
renvoie 0
*/
if (strncmp (mafile,motif,MAX) == 0)
return (1);
else
return (0);
}
int file_pleine (void)
{
/* Le test doit porter sur MAX - 1
puisque les tableaux commencent en 0
*/
if (queue == (MAX - 1))
return (1);
else
return (0);
}
/* Si vous desirez plus de details quant aux fonctions ci-dessous
referez vous aux primitives donnees plus haut
*/
int file_vide (void)
{
if (TETE == (queue + 1))
return (1);
else
return (0);
}
void enfiler (char carac)
{
if (file_pleine() == 0)
{
queue++;
mafile[queue] = carac;
}
else
puts ("File PLEINE");
}
char defiler (void)
{
char val = '\0';
int i;
if (file_vide() == 0)
{
val = mafile[queue];
i = 0;
while (i < queue)
{
mafile[i] = mafile[i + 1];
i++;
}
queue--;
}
else
puts ("File VIDE");
return (val);
}
|
Pour remédier au problème posé par la gestion contigüe des files, une alternative nous est offerte, la
gestion contigüe de la file avec décalage : nous devons nous-mêmes effectuer l'opération de décalage. Pour cela,
nous devons imposer certaines règles : la tête devient une constante et seule la queue varie au fur et à mesure
des appels aux procédures d'enfilement et de défilement. Voyons ensemble l'unique procédure à modifier.
Comme nous le constatons, peu de modifications sont à apporter. En contrepartie, nous remarquons que notre file est
mieux gérée puisque seule une des deux bornes bouge. De ce fait, nous occupons réellement chacune des cases du
tableau (la file ne sera pleine que lorsque toutes les cases du tableau seront utilisées). Cependant, il reste
tout de même un inconvénient, qui est le temps de permutation de chaque case. Sur une file de grande taille, le
temps consacré à la permutation peut s'avérer excessivement long. Ceci nous amène à considérer une troisième méthode
appelée gestion circulaire de la file.
Les files circulaires
La file circulaire se propose de remédier à ces inconvénients (merci la file circulaire) en faisant varier ses
deux pointeurs (tête et queue) sans que la notion de borne du tableau n'intervienne. Éclaircissons un peu les
choses par un exemple graphique :
Nous avons rempli notre file avec les 8 premières lettres de l'alphabet. A l'étape (1) nous décidons de défiler
un élément, en l'occurrence, le "A". Le pointeur "Tete" est donc incrémenté et pointe maintenant sur la seconde
case du tableau. A l'étape (2), nous enfilons la lettre "I". Comme la "Queue" pointe sur la dernière case du
tableau, nous la ramenons en première position (la place de la case 1 étant maintenant libre).
Le schéma (2) est le résultat de ces deux opérations.
Notre exemple n'a pas été choisi au hasard. Nous avons vu plus haut que le test filevide() était vérifié si Tete>Queue.
Or, dans le second schéma, la "Tete" est bien supérieure à la "Queue", mais notre file est pleine... Déjà, nous
sentons arriver les prémices des premières ambiguïtés. En effet, les deux pointeurs sont désormais gérés de la même
manière et la notion de tête et de queue apparaît différemment. La "Tete" peut ne pas être inférieure à la "Queue"
(comme dans l'exemple). Voyons sans plus tarder les primitives.
Nous ne saurons trop vous conseiller de tester le déroulement de ces primitives sur un petit exemple de votre choix.
La difficulté réside dans les tests d'évaluation de l'état de la file...
#include <exec/types.h>
#define MAX 3
int tete, queue ;
BOOL filevide, filepleine ;
VOID enfile (char) ;
VOID batimotif (VOID) ;
VOID defile (VOID) ;
BOOL cherche (VOID) ;
/* File d'origine qui subira toutes les primitives et a partir
de laquelle nous construirons buildmotif. La file etant
geree de maniere circulaire, nous ne pouvons pas la tester
comme un motif a rechercher. Car bien que toutes les lettres
y soient presentes, ces dernieres sont en desordres */
char file[MAX+1] = {'*', '*', '*', '\0'} ;
/* chaine a parcourir */
char *chaine = "Only AMIGA makes it possible !!!" ;
/* motif que l'on souhaite retrouver, et pointeur de parcours
sur la chaine de depart */
char *motif = "!! ", *courant = NULL ;
/* le motif qui sera construit a partir de la file et qui
servira pour tous les tests */
char buildmotif[sizeof(motif)] = {'*', '*', '*', '\0'} ;
main (char **argv, int argc)
{
BOOL trouve = FALSE ;
int cptdefile = 0 ;
tete = 0 ;
queue = -1 ;
/* ces 2 booleens nous permettent de connaitre les differents
etats de notre file. Ils sont combines dans les tests afin
d'eviter que notre queue (ou la votre, mais cela ne nous
regarde pas !!) ne morde la tete */
filevide = TRUE ;
filepleine = FALSE ;
/* cette ligne permet de voir le cheminement des lettres dans
la file ainsi que les differents etats de cette derniere.
Elle est facultative mais peut aider a comprender le
mecanisme. */
printf ("file : %s \t tete : %d \t queue : %d \t filevide :
%d \t filepleine : %d \n", file, tete, queue,
filevide, filepleine) ;
courant = chaine ;
/* remplissage initial de la file a partir de la chaine */
while (!filepleine)
{
enfile (*courant) ;
courant++ ;
}
/* remettre les lettres dans le bon ordre afin d'effectuer
un test coherent avec le motif a rechercher. La file etant
etant geree de maniere circulaire, les lettres ne sont pas
redecalees a partir de la tete mais enfilees les unes a la
suite des autres. */
batimotif () ;
trouve = cherche () ;
while ((!trouve) && ((courant - chaine) < strlen (chaine)))
{
/* puisque cherche n'a pas trouve notre motif nous pouvons
defiler le premier caractere sans risque. Mais pas les
suivants car il se peut que le motif debute un peu plus
loin. Exple : motif = "mad" et buildmotif = "mma".
cherche () nous dit que les deux chaines sont differentes.
Or il se peut qu'apres "mma" il y ait un 'd'. Donc dans tous
les cas nous defilons le premier caracteres et autant qu'il
y en a de differents apres. Dans notre exemple nous ne defi
lerons que le premier 'm'. Si la premiere lettre avait ete
conservee nous aurions boucle a l'infinie. En effet n'ayant
rien defile nous nous retrouvons avec la chaine de depart
"mma". Nous ne pourrions plu enfiler et par la meme occasion
avance dans la chaine a parcourir */
defile () ;
cptdefile = 1 ;
while ((buildmotif[cptdefile] != motif[0]) &&
(cptdefile != MAX))
{
cptdefile ++ ;
defile () ;
}
while (!filepleine)
{
enfile (*courant) ;
courant ++ ;
}
batimotif () ;
trouve = cherche () ;
}
if (trouve)
printf ("le motif [%s] est present dans :\n%s\n\n",
motif, chaine);
else
printf ("le motif [%s] n'existe pas.\n", motif);
exit (0) ;
}
VOID enfile (char symbol)
{
if (!filepleine)
{
if (queue == MAX - 1)
queue = 0 ;
else
queue++ ;
file [queue] = symbol ;
filevide = FALSE ;
if ( ((tete == 0) && (queue == MAX - 1)) ||
((queue < MAX - 1) && (tete == queue + 1)) )
filepleine = TRUE ;
}
else
printf ("file pleine \n") ;
/* encore une ligne d'aide a la comprehension */
printf ("file : %s \t tete : %d \t queue : %d \t filevide :
%d \t filepleine : %d \n", file, tete, queue,
filevide, filepleine) ;
}
VOID defile (VOID)
{
if (!filevide)
{
file [tete] = '*' ;
if (tete == MAX - 1)
tete = 0 ;
else
tete++ ;
filepleine = FALSE ;
if ( ((tete == 0) && (queue == MAX - 1)) ||
((queue < MAX - 1) && (tete == queue + 1)) )
filevide = TRUE ;
}
else
printf ("file vide \n") ;
/* toujours elle */
printf ("file : %s \t tete : %d \t queue : %d \t filevide :
%d \t filepleine : %d \n", file, tete, queue,
filevide, filepleine) ;
}
BOOL cherche (VOID)
{
if (strncmp (buildmotif,motif,MAX) == 0)
return (TRUE);
else
return (FALSE);
}
VOID batimotif (VOID)
{
int cptfile, cptbuild ;
cptbuild = 0 ;
/* nous recuperons d'abord toutes les lettres de la tete */
/* a la fin de la file. */
for (cptfile = tete ; cptfile < MAX ; cptfile ++, cptbuild ++)
buildmotif[cptbuild] = file[cptfile] ;
/* puis de la queue jusqu'a la tete */
for (cptfile = 0 ; cptfile < tete ; cptfile ++, cptbuild ++)
buildmotif[cptbuild] = file[cptfile] ;
}
|
|