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

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
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
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 9688 Date d'inscription vendredi 23 avril 2004 Statut Contributeur Dernière intervention 2 octobre 2020 1 328
14 janv. 2011 à 14:42
met nous la partie de ton code qui alloue l'espace.
0
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
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
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
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 9688 Date d'inscription vendredi 23 avril 2004 Statut Contributeur Dernière intervention 2 octobre 2020 1 328
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;
0
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
Est-ce que cela marchera aussi alors que NOEUD n'est pas une classe mais un struct ?
0
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
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 16668 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 17 mars 2023 3 005
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...
0
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 16668 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 17 mars 2023 3 005
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.
0