Discussion :

[Orus]

Voici un petit projet que j'ai à compléter en C++ sur les arbres binaires et équilibrés

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
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
 
#ifndef _Binary_tree
 
#define _Binary_tree
 
 
 
#include <math.h>
 
#include <stddef.h> // NULL
 
#include <cassert>
 
 
 
template<class T> class Binary_tree {     
 
protected:            
 
	T _content;
 
	Binary_tree<T>* _left,*_right,*_super;
 
	int number_node() const;
 
	int search() const;
 
public:  
 
	inline virtual bool validator() const{ return true;}   /* Fonction utile pour l'arbre AVL */ 
 
	Binary_tree(const T&);
 
	int h() const;
 
	int H() const;
 
	virtual bool isAVL() const;
 
	virtual void push_left(Binary_tree<T>*);
 
	virtual void push_right(Binary_tree<T>*);
 
	inline Binary_tree<T>* root() {if(! _super) return this;return _super->root();};
 
	inline Binary_tree<T>*& super() {return _super;};
 
	virtual bool isComplete() const;
 
	virtual bool isPerfect() const;
 
	virtual bool remove_left();
 
	virtual bool remove_right();
 
 
 
};
 
template<class T> Binary_tree<T>::Binary_tree(const T& t) : _content(t) {
 
	_left = _right = _super = NULL;
 
}
 
template<class T> int Binary_tree<T>::h() const {
 
	if(! _super) return 0;
 
	return _super->h() + 1;	
 
}
 
template<class T> int Binary_tree<T>::H() const {
 
	int H_left,H_right;
 
	_left ? H_left = _left->H() + 1 : H_left = 0;
 
	_right ? H_right = _right->H() + 1 : H_right = 0;	
 
	return H_left < H_right ? H_right : H_left;	
 
}
 
template<class T> bool Binary_tree<T>::isAVL() const {  
 
	if(! _left && ! _right) return true; 
 
	if(! _left) return _right->H() < 1;  /* il faut enlever le = ? */
 
	if(! _right) return _left->H() < 1; 	
 
	return ::abs(_right->H() - _left->H()) <= 1;
 
}
 
template<class T> void Binary_tree<T>::push_left(Binary_tree<T>* left) {
 
	bool add;
 
	assert(left);
 
	if(_left || left->_super) return;
 
	left->_super = this;
 
	_left = left;
 
	add = root()->validator();
 
	if(add == false){
 
	  left->_super = NULL;
 
	  _left = NULL;
 
	}	
 
}
 
template<class T> void Binary_tree<T>::push_right(Binary_tree<T>* right) {
 
	bool add;
 
	assert(right);
 
	if(_right || right->_super) return;
 
	right->_super = this;
 
	_right = right;	
 
	add = root()->validator();
 
	if(add == false){
 
	  right->_super = NULL;
 
	  _right = NULL;
 
	}
 
}
 
template<class T> int Binary_tree<T>::number_node() const {
 
	int nbNode=0;
 
	if(_left != NULL) nbNode = nbNode + _left->number_node();
 
	if(_right != NULL) nbNode = nbNode + _right->number_node();
 
	return (1+nbNode);
 
}
 
template<class T> bool Binary_tree<T>::isComplete() const {
 
	double height;                  /* nombre de noeuds théoriques selon la hauteur */
 
	double nbNode;
 
	height = pow(2,H()+1)-1;
 
	nbNode = number_node();
 
	if(height == nbNode)return true;
 
	else return false;
 
}
 
template<class T> int Binary_tree<T>::search() const{  
 
	if(!_right && !_left) return 1; 
 
	if(!_left && _right) return 0;
 
	if(_left && !_right) return 1;
 
	if(_left->search() >= _right->search()) return 1;
 
	else return 0;
 
}
 
template<class T> bool Binary_tree<T>::isPerfect() const {
 
	double height;         /* Nombre de noeuds théoriques minimum selon la hauteur */
 
	double nbNode;
 
	height = pow(2,H())-1;
 
	nbNode = number_node();
 
	if(nbNode <= height) return false;
 
	else return search();
 
}
 
template<class T> bool Binary_tree<T>::remove_left() {
 
	Binary_tree<T> *temp1,*temp2;
 
	bool del = true;        /* valide ou pas la suppression */
 
	temp1 = _left;
 
	temp2 = _left->_super;
 
	_left->_super = NULL;
 
	_left = NULL;
 
	del = root()->validator();
 
	if(del == false){
 
	  _left = temp1;
 
	  _left->_super = temp2;
 
	}
 
	return del;
 
}
 
template<class T> bool Binary_tree<T>::remove_right() {
 
	Binary_tree<T> *temp1,*temp2;
 
	bool del = true;        /* valide ou pas la suppression */
 
	temp1 = _right;
 
	temp2 = _right->_super;
 
	_right->_super = NULL;
 
	_right = NULL;
 
	del = root()->validator();
 
	if(del == false){
 
	  _right = temp1;
 
	  _right->_super = temp2;
 
	}
 
	return del;
 
}
 
 
 
 
 
template<class T> class AVL_tree : public Binary_tree<T> {
 
protected:
 
	virtual bool validator() const; /* Valide ou pas la modification de l'arbre AVL */
 
public:
 
	AVL_tree(const T&);
 
	virtual void push_left(Binary_tree<T>*);
 
	virtual void push_right(Binary_tree<T>*); 
 
	inline bool isAVL() const { return true;}       
 
};
 
template<class T> AVL_tree<T>::AVL_tree(const T& t) : Binary_tree<T>(t) {
 
}
 
template<class T> void AVL_tree<T>::push_left(Binary_tree<T>* left) {
 
	bool add;
 
	assert(left);
 
	if(_left || left->super()) return;
 
	if(! _right && left->H() > 1) return;
 
	if(_right && ::abs(_right->H() - left->H()) > 1) return;
 
	left->super() = this;
 
	_left = left;
 
	if(_right != NULL) return;
 
	add = root()->validator();
 
	if(add == false){
 
	  left->super() = NULL;
 
	_left = NULL;
 
	}
 
}
 
template<class T> void AVL_tree<T>::push_right(Binary_tree<T>* right) {
 
	bool add;
 
	assert(right);
 
	if(_right || right->super()) return;
 
	if(! _left && right->H() > 1) return;
 
	if(_left && ::abs(_left->H() - right->H()) > 1) return;
 
	right->super() = this;
 
	_right = right; 
 
	if(_left != NULL) return;
 
	add = root()->validator();
 
	if(add == false){
 
	  right->super() = NULL;
 
	  _right = NULL;
 
	}
 
} 
 
template<class T>bool AVL_tree<T>::validator() const{
 
	if(_super == NULL){
 
	  if(this->Binary_tree<T>::isAVL()) return true;
 
	  else return false;
 
	}
 
}
 
#endif

je ne viens pas vous demander de l'aide pour le faire, vu que j'ai réussi à tout faire, et que ca marche (enfin à priori tout ce qu'on a testé, mais comme on nous a deja dit, ca peut marcher 1000 fois et la 1001eme fois aller dans le mur )

c'est surtout pour savoir si le code était propre ?, car c'est important et meme si on avait une partie en modèle, je préfère avoir des avis de pro comme vous

d'ailleurs si vous voyez quelquechose qui cloche aussi n'hésitez pas
je suis loin de maitriser les algorithmes et le C++ alors ca me permettra de m'améliorer

merci d'avance !!

[Luc Hermitte]

Je crois que tu connais déjà la réponse, non ?
- Indentation aléatoire. Trop de lignes sautées.
- Un fichu "if (expr) return true; else return false;" -- Et pas de retour si un truc est null
- Des pointeurs bruts qui circulent dans l'interface publique de la classe.
- Pas de commentaires
- Des variables déclarées sans être initialisées

[Aurelien.Regat-Barrel]

Peut être un pitit bug ici:

Code :

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

1
2
3
4
5
6
7
 
template<class T>bool AVL_tree<T>::validator() const{ 
        if(_super == NULL){ 
     if(this->Binary_tree<T>::isAVL()) return true; 
     else return false; 
   } 
}

si _super n'est pas NULL ça renvoie rien... Normalement ça donne droit à un warning ce genre de trucs.
Ce genre d'expressions tu peux simplifier :

Code :

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

1
2
3
4
5
6
 
template<class T>bool AVL_tree<T>::validator() const{ 
   if(_super == NULL)
      return this->Binary_tree<T>::isAVL();
   return false; // exemple
}

Ton identation est laborieuse au passage.
On peut chipoter sur certains trucs:

Code :

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

1
2
3
 
#include <cmath> 
#include <cstddef>

et du coup plus de :: devant abs. Tu pourrais aussi déclarer les variables plus près de leur première utilisation, surtout avec

Code :

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

1
2
3
4
5
6
7
8
 
    int H_left,H_right; 
 
   _left ? H_left = _left->H() + 1 : H_left = 0; 
 
   _right ? H_right = _right->H() + 1 : H_right = 0;    
 
   return H_left < H_right ? H_right : H_left;

Code :

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

1
2
3
4
5
6
7
8
9
10
 
   int H_left = _left ?
      _left->H() + 1 :
      0; 
 
   int H_right = _right ?
      _right->H() + 1 :
      0;    
 
   return std::min( H_left, H_right );

Je pense qu'on pourrait virer les inline aussi dans les classes, et utiliser typename au lieu de class en argument template.
Moi je suis assez exigent sur les conventions, en particulier un coup tu préfixes tes noms par this-> un coup non, moi j'aime bien quand c'est tout pareil

[Luc Hermitte]

J'avais manqué les symbôles préfixés par des underscores. A moins d'être un fournisseur du C, ce n'est pas pour toi.

[Orus]

Je crois que tu connais déjà la réponse, non ?
- Indentation aléatoire. Trop de lignes sautées.
- Pas de commentaires

en fait j'avais pas fait gaffe pour l'indentation, une partie du code nous a été fourni, on a complété, visiblement cela semblait bien aligné sour Emacs mais ca ne semble pas le cas, je vais l'éditer avec autre chose pour régler ca
[edit] ca devrait etre mieux la

en effet les commentaires sont faibles, mais on penser corriger ca en réalisant le rapport

- Un fichu "if (expr) return true; else return false;" -- Et pas de retour si un truc est null

c'est la fonction validator cité plus bas ? corrigé

- Des pointeurs bruts qui circulent dans l'interface publique de la classe.
- Des variables déclarées sans être initialisées

il faut forcément initialiser une variable quand on la déclare ??? on nous a jamais imposé cela

pour les pointeurs tu parles de ca par exemple ?

inline Binary_tree<T>* root() {if(! _super) return this;return _super->root();};

on nous la fournit celle la, mais je pourrais faire la remarque

Peut être un pitit bug ici:

Code :

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

1
2
3
4
5
6
7
 
template<class T>bool AVL_tree<T>::validator() const{ 
        if(_super == NULL){ 
     if(this->Binary_tree<T>::isAVL()) return true; 
     else return false; 
   } 
}

si _super n'est pas NULL ça renvoie rien... Normalement ça donne droit à un warning ce genre de trucs.
Ce genre d'expressions tu peux simplifier :

Code :

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

1
2
3
4
5
6
 
template<class T>bool AVL_tree<T>::validator() const{ 
   if(_super == NULL)
      return this->Binary_tree<T>::isAVL();
   return false; // exemple
}

en effet la vérification du NULL car normalement on est censé n'envoyer que des racines, c'est pour éviter au cas ou y aurait un mauvais appel de faire le traitement,
mais tu as raison on est censé renvoyé quelquechose car cette fonction doit renvoyer un booléen, merci pour l'erreur et pour l'optimisation que j'avais pas vu

On peut chipoter sur certains trucs:

Code :

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

1
2
3
 
#include <cmath> 
#include <cstddef>

et du coup plus de :: devant abs.

on nous a fournit ca comme ca

Tu pourrais aussi déclarer les variables plus près de leur première utilisation, surtout avec

Code :

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

1
2
3
4
5
6
7
8
 
    int H_left,H_right; 
 
   _left ? H_left = _left->H() + 1 : H_left = 0; 
 
   _right ? H_right = _right->H() + 1 : H_right = 0;    
 
   return H_left < H_right ? H_right : H_left;

On nous a toujours dit de tout déclarer au début en fait
alors c'est ce qu'on fait


quote]
Je pense qu'on pourrait virer les inline aussi dans les classes, et utiliser typename au lieu de class en argument template.
Moi je suis assez exigent sur les conventions, en particulier un coup tu préfixes tes noms par this-> un coup non, moi j'aime bien quand c'est tout pareil

On nous a dit que le inline etait obligatoire les fonctions en une ligne
et pour le this je crois l'avoir utilisé les this que pour les attributions, mis à part dans la fonction Validator, je sais pas pourquoi je l'ai mis dedans d'ailleurs , et dans une fonction inline mais celle la etait fournit


merci pour ces réponses je n'en attendais pas de si rapide

[Aurelien.Regat-Barrel]

inline est sous entendu dans le corps d'une classe. Par exemple, le fait que root() soit implémentée directement dans le classe la rend inline.

[Orus]

inline est sous entendu dans le corps d'une classe. Par exemple, le fait que root() soit implémentée directement dans le classe la rend inline.

ok
pourtant on nous a dit qu'il fallait le mettre dans 2cas :
quand on avait la fonction directement dans la classe et l'autre cas je sais plus

comme il a insisté dessus, on préfère faire ce qu'on nous dit

[Aurelien.Regat-Barrel]

Oui oui. Y'a 2 possibilités:
- ce qu'il est bon de faire
- ce que ton prof considère comme bon de faire
Pas la peine de dire la quelle choisir en TP/devoirs

[Orus]

Oui oui. Y'a 2 possibilités:
- ce qu'il est bon de faire
- ce que ton prof considère comme bon de faire
Pas la peine de dire la quelle choisir en TP/devoirs

en effet

en plus il a l'air assez à cheval sur les (ses?) normes

[SKZ81]

J'avais manqué les symbôles préfixés par des underscores. A moins d'être un fournisseur du C, ce n'est pas pour toi.

Hum... En l'occurence, j'utilse toujours des underscores pour préfixer les attributs de mes classes (leurs variables "private", j'entend).
A partir du moment où c'est encapuslé, je ne vois pas le problème....
Cela permet, comme dans l'exemple d'avoir un attribut _super et une méthode super()... Ce qui est loin d'être idiot ! Et ce sans se mélanger les pattes entre l'attribut et l'adresse d'une eventuelle méthode.
En fait dans le cas de la génération d'un modèle UML, on peut souvent redéfinir l'inspecteur (accesseur en lecture).
Ex : pour "attribut" on choisira souvent "getAttribut()", mais je peux choisir finalement "attribut()", et alors avoir généré la variable sous le nom "_attribut" sauve la mise... D'autre part ça évoque le "-" d'UML qui signifie "privé".

[Aurelien.Regat-Barrel]

Le problème c'est que c'est une convention dont l'usage est réservé aux créateurs de compilateurs.
Tu peux mettre tes undescores à la suite, utilise m_, ou faire comme moi : préfixer par 'z'. 8)

Code :

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

1
2
3
4
5
6
 
class Test
{
private:
    int zValue;
};

Ca m'étonnerais fort que Luc trouve pourquoi je fais ça

[Luc Hermitte]

@ Aurélien -> Parce que c'est zàtoi ? C'est la zis-value ?

@ SKZ81 -> Sinon, tu n'est pas à l'abri d'un mot clé propriétaire ou d'un symbôle pour le préprocesseur qui commence par un tiret-bas. Dans les faits c'est extrêmement rare -- les fournisseurs doivent savoir qu'il y a des développeurs qui ne sont pas au courant au sujet des symbôles réservés. Mais le jour où tous tes attributs "__gc" refusent de compiler, tu es content -- je n'ai pas d'exemple type-C (un seul tiret) en tête.

Perso pour mes développements, j'opte pour le post-fixage par le tiret-bas. Après, cela dépend des régles qualité des projets

Bref. Un dérivé de la notation hongroise (?) adapté aux attributs c'est très bien, mais le préfixage par des '_' est déconseillé.

[Aurelien.Regat-Barrel]

@ Aurélien -> Parce que c'est zàtoi ? C'est la zis-value ?

Eh eh, un utilisateur de VI ne peut pas trouver.
Quand j'écris:

Code :

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

1
2
3
 
Test t;
t.

Arrivé à t., hop une liste se déroule me proposant les fonctions / variables membres de Test. Vu que c'est private et donc non utilisable, avec un z devant ça se trouve en fin de liste et donc ça l'allège et accélère ma recherche et donc ma productivité

[Luc Hermitte]

Hum. Je rajoute à la todo list -> trier en fonction des accessibilités / essayer de détecter si on est dans un contexte duquel on peut accéder à ces trucs privés.

BTW, vim != VI. D'abord.

[JolyLoic]

Pour noter les attributs d'une classe, j'ai vu les cas suivants :

value_
m_value
myValue

Mon préféré actuellement est le denier, car à l'oral, il se prononce facilement. Il en existe des variantes avec our (pour les données statiques), is (pour les booléens)

[Orus]

merci pour ces précisions

on nous avait dit qu'on mettait _var pour les variables privées
dans ce cas la on va laisser, mais je saurais qu'en fait c'est pas le cas

[rolkA]

Pour noter les attributs d'une classe, j'ai vu les cas suivants :

value_
m_value
myValue

Mon préféré actuellement est le denier, car à l'oral, il se prononce facilement. Il en existe des variantes avec our (pour les données statiques), is (pour les booléens)

Bonjour je saute sur ce thread car je connais quelqu'un qui, pour faire la différence, dans une méthode d'une classe, entre les données membres (m_ chez moi) et le reste, utilise carrément le nom de la classe (Classe::donnee) par exemple, alors qu'on est dans l'implémentation de cette classe (dans le code d'une de ses méthodes). Vous avez déjà vu çà quelquepart ? Ca me paraît très lourd

Sinon pour Orus, n'oublie pas en effet de suivre les recommandations de ton prof, même s'il s'agit + de "ses" normes . Il s'agit aussi et surtout d'uniformiser le style de programmation à tous ses élèves pour que ce soit plus facile à lire/corriger et que tout le monde comprenne le code de son voisin

[Aurelien.Regat-Barrel]

Plus que lourd, ça me parrait problématique pour les fonctions virtuelles, à mois que ce soit l'effet recherché. Personnelement je préfixe tout par "this->" (fonctions / variables membres).

[tut]

@Aurélien : ça sert à quoi de mettre des "this" partout ? c'est uniquement esthétique ? à part lever l'ambiguïté qu'il peut y avoir sur des variables de même nom mais de portée différente, je ne vois pas à quoi ça sert, en plus ça doit bien alourdir le code.
perso, c'est "m_" devant les variables, "p" pour les pointeurs, et un peu de notation hongroise.
De toute façon, ce genre de chose est souvent défini par des règles de codage propre au projet.

[Luc Hermitte]

Sorti de règles de codage qui l'exigeraient, mettre "this->" partout devient nécessaire selon le standard (et GCC 3.4 -> du code a été cassé) avec certaines constructions à base de templates.