Les Allergies
Alimentaires
Posez votre question Signaler

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

sylphide - Dernière réponse le 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.
Lire la suite 

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

13 réponses
Réponse
+0
moins plus
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é...
Ajouter un commentaire
Réponse
+0
moins plus
Ok j'essaierai tout en objet. Mais j'aimerais quand meme savoir pourquoi ca marche pas histoire d'ameliorer ma comprehension du truc.
Merci
Char Snipeur- 14 janv. 2011 à 14:42
met nous la partie de ton code qui alloue l'espace.
Ajouter un commentaire
Réponse
+0
moins plus
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;
}

Ajouter un commentaire
Réponse
+0
moins plus
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.
Ajouter un commentaire
Réponse
+0
moins plus
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.
KX- 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...
Lucas - 11 mars 2011 à 08:59
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.
Char Snipeur- 11 mars 2011 à 09:56
affirmation gratuite et fausse ! Trouver sur un site IBM (pas des guignols) http://publib.boulder.ibm.com/...
et pour t'en convaincre :
#include <iostream>
class C
{
  int i;
  double d;
public:
  C():i(11),d(2.1){}
};
struct S
{
  int i;
  double d;
};
int main()
{
  S s={21,1e-3};
  C c;
  std::cout<<*((int*)&s)<<" "<<*((double*)((int*)&s+1))<<"\n";
  std::cout<<*((int*)&c)<<" "<<*((double*)((int*)&c+1))<<"\n";
  return 0;
}

et bien entendu, j'obtiens les valeurs souhaitées. Montre moi un cas où cela ne fonctionne pas.
Ajouter un commentaire
Réponse
+0
moins plus
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.
Ajouter un commentaire
Ce document intitulé « Arbre n-aire avec liste de fils stl (C++) » issu de CommentCaMarche (www.commentcamarche.net) est mis à disposition sous les termes de la licence Creative Commons. Vous pouvez copier, modifier des copies de cette page, dans les conditions fixées par la licence, tant que cette note apparaît clairement.
Dossier à la une
Passage au tout numérique : quel coût pour les particuliers ?