IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C Discussion :

binarisation d'un arbre n-aire


Sujet :

C

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre éclairé
    Inscrit en
    Novembre 2006
    Messages
    422
    Détails du profil
    Informations forums :
    Inscription : Novembre 2006
    Messages : 422
    Par défaut binarisation d'un arbre n-aire
    Slt j’ai fais qlq tentatives pour écrire un prog qui binarise un arbre n-aire. j’ai réussi a pondre une fonction qui binarise seulement les fils d’un nœud donné mais j’ai pas trouvé cmt faire pour qu’elle devienne récursive.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
     
    #define N 3
     
     
    typedef struct cel 
    {
    	int val;
    	cel* fils[N];
    }cel;
     
     
    typedef struct cel_b
    {
    	int val;
    	cel_b* fg;
    	cel_b* fd;
    }cel_b;
     
     
     
    void bin(cel** a,cel_b** b,int i)
    {
    	cel_b *temp=NULL,*bb;
     
    	puts("hy");
     
    	bb=(*b);
    	puts("entre");
    	while (i<N)
    	{
     
    		if ((*a)->fils[i]!=NULL)
    		{
     
    			if (i==0) 
    			{
    				puts("i==0");
    				bb->fg=creer_feuille_b(bb->fg);//creer_feuille_b //alloue la memoire et initialise les 2 fils du pointeur a null 
     
     
    				bb->fg->val=(*a)->fils[i]->val;
    				i++;
    			}
     
    			else
    			{
     
    				if (bb->fd==NULL  && (*a)->fils[1]!=NULL)
    				{
    						puts("b==NULL");
    					bb->fd=creer_feuille_b(bb->fd);
    					bb->fd->val=(*a)->fils[i]->val;
    					i++;
    				}
    				else
    				{
    					if ( (*a)->fils[i]!=NULL )
    					{
    					puts("recu");
     
    					bb->fd->fd=creer_feuille_b(bb->fd);
    					bb->fd->fd->val=(*a)->fils[i]->val;
    					i++;
    					}
    				}
     
    			}
     
     
     
    		puts("FINNN");
     
    	}
    		else
    		{
    		i++;
    		}
     
    }
     
    }
    Edit le code n’est pas encore propre.
    merci.

  2. #2
    Expert confirmé
    Avatar de Thierry Chappuis
    Homme Profil pro
    Enseignant Chercheur
    Inscrit en
    Mai 2005
    Messages
    3 499
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : Suisse

    Informations professionnelles :
    Activité : Enseignant Chercheur
    Secteur : Industrie Pharmaceutique

    Informations forums :
    Inscription : Mai 2005
    Messages : 3 499
    Par défaut
    Salut,

    Quelle est ta question sur le langage C? Est-ce la conception de l'agorithme qui te pose des problèmes? Son implantation? Donne-nous plus de précisions. Je jetterai un coup d'oeil au code quand j'aurais le temps, mais n'hésite pas à donner plus d'indications sur les problèmes que tu rencontres, voir même à poster le pseudo-code de l'algorithme que tu désires implanter.

    Cordialement

    Thierry
    "The most important thing in the kitchen is the waste paper basket and it needs to be centrally located.", Donald Knuth
    "If the only tool you have is a hammer, every problem looks like a nail.", probably Abraham Maslow

    FAQ-Python FAQ-C FAQ-C++

    +

  3. #3
    Membre éclairé
    Inscrit en
    Novembre 2006
    Messages
    422
    Détails du profil
    Informations forums :
    Inscription : Novembre 2006
    Messages : 422
    Par défaut
    slt deja l'algo me pose un probleme et comme je l'ai dit je n'ai pas pu rendre la fonction recursive , elle n'opere que pour 1 noeud.
    merci

  4. #4
    Expert éminent
    Avatar de Médinoc
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Septembre 2005
    Messages
    27 397
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2005
    Messages : 27 397
    Par défaut
    Ton code est mal indenté et tes noms de variables trop peu explicites.
    Tu le fais exprès "pour corser le jeu" ?

    Edit: Ceci ne compile pas en C:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    typedef struct cel 
    {
    	int val;
    	cel* fils[N];
    }cel;
     
     
    typedef struct cel_b
    {
    	int val;
    	cel_b* fg;
    	cel_b* fd;
    }cel_b;
    De plus, je pense que le pointeur passé en paramètre à creer_feuille_b est inutile, d'après ton commentaire.

    PS: Qu'est-ce que c'est que cette manie de mettre un espace entre un opérateur et sa parenthèse ouvrante?
    Y'a vraiment des gens qui trouvent ça plus lisible ??
    SVP, pas de questions techniques par MP. Surtout si je ne vous ai jamais parlé avant.

    "Aw, come on, who would be so stupid as to insert a cast to make an error go away without actually fixing the error?"
    Apparently everyone.
    -- Raymond Chen.
    Traduction obligatoire: "Oh, voyons, qui serait assez stupide pour mettre un cast pour faire disparaitre un message d'erreur sans vraiment corriger l'erreur?" - Apparemment, tout le monde. -- Raymond Chen.

  5. #5
    Expert éminent
    Avatar de Médinoc
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Septembre 2005
    Messages
    27 397
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2005
    Messages : 27 397
    Par défaut
    Tiens, je me suis essayé à la binarisation, dis-moi ce que tu ne comprends pas dans ce code:
    Code C : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    #include <stdlib.h>
    #include <assert.h>
     
    #define N 3
     
    typedef struct cel 
    {
    	int val;
    	struct cel * fils[N];
    }cel;
     
    typedef struct cel_binEx
    {
    	int val;
    	struct cel_binEx * filsGauche;
    	struct cel_binEx * frereDroit;
    } cel_binEx;
     
    //Fonction d'allocation, initialise les pointeurs à NULL.
    cel_binEx * CreeNoeudBinaireEx(void)
    {
    	cel_binEx *pRet = malloc(sizeof(*pRet));
    	if(pRet != NULL)
    	{
    		static const cel_binEx def = { 0, NULL, NULL };
    		*pRet = def;
    	}
    	return pRet;
    }
     
    //Fonction de binarisation des fils d'un noeud.
    //[recursif]
    static int BinariseFils(cel const *pcArbre, cel_binEx * pBin)
    {
    	//pBin ne peut PAS être NULL ici
    	assert(pBin != NULL);
    	//pcArbre non plus
    	assert(pcArbre != NULL);
     
    	//Erreur si pBin a déjà des fils
    	if(pBin->filsGauche != NULL)
    		return -1;
     
    	//Pour chaque fils de pcArbre, ajoute un fils à pBin, puis binarise le fils.
    	{
    		//Le premier fils ajouté sera le fils gauche de pBin
    		cel_binEx ** ppNewFils = &(pBin->filsGauche);
    		size_t i;
     
    		for(i=0 ; i<N ; i++)
    		{
    			cel const * pcFils = pcArbre->fils[i];
     
    			assert(ppNewFils != NULL);
    			assert(*ppNewFils == NULL);
     
    			if(pcFils != NULL)
    			{
    				//Ajouter le fils, retourner -1 si erreur.
    				//Penser à s'assurer de ne perdre aucun pointeur,
    				//Ni ne laisser aucun pointeur sauvage dans l'arbre de destination :
    				//--> Tout pointeur de l'arbre de destination sera valide et libérable.
    				cel_binEx * pNewFils = NULL;
     
    				pNewFils = CreeNoeudBinaireEx();
    				if(pNewFils == NULL)
    					return -1;
     
    				//Maintenant que le fils existe, on l'ajoute.
    				//Le prochain fils ajouté sera le frère droit du fils courant.
    				*ppNewFils = pNewFils;
    				ppNewFils = &(pNewFils->frereDroit);
    				pNewFils->val = pcFils->val;
     
    				//Les pointeurs du fils sont nuls, on peut lui binariser ses fils à son tour.
    				if(BinariseFils(pcFils, pNewFils) < 0)
    					return -1;
    			}//if
    		}//for
    	}//variables locales
    	return 0;
    }
     
    //Fonction racine de binarisation.
    //Valeurs de retour : 
    //	0 = OK
    //	-1 = Erreur, *ppBin NULL ou pointeur valide vers arbre à détruire.
    //	-2 = Erreur, *ppBin inchangé.
    int Binarise(cel const *pcArbre, cel_binEx * * ppBin)
    {
    	if(ppBin == NULL)
    		return -2;
     
    	//Si pcArbre est NULL, retourner OK si *ppBin l'est aussi, sinon erreur.
    	if(pcArbre == NULL)
    		return ((*ppBin == NULL) ? 0 : -2);
     
    	//Si *ppBin est NULL, on traite aussi la racine
    	if(*ppBin == NULL)
    	{
    		cel_binEx *pNewBin = CreeNoeudBinaireEx();
    		if(pNewBin==NULL)
    			return -1;
    		if(pcArbre != NULL)
    			pNewBin->val = pcArbre->val;
    		*ppBin = pNewBin;
    	}
     
    	//On traite les fils
    	return BinariseFils(pcArbre, *ppBin);
    }
    Ça compile, mais ce n'est pas testé. Je suis en train de tester...
    SVP, pas de questions techniques par MP. Surtout si je ne vous ai jamais parlé avant.

    "Aw, come on, who would be so stupid as to insert a cast to make an error go away without actually fixing the error?"
    Apparently everyone.
    -- Raymond Chen.
    Traduction obligatoire: "Oh, voyons, qui serait assez stupide pour mettre un cast pour faire disparaitre un message d'erreur sans vraiment corriger l'erreur?" - Apparemment, tout le monde. -- Raymond Chen.

Discussions similaires

  1. [Graphique] affichage d'arbres n-aires
    Par jeepnc dans le forum Graphisme
    Réponses: 2
    Dernier message: 21/03/2006, 21h27
  2. Parcours en profondeur d'un arbre n-aire
    Par Premium dans le forum Langage
    Réponses: 11
    Dernier message: 20/02/2006, 08h01
  3. [debutant] parcours en profondeur arbre n-aire
    Par tx dans le forum Langage
    Réponses: 1
    Dernier message: 15/02/2006, 03h56
  4. construire un arbre n-aire
    Par emidelphi77 dans le forum Langage
    Réponses: 2
    Dernier message: 11/10/2005, 18h47
  5. arbre n-aire delete
    Par Fry dans le forum C++
    Réponses: 13
    Dernier message: 19/10/2004, 21h22

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo