bisuccesseur

Version imprimable

22/08/2007, 06h16
Lucas Panny

Modélisation d'une liste chainee/arbre mono/bisuccesseur

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 !
22/08/2007, 12h35
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 ?
22/08/2007, 14h19
loufoque

Ce que tu veux c'est pas un graphe plutôt ?
22/08/2007, 15h27
HanLee

Citation:

Envoyé par loufoque

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

+1
22/08/2007, 17h23
Lucas Panny
Bonjour,

Je ne pense pas que ce soit un graphe !

J'ai utilisé le cas suivant:
Code:

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:

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
22/08/2007, 22h08
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 !!!
22/08/2007, 22h57
aoyou

Est-ce que tu sais comment parcourir une liste list<C*> ?

A partir de là, en usant d'un peu de polymorphisme, tu devrais alors avoir une première solution.

Voici je pense parcourir un type list
Code:

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:

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 ?

23/08/2007, 11h14
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:

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)
23/08/2007, 14h59
loufoque

Citation:

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.

Citation:

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.

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:

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 !

23/08/2007, 21h56
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.

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:

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 !

24/08/2007, 10h23
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:

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.
24/08/2007, 13h16
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:

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 !
24/08/2007, 14h20
aoyou

Pour continuer dans la même idée que le bug, tu ne libères pas x1, x2, x3 et x4. C'est dommage de ne faire que la moitié du boulot.

Bah sinon, je ne sais pas trop, ça me paraît pas mal ce que tu as fait.

Bonjour !

Je pense que la raison du bug dans mon code est la rubrique de la faq C++
[B]Dois-je effacer ce que j'ai stocké dans un vecteur ?[B]

Citation:

Envoyé par LFE

La réponse dépend de la nature de ce qui est stocké dans un vecteur.
S'il s'agit d'un objet, il n'est pas utile de le détruire, il le sera lorsqu'il est retiré du vecteur, ou lorsque le vecteur est détruit.
Par contre, s'il s'agit d'un pointeur sur un objet, il faut le détruire car un pointeur n'est pas un objet. Si cette destruction n'est pas faite, le programme présentera une fuite de mémoire.

C'est sûrement mon cas car même en enlevant "advance (itor, ListDInstructions.size () - 3);" ça plante toujours à la fin.

Citation:

Envoyé par aoyou

Bah sinon, je ne sais pas trop, ça me paraît pas mal ce que tu as fait.

Je trouve aussi pas mal mon code mais je ne sais pas gérer les destructions surtout que la liste contient des pointeurs vers des objets. J'ai essayé donc de faire
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 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"); CLoop x4=new CLoop(" z == sin(25)"); cond1.addIf(x1); cond1.addIf(x2); CAffectation xfar = new CAffectation(" RRRRRRRRRRRRRRRR"); x4.addInstruction(xfar); x3.addIf(x4); cond1->addElse(x3); CAffectation xf1 = new CAffectation(" xf1 = abs(xf1/3))"); loop1->addInstruction(xf1); // 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); ...................................
C-à-d changer les listes en liste de <CInstruction> mais non plus de <CInstruction *>, mais beuh, il ne s'affiche plus rien, bizarre, je ne sais si je me suis bien expliqué mais pour éviter le soucis des instructions, j'ai voulu utiliser une liste de CInstruction tout court !!

25/08/2007, 16h19
aoyou

Si tu veux libérer la mémoire des éléments de ta liste, il faut que tu sois sûr qu'un pointeur n'est présent qu'une seule fois dans la liste. Comme tu ajoutes deux fois cond1, à la première libération de cond1 il n'y a pas de problème. Au deuxième cond1, tu as un segmentation fault. On ne peut pas libérer quelque chose qui a déjà été libéré.

Dans un tel cas, il faut que tu libéres tes éléments un à un et non en passant par la liste ou alors il faut que tu t'assures que chaque élément dans ta liste est unique (quitte a créer un nouvel objet avant de le mettre dans la liste).

Dans ton exemple, tu pourrais ne pas faire de new pour chacune de tes instructions. Tu n'aurais alors pas à libérer la mémoire.

Conserve ta liste de pointeurs ou ta méthode generer () ne pourra plus être virtuelle pure. Si tu ne vois plus rien, c'est surement que ça ne compile plus.
20/09/2007, 22h04
Lucas Panny

Bonjour chers collègues forumeurs !

Je reviens sur mon thread pour avoir plus de détails !

Mon modèle va donc utilisé la list ou vector de la STL :

Code:

list<CBaseType *> listInstructions;

où CBaseType ne sera jamais utilisé mais seulement les classes descendantes mais ces classes peuvent donc ensuite avoir des compositions list<CBaseClass *> !!! (voir le code que j'ai posté avant)

Fallait maintenant représenter cette structure : sous MFC de Visual C++ ou avec C++ Builder 6 ou ... La représentation de chaque type de classe est différente: ça peut-être un rectangle, un ellipse, 3 rectangles, rectangle+ellipse. Je connais la technique d'une liste chainée pour stocker les figures afin de pouvoir rafraichir !

Comment lier la structure logique avec l'affichage graphique ? Est-ce qu'on va utiliser un identifiant dans la logique et dans la classe graphique comme les clés primaires en Base de données