Arbre n-aire avec liste de fils stl (C++)
Fermé
sylphide
-
13 janv. 2011 à 20:19
Char Snipeur Messages postés 9688 Date d'inscription vendredi 23 avril 2004 Statut Contributeur Dernière intervention 2 octobre 2020 - 11 mars 2011 à 09:56
Char Snipeur Messages postés 9688 Date d'inscription vendredi 23 avril 2004 Statut Contributeur Dernière intervention 2 octobre 2020 - 11 mars 2011 à 09:56
A voir également:
- Arbre n-aire avec liste de fils stl (C++)
- Liste déroulante excel - Guide
- Liste de numéro de téléphone suspect 07 ✓ - Forum Mobile
- Annuaire inversé gratuit liste rouge - Forum Internet / Réseaux sociaux
- Le fichier contient une liste de prénoms. triez ce tableau par ordre alphabétique des prénoms. quel mot est formé par les 6 premières lettres de la colonne code ? - Forum Bureautique
- Triez la liste comme sur cette illustration (attention, on ne voit que le début …). quel est le mot formé par les 6 dernières lettres de la colonne code ? - Forum Excel
6 réponses
KX
Messages postés
16668
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
17 mars 2023
3 005
13 janv. 2011 à 21:26
13 janv. 2011 à 21:26
Tu travailles en C++, qui plus est avec la STL, alors pourquoi ne pas tout faire objet ?
Ça te faciliterai la gestion de la mémoire et t'éviterai ainsi quelques erreurs...
Remarque : j'aurai probablement choisi set plutôt que list, ça me semble plus adapté...
Ça te faciliterai la gestion de la mémoire et t'éviterai ainsi quelques erreurs...
class Arbre
{
int numero;
int valeur;
list<Arbre> fils;
};
Remarque : j'aurai probablement choisi set plutôt que list, ça me semble plus adapté...
Ok j'essaierai tout en objet. Mais j'aimerais quand meme savoir pourquoi ca marche pas histoire d'ameliorer ma comprehension du truc.
Merci
Merci
Char Snipeur
Messages postés
9688
Date d'inscription
vendredi 23 avril 2004
Statut
Contributeur
Dernière intervention
2 octobre 2020
1 328
14 janv. 2011 à 14:42
14 janv. 2011 à 14:42
met nous la partie de ton code qui alloue l'espace.
KX
Messages postés
16668
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
17 mars 2023
3 005
Modifié par KX le 14/01/2011 à 14:17
Modifié par KX le 14/01/2011 à 14:17
Il faudrait voir comment tu as fait ton allocation dynamique pour comprendre d'où vient le problème !
Voici un code (que je trouve personnellement très moche :p) mais qui marche.
La confiance n'exclut pas le contrôle
Voici un code (que je trouve personnellement très moche :p) mais qui marche.
// 0
// / \
// / \
// 1 2
// / \ / \
// 11 12 21 22
#include <iostream>
#include <list>
struct NOEUD
{
int numero;
int valeur;
std::list<struct NOEUD *> fils;
};
void afficher(struct NOEUD *arbre,unsigned n=0)
{
for (unsigned i=0; i<n; i++)
std::cout << "\t";
std::cout << arbre->numero << " " << arbre->valeur << std::endl;
for (std::list<struct NOEUD *>::const_iterator it=arbre->fils.begin(); it!=arbre->fils.end(); it++)
{
afficher(*it,n+1);
}
}
int main(void)
{
std::list<struct NOEUD *> liste(NULL);
struct NOEUD arbre = { 0, 0, liste };
std::list<struct NOEUD *> liste1(NULL);
struct NOEUD fils1 = { 1, 1, liste1 };
std::list<struct NOEUD *> liste11(NULL);
struct NOEUD fils11 = { 11, 11, liste11 };
fils1.fils.push_back(&fils11);
std::list<struct NOEUD *> liste12(NULL);
struct NOEUD fils12 = { 12, 12, liste12 };
fils1.fils.push_back(&fils12);
arbre.fils.push_back(&fils1);
std::list<struct NOEUD *> liste2(NULL);
struct NOEUD fils2 = { 2, 2, liste2 };
std::list<struct NOEUD *> liste21(NULL);
struct NOEUD fils21 = { 21, 21, liste21 };
fils2.fils.push_back(&fils21);
std::list<struct NOEUD *> liste22(NULL);
struct NOEUD fils22 = { 22, 22, liste22 };
fils2.fils.push_back(&fils22);
arbre.fils.push_back(&fils2);
afficher(&arbre);
return 0;
}
La confiance n'exclut pas le contrôle
Bonjour,
En fait si j'ai bien compris avant de créer un noeud tu créer une liste et après tu créer le noeud qui contient cette liste. Finalement ca revient à faire une sorte d'"allocation dynamique" de la liste avant de l'insérer via le noeud si j'ai bien compris. Ou plus précisément tu fais l'allocation dynamique d'un noeud avant de l'ajouter dans une liste que tu insère dans le noeud d'origine. Enfin cela à beau être une écriture "moche" ça m'aide à comprendre et cela améliore ma compréhension de la stl.
Merci Beaucoup.
En fait si j'ai bien compris avant de créer un noeud tu créer une liste et après tu créer le noeud qui contient cette liste. Finalement ca revient à faire une sorte d'"allocation dynamique" de la liste avant de l'insérer via le noeud si j'ai bien compris. Ou plus précisément tu fais l'allocation dynamique d'un noeud avant de l'ajouter dans une liste que tu insère dans le noeud d'origine. Enfin cela à beau être une écriture "moche" ça m'aide à comprendre et cela améliore ma compréhension de la stl.
Merci Beaucoup.
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
Pour compléter, les seules allocations dynamique que je fais sont :
NOEUD* arbre;
arbre=(NOEUD*)malloc(sizeof(NOEUD));
Évidement je me rends compte que cela ne suffit pas.
NOEUD* arbre;
arbre=(NOEUD*)malloc(sizeof(NOEUD));
Évidement je me rends compte que cela ne suffit pas.
Char Snipeur
Messages postés
9688
Date d'inscription
vendredi 23 avril 2004
Statut
Contributeur
Dernière intervention
2 octobre 2020
1 328
15 janv. 2011 à 19:53
15 janv. 2011 à 19:53
en C++, utilise new pour créer des objet, c'est mieux, et delete pour les détruire.
arbre=new NOEUD;
arbre=new NOEUD;
KX
Messages postés
16668
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
17 mars 2023
3 005
15 janv. 2011 à 19:57
15 janv. 2011 à 19:57
Est-ce que cela marchera aussi alors que NOEUD n'est pas une classe mais un struct ?
Char Snipeur
Messages postés
9688
Date d'inscription
vendredi 23 avril 2004
Statut
Contributeur
Dernière intervention
2 octobre 2020
1 328
15 janv. 2011 à 20:05
15 janv. 2011 à 20:05
je me doutait que tu parlais sans savoir ;-)
en C++ "struct" et "class" n'ont qu'une seule et unique différence. Par défaut les membres sont privés dans les class et public dans les struct. Il n'est donc pas obligatoire de faire "struct NEOUD arbre" comme en C, "NOEUD arbre" suffit.
en C++ "struct" et "class" n'ont qu'une seule et unique différence. Par défaut les membres sont privés dans les class et public dans les struct. Il n'est donc pas obligatoire de faire "struct NEOUD arbre" comme en C, "NOEUD arbre" suffit.
KX
Messages postés
16668
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
17 mars 2023
3 005
15 janv. 2011 à 20:19
15 janv. 2011 à 20:19
J'avoue ne pas avoir l'habitude de mélanger C et C++, quand je fais du C++ je fais tout objet.
Je pensais que new servait à faire une allocation dynamique en appelant la constructeur de la classe et que du coup il ne pouvait pas être appliqué à autre chose qu'un objet...
Je pensais que new servait à faire une allocation dynamique en appelant la constructeur de la classe et que du coup il ne pouvait pas être appliqué à autre chose qu'un objet...
Si je peux me permettre une petite remarque pour Snipeur, entre une struct et une classe, la seule différence n'est pas les méthodes privées ou publiques par défaut, il y est aussi question de mémoire. En effet, dans une struct, les données sont stockées de façon séquentielle( à la suite en mémoire) alors que dans une classe ,ce n'est pas le cas. Par exemple, si on a une structure comme ceci :
struct A
{
short val1;
short val2;
};
La valeur val1 se trouve à l'offset 0 par rapport à A tandis que val2 se trouve à l'offset A+sizeof(val1). ce ne serait pas le cas pour une classe.
C'est aussi pour cela que l'on utilise des struct pour faire de lectures de fichiers (lire un header de fichier EXE ou autre).
Voila pour la petite info.
struct A
{
short val1;
short val2;
};
La valeur val1 se trouve à l'offset 0 par rapport à A tandis que val2 se trouve à l'offset A+sizeof(val1). ce ne serait pas le cas pour une classe.
C'est aussi pour cela que l'on utilise des struct pour faire de lectures de fichiers (lire un header de fichier EXE ou autre).
Voila pour la petite info.
KX
Messages postés
16668
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
17 mars 2023
3 005
15 janv. 2011 à 00:13
15 janv. 2011 à 00:13
En fait, je ne fais pas d'allocation dynamique dans mon exemple !
Toutes mes listes sont détruites (appel du destructeur de l'objet) dès qu'elles ne sont plus dans la portée de leur définition (ici mon main).
C'est pour ça que j'ai jugé mon code "moche", ça ne marcherai pas en général.
Toutes mes listes sont détruites (appel du destructeur de l'objet) dès qu'elles ne sont plus dans la portée de leur définition (ici mon main).
C'est pour ça que j'ai jugé mon code "moche", ça ne marcherai pas en général.