Discussion :

[Lucas Panny]

Bonjour,

J'aimerais créer des classes permettant de représenter un arbre de type programmatique : un arbre comme les vieux algorithmes en rectangle et losange pour les conditions et boucles, le next de la liste pointe donc sur n'importe quoi et les maillons (node) peuvent avoir un successeur ou 2 successeurs.
J'avais pensé à "vector" de la bibliothèque standard mais c'est un tableau dynamique mais pas une structure complexe !
Ce qui me perturbe aussi avec la liste chainee que je veux créer c'est l'ajout et le parcours de cet arbre car un maillon peut pointer vers un maillon à un niveau supérieur, 2 maillons peuvent pointer sur un même maillon.

En fait, le forum est pour l'entr'aide mais pas pour initier totalement quelqu'un dans tous ces projets, je demande seulement quelques tuyaux !

Merci d'avance !

[Lucas Panny]

Je cherche donc une liste chainée dont les éléments peuvent être de différents types pour chaque maillon !
Si je ne me trompe pas, list et vector de la STL ne peut pas que pour un seul type ! Comment le contourner ?

[loufoque]

Ce que tu veux c'est pas un graphe plutôt ?

[HanLee]

Ce que tu veux c'est pas un graphe plutôt ?

+1

[Lucas Panny]

Bonjour,

Je ne pense pas que ce soit un graphe !

J'ai utilisé le cas suivant:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
class A{
    string name;
}
 
class B:A{
    A * pNext;
}
 
class C:A{
    A * pLeft, * pRight;
}

Puis j'utilise une structure list de la STL:

Code :

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

1
2
3
4
5
std::list<A *> InstructionList;
B a1=new B("Salut");
C a2=new C("Hello");
InstructionList.push_back(a1);
InstructionList.push_back(a2);

et ben ça marche !

Mais je ne sais pas comment parcourir de telle liste: une liste qui contient que des objets de type A et de type de ses dérivées. Mais comment aller dans les listes des pointeurs dans la classe B et C.

[EDIT]Merci de penser à la balise CODE koala01

[Lucas Panny]

Bonsoir !

Si quelqu'un peut admirer ce bout de code et comprendre comment le parcourir, il est le bienvenu ! Tout à l'heure, je me suis trompé de thread , sorry !!!

[Lucas Panny]

Voici je pense parcourir un type list

Code :

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

1
2
3
4
5
  std::list<A *> ListDInstructions;
 
  std::list<A *>::iterator itor;
  for (itor = ListDInstructions.begin (); itor != ListDInstructions.end (); ++itor)
    (*itor)->generer ();

generer une méthode d'affichage dan la classe B comme suit

Code :

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

1
2
3
4
5
6
virtual void generer () { 
		std::cout <<name << std::endl;
		std::list<A *>::iterator itor;
		for (itor = pNext.begin (); itor != pNext.end (); ++itor)
			(*itor)->generer ();
	}

J'affiche le maillon de la liste puis la boucle de itor me permet d'afficher le contenu de pNext. Ca semble marcher mais est-ce correct selon vous ?

Qu'en pensez-vous de ma structure chers amis ?

[aoyou]

Ta structure de données représente déjà en elle-même une liste chaînée (si on ne regarde que les objets B). Je ne vois pas pourquoi alors tu veux une liste de la STL.

Avec ton parcours, tu risques d'appeler générer sur plusieurs fois le même élément à moins que tu fasses une liste (STL) contenant des listes chaînées... encore que non. 9a ne compile pas. Quand on lit le code de generer de ta classe b, tu suggéres que pNext est une liste STL et non plus un A*.

Prenons une liste à deux éléments, l'élément suivant b1 est b2. b1 -> b2. Tu chaines donc tes éléments ainsi

Code :

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

1
2
3
 
b1.pNext = b2;
b2.pNext = NULL;

Tu n'as alors plus besoin d'une liste STL.

Alors tu choisis, liste STL ou ta structure de données mais pas les deux.

Ou alors tu conserves le chaînage dans la liste mais sans rappeler generer sur pNext (ce qui n'a plus beaucoup d'intérêt)

[loufoque]

le next de la liste pointe donc sur n'importe quoi et les maillons (node) peuvent avoir un successeur ou 2 successeurs.

A priori, c'est un arbre binaire.

car un maillon peut pointer vers un maillon à un niveau supérieur, 2 maillons peuvent pointer sur un même maillon.

Ce n'est donc pas un arbre (graphe orienté) mais un graphe général.

[Lucas Panny]

Voici un bout de mon code pour que mon prob soit plus précis, je l'ai écris sous Visual C++ utilisant des classes STL:

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
class CInstruction
{
public:
  // Constructeurs/destructeur
  CInstruction () { }
  CInstruction (string _zName): zInstruction (_zName) { }
 
  //virtuel pour que lorsque les dérivées sont détruites, elles affichent leurs zInstruction propres	
  virtual ~CInstruction () { 
	  cout << "destroying " << zInstruction << endl; }
 
public:
  virtual void generer () { }
 
protected:
  string zInstruction;
};
 
class CLoop : public CInstruction
{
public:
  // Constructeur
  CLoop (string _zInstr): CInstruction (_zInstr) { }
 
  void addInstruction(CInstruction * pInstr){
		pAction.push_back(pInstr);
	}
 
private:
	list<CInstruction *>  pAction; //pointeur vers les instructions dans la boucle
  // Fonctions internes
	virtual void generer () { 
		cout << "TANT QUE (" << zInstruction << ")"<<endl;
		list<CInstruction *>::iterator itor;
		for (itor = pAction.begin (); itor != pAction.end (); ++itor)
			(*itor)->generer ();
		cout<<"FIN TANT QUE"<<endl; 
	}
};
 
class CCondition : public CInstruction
{
public:
  // Constructeur
  CCondition (string _zCondition): CInstruction (_zCondition) { }
 
  void addIf(CInstruction * pInstr){
	  pIf.push_back(pInstr);
  }
  void addElse(CInstruction * pInstr){
	  pElse.push_back(pInstr);
  }
 
private:
	list<CInstruction *>  pIf, pElse;
  // Fonctions internes
  virtual void generer () { 
	  cout << "IF (" << zInstruction << ") {"<<endl;
	  list<CInstruction *>::iterator itor;
	  //drawing si des instructions dans la condition TRUE
	  for (itor = pIf.begin (); itor != pIf.end (); ++itor)
		(*itor)->generer ();
	  cout <<"}\nELSE {\n";
	  //drawing si des instructions dans la condition FALSE
	  list<CInstruction *>::iterator itor2;
	  for (itor2 = pElse.begin (); itor2 != pElse.end (); ++itor2)
		(*itor2)->generer ();
	  cout<<"}\n";
  }
};
 
class CDoWhile : public CInstruction
{
public:
  // Constructeur
  CDoWhile (string _zCondition): CInstruction (_zCondition) { }
 
  void addInstruction(CInstruction * pInstr){
	  pAction.push_back(pInstr);
  }
 
private:
	list<CInstruction *>  pAction;
  // Fonctions internes
	virtual void generer () { 
		cout << "REPETER {" <<endl;
		list<CInstruction *>::iterator itor;
		for (itor = pAction.begin (); itor != pAction.end (); ++itor)
			(*itor)->generer ();
		cout<<"}\nJUSQU'A CE QUE ("<< zInstruction << ")"<<endl; 
	}
};
 
class CAffectation :  public CInstruction
{
public:
  // Constructeur
 CAffectation (string _zInstr): CInstruction (_zInstr) { }
 
 private:
  // Fonctions internes
  virtual void generer () { cout << "AFFECTER " << zInstruction << endl; }
};
 
int main ()
{
  cout << "# creating linked list :" << endl;
 
  //Rija : liste chainee de tout le programme
  list<CInstruction *> ListDInstructions;
 
  list<CInstruction *>::iterator itor;
 
  // Création des instructions
  CAffectation *a = new CAffectation ("a = 5");
  CAffectation *b = new CAffectation ("b = a * 2");
  CCondition * cond1 = new CCondition ("a > b");
  CLoop * loop1 = new CLoop ("i < 20");
 
  //Les instructions dans la condition et la boucle cond1 et loop1
  CAffectation * x1=new CAffectation(" x1 = 3");
  CAffectation * x2=new CAffectation(" x2 = 45789");
  CCondition * x3=new CCondition(" x1 == x2");
  CAffectation * x4=new CAffectation(" z = sin(25)");
 
  cond1->addIf(x1);
  cond1->addIf(x2);	
  x3->addIf(x4);
  cond1->addElse(x3);
 
  // On place les instructions dans la liste chainee de tout le programme
  ListDInstructions.push_back (a);
  ListDInstructions.push_back (b);
  ListDInstructions.push_back (cond1);
  ListDInstructions.push_back (loop1);
  //ListDInstructions.push_back (new CLoop ("(j == 3) && (i < 5)")); 
 
  // On affiche les instructions
  for (itor = ListDInstructions.begin (); itor != ListDInstructions.end (); ++itor)
    (*itor)->generer ();
 
  cout <<endl <<"# taille de ListDInstructions = "<<ListDInstructions.size()<<endl;
  // On retire "cond1" de la liste
  cout << endl << "# removing cond1 :" << endl;
 
  itor = ListDInstructions.begin ();
  advance (itor, ListDInstructions.size () - 3);
  ListDInstructions.erase (itor);
 
  // On redessine la liste puis on rattache "cond1" à la liste
  for (itor = ListDInstructions.begin (); itor != ListDInstructions.end (); ++itor)
    (*itor)->generer ();
 
  ListDInstructions.push_back (cond1);
 
  // Destruction des objets de la liste
  cout << endl << "# destroying linked list :" << endl;
 
  /*for (itor = ListDInstructions.begin (); itor != ListDInstructions.end (); ++itor)
    delete (*itor);*/
  return 0;
}

Je me demande pourquoi ça fait une exception dans la dernière partie dans cette boucle que j'ai mise en commentaire !

[aoyou]

Contrairement a ce que tu écris en commentaire, tu as deux cond1 dans ta liste.
Tu essaies donc de le supprimer deux fois, ce qui pose problème.

[Lucas Panny]

Bonjour,

L'erreur dans mon code se produit après les destructions des 4 listes push_backées à la liste chainée principale. Je ne crois pas que ce soit un problème de cond1 qui insérée puis enlevée puis réinsérée.
[QUOTE=aoyou]Ta structure de données représente déjà en elle-même une liste chaînée (si on ne regarde que les objets B). Je ne vois pas pourquoi alors tu veux une liste de la STL[QUOTE]
En effet aoyou, je veux utiliser la liste chainée list préfaite de la STL car je l'ai trouvé parfait après qlq essais.
Voyez la classe CBoucle par exemple, cette classée sera push_backée dans une liste chainee de CInstruction * , mais il contient aussi en attribut une liste chainee list<CInstruction *> pAction; qui m'est utile.

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
class CLoop : public CInstruction
{
public:
  // Constructeur
  CLoop (string _zInstr): CInstruction (_zInstr) { }
 
  void addInstruction(CInstruction * pInstr){
pAction.push_back(pInstr);
}
 
private:
list<CInstruction *>  pAction; //pointeur vers les instructions dans la boucle
  // Fonctions internes
virtual void generer () { 
cout << "TANT QUE (" << zInstruction << ")"<<endl;
list<CInstruction *>::iterator itor;
for (itor = pAction.begin (); itor != pAction.end (); ++itor)
(*itor)->generer ();
cout<<"FIN TANT QUE"<<endl; 
}
};

Comment parcourir une telle liste, existe-t-il une liste préfabriquée pareil ?
La liste que je cherche est donc comme un menu Fichier>Edition>Format>Affichage mais ces menus possèdent des menuitem Fichier->Nouveau>Ouvrir !

[aoyou]

J'insiste...
Quand j'ai regardé le code source hier soir, tu ne supprimais pas cond1 mais b je crois. Tu as donc deux cond1 dans ta liste.

Pour ma part, quand je corrige cette ligne là, je n'ai plus de problème.

Code :

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

  advance (itor, ListDInstructions.size () - 3);

Au passage, quitte à envoyer tout un code source, envoie le complet (avec les #include). C'est plus sympa pour celui qui essaie de compiler.

[Lucas Panny]

Ok, aoyou, j'enverrai le code complet la prochaine fois pour que vous puissez le tester, à ajouter au code précédent donc:

Code :

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

1
2
3
4
#include <iostream>
#include <string>
#include <list>
using namespace std;

Alors les amis, qu'en pensez vous de ma structure ? Est-ce que c'est optimisé parce que c'est déja faisable puisque mon code marche très bien sauf le bug que aoyou vient de corriger, je le remercie !