[C] Factorisation d'arbre en C

Guillaume Coutelle -
kij_82 - 12 avril 2005 à 10:13

Bonjour !!
J'aurait besoin de conseil en vue de créer une fonction C pour factoriser un arbre. voici le début de mon programme. Il prend en paramètre un ensemble de clause ( exemple: x|y|nz,nx|ny,ny|nz,z ) , ensuite il tranforme l'expression en un arbre. (seul les 3 variables x, y, z sont possible , ou s'écrit| et non x s'écrit nx ) puis il simplifie l'arbre en ramplacant un noeud avec un 0 en filsgauche par son filsdroit .
Je voudrait maintenant le factoriser comme suit :

[URL=http://img174.exs.cx/my.php?loc=img174&image=sanstitre2ay.jpg][IMG]http://img174.exs.cx/img174/9806/sanstitre2ay.th.jpg[/IMG][/URL]

Un peu d'aide, une idée, un algorithme de factorisation serait bienvenue.
Merci d'avance.
Guillaume Coutelle

Afficher la suite

A voir également:

[C] Factorisation d'arbre en C
Arbre généalogique famille michelin - Télécharger - Généalogie
Dessin animé arbre qui parle ✓ - Forum Cinéma / Télé
Arbre de tournoi - Forum Programmation
Film arbre qui pousse dans le ventre ✓ - Forum Cinéma / Télé
Logiciel arbre généalogique ✓ - Forum Bureautique

4 réponses

Réponse 1 / 4

Coutelle Guillaume

j'ai oublié de mettre le code du début de notre programme !! lol
Le voici:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct cellule{
char var[2];
struct cellule *filsg;
struct cellule *filsd;
}type_cellule;

typedef struct cellule *arbre;

arbre cc(char nom[2], type_cellule *g, type_cellule *d )
{
type_cellule *cellule1;
cellule1 = (type_cellule*)malloc(sizeof(type_cellule));
strcpy(cellule1->var,nom);
cellule1->filsg = g;
cellule1->filsd = d;
return cellule1;
}

void affiche(arbre A){

printf(A->var);
if(A->filsg != NULL) affiche(A->filsg);
if(A->filsd != NULL) affiche(A->filsd);
}

arbre simplif (arbre A)
{
printf( "\n on est au tour A->var = %s\n", A->var );
arbre B;
if ( (A->filsg==NULL) && (A->filsd==NULL) ) {
printf( "cas ou a->g & a->d sont nuls\n" );
return A;
}
if ( (A->filsg->filsg!=NULL) && (A->filsg->filsd!=NULL) ) {
printf( "cas ou a-g-g & a-g-d non nuls\n Voici a-g-g-var : %s\n", A->filsg->filsg->var );
if ( strcmp( A->filsg->filsg->var, "0" ) == 0 ) {
printf( "cas ou a-g-g-var = 0\n" );
B = A->filsg->filsd;
free( A->filsg->filsg );
A->filsg = B;
printf( "changement du a-g-var : %s\n", A->filsg );
}
if ( A->filsd != NULL )
simplif( A->filsd );
if ( A->filsg != NULL )
simplif( A->filsg );
}
if ( (A->filsd->filsg!=NULL) && (A->filsd->filsd!=NULL) ) {
printf( "cas ou a-d-g & a-d-d non nuls\n Voici a-d-g-var : %s\n", A->filsd->filsg->var );
if ( strcmp( A->filsd->filsg->var, "0" ) == 0 ) {
printf( "cas ou a-d-g-var = 0\n" );
B = A->filsd->filsd;
free( A->filsd->filsg );
A->filsd = B;
printf( "changement du a-d-var : %s\n", A->filsd );
}
if ( A->filsd != NULL )
simplif( A->filsd );
if ( A->filsg != NULL )
simplif( A->filsg );
}
return A;
}

arbre simplifarbre(arbre A)
{
int i=8;
while(i>0)
{
printf("tour num %i\n",i);
A=simplif(A);
affiche(A);
printf("\n");
i--;
}
return A;
}
arbre ajoutc( char *c, arbre arbree){

struct cellule *ptr = arbree;
int n,i,k=0;
n = strlen(c);
for(i=0;i<n;i++){
if( c[i]!='|'||c[i]!='\0' ){
if(c[i]=='n' && c[i+1]=='x')
{ptr = ptr->filsd->filsg;
k=1;}
else if(c[i]=='x')
{ptr = ptr->filsg->filsd;
k=1;}
}
if(k==1)i=n;}
if (k==0) ptr = ptr->filsd->filsd;
k=0;
for(i=0;i<n;i++){
if( c[i]!='|'||c[i]!='\0' ){
if(c[i]=='n' && c[i+1]=='y')
{ptr = ptr->filsd->filsg;
k=1;}
else if(c[i]=='y')
{ptr = ptr->filsg->filsd;
k=1;}
}
if(k==1)i=n;}
if(k==0) ptr = ptr->filsd->filsd;
k=0;
for(i=0;i<n;i++){
if( c[i]!='|'||c[i]!='\0' ){
if(c[i]=='n' && c[i+1]=='z')
{ptr = ptr->filsd->filsg;
k=1;}
else if(c[i]=='z')
{ptr = ptr->filsg->filsd;
k=1;}
}
if(k==1)i=n;}
if(k==0) ptr = ptr->filsd->filsd;
strcpy(ptr->var,"1") ;
return arbree;
}

int main (int argc, char *argv[])
{
int i=0,j=0,n=0,nbformule=1;
arbre arbre1;
printf("%s \n",argv[1]);
while(argv[1][i]!='\0')
{if(argv[1][i]==',')nbformule++;
i++;}
printf("%i\n", nbformule);
char formule[nbformule][9];
i=0;
while(argv[1][i]!='\0')
{if(argv[1][i]==',') {
formule[n][j]='\0';
n++;
j=0;}
else { formule[n][j]=argv[1][i];
j++;}
i++;}
formule[n][j]='\0';

arbre1 = cc("x",cc("nx",cc("0",NULL,NULL)
,cc("y",cc("ny",cc("0",NULL,NULL),cc("z",cc("nz",cc("0",NULL,NULL),cc("0",NULL,NULL)),cc("nz",cc("0",NULL,NULL),cc("0",NULL,NULL))))
,cc("ny",cc("z",cc("nz",cc("0",NULL,NULL),cc("0",NULL,NULL)),cc("nz",cc("0",NULL,NULL),cc("0",NULL,NULL)))
,cc("z",cc("nz",cc("0",NULL,NULL),cc("0",NULL,NULL)),cc("nz",cc("0",NULL,NULL),cc("0",NULL,NULL))))))
,cc("nx",cc("y",cc("ny",cc("0",NULL,NULL),cc("z",cc("nz",cc("0",NULL,NULL),cc("0",NULL,NULL)),cc("nz",cc("0",NULL,NULL),cc("0",NULL,NULL))))
,cc("ny",cc("z",cc("nz",cc("0",NULL,NULL),cc("0",NULL,NULL)),cc("nz",cc("0",NULL,NULL),cc("0",NULL,NULL)))
,cc("z",cc("nz",cc("0",NULL,NULL),cc("0",NULL,NULL)),cc("nz",cc("0",NULL,NULL),cc("0",NULL,NULL)))))
,cc("y",cc("ny",cc("0",NULL,NULL),cc("z",cc("nz",cc("0",NULL,NULL),cc("0",NULL,NULL)),cc("nz",cc("0",NULL,NULL),cc("0",NULL,NULL))))
,cc("ny",cc("z",cc("nz",cc("0",NULL,NULL),cc("0",NULL,NULL)),cc("nz",cc("0",NULL,NULL),cc("0",NULL,NULL)))
,cc("z",cc("nz",cc("0",NULL,NULL),cc("0",NULL,NULL)),cc("nz",cc("0",NULL,NULL),cc("0",NULL,NULL)))))));

affiche(arbre1);
printf("\n");
for(i=0;i<nbformule;i++)
{printf("%s\n",formule[i]);
arbre1=ajoutc(formule[i],arbre1);
}
printf("\n");
affiche(arbre1);
printf("\n");
arbre1=simplifarbre(arbre1);
affiche(arbre1);

j = 0;
while( j<10 )
printf( "Hi\b\b" );
return 0;

}

Réponse 2 / 4

kij

Ah ah ah , l'analyse des expression, quelle belle merde à faire !

Si tu veux un algo déjà fait je peux te filer le miens (eh oui g du en faire un aussi cette année), mais c'est en java, si tu connait un peu le langage, tu pourra reprendre le principe.
Le probleme, c'est que je ne pourrait te l'envoyer que la semaine prochaine (g oublié mon dur ché ma cops)

Voilà si t'en a toujour besoin redi le moi

++

Réponse 3 / 4

Guillaume Coutelle

Yep , yep, yep !!
Je connais le language Java et oui je suis interessé par ton algo, pour la semaine prochaine y pas de problème.
M'oublie pas, merci d'avance.

Guillaume Coutelle

Réponse 4 / 4

Guillaume Coutelle

Bah voilà j'attend ton algo avec impatience !!!
:-)

god_is_a_dj

kij_82

Donne moi ton adresse stp pour l'envoie.
:
kij_82@hotmail.fr

@++

Discussions similaires

Topologie des réseaux

Arbre de décision

Comment s'appel cet arbre ?

le feuillage d'un arbre

arbre généalogique de Nicolas Menoux

Votre réponse

Discussions similaires