[débutant] probleme avec une classe arbre

Version imprimable

Salut, je voudrais creer une classe arbre, ou les noeuds ont au maximum n fils.
J'ai fait un petit truc, j'aimerais savoir s'il n'y a pas des erreurs grossieres (au niveau du style), mais surtout j'ai un probleme quand j'affiche un arbre : il ne va qu'a un rang plus loin... enfin il affiche le noeud courant et ses fils seulement, pas les petits fils.

Voila le .h :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Arbre { public: Arbre(){}; ~Arbre(); void init(int valeur, int profondeur); void Arbre::affiche(); void Arbre::ajouteFils(Arbre fils); private: Arbre *fils; int val; int arite; int profondeur; //racine a pour profondeur 0 };
Et le .cpp :
Code:

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 void Arbre::init(int val, int profondeur) { Arbre *liste_de_fils=new Arbre[8]; if(!liste_de_fils) exit(0); this->fils=liste_de_fils; this->val=val; this->arite=0; this->profondeur=profondeur; } Arbre::~Arbre() { if (fils!=NULL) for (int i=0;i<arite;i++) (fils[i]).~Arbre(); } void Arbre::ajouteFils(Arbre fils) { this->fils[arite]=fils; arite++; } void Arbre::affiche() { cout << val << "("; if (fils!=NULL) for (int i=0;i<arite;i++) (fils[i]).affiche(); cout << ")"; }
Vous l'aurez compris je debute, mais je n'ai pas reussi a trouver beaucoup d'info sur les arbres NON binaires :?

07/06/2006, 17h37
ep31

Déjà, les destructeurs, il faut TOUJOURS qu'ils soient virtuels
07/06/2006, 17h40
Rafy
Si tu veux faire un arbre, alors chaque élément de ton arbre doit stocker une liste d'autre éléments :
Code:

1 2 3 4 5 6 7 8 9 class CElement { public : CElement(void); protected : std::list<CElement> ElementList; int Value; };
Tu n'a pas besoin de stocker dans chaque element sa profondeur, ni sont rang.
Avec cette architecture on a :
Un element à la base, il stocke une liste d'élément, qui eux aussi stocke des listes d'éléments... Pour n'avoir que n élément maxi dans chaque branche alors lors de l'introduction, regarde si dans ta liste tu as déjà n éléments.

Voila une class élément plus complète :

Code:

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
// Dans le H
#include <list>
class CElement
{
    public :
        explicit CElement(int Value);
        virtual ~CElement(void);
 
        virtual void AddElement(const CElement& ElementToAdd);
 
    protected :
        std::list<CElement> ElementList;
        int Value;
};
 
// Dans le CPP
CElement::CElement(int Value)
{
        this->Value = Value;
}
 
CElement::~CElement(void) {}
 
void CElement::AddElement(const CElement& ElementToAdd)
{
        this->ElementList.push_front(ElementToAdd);
}

A toi de coder les accesseurs

07/06/2006, 17h48
MatRem

Citation:

Déjà, les destructeurs, il faut TOUJOURS qu'ils soient virtuels

Là je dirais ça se discute ...
Si c'était le cas, il n'y aurais pas de mot clef virtual et les destructeurs serait toujours virtuel. ;)

C'est sur que ça peut être une bonne habitude, mais ce n'est obligatoire que quand on utilise le polymorphisme, et que les classes dérivées ont besoin que leur destructeur soit appellée.

Pour ce qui est de la structure de ton code:
- tu peux peut peu être utiliser le constructeur à la place de la fonction init, cela dépendra de la façon dont tu instancie les variables du type Arbre.
- Comme ça été dit il est intéressant d'utiliser les conteneurs de la bibliothèque standart (comme vector).

Si tu veux nous faire voir ton main ça peut aider pour voir pourquoi les petis fils ne sont pas affichés.
07/06/2006, 18h10
ep31
Citation:

Envoyé par MatRem

Là je dirais ça se discute ...
Si c'était le cas, il n'y aurais pas de mot clef virtual et les destructeurs serait toujours virtuel. ;)

C'est sur que ça peut être une bonne habitude, mais ce n'est obligatoire que quand on utilise le polymorphisme, et que les classes dérivées ont besoin que leur destructeur soit appellée.

Pour ce qui est de la structure de ton code:
- tu peux peut peu être utiliser le constructeur à la place de la fonction init, cela dépendra de la façon dont tu instancie les variables du type Arbre.
- Comme ça été dit il est intéressant d'utiliser les conteneurs de la bibliothèque standart (comme vector).

Si tu veux nous faire voir ton main ça peut aider pour voir pourquoi les petis fils ne sont pas affichés.

Je suis pas tout à fait d'accord pour le destructeur.
Il ne doit pas être virtual si on n'utilise pas le polymorphisme et uniquement si on ne l'utilise pas.
Par exemple si B dérive de A, qu'on a une collection de A et que l'on détruit ces objets, le destructeur de B ne sera pas appelé avec un compilo codewarrior car il n'a pas la vtable.
Et en utilisant gcc sous Mac, si on a toujours B qui dérive de A et un destructeur non virtual de A ou/et B, et qu'on fait :
Code:

1 2 3 4 B* b = new b(); ... ~b(); // Appel implicite
Ca crache au niveau du destructeur car il ne trouve pas le destructeur parent.
Dans le cadre de Visual, c'est sur que c'est inutile de déclarer les destructeurs virtuels grâce à la vtable mais si le code doit être porté, mieux vaut préciser virtual, ça ne mange pas d epain.
Mais je veux bien un exemple où un destructeur ne DOIT PAS être virtuel.
07/06/2006, 20h16
Médinoc
Citation:
Envoyé par ep31

Je suis pas tout à fait d'accord pour le destructeur.
Il ne doit pas être virtual si on n'utilise pas le polymorphisme et uniquement si on ne l'utilise pas.
Par exemple si B dérive de A, qu'on a une collection de A et que l'on détruit ces objets, le destructeur de B ne sera pas appelé avec un compilo codewarrior car il n'a pas la vtable.
Et en utilisant gcc sous Mac, si on a toujours B qui dérive de A et un destructeur non virtual de A ou/et B, et qu'on fait :

Code:

1 2 3 4 B* b = new b(); ... ~b(); // Appel implicite
Euh... C'est pas plutôt un appel explicite, ça ?

Citation:

Dans le cadre de Visual, c'est sur que c'est inutile de déclarer les destructeurs virtuels grâce à la vtable mais si le code doit être porté, mieux vaut préciser virtual, ça ne mange pas d epain.
Mais je veux bien un exemple où un destructeur ne DOIT PAS être virtuel.

???
07/06/2006, 20h17
MatRem

Citation:

Par exemple si B dérive de A, qu'on a une collection de A et que l'on détruit ces objets, le destructeur de B ne sera pas appelé.

Normal, je vois pas le problème...

Au niveau de ton exemple je trouve ça bizzare. Je savais pas que le c++ définissait l'utilisation du mot clef virtual pour appeller le destructeur de la classe parent ??? (sous gcc c'est automatique)

N'est ce pas un bug de ton compilateur codewarrior (que je ne connais pas d'ailleurs) ?

Je vois pas d'exemple concret pour un destructeur non virtuel, mais il doit bien y avoir des cas de polymorphisme ou on ne veut pas que le destructeur de la classe dérivée soit appellé... non?

En tous cas merci pour votre reponse rapide, je n'avais pas pensé a utiliser les listes en effet. C'est plus simple et c'est ce que je vais faire.

Par contre je ne comprend toujours pas pourquoi ma fonction afficher ne marche pas...
Dans le main j'ai mis ca :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Arbre a; a.init(12,0); Arbre b; b.init(8,1); Arbre c; c.init(7,2); Arbre d; d.init(5,3); a.ajouteFils(b); b.ajouteFils(c); c.ajouteFils(d); a.affiche(); cout << endl; b.affiche(); cout << endl;
Et ca me renvoie ca :
Code:

1 2 12(8()) 8(7())
(sans seg fault)

07/06/2006, 21h48
Luc Hermitte

Citation:

Envoyé par ep31

Déjà, les destructeurs, il faut TOUJOURS qu'ils soient virtuels

Non! En schématisant, seulement s'il a une sémantique d'entité et que le polymorphisme se tapera probablement (ou sûrement) l'inscruste. Dans le cas d'une sémantique de valeur, cela enduit en erreur quant à ce que l'on peut véritablement faire de l'objet.
Les destructeurs non publics n'ont pas besoin d'être virtuels non plus -- à part peut-être des protégés pour des objets polymorphes gérés par une factory amie.

Sinon, pour en revenir à la question de l'OP:
- toujours séparer les données de l'IHM. i.e., la présence d'une fonction membre affiche() est rarement recommandable (/jamais ?).

- Je préfère les désign où les rôles sont bien établis => arbre, noeud, feuille

- s/exit()/throw

- s/fils+arité/vector de fils ; cela simplifira le code et corrigera le possible buffer overflow de ajouteFils()

- ne jamais appeller le destructeur explicitement (il y a quelques très rares cas où c'est autorisé (limite nécessaire en fait), mais on en reparlera quand tu ne seras plus un débutant)

- Je n'aime pas les fonctions init(). Les constructeurs sont tes amis.
08/06/2006, 07h45
MatRem

Tu utilises la solution avec les références maintenant?
Postes ton code complet plutôt ;).

SI c'est le cas tu dois stocker des références vers les objets:
std::list<CElement &> ElementList;

et non reinstancier de nouveau élément:
std::list<CElement> ElementList;
08/06/2006, 09h32
Luc Hermitte

Citation:

Envoyé par MatRem

SI c'est le cas tu dois stocker des références vers les objets:
std::list<CElement &> ElementList;

???
Ceci n'est pas possible. Une référence est un alias. Ce n'est pas une variable qui puisse être stockée comme les autres.

Ha tient c'est bizarre j'ai toujours cru que c'était possible mais je n'ai jamais du le faire... :aie:
Moi qui croyais bien connaitre le c++, me voilà bien surpris.. on en apprends tout les jours :)

Pour me faire pardonner des bétises que j'ai dit ;) , voilà une solution qui fonctionne (en stockant des pointeurs):

Code:

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
include <cstdlib>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
 
using namespace std;
 
 
class Arbre{
        public:
                Arbre(int);
                void addChild(Arbre & a);
                string toString();
        private:
                int value;
                vector<Arbre *> children;
};
 
Arbre::Arbre(int value){
        this->value = value;
}
void Arbre::addChild(Arbre & child){
        children.push_back(&child);
}
string Arbre::toString(){
        vector<Arbre *>::iterator it;
        ostringstream flux;
 
        flux<<"(["<<value<<"]";
        for(it=children.begin(); it!=children.end(); it++){
                flux<<(*it)->toString();
        }
        flux<<")";
 
        return flux.str();
}
 
int main(){
        Arbre a(1);
        Arbre b(2);
        Arbre c(3);
        Arbre d(4);
        a.addChild(b);
        a.addChild(c);
        b.addChild(d);
 
        cout<<a.toString()<<endl;
 
        return EXIT_SUCCESS;
}

08/06/2006, 10h11
Matthieu Brucher

Si tu veux faire encore mieux, passe par des pointeurs intelligents, ça te permettra de ne pas avoir de fuite mémoire, même en utilisant des pointeurs - pb que tu risques d'avoir quand tes Arbre() sortiront du scope lorsque le programme sera plus conséquent -
08/06/2006, 10h18
MatRem

Si les arbres sortent du scope (ils ne sont plus définis), c'est pas vraiment des fuites mémoire que l'on va avoir, mais plutôt des pointeurs NULL, non?

Ou alors j'ai pas bien compris ce que tu veux dire...
08/06/2006, 10h24
Matthieu Brucher

Tu auras des pointeurs qui pointent sur du vide, donc le mieux est d'utiliser de l'allocation dynamique, et avec des SP, la gestion est plus simple - pub inside :) -
08/06/2006, 10h32
MatRem

Oki on est d'accord :P ,

par contre ça risque de compliquer un peu l'exemple.
08/06/2006, 10h33
Matthieu Brucher

C'est vrai ;)