Arbre n-aire avec liste de fils stl (C++)

sylphide -  
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.

A voir également:

6 réponses

KX Messages postés 16761 Date d'inscription   Statut Modérateur Dernière intervention   3 020
 
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...

class Arbre
{
	int numero; 
	int valeur; 
	list<Arbre> fils; 
};

Remarque : j'aurai probablement choisi set plutôt que list, ça me semble plus adapté...
0
sylphide
 
Ok j'essaierai tout en objet. Mais j'aimerais quand meme savoir pourquoi ca marche pas histoire d'ameliorer ma comprehension du truc.
Merci
0
Char Snipeur Messages postés 9813 Date d'inscription   Statut Contributeur Dernière intervention   1 299
 
met nous la partie de ton code qui alloue l'espace.
0
KX Messages postés 16761 Date d'inscription   Statut Modérateur Dernière intervention   3 020
 
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.

//              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
0
sylphide
 
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.
0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
sylphide
 
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.
0
Char Snipeur Messages postés 9813 Date d'inscription   Statut Contributeur Dernière intervention   1 299
 
en C++, utilise new pour créer des objet, c'est mieux, et delete pour les détruire.
arbre=new NOEUD;
0
KX Messages postés 16761 Date d'inscription   Statut Modérateur Dernière intervention   3 020
 
Est-ce que cela marchera aussi alors que NOEUD n'est pas une classe mais un struct ?
0
Char Snipeur Messages postés 9813 Date d'inscription   Statut Contributeur Dernière intervention   1 299
 
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.
0
KX Messages postés 16761 Date d'inscription   Statut Modérateur Dernière intervention   3 020
 
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...
0
Lucas
 
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.
0
KX Messages postés 16761 Date d'inscription   Statut Modérateur Dernière intervention   3 020
 
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.
0