Discussion :

[henry.delapub]

Bonjour a tous,
J'ai une petite question actuellement, étudiant je dois programmer un algorithme de tri par tas en c++.
Et quelque petit souci a priori, rien ne se passe comme sa devrait se passer
SI quelqu'un pouvait m'aider sa serait avec plaisir.

J'ai fais la modification que tu me propose il y a du mieux mais sa ne marche toujours pas..

help me please

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
 
#include <iostream>
using namespace std;
void echanger(int& a,int& b)
{
    int aux=a;
    a=b;
    b=aux;
}
void ajouter(int arbre[], int *noeud, int x)
{
    int i;
    *noeud=*noeud+1;
    arbre[*noeud]=x;
    i=*noeud;
 
    while (i>=1 && arbre[i]<arbre[i/2])
    {
        echanger(arbre[i],arbre[i/2]);
        i =i/2;
    }
}
 
void supprimerMin(int arbre[], int *noeud, int *min)
{
    int i=1,j=0;
    arbre[1]=arbre[*noeud];
    *noeud=*noeud-1;
    while ((*noeud/2) >= i )
    {
        j=2*i;
        if ((j != *noeud) && (arbre[j+1] < arbre[j]))
        {
            j++;
        }
 
        if (arbre[i]>arbre[j])
        {
            echanger(arbre[i],arbre[j]);
            i=j;
        }
        else
        {
            i=*noeud;
        }
    }
}
 
void trinoeudarTas(int arbre[],int taille)
{
 
    int noeud=1,min=arbre[1];
 
    while (noeud<taille)
    {
        ajouter(arbre,&noeud,arbre[noeud+1]);
    }
 
    cout<<"noeud==taille"<<endl<<endl;
    for (int i=1;i<10;i++)
    {
        cout<<arbre[i]<<" || ";
    }
 
 
    while (noeud>0)
    {
        supprimerMin(arbre,&noeud,&min);
 
        arbre[noeud+1]=min;
    }
}
 
int main()
{
 
    int arbre[10]={10,0,7,4,1,6,3,4};
 
    for (int i=1;i<10;i++)
    {
        cout<<arbre[i]<<" || ";
    }
    cout<<endl;
    trinoeudarTas(arbre,8);
    cout<<endl;
 
    for (int i=1;i<10;i++)
    {
        cout<<arbre[i]<<" || ";
    }
 
 
    return 0;
}

Merci d'avance

[bruno_pages]

Bonjour,

la fonction echanger ne fait rien, l faut utiliser des références : void echanger(int& a,int & b)

j'avoue que je n'ai pas regarder le reste de l'algo

[henry.delapub]

up
Help please

[bruno_pages]

Bonjour,

avez-vous modifié echanger comme indiqué ?
est-ce que cela marche avec cette nouvelle définition ?

sinon je remarque que vous affichez le contenu du vecteur à partir du rang 1, or le premier élément est au rang 0. Est-ce une simple erreur de typo locale ou une vraie erreur de votre part ?

[gb_68]

Bonjour,
personnellement je vois déjà deux problèmes potentiels dans le code :

• Comme le dit bruno_pages, les tableaux en C++ commencent à l'indice 0 et non 1. Les boucles for (int i=1;i<10;i++) n'affecte donc que les éléments de 1 à 9 (au lieu 0 à 9, soit les 10 éléments).
• Dans la fonction void supprimerMin(int arbre[], int *noeud, int *min), min n'est jamais affecté !
  

  Code :

  Sélectionner tout - Visualiser dans une fenêtre à part

  1
  2
  3
  4
  5
  6
  7
  8
  void supprimerMin(int arbre[], int *noeud, int *min)
  {
      int i=1,j=0;
      // d'après les tests effectués dans les autres fonctions pour ranger les éléments, 
      // le plus petit semble être à la racine de l'arbre, donc
     *min = arbre[0]; 
   
      arbre[0]=arbre[*noeud];

Remarque : il est possible d'alléger quelque peu l'écriture en utilisant des références plutôt que des pointeurs pour le passage de certains paramètres (noeud, min).

[henry.delapub]

En fait, oui l'incrémentation de 1 a 9 est volontaire.
Car dans la case 0, qui je suis d'accord est la première valeur du tableau correspond a la longueur de notre tableau.
Donc pour un tableau de taille n, dans la T[0]=n.

Représentation que nos enseignants nous conseille pour les tas.

Et oui j'ai fais les modifs directement sur le premier

Si il y a bien une décrémentation de faite dans la fonction supprimer.
Sinon j'obtiendrai une boucle infini, il me semble...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
void supprimerMin(int arbre[], int *noeud, int *min)
{
    int i=1,j=0;
    arbre[1]=arbre[*noeud];
    *noeud=*noeud-1;//permet la décrementation

[koala01]

Salut, et bienvenue sur le forum

En fait, oui l'incrémentation de 1 a 9 est volontaire.
Car dans la case 0, qui je suis d'accord est la première valeur du tableau correspond a la longueur de notre tableau.
Donc pour un tableau de taille n, dans la T[0]=n.

Représentation que nos enseignants nous conseille pour les tas.

Dans l'absolu, nous pourrions effectivement estimer que c'est une solution raisonnable à envisager, mais...

Si cela fonctionnera effectivement tant que tu manipulera des valeurs numériques "réelles" (en gros, pour les types primitifs), je ne peux m'empêcher de me poser la question de savoir comment tu indiquera que ton tableau manipule dix pommes, dix poires ou dix coordonnée (et des scoubidou bidou, wah...), enfin, en deux mots, des types de valeurs susceptibles d'être triés, mais n'ayant aucun rapport avec la représentation d'un nombre...

J'ai, personnellement, tendance à estimer qu'un conseil ne vaut que par l'usage que l'on peut en faire, or, ce conseil vaut, dans le meilleur des cas, pour une petite dizaines de types, alors qu'il sera totalement inefficace pour la grosse majorité (en gros, la quasi totalité types que tu sera amené à créer dans ta carrière)

Peut on dés lors estimer qu'il soit opportun de prendre l'habitude de suivre ce conseil, sachant que, d'autres part, il va à l'encontre de ce que les gens ont l'habitude de faire, la réaction de Bruno étant ici symptomatique de la manière dont tout le monde risque de réagir