Liste circulaire en C

Fermé
etudiante23 Messages postés 2 Date d'inscription vendredi 4 avril 2008 Statut Membre Dernière intervention 4 avril 2008 - 4 avril 2008 à 03:14
 etudiente - 21 mars 2011 à 21:01
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.

4 réponses

kilian Messages postés 8731 Date d'inscription vendredi 19 septembre 2003 Statut Modérateur Dernière intervention 20 août 2016 1 524
4 avril 2008 à 03:20
Bonne chance alors!
5
teutates Messages postés 19599 Date d'inscription vendredi 28 décembre 2001 Statut Modérateur Dernière intervention 2 janvier 2020 3 592
4 avril 2008 à 19:05
Tu aurais pu faire un effort après avoir scanner ton exo !!

Tu devrais trouver une partie de la solution à ton problème.
3
mais si on clic sur "une partie de la solution à ton probléme" on trouve que ce site ne fonctionne pas!!!!!
0
Char Snipeur Messages postés 9688 Date d'inscription vendredi 23 avril 2004 Statut Contributeur Dernière intervention 2 octobre 2020 1 333
4 avril 2008 à 08:40
+1
2
blux Messages postés 24430 Date d'inscription dimanche 26 août 2001 Statut Modérateur Dernière intervention 27 septembre 2022 3 231
4 avril 2008 à 09:05
C'est à rendre pour quand ?

Tu le veux en JAVA ou en TAMP ?
2
en C
0