Donc je veux realiser une representation contigue d'une file d'attente avec tableau circulaire, donc j'ai initialisé mon tableau a 0 et bien sure la tete a -1 et la queue a -1 aussi, mais quand je fais un teste pour verifier si la tete et la la queue sont bien a -1, la ça ma surpris , je comprend pas pourquoi sa me renvoie un 0.
Je vois des for(i=0; i<=MAX;i++) qui sentent mauvais. Il faut se mettre dans la tête que les indices commence à 0 en C. Et finissent à taille-1.
Par ailleurs, rien n'empêche de tenir à jour un compteur pour la longueur.
Ça ne prend pas plus de place que de réserver une case dont on ne se servira pas, faute de pouvoir déterminer si debut==fin veut dire que c'est vide, ou plein.
N'avoir que les deux indices, c'est une économie de bouts de chandelle héritée des années 50. Où on prenait comme taille une puissance de 2 pour ne pas avoir à faire une comparaison. Jamais un modulo par division, ça coûte trop cher.
Ps Pour début, fin, l'expérience montre qu'il vaut mieux prendre un intervalle semi ouvert. Avec Fin qui désigne la case après celle qui contient le dernier élément. Believe me or not : Écrire les 2 versions, et comparer.
Le message qui suit est une réponse automatique activée par un membre de l'équipe. Les réponses automatiques leur permettent d'éviter d'avoir à répéter de nombreuses fois la même chose, ce qui leur fait gagner du temps et leur permet de s'occuper des sujets qui méritent plus d'attention. Nous sommes néanmoins ouverts et si vous avez une question ou une remarque, n'hésitez pas à contacter la personne en question par Message Privé. Pour plus d'informations, nous vous invitons à lire les règles générales du forum
Mauvais titre
Le titre est un élément important qui ne doit pas être négligé. N'oubliez pas cette règle simple : le titre idéal résume la question que vous allez poser en une petite phrase. Il doit permettre aux visiteurs de se repérer facilement dans le forum visité et d'identifier le sujet à sa seule lecture.
Vous pouvez utiliser divers préfixes comme [Erreur], [MySQL], [Compatibilité], etc... Aussi, pensez à consulter les règles propres à chaque forum (visibles dans les topics épinglés en haut des sections).
De plus, choisir un bon titre permet de rendre plus faciles les recherches des autres membres.
Les titres de type "besoin d'aide" ou "problème" ne sont pas tolérés.
Pour modifier votre titre, éditez le premier message de votre sujet.
(titre originel : probleme d'initialisation en langage c)
Merci de colorer votre code à l'aide du bouton Code
Les forums d'Openclassrooms disposent d'une fonctionnalité permettant de colorer et mettre en forme les codes source afin de les rendre plus lisibles et faciles à manipuler par les intervenants. Pour cela, il faut utiliser le bouton de l'éditeur, choisir un des langages proposés et coller votre code dans la zone prévue. Si vous utilisez l'éditeur de messages en mode Markdown, il faut utiliser les balises <pre class="brush: cpp;">Votre code ici</pre>.
Merci de modifier votre message d'origine en fonction.
Encore du code pour lequel on ne ppeut pas faire de copier-coller?
La raison pour laquelle les longueurs des tampons circulaires était une puissance de 2 + 1 est parce que l'espace disque pour un bloc minimal était (et est encore) une puissance de 2.
On ne faisait pas de modulo, on testait par rapport à max+1 et on revenait à 0.
l'expression "lwa" pour last word address avait un sens un peux faux car elle désignait la case suivante de la fin.
Pour savoir si le tampon (ici la pile) est vide, il faut tester si indiceQueue == indiceTete.
Une pile est pleine s'il ne reste qu'un espace dans le tampon (tableau) comme j'ai indiqué.
La notion d'intervalle semi-ouvert est une abstraction qui veut dire que les indices commencent à 0 et finissent où on veut bien.
Le Tout est souvent plus grand que la somme de ses parties.
donc pour l'initialisation c'est juste pour l'affichage (sinon on aura des adresses), et les -1 parce que j'avance l'indice de la tete (ou queue) pour defiler (ou enfiler) ,donc si j'initialise a 0 le premier element sera dans l'indice 1 . Et dans mon cas la condition pour vérifie s'il reste qu'un seul element c'est if (indice queue % longueur == tete + 1 % longueur ) . normalement ça devrait marcher mais le truc c'est que quand j'initialise indice tete = -1 c'est comme si on a initialisé a 0 . MErci
@RayaneRayane2 Merci de modifier le titre de votre sujet comme demandé, et tant qu'a faire écrire le code sous forme de texte à insérer avec l'outil intégrer au forum, le bouton code </>.
Pour le modulo avec une puissance de 2, on applique un masque binaire. n = (n + 1) & (1 << k); parce que ça demande moins d'instructions que comparaison + branchement conditionnel + affectation. En plus, l'absence de branchement conditionnel, ça évite les bulles dans le pipeline (notion qui apparait avec le Stretch d'IBM en 1961).
Erratum :
n = (n + 1) & ((1 << k) - 1); // avec k nombre de bits
Je ne vois pas pourquoi Ça te donnerais 0 si tu as -1. Avec -1, tu sort de ton tableau.
Tu ne peux pas afficher fileAttente[-1].
La façon usuelle pour se représenter une file d'attente est qu'on insère les éléments à gauche et qu'on les retire à droite.
De la mème façon, on se représente un tableau avec les petits indices à gauche et les grands indices à droite.
C'est pour cela que les gens sont surpris quand on leur dit qu'il faut avancer l'indice 'indiceQueue' en premier pour insérer, et l'indice 'indiceTete' ensuite pour retirer.
Quand tu auras inséré le premier élément, tu auras indiceTete=0 et indiceQueue=1.
L'élément que tu viens d'insérer se trouve à la position fileAttente[0].
indiceQueue représente la position du prochain élément à venir.
Le nombre d'éléments dans la file d'attente est indiceQueue - indiceTete au départ (ça change avec la circularité).
Si tu veux retirer un élément, tu commences par le recopier ailleurs et tu avances indiceTete de 1 ensuite seulement.
Tu te retrouveras avec indiceTete = indiceQueue = 1 et ta file est vide parce que tes indices sont égaux.
Rappelles toi, tu veux un tableau circulaire pour ta file d'attente.
Si tu ajoutes 1 à un indice et qu'il devient égal à la longueur, tu le remets à 0. C'est pourquoi j'ai écrit
indice = (indice + 1) % longueur;
dans mon premier message pour simplifier. Et ça vaut pour les deux indices.
On insère donc à droite et on retire à gauche (hormis la circularité).
Avant de retirer, il faut vérifier que les deux indicessont différents. Sinon, la file est vide.
L'élément se trouve à la position fileAttente[indiceTete].
Pour insérer, il faut vérifier que la file d'attente n'est pas pleine (voir mon premier message).
Il sera inséré à la position fileAttente[indiceQueue]
Dans les deux cas, on avance l'indice correspondant seulement après l'action.
@michelbillaud: je n'ai pas d'objection à avoir une longueur d'une puissance de 2 et utiliser un masque.
- Edité par PierrotLeFou 29 mars 2020 à 1:03:54
Le Tout est souvent plus grand que la somme de ses parties.
Je ne vois pas pourquoi Ça te donnerais 0 si tu as -1. Avec -1, tu sort de ton tableau.
Tu ne peux pas afficher fileAttente[-1].
La façon usuelle pour se représenter une file d'attente est qu'on insère les éléments à gauche et qu'on les retire à droite.
De la mème façon, on se représente un tableau avec les petits indices à gauche et les grands indices à droite.
C'est pour cela que les gens sont surpris quand on leur dit qu'il faut avancer l'indice 'indiceQueue' en premier pour insérer, et l'indice 'indiceTete' ensuite pour retirer.
Quand tu auras inséré le premier élément, tu auras indiceTete=0 et indiceQueue=1.
L'élément que tu viens d'insérer se trouve à la position fileAttente[0].
indiceQueue représente la position du prochain élément à venir.
Le nombre d'éléments dans la file d'attente est indiceQueue - indiceTete au départ (ça change avec la circularité).
Si tu veux retirer un élément, tu commences par le recopier ailleurs et tu avances indiceTete de 1 ensuite seulement.
Tu te retrouveras avec indiceTete = indiceQueue = 1 et ta file est vide parce que tes indices sont égaux.
Rappelles toi, tu veux un tableau circulaire pour ta file d'attente.
Si tu ajoutes 1 à un indice et qu'il devient égal à la longueur, tu le remets à 0. C'est pourquoi j'ai écrit
indice = (indice + 1) % longueur;
dans mon premier message pour simplifier. Et ça vaut pour les deux indices.
On insère donc à droite et on retire à gauche (hormis la circularité).
Avant de retirer, il faut vérifier que les deux indicessont différents. Sinon, la file est vide.
L'élément se trouve à la position fileAttente[indiceTete].
Pour insérer, il faut vérifier que la file d'attente n'est pas pleine (voir mon premier message).
Il sera inséré à la position fileAttente[indiceQueue]
Dans les deux cas, on avance l'indice correspondant seulement après l'action.
@michelbillaud: je n'ai pas d'objection à avoir une longueur d'une puissance de 2 et utiliser un masque.
- Edité par PierrotLeFou il y a 33 minutes
D'accord merci pour ton aide je vais essayer avec votre methode.
@michelbillaud: je n'ai pas d'objection à avoir une longueur d'une puissance de 2 et utiliser un modulo
Non plus mais j'explique la raison "historique" qui fait que quand on a besoin d'un tampon d'une centaine, on va prendre 128. C'est juste de la micro-optimisation.
Ou alors c'est la transposition de ce qu'on trouve dans un CIRCUIT logique (materiel) où on va utiliser des compteurs, qui "font le tour" tous seuls.
L'idée du modulo, c'est un truc de matheux. C'est vrai que c'est des compteurs modulo quelque chose, mais l'implementer avec une division, c'est le contraire d'une optimisation.
De nos jours la séquence if (++x == MAX) x = 0; fait très bien l'affaire sur les processeurs qui ont des instructions conditionnelles, ça se compile sans générer de branchement. Pas besoin d'une puissance de 2.
Si on écrit les choses en C, c'est pas pour que ça soit plus court ou plus simple à écrire.
Si un truc nécessaire est compliqué à écrire, mais utile, on peut faire une macro
#define INC(v,MAX) { if((++v == MAX) v = 0; }
SI on veut savoir lequel est plus rapide, ou donne le code exécutable le plus court - on teste, on regarde le codé généré par les diverses solutions, et on compare les performances. Mais ça ne donne une conclusion valide que pour le cas particulier qu'on a testé (version du compilateur, options de compilation, machine sur laquelle on fait exécuter).
Pour un utilisateur averti, on peut se permettre des trucs compliqués (?), mais si une file d'attente pose déjà problème, c'est autre chose.
Même si tu "caches" la complexité derrière la macro, il faut bien écrire cette dernière. Si on l'utilise plusieurs fois dans le code, ça vaut la peinne.
D'autre part, on ne sait rien du reste du programme. Quel pourcentage du code représente cette opération?
Le Tout est souvent plus grand que la somme de ses parties.
En fait, quasiment rien. On n'utilise pas la file juste comme ça, mais pour stocker des infos dont on fait quelque chose. Ce qui prend du temps
En fait, c'est de la frime : regardez comme je suis fort, je sais faire un modulo (Ou un masque binaire)
Si on est si fort, on écrit les diverses versions, et on compare le résultat, objectivement.
- Edité par michelbillaud 30 mars 2020 à 8:30:49
initialisation d'une file d'attente en c
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.