TP N°7 - Les Files
Exercice 1 : Implémentation d’une file à partir d’un tableau - Solution 1
On peut représenter une file par un tableau (contigue).
On définira la file (file d’entier) en C comme suit :
typedef int typeElem;
#define Max 20
typedef struct
{
int queue;
typeElem tab[Max];
} file;
Ecrire les fonctions :
initFile : Initialisation de la file
fileVide : teste si la file est vide ou non
filePleine : teste si la file est pleine ou non
enfiler : ajoute un élément à la file (en queue de file) si la file n’est pas pleine
desemfiler : enlève l’élément en tête de la file si la file n’est pas vide
consulterTeteFile : consulte l’élément en tête de la file (sans l’enlever)
consulterQueueFile : consulte l’élément en queue de la file (sans l’enlever)
Remarque : Le premier élément de la file (si la file n’est pas vide) sera toujours mis à la position 0 (c.a.d la tete de la file est toujours egale a 0). Apres avoir désemfilé un élément de la position 0, il faudra décaler les éléments restants de la file d’une position vers la gauche pour avoir le prochain élément à desemfiler dans la position 0 du tableau. On intialisera queue à -1.
Les prototypes de ces fonctions sont les suivants :
void initFile(file *F) ;
int fileVide(file *F) ;
int filePleine(file *F) ;
void enfiler(file *F, typeElem x) ;
void desemfiler(file *F, typeElem *x) ;
void consulterTeteFile(file *F, typeElem *x) ;
void consulterQueueFile(file *F, typeElem *x) ;
Exercice 2 : Implémentation d’une file à partir d’un tableau - Solution 2
Pour éviter qu’à chaque fois qu’on desemfile un élément de la file de décaler tous les éléments de la file qui suivent on ajoute le champ tete qui contiendra l’indice du premier élément de la file. Apres avoir desemfile un élément on incrementera le champ tete. Evidemment on risque avec cette solution d’avoir des positions vides au début du tableau alors que la queue arrive à la fin du tableau. Donc ce qu’on va faire c’est lorsqu'on a un element a enfiler et que la queue arrive à la fin du tableau on fera un décalage des éléments de la file vers le debut du tableau, si cela est possible.
On initialisera tete à 0 et queue à -1.
On définira la file (file d’entiers) en C comme suit :
typedef int typeElem;
#define Max 20
typedef struct
{
int tete, queue;
typeElem tab[Max];
} file;
Ecrire les mêmes fonctions précédentes :
void initFile(file *F) ;
int fileVide(file *F) ;
int filePleine(file *F) ;
void enfiler(file *F, typeElem x) ;
void desemfiler(file *F, typeElem *x) ;
void consulterTeteFile(file *F, typeElem *x) ;
void consulterQueueFile(file *F, typeElem *x) ;
Exercice 3 : Implementation d’une file à partir d’un tableau - Solution 3 : Utilisation d’un Tableau Circulaire
Pour éviter de faire des décalages lorsque la queue atteint la dernière position du tableau on peut enfiler les éléments à partir des premières positions vides du tableau en considérant dans ce cas le tableau comme un tableau circulaire. Dans ce cas lorsque queue arrive à la valeur (Max – 1) sa prochaine valeur sera 0. Donc on incrementera queue de 1 modulo Max. On fera la même chose avec tete pour desemfiler un élément; après avoir desemfiler un élément on incrementera tete de 1 modulo Max.
Remarque :
On intialisera tete et queue a 0.
Il y’a un probleme pour distinguer la file vide ou pleine car lorsque la file est vide on aura (tete = queue) et de meme lorsque la file est pleine.
Il y’a 2 solutions à ce probleme. Utiliser un compteur qui compte à tout moment le nombre d’élément dans la file. Ce compteur sera incrementé chaque fois qu'un élément est enfilé dans la file et est décrementé chaque fois qu'un élément est désemfilé de la file. Lorsque le compteur est à 0 la file est vide et lorsque le compteur est egale à Max la file est pleine.
L’autre solution est pour un tableau de Max éléments n’admettre que (Max – 1) éléments au maximum dans le tableau. Dans ce cas la file est vide lorsque (tete = queue) et la file est pleine lorsque ( ((queue + 1) mod Max) = tete).
Utiliser la 2eme solution pour implémenter les fonctions :
void initFile(file *F) ;
int fileVide(file *F) ;
int filePleine(file *F) ;
void enfiler(file *F, typeElem x) ;
void desemfiler(file *F, typeElem *x) ;
void consulterTeteFile(file *F, typeElem *x) ;
void consulterQueueFile(file *F, typeElem *x) ;
Exercice 4 : Implémentation d’une file à partir d’une liste chainée simple
On peut représenter une file par une liste chainée simple.
On définira la file (file d'entiers) en C comme :
typedef int typeElem;
typedef struct fileNoeud
{
typeElem element;
struct fileNoeud *suivant;
} fileNoeud;
typedef fileNoeud *file;
Ecrire les fonctions :
initFile : Initialisation de la file
fileVide : teste si la file est vide ou non
filePleine : teste si la file est pleine ou non
enfiler : ajoute un élément à la file (en queue de file) si la file n’est pas pleine
desemfiler : enlève l’élément en tête de la file si la file n’est pas vide
consulterTeteFile : consulte l’élément en tête de la file (sans l’enlever)
consulterQueueFile : consulte l’élément en queue de la file (sans l’enlever)
Ces fonctions ont les mêmes prototypes que dans l’exercice 1.
Il faudra d’abord écrire la fonction creerNoeud() qui alloue un élément de type pileNoeud. Cette fonction sera appelé par la fonction empiler().
Il faut noter que la file a été implementé dans les exercices 1 a 4 de telle façon qu’on peut utiliser n'importe laquelle de ces implementations dans une application quelconque sur les files.
Exercice 5 : Implémentation d’une file à priorite en utilisant une heap (tas)
Une file à priorité est une file où chaque élément possède une priorité. L’élément qui sera servi en premier est toujours l’élément le plus prioritaire.
Une file à priorité peut être implementée de différentes manières. Elle peut être implementée en utlisant un tableau non trié, un tableau trié, une liste non triée ou une liste triée. Mais toutes ces méthodes d’implementer une liste prioritaire ne sont pas trés efficace en terme de temps d’execution des opérations inserer un élément ou enlever l'élément le plus prioritaire de la liste.
Une méthode plus efficace est d’utiliser une heap. Une heap est un arbre binaire (arbre dont chaque nœud possède au maximum 2 enfants) complet dont chaque nœud a une valeur plus petite (ou plus grande) que chacun de ces enfants. Une valeur plus petite veut dire que l'élément est plus prioritaire. Un arbre binaire est dit complet lorsque tous les niveaux de l'arbre sont remplis sauf possiblement le dernier niveau qui a tous les noeuds aussi gauche que possible.
Une heap où chaque noeud a une valeur plus petite que chacun de ces enfants est appelé MinHeap.
Une heap où chaque noeud a une valeur plus grande que chacun de ces enfants est appelé MaxHeap.
La figure ci-dessous montre une minheap.
Insertion
Comment inserer un élément dans la heap en gardant toujours une heap :
Insérer nouveau élément à la fin de la heap (prochain élément disponible)
While (nouveau élément n’est pas racine et nouveau élément < le parent )
{
Permuter nouveau élément et le parent
}
Exemple ci-dessous montre l'insertion de l'élément ayant la priorité égale a 5. Il y'a 3 étapes nécessaires dans ce cas.
Etape 1: 5 est insere à la fin
Etape 2: On permute 5 et 63 (car 5 < 63)
Etape 3: On permute 5 et 26 (car 5 < 26)
Après l'étape 3 on ne peut par permuter 5 avec la racine 3 car 5 n'est pas inférieur à 3.
Suppression (élément le plus prioritaire)
Enlever un élément de la heap
On enleve toujours l’élément à la racine (le plus prioritaire)
Enlever l’élément à la racine en le remplacant par le dernier élément de la heap (DEH)
While ( DEH a des enfants et DEH est plus grand que au moins un des 2 enfants)
{
Permuter DEH avec le plus petit des 2 enfants
}
L'exemple ci-dessous montre la suppression de l'élément le plus proritaire de la heap (élément ayant la priorité 3). Il y'a 3 étapes nécessaires dans ce cas:
Etape 1: On enleve l'élément le plus prioritare 3 et on le remplace par le DEH 63.
Etape 2: On permute 63 et 5 (5 est le fils le plus petit de 63)
Etape 3: On permute 63 et 26 (26 est le fils le plus petit de 63).
Après cela 63 n'a plus de fils et on a fini.
Implementation
Généralement on utilise un tableau pour representer une heap:
Ce qu'il faut remarquer avec cette representation on a:
Noeud a la position p dans le tableau:
Enfant à gauche a la position 2p + 1
Enfant à droite a la position 2p + 2
Noeud a la position c:
Parent a la position (c – 1) / 2
Dans la figure ci-dessus est montré par exemple:
La valeur 26 est située à la position 2 (p=2) alors l'enfant gauche a la position ( 2 * 2 + 1 = 5) et l'enfant droit a la position (2 * 2 + 2 = 6),
Effectivement l'enfant gauche est 36 (position 5) et l'enfant droit est 63 (position 6).
La valeur 71 a la position 11 (c=11). Le parent de 71 a la position (11 - 1 / 2 = 5). Effectivement le parent de 71 est 36 qui a la positon 5.
Insertion
Inserer un élément dans le heap:
Inserer le nouveau élément à la fin du tableau
While ( (parent >= 0) et (Table[parent] > Table[enfant]))
{
Permuter Table[parent] et Table[enfant]
enfant ß parent
Parent ß (enfant – 1) / 2
}
Enfant = table.size() – 1 // 13
Parent = (child – 1) / 2 // 6
Suppression
Enlever élément à la position 0 (racine) et le remplacer par le dernier élément:
Parent ß 0
While(True)
{
enfantGauche ß (2 * parent) + 1
enfantDroit ß enfantGauche + 1
if (enfantGauche >= Table.size)
break; // parent n’a pas d’enfant : on a termine
minEnfant ß index du plus petit des enfants
if (Table[parent] > Table[minEnfant])
{
Permute(Table[parent], Table[minEnfant])
Parent ß minEnfant
}
Else
Break // parent est <= minEnfant: on a terminé
}
