Extraction tas max et correspondance avec une suite
Bonjour à tous,
je plante depuis hier sur cela, c'est un peu complexe, je vais tenter d'être le plus clair possible :
J'ai une suite de nombre aléatoire que j'ordonne par sous-suite. La taille de la suite ainsi que de sous-suite est fixé par l'utilisateur.
La suite d'origine que je souhaite ordonné par tranche de 2
Citation:
:
34 22 1 54 12 3 4
Après avoir ordonné j'obtiens :
Citation:
22 34 | 1 54 | 3 12 | 4
(les pipe ne sont là que pour éclaircir, il s'agit du même tableau qui contient ces chiffres.
A partir de maintenant, je souhaite stocké les indices de chaque sous-suite dans un tableau de struct qui sera donc :
Code:
1
2
3
4
|
struct noeud {
int bInf;
int bSup; |
Ce tableau est mon tas.
Je boucle pour le transformer en tas max selon la valeur
Vous voyez un peu où je veux en venir ?
Désormais, j'ai un tas max de l'apparence suivante
je n'ai écris que les valeurs de bSup, sois les indices des valeurs max de la sous suite dans le tableau, mais c'est bien un tas de struct
Jusque là tous va bien.
Je souhaite ensuite extraire, en fonction de ces indices les valeurs correspondante dans le tableau suite. Dès que j'ai extrait une valeur, je décrémente bSup, dès que bSup est inférieur à bInf, cela signifie que j'ai extrait toutes les valeurs de la sous-suite et que je peux donc la supprimer.
Voila le code :
La fonction entasser est la fonction basique entasser pour un tas, je l'ai récupérer sur internet et adapté à mes besonis, je vous la met tous de même
Voila, ouf!! et maintenant, je n'ai pas l'affichage escompté,
En effet, on peut voir que la valeur 12 est extraite deux fois et que 1 est absent.
Citation:
passage : 0
Valeur extraite : 54
Arbre changer par entasser
echange le noeud 0 avec 1
Arbre changer par entasser
echange le noeud 1 avec 3
Valeur extraite : 54
passage : 1
Valeur extraite : 34
Valeur extraite : 34
passage : 2
------Sous suite vide
Valeur extraite : 22
Valeur extraite : 22
passage : 3
Valeur extraite : 12
Arbre changer par entasser
echange le noeud 0 avec 2
Valeur extraite : 12
passage : 4
Valeur extraite : 12
Arbre changer par entasser
echange le noeud 0 avec 1
Valeur extraite : 12
passage : 5
------Sous suite vide
Valeur extraite : 4
Valeur extraite : 4
passage : 6
------Sous suite vide
Valeur extraite : 3
Valeur extraite : 3
valeur final de size 1
Voila, je sais que c'est assez indigeste, mais je n'arrive plus à avancé, en espérant que l'erreur soit stupide
à trouver, en tous cas je ne l'a vois pas...
Merci déjà à ceux qui en sont arrivé là. =)
EDIT : Voici également un autre affichage étrange avec une suite de taille 13 et sous suite de taille 3, voyez plutot les dernières valeurs extraites, et plus particulièrement la dernière. Y a du dépassement quelque part, mais où...
Citation:
passage : 0
Valeur extraite : 45
Valeur extraite : 45
passage : 1
Valeur extraite : 45
Arbre changer par entasser
echange le noeud 0 avec 1
Arbre changer par entasser
echange le noeud 1 avec 3
Valeur extraite : 45
passage : 2
------Sous suite vide
Valeur extraite : 44
Arbre changer par entasser
echange le noeud 0 avec 1
Valeur extraite : 44
passage : 3
Valeur extraite : 36
Arbre changer par entasser
echange le noeud 0 avec 2
Valeur extraite : 36
passage : 4
Valeur extraite : 33
Valeur extraite : 33
passage : 5
Valeur extraite : 32
Arbre changer par entasser
echange le noeud 0 avec 2
Valeur extraite : 32
passage : 6
Valeur extraite : 23
Arbre changer par entasser
echange le noeud 0 avec 1
Arbre changer par entasser
echange le noeud 1 avec 3
Valeur extraite : 23
passage : 7
------Sous suite vide
Valeur extraite : 22
Arbre changer par entasser
echange le noeud 0 avec 1
Valeur extraite : 22
passage : 8
------Sous suite vide
Valeur extraite : 22
Valeur extraite : 22
passage : 9
------Sous suite vide
Valeur extraite : 5
Valeur extraite : 5
passage : 10
------Sous suite vide
Valeur extraite : 1
Valeur extraite : 1
passage : 11
Valeur extraite : 0
Valeur extraite : 0
passage : 12
Valeur extraite : 134513760
Valeur extraite : 134513760
valeur final de size 0
