Arbre n-aire avec liste de fils stl (C++)
sylphide
-
Char Snipeur Messages postés 9813 Date d'inscription Statut Contributeur Dernière intervention -
Char Snipeur Messages postés 9813 Date d'inscription Statut Contributeur Dernière intervention -
Bonjour,
J'essaie de créer un arbre avec un nombre de fils variable et j'ai opté pour l'utilisation des listes stl pour les stocker. Voici ma structure :
using namespace std;
struct NOEUD{
int numero;
int valeur;
list <NOEUD*> fils;
}
Le problème est le suivant :
Je crée tout d'abord un NOEUD* que j'alloue dynamiquement. Ensuite impossible d'accéder à la liste des fils. Même un simple (noeud->fils).size() ne marche pas. J'ai droit à une belle erreur de segmentation comme si la liste n'existait tous simplement pas. Alors que si je crée hors de ma structure une liste de NOEUD* et que j'essaie d'en tirer la taille avant toute opération j'y arrive sans problème.
Merci d'avance pour votre aide.
J'essaie de créer un arbre avec un nombre de fils variable et j'ai opté pour l'utilisation des listes stl pour les stocker. Voici ma structure :
using namespace std;
struct NOEUD{
int numero;
int valeur;
list <NOEUD*> fils;
}
Le problème est le suivant :
Je crée tout d'abord un NOEUD* que j'alloue dynamiquement. Ensuite impossible d'accéder à la liste des fils. Même un simple (noeud->fils).size() ne marche pas. J'ai droit à une belle erreur de segmentation comme si la liste n'existait tous simplement pas. Alors que si je crée hors de ma structure une liste de NOEUD* et que j'essaie d'en tirer la taille avant toute opération j'y arrive sans problème.
Merci d'avance pour votre aide.
A voir également:
- Arbre n-aire avec liste de fils stl (C++)
- Liste déroulante excel - Guide
- Liste déroulante en cascade - Guide
- Liste code ascii - Guide
- Liste de diffusion whatsapp - Guide
- Site dangereux liste - Guide
6 réponses
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
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.
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.