Sérialiser un arbre et sauver dans un fichierRésolu

Question

Bonjour,

Je suis debutant à ce que je vais vous demander. Ne soyez pas étonner si vous me trouvez pas trop clair.
En effet, je dispose d'un arbre N aire très complexe(chq Noeud a 500 fils eux aussi ont 500 fils chacun ainsi de suite), On me demande de serialiser cet arbre et le stocker dans un fichier sur le disque. Si quelqu'un a une idée de ce genre d'algorithme en C. 

Voila mon idée:
typedef struct noeud{
            int element;//contenu du noeud
            struct noeud**pfils;
 /* tableau de pointeur vers les 500 fils possibles de ce noeud*/
} noeud;

struct noeud* Arbre;

Je fais une fonction de Creer_Noeud() et une fonction [b]Creer_Fils();
/b
Mon probleme est que je n'ai aucune idée, sur comment construire cet arbre complexe, après le parcourir et le sauver. Merci pour vos aides.

korsakoff69 · Accepted Answer

peut être quelque chose comme ça

typedef struct NOEUD
{
int iID;            // identifiant
NOEUDDATA* pDATA;   // données du noeud
int* pTableauFils;  // pointeur vers un tableau d'identifiants des neouds fils

} noeud; 

puis fonction WriteToDisk pour le noeud
dans lequel tu sauve tes data du noeud
ainsi que les identifiants des fils

NB: il faut que l'intégralité des noeuds fils utilisés soient écrits sur le disque une fois, et d'utiliser les index pour recharger le tout

korsakoff69 · Answer

youscoul · Answer

Salut Korsakoff, 
NB: il faut que l'intégralité des noeuds fils utilisés soient écrits sur le disque une fois, et d'utiliser les index pour recharger le tout
Peux tu être beaucoup plus clair sur ce plan.Aussi je comprend pas ta structure. Quelle est la différence par rapport à celle que j'ai postulé plus haut. Merci

korsakoff69 · Answer

dans chaque noeud, tu stocke les données du noeud + 1 identifiant unique pour le noeud

et pour chaque noeud, tu stocke un tableau d'entier qui contient les identifiants des noeuds fils (  index )

pour charger et sauver les fils, tu parcours le tableau d'entier correspondant aux identifiants des noeuds fils, et tu peux donc associer à chaque identifiant dans le tableau un noeud unique pour chacun des ses fils.

quand tu sauve un noeud, tu sauve l'identifiant unique du noeud, et le tableau d'entier des identifiants des noeuds fils.

pour recharger les données, il faut donc que les noeuds fils existent dans le fichier

pour chque noeud, on charge les données du noeuds
pour chacun des ses noeuds fils, on parcourt le tableau d'entier du noeuds, et on charge chaque noeud fils

youscoul · Answer

C'est vraiment gentille tout ce que tu fais. Mais j'ai été clair au debut que c'est une premiere pour moi de travailler avec les arbres surtout avec de telle complexité. Donc si tes explications sont accompagnées de bout de code. Ca ne peut qu'être benefice pour moi et autre personne ayant le même problème dans le futur primo. Secondo, si j'ai plusieurs intervenants sur ce sujet c'est très difficile de coder les propositions de tout un chacun pour qu'il sache que j'ai pris en compte sa proposition. D'accord d'après ce que tu dis, je suppose que mon arbre est construit (même si j'ai pas de la même manière que toi) et ke je dois le parcourir et le stocker dans un fichier. voici le code de construction de l'arbre: typedef enum _profondeur_t{ A, B, C, D} prof_t; typedef struct _noeud_t{ unsigned numero_noeud; // noeud numeroté de 0 à 700 selon son profondeur unsigned nb_fils; struct _noeud_t **fils; // tableau de pointeurs vers ses fils prof_t profond; struct _noeud_t*pere; // Pour que chq fils connaisse son pere } noeud_t; typedef struct _arbre_t{ noeud_t *racine; } arbre_t; /** ***************************************************************/ /** @ Construction d'un neoud de l'arbre */ noeud_t* new_noeud(unsigned nb_fils) { noeud_t *noeud = (noeud_t*)malloc(sizeof(noeud_t)); noeud->fils =(noeud_t**) calloc(nb_fils,sizeof(noeud_t)); noeud->nb_fils = nb_fils; return noeud; } /** @ Construction en fonction de son profondeur dans l'arbre */ noeud_t* new_noeud2(prof_t prof_noeud) { unsigned nb_fils; switch(prof_noeud) { case A: nb_fils = 64; break; case B: nb_fils = 64; break; case C: nb_fils = 700; break; case D: nb_fils = 700; break; default: nb_fils = 1; break; } return new_noeud(nb_fils); } /** @ Supprimer d'un neoud de l'arbre */ void supprimer_noeud(noeud_t *noeud) { unsigned i; // Appel récursif : on détruit les fils avant le noeud courant for(i=0;inb_fils;++i) { if(noeud->fils[i]) supprimer_noeud(noeud->fils[i]); } // On relâche le noeud courant free(noeud->fils); // relâche le calloc free(noeud); // relâche le malloc } /** @ Construction d'un fils à partir d'un noeud de l'arbre */ // Pour initialiser le index ème fils d'un noeud, il faut désallouer le index ème fils (s'il y en a déjà un) void construit_un_fils(noeud_t *noeud, unsigned index, noeud_t *fils) { if(index < fils->nb_fils) { if(noeud->fils[index]) supprimer_noeud(noeud->fils[index]); noeud->fils[index] = fils; } } // Et pour récupérer le ième fils d'un noeud : noeud_t *get_fils(noeud_t *noeud, unsigned i) { if(i < noeud->nb_fils) return noeud->fils[i]; } Avec ce code je doispouvoir construire mon arbre, mais comment je fais pour inserer les données et surtout une fonction de parcours de l'argent afin de le stocker merci.

youscoul · Answer

Desolé je veux dire une fonction de parcours de l'arbre....!!!!! et non l'argent ke je suis pauvre moi (ke l'argent en tête alors que suis un simple étudiant qui n'a même pas fait la moitié de son cycle LOL)

korsakoff69 · Answer

tu devrais regarder un tutoriel sur les listes doublement chaînées

en gros : dans chaque noeud tu stocke un pointeur vers le noeud parent et le noeud fils

voici un exemple de liste simplement chainée que j'utilise avec visual studio c++, 
tu peux peut être t'en inspirer

//-----------------------------------------------------------------------------
// Nom: Classe CGameObjectListe
// Desc: liste de GameObjects, avec fonctions de liste
//-----------------------------------------------------------------------------
class CGameObjectListe
{
public:	
CGameObjectListe::CGameObjectListe( void );		// constructeur
CGameObjectListe::~CGameObjectListe( void );	      // destructeur

CGameObject* AddNewGameObject( int iObjectID );	         // ajoute nouvel item
void AddExistingGameObject( CGameObject* pGameObject );	// ajoute item existant
void RemoveGameObjectFromListe( CGameObject* pGameObject );		// supprime item de la liste
CGameObject* FindGameObject( int iObjectID );					// trouve item
void OutputGameObjectListeDebug();								// output iObjectID de l'élément courant
CGameObject* GetGameObjectListHead() { return m_pListeHead; }	// renvoie tête de liste
int GetGameObjectCount() { return m_iNbObjects; }				// renvoie le nombre total d'objets

/*	void DeleteGameObject( int iObjectID );						// supprime item par id

*/
private:
CGameObject* m_pListeHead;	// pointeur vers le premier élément créé
int m_iNbObjects;			// nombre d'objets créés


};

// les déclarations

/*----------------------------------*/
/*	Classe CGameObjectListe			*/
/*	Desc: liste de GameObject		*/
/*----------------------------------*/

//-----------------------------------------------------------------------------
//	constructeur
//-----------------------------------------------------------------------------
CGameObjectListe::CGameObjectListe( void )
{
//	OutputDebugString( L"CGameObjectListe::CGameObjectListe() constructeur
" );

m_iNbObjects = g_static_iNbObject;	// nombre total d'objets
m_pListeHead = NULL;				// initialise le premier élément de la liste
}
//-----------------------------------------------------------------------------
//	destructeur
//-----------------------------------------------------------------------------
 CGameObjectListe::~CGameObjectListe( void )
{
//	OutputDebugString( L"CGameObjectListe::~CGameObjectListe() destructeur
" );

}

//-----------------------------------------------------------------------------
//	Ajoute nouveau GameObject
//-----------------------------------------------------------------------------
CGameObject* CGameObjectListe::AddNewGameObject( int iObjectID )
{
//	OutputDebugString( L"CGameObjectListe::AddNewGameObject()
" );

CGameObject* pGameObject = new CGameObject;	// créé nouvel élément

m_iNbObjects++;

pGameObject->SetObjID( iObjectID );				// On fixe la iObjectID de l'élément

// Comme on place le nouvel élément en début de liste,
// on dit que son suivant est le premier élément de la liste.
pGameObject->m_pNextObject = m_pListeHead;

// Puis on remet à jour le pointeur vers le  premier élément de la liste
// qui est notre nouvel élément.
m_pListeHead = pGameObject;

return pGameObject;
}
//-----------------------------------------------------------------------------
//	Ajoute GameObjectexistant
//-----------------------------------------------------------------------------
void CGameObjectListe::AddExistingGameObject( CGameObject* pGameObject )
{
WCHAR sz[256];
OutputDebugString( L"CGameObjectListe::AddExistingGameObject()
" );
StringCchPrintfW( sz, 256, L"object ajouté ID: %i,
",	pGameObject->GetObjID() );
OutputDebugString( sz );

m_iNbObjects++;

//	iObjectID = pGameObject->iObjectID;			// On fixe la iObjectID de l'élément

// Comme on place le nouvel élément en début de liste,
// on dit que son suivant est le premier élément de la liste.
pGameObject->m_pNextObject = m_pListeHead;

// Puis on remet à jour le pointeur vers le  premier élément de la liste
// qui est notre nouvel élément.
m_pListeHead = pGameObject;

return ;
}

//-----------------------------------------------------------------------------
// Nom:	RemoveGameObjectFromListe()
// Desc: supprime un objet de la liste ( ne le détruit pas )
//-----------------------------------------------------------------------------
void  CGameObjectListe::RemoveGameObjectFromListe( CGameObject* pGameObject )
{
//	OutputDebugString( L"CGameObjectListe::RemoveGameObjectFromListe()
" );

CGameObject* pPreviousObject = m_pListeHead;

if( pGameObject == m_pListeHead )	// si l'élément à supprimer est le premier de la liste
{
m_pListeHead = NULL;
//		delete pGameObject;
m_iNbObjects--;
return; 
} 

// Sinon, il faut rechercher l'élément précédent, et détourner le pointeur de ce précédent pour
// pointer vers l'élément suivant celui à supprimer.  ainsi, il ne se trouve plus dans la liste. 
while( ( pPreviousObject != NULL ) && ( pPreviousObject->m_pNextObject != pGameObject ) )
pPreviousObject = pPreviousObject->m_pNextObject;

if( pPreviousObject == NULL ) 
{
m_iNbObjects--;
return;	
}

pPreviousObject->m_pNextObject = pGameObject->m_pNextObject;

//	delete pGameObject;
m_iNbObjects--;

}

//-----------------------------------------------------------------------------
// Nom: FindGameObject()
// Desc:  trouve un élément par son ID
//-----------------------------------------------------------------------------
CGameObject*  CGameObjectListe::FindGameObject( int iObjectID )
{
//	OutputDebugString( L"CGameObjectListe::FindGameObject()
" );

if ( g_static_iNbObject == 0 )
{
OutputDebugString( L"CGameObjectListe::FindGameObject() PAS D'OBJETS DANS LAS LISTE 
" );
return NULL;	// il n'y a aucun objet
}

CGameObject* pGameObject = m_pListeHead;	// le premier élément

if ( pGameObject == NULL )
{
OutputDebugString( L"CGameObjectListe::FindGameObject() PAS DE LISTE HEAD 
" );
return NULL;	// il n'y a aucun objet
}


// méthode de recherche:
// On se place en première position, et tant  qu'il y a des éléments suivants,
// on balaye la liste jusqu'à ce qu'on trouve un élément de liste qui contienne la iObjectID
// recherchée.

while( ( pGameObject != NULL )&&(  pGameObject->GetObjID() != iObjectID ) )
pGameObject = pGameObject->m_pNextObject; 

// ici, on renvoie une information pertinente :
// - ou bien on a trouvé quelque chose, auquel cas on renvoie ce quelque chose,
// - ou bien on n'a rien trouvé et l'élement vaut NULL,
//  ce qui indique qu'un élément n'a pas été trouvé.

return pGameObject;
} 

//-----------------------------------------------------------------------------
//	OutputGameObjectListe()
//	Desc: sortie debug des objets et de leurs types dérivés
//-----------------------------------------------------------------------------
void  CGameObjectListe::OutputGameObjectListeDebug()
{
OutputDebugString( L"CGameObjectListe::OutputGameObjectDebug()
" );

wchar_t* sz = new wchar_t[256];
CGameObject* pGameObject = m_pListeHead;	 // pointeur vers le premier élément créé
CPlanet* pPlanet = NULL;
CShip* pShip = NULL;

while( pGameObject != NULL )
{
//		_itow_s( pGameObject->GetObjID(), sz, sizeof(sz), 10 );	// conversion int en wchar[] en base 10

if ( pGameObject->GetObjType() == TYPE_PLANET )
StringCchPrintf( sz, 256, L"object ID: %i, TYPE_PLANET 
", pGameObject->GetObjID() );
else if ( pGameObject->GetObjType() == TYPE_SHIP )
StringCchPrintf( sz, 256, L"object ID: %i, TYPE_SHIP 
", pGameObject->GetObjID() );

OutputDebugString( sz );

if ( pGameObject->GetObjType() == TYPE_PLANET )
{
pPlanet = (CPlanet*) pGameObject;
pPlanet->OutputPlanetDebug();
}
else if ( pGameObject->GetObjType() == TYPE_SHIP )
{
pShip = (CShip*) pGameObject;
pShip->OutputShipDebug();
}

pGameObject = pGameObject->m_pNextObject;
}

StringCchPrintf( sz, 256, L"NB TOTAL D'OBJETS: %i
", m_iNbObjects );
OutputDebugString( sz );

delete sz;

}

Sérialiser un arbre et sauver dans un fichier

7 réponses

Votre réponse

Discussions similaires