Svp quelqu'un m'aide pour résoudre ce probleme
Hors ligneShivashiki Le 13/04/2014 Ă  18:51 Profil de Shivashiki Configuration de Shivashiki

Dans une reprĂ©sentation contiguĂ« d'une liste, la manipulation de l'Ă©lĂ©ment en tĂȘte est trĂšs

coûteuse (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 façon circulaire.

D’une maniĂšre gĂ©nĂ©rale pour pouvoir gĂ©rer les listes circulaires il faut utiliser deux

indices :

 tĂȘte= 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 à l’indice)

 Si la liste est vide alors tĂȘte=0 et queue=0

 Les indices de tĂȘte et de queue sont incrĂ©mentĂ©s ou dĂ©crĂ©mentĂ©s de 1 Ă  chaque

ajout ou suppression

 L’indice de tĂȘ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 à la

position 4 cad l’affecter à elements[4]), par ailleurs L->lg correspond toujours à 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 Ă  la tĂȘte ou Ă  la queue. Par exemple la boucle de

dĂ©calage pour les listes non circulaires : 

Vous avez résolu votre problème avec VIC ? Faites-le savoir sur les réseaux sociaux !
Vulgarisation-informatique.com
Cours en informatique & tutoriels