Liste circulaire en C

PARTIE 1


Dans une repr´sentation contigu¨ d'une liste, la manipulation de l'´l´ment en te te est tr`s
couteuse (O(n)) car elle provoque un d´calage de tous les ´l´ments de la liste. Il est
possible d'´viter cela, en g´rant la liste contigu¨ de facon circulaire.
Exemple en supposant que LongMax=7 et lg=4 ces 7 listes sont ´gales :
5 20 4 9
5 20 4 9
5 20 4 9
5 2 0 4 9
9 5 20 4
4 9 5 20
20 4 9 5
Dàune mani` re g´n´rale pour pouvoir g´rer les listes circulaires il faut utiliser deux
indices :
· tete= indice du premier ´l´ment du tableau elements
· queue = indice de làemplacement apr`s le dernier ´l´ment de la liste
Exemple :
t’te=1 queue=5
5 20 4 9
queue=0 t’te=3
5 20 4 9
queue=1 t’te=4
9 5 20 4
Remarques
· Dans les listes circulaires la premi` re case du tableau est utilis´e (donc on nàa pas
une correspondance entre indice et position cad la position est toujours en d´calage
de 1 par rapport a làindice)
· Si la liste est vide alors te te=0 et queue=0
· Les indices de te te et de queue sont incr´ment´s ou d´cr´ment´s de 1 a chaque
ajout ou suppression
· Làindice de te te ne pr´c`de pas forc´ment làindice de queue
Dans une liste non circulaire les positions et les indices sont ´gaux (ajouter un ´l´ment a la
position 4 cad làaffecter a elements[4]), par ailleurs L->lg correspond toujours a la position du
dernier ´l´ment de la liste L.
Ceci nàest pas le cas dans les listes circulaires oü il faut faire une correspondance entre les
indices et les positions. En effet, lg et pos nàont pas de signification en tant quàindice : Pour
trouver leurs vrais indices il faut les lier a la te te ou a la queue. Les d´bordements sont g´r´s
par làop´rateur Modulo (reste de la division enti` re exprim´ par % dans le langage C)
Par exemple la boucle de d´calage pour les listes non circulaires :
for (i= L->lg; i>=pos; i --)
elementAffecter[&L->elements[i], L->elements[i-1]);
devient pour les listes circulaires:
for (i= L->lg+ L->tete; i>=pos+ L->tete; i --)
elementAffecter[&L->elements[i% LongMax], L->elements[(i-1)% LongMax]);

Exemple si on veut ins´rer là´l´ment 3 a la position 2 dans la liste suivante:
queue tete
4 9 5 20
0 1 2 3 4 5 6
On a : pos=2, L->tete=5, L->queue=2, L->lg=4, LongMax=7
i= 4+5=9 elementAffecter[&L->elements[9% 7], L->elements[8% 7])
= elementAffecter[&L->elements[2], L->elements[1])
4 9 9 5 20
0 1 2 3 4 5 6
i=8 elementAffecter[&L->elements[8% 7], L->elements[7% 7])
= elementAffecter[&L->elements[1], L->elements[0])
4 4 9 5 20
0 1 2 3 4 5 6
i=7 elementAffecter[&L->elements[7% 7], L->elements[6% 7])
= elementAffecter[&L->elements[0], L->elements[6])
20 4 9 5 20
0 1 2 3 4 5 6
Une fois le d´calage termin´, on peut ajouter 3 comme suit (il est clair que la queue change de
la position 2 a la position 3):
20 4 9 5 3
0 1 2 3 4 5 6
Notons aussi que dans cet exemple le d´calage a ´t´ fait cot´ queue mais on peut làoptimiser
en choisissant un d´calage cot´ te te ou queue selon la position.
Travail demande
1. Impl´menter les primitives des listes dàune mani` re circulaire contig4e optimale. Dans le
rapport a remettre pr´ciser pour chaque programme sa complexit´ temporelle.
2. Proposer un programme principal avec un menu de choix qui propose la gestion dàun type
dà´l´ments en stockage indirect de votre choix. Par gestion on veut dire la possibilit´
dàajout, de suppression, de consultation etc.


PARTIE 2


Les files dattentes sont des structures de donn´es dont la gestion se fait en FIFO (First In
First Out) :
· làajout dans une file = enfiler : se fait toujours a la fin
· la suppression dans une file = de filer : se fait toujours au d´but
La meilleure mani` re pour impl´menter les files dàattentes contig4es est dàutiliser les listes
circulaires contig4es. En effet, ce choix assure une complexit´ O(1) pour les op´rations
dàempilement et de d´pilement.
Travail demande
1. Impl´menter les primitives suivantes pour les files (FilePrim.h) en utilisant les listes
circulaires impl´ment´es dans la partie 1.
File fileCreer(void);
void fileDetruire (File);
int estVide(File);
int estSaturee(File);
int fileTaille(File);
ELEMENT Sommet(File);
int Enfiler(File, ELEMENT);
ELEMENT Defiler(File);
void fileAfficher(File);
File fileCopier(File);
int fileComparer(File, File);
3. Proposer un programme principal avec un menu de choix qui propose la gestion dàune file
dàattente avec les me mes ´l´ments utilis´s dans la partie 1.