tableau file circulaire

Version imprimable

15/12/2006, 19h26
P'tite Nélodie

tableau file circulaire

bonsoir,

j'essaye de modélisation une file avec un tableau statique et pour optimiser la place, je souhaite faire une file circulaire.
avant de coder tout ça , j'essaye dèjà de faire l'algo. j'ai trouvé des codes sur ce site mais je ne comprends pas l'incrémentation de certains indices.

voilà ce que j'ai :

taille_maximale : 10
file : tableau d'entier de 0 à 9
la file étant en fifo j'ai besoin de deux indices:
indice_ins : indice de la case pour l'insertion d'un nouveau entier
indice_ext : indice de la case où extraire l'élement
j'utilise un booléen "plein" pour savoir si la file est pleine ou non

pour l'initialisation :
indice_ins et indice_ext prennent la valeur 0, celle de la première case du tableau
plein prend la valeur faux

La file est vide si indice_ins = indice_ext et si plein vaut faux

Pour l'insertion , il faut d'abord vérifié que la file n'est pas plein en vérifiant la valeur du booléen plein , puis on insert à l'indice "indice_ins" et on doit l'incrémenter de 1.
c'est là que mon résonnement differt de ce que je trouve sur le net :
moi je teste si indice_ins == taille_max et si c'est le cas je dis que indice_ins doit prend la valeur 0.
les codes trouvés incrémentent indice_ins avec (indice_ins+1) % taille_max
et je ne vois pas pourquoi :oops:
est ce que quelqu'un pourait m'expliquer s'il vous plait ??
j'ai fais des exécutions papiers des deux résonnements et je n'arrive pas à comprendre "(indice_ins+1) % taille_max" et je doute que mon résonnement soit exaxte vu que je l'ai trouvé nulle part :(

merci d'avance
15/12/2006, 21h29
millie

Citation:

Envoyé par P'tite Nélodie

c'est là que mon résonnement differt de ce que je trouve sur le net :
moi je teste si indice_ins == taille_max et si c'est le cas je dis que indice_ins doit prend la valeur 0.
les codes trouvés incrémentent indice_ins avec (indice_ins+1) % taille_max

Ca sera équivalent puisque tu incrémentes ou décrementes toujours ton indice de 1 en 1. Ca permet juste de retirer la condition et d'obtenir directement la bonne formule en utilisant un modulo.
16/12/2006, 11h03
koala01
Salut,

Le gros avantage du modulo (X % 3), c'est qu'il donne le reste de la division du premier terme par le second...

Autrement dit, tu n'auras jamais une valeur comprise entre 0 et X-1, ce qui, dans ton cas, correspond justement à... la fourchette d'indices utilisables dans ton tableau.

(ben oui: 1%3=1, 2%3=2 3%3=...0 4%3=...1 et on recommence...)

Ceci dit, le principe d'une même d'une liste circulaire fait que les avantages sont important à l'utiliser de manière dynamique:
- L'insertion et le retrait d'élément est facilité (plus besoin de vérifier si le tableau est plein, ou si l'élément existe)
- la sélection d'un élément est facilité (si tu ne dois plus disposer d'un élément, tu le supprime de la liste, et tu ne dois pas commencer à faire attention au fait qu'il y a peut etre un élément "supprimé" au milieu du tableau)
- ...
Pour implémenter une liste circulaire de manière dynamique, ce n'est, en outre, pas beaucoup plus compliqué que pour l'implémenter de manière statique...

La seule différence (et, il est vrai, le seul inconvéniant) notable sera du point de vue de son utilisation où l'acces au Nième élément par rapport à ta position dans la liste ne se fera plus avec une complexité de 1, mais bien avec une complexité de N (il faudra demander d'accéder N fois à l'élément suivant dans la liste)...

Ceci dit, la différence de temps d'exécution, tant que tu n'essaye pas d'accéder au 10.000.000 élément de la liste par rapport à ta position actuelle, sera minime, du fait meme des vitesses atteintes à ce jour par les ordinateurs :P

Le principe d'implémentation d'une liste chaînée dynamique est relativement simple, mais, il semblerait que la balise CODE ne soit plus en activité pour l'instant... si l'implémentation dynamique t'intéresse, je me ferai un plaisir de te donner un exmple plus tard ;)
16/12/2006, 11h58
Emmanuel Delahaye

Citation:

Envoyé par P'tite Nélodie

j'essaye de modélisation une file avec un tableau statique et pour optimiser la place, je souhaite faire une file circulaire.
avant de coder tout ça , j'essaye dèjà de faire l'algo. j'ai trouvé des codes sur ce site mais je ne comprends pas l'incrémentation de certains indices.

voilà ce que j'ai :

taille_maximale : 10
file : tableau d'entier de 0 à 9
la file étant en fifo j'ai besoin de deux indices:
indice_ins : indice de la case pour l'insertion d'un nouveau entier
indice_ext : indice de la case où extraire l'élement
j'utilise un booléen "plein" pour savoir si la file est pleine ou non

OK. Mais pour savoir si tu as le droit de lire, il faut aussi un flag ('vide'), car l'égalité des indices ne permet pas de savoir si le file est vide ou pleine.

Il est cependant possible de le déterminer en combinat l'égalité des indices et l'état du flag plein... (iw : indice d'écriture, ir : indice de lecture)

Code:

vide := iw = ir AND NOT full

personnellement, et pas souci de symétrie et de simplicité, je préfère maintenir l'état d'un flag vide au moment de l'initialisation (vide := TRUE) et des lectures (vide := ir = iw, après lecture)

Citation:

pour l'initialisation :
indice_ins et indice_ext prennent la valeur 0, celle de la première case du tableau
plein prend la valeur faux

OK.

Citation:

La file est vide si indice_ins = indice_ext et si plein vaut faux

OK, on s'est compris...

Citation:

Pour l'insertion , il faut d'abord vérifié que la file n'est pas plein en vérifiant la valeur du booléen plein , puis on insert à l'indice "indice_ins" et on doit l'incrémenter de 1.

Correct.

Citation:

c'est là que mon résonnement differt de ce que je trouve sur le net :
moi je teste si indice_ins == taille_max et si c'est le cas je dis que indice_ins doit prend la valeur 0.

Ton 'raisonnement' est correct.

Citation:

les codes trouvés incrémentent indice_ins avec (indice_ins+1) % taille_max
et je ne vois pas pourquoi :oops:
est ce que quelqu'un pourait m'expliquer s'il vous plait ??

L'implémentation (peu recommandée, AMA, question de perf) avec les % produit le même comportement.

Ton raisonnement est correct et c'est celui que j'utilise, si je me souviens bien.

http://emmanuel-delahaye.developpez.com/clib.htm
Module FIFO.