Remplacement d'un mot par un arbre

Version imprimable

Bonjour,

le code suivant a pour but de remplacer toutes les occurences d'un mot "mot" par l'arbre "arbremot" qui lui est associé dans l'arbre "arbre".

Code:

1
2
3
4
5
6
7
 
typedef struct noeud
{
char *mot;
struct noeud *gauche;
struct noeud *droit;
}Noeud,*Arbre;

Code:

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
 
void Remplace_aux(Arbre *arbre, char *mot, Arbre arbremot)
{
    if(*arbre != NULL)
       {
          if(strcmp((*arbre)->mot,mot) == 0)
             {
                (*arbre)->mot = arbremot->mot;
                (*arbre)->gauche = arbremot->gauche;
                (*arbre)->droit = arbremot->droit;
             }
         else
            {
                Remplace_aux(&((*arbre)->gauche),mot,arbremot);
                Remplace_aux(&((*arbre->droit),mot,arbremot);
            }
      }
}
 
 
Arbre Remplace(Arbre *arbre, char *mot, Arbre arbremot)
{
   Arbre tmp;
   tmp = *arbre;
   Remplacement_aux(&tmp,mot,arbremot);
return tmp;
}

Est ce que vous pourriez m'indiquer si le code suivant est correcte et comment je dois m'y prendre pour récupérer l'arbre initial (avant les Remplacement).

Merci d'avance

30/12/2005, 17h25
Trap D

Tu ne travaille pas de manière très logique, une de tes foncitons est de type void et l'autre renvoie un arbre, ce qui parait plus logique.
d'autre part que fais-tu quand *arbre est NULL ?
30/12/2005, 18h08
PRomu@ld
Code:

1 2 Arbre tmp; tmp = *arbre;
Je suis pas sur que ceci marche comme tu le souhaite.

D'après ton code, Arbre est un pointeur sur un noeud (c'est normal). Mais comme c'est un pointeur lorsque que tu fais l'affectation, tu fais une affectation sur une adresse. C'est à dire que tmp va contenir la même adresse que arbre, mais ce ne sera en aucun cas une copie de ton arbre, par conséquent losque tu va modifier ton arbre tmp (via ta fonction auxilière), tu va aussi modifier ton arbre originel.

Par conséquent, en procédant ainsi comme tu l'a fais, il te faut une fonction qui te fasse une copie de ton arbre (et pas seulement copier l'adresse).

Citation:

Tu ne travaille pas de manière très logique, une de tes foncitons est de type void et l'autre renvoie un arbre, ce qui parait plus logique.

Je comprend pas ta remarque (tu dis que c'est pas logique, tu dis ce qu'il fait et ensuite tu dis que c'est logique ...)

Par contre, si l'arbre est NULL, il n'y a rien à faire, et c'est ce qui se passe.
30/12/2005, 18h46
Gryzzly

Bonsoir,

est ce que vous avez une manière de procéder à me suggerer?(pseudo code)

Je pense à un truc récursif du genre :

Code:

1
2
3
4
5
6
7
8
copie (src, dst)
{
     si src non vide alors
         copier la racine de src dans celle de dst.
 
         copie(fils_gauche(src),fils_gauche(dst) )
         copie(fils_droit(src),fils_gauche(dst) );
}

Ceci est très loin d'être correct (aucune allocation de mémoire n'est faite). Mais c'est le schéma global. Ensuite si tu veux être un peu plus fin il faudrait faire comme celà :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
copie (src, dst)
{
     si src non vide alors
 
          si dst est vide alors 
               creer un noeud pour dst.
 
         copier la racine de src dans celle de dst.
 
         si fils_gauche(src) n'est pas vide alors
               creer un noeud pour le fils gauche de dst
               copie(fils_gauche(src),fils_gauche(dst) )
 
         si fils_droit(src) n'est pas vide alors
               creer un noeud pour le fils droit de dst.
               copie(fils_droit(src),fils_gauche(dst) );
}

C'est vrai que je n'ai pas été clair, dans ce genre de fonction, il est plus "logique" de renvoyer un pointeur plutôt que de modifier les arg

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
arbre Remplace_aux(Arbre arbre, char *mot, Arbre arbremot)
{
    if(arbre != NULL)
    {
          if(strcmp(arbre->mot,mot) == 0)
          {
                arbre->mot = arbremot->mot;
                arbre->gauche = arbremot->gauche;
                arbre->droit = arbremot->droit;
          }
          else
          {
                arbre->gauche = Remplace_aux(arbre->gauche,mot,arbremot);
                arbre->droit = Remplace_aux(arbre->droit,mot,arbremot);
          }
     }
     return arbre;
}

En espérant qu'on ne détruit rien quand (strcmp(arbre->mot,mot) == 0)
D'autre part, comme c'est un remplacement, il est normal de ne rien faire si on ne trouve rien.

30/12/2005, 20h36
PRomu@ld

En fait le soucis en procédant comme tu le fais, il perd son arbre originel (ce qui n'est pas ce qu'il veut).

En fait admettons que tu ais un arbre d'une fonction (ex f(x) = 2 x + 3), tu veux l'évaluer quand x = 2, il va donc appeler sa fonction de remplacement mais il ne veut pas perdre son arbre de fonction (il voudra surement le réutiliser plus tard)
31/12/2005, 00h23
Trap D

OK, je ne connaissais pas le contexte. Il faut effectivement faire une recopie de l'arbre dans ce cas.

Bojour,

est ce que cette manière de faire pour la copie est correcte?

Merci d'avance

Code:

1
2
3
4
5
6
7
enum Type{Constante,Operateur};
 
union Info
{
  double cte;
  char op;
}

Code:

1
2
3
4
5
6
7
typedef struct noeud
{
  enum Type type;
  union Info info;
  struct noeud*gauche;
  struct noeud*droit;
}Noeud,*Arbre;

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Noeud *CreerNoeud(union Info info)
{
  Noeud *noeud;
  noeud = (Noeud *)malloc(sizeof(Noeud));
 
  if(noeud == NULL)
    return NULL;
 
  noeud->info = info;
  noeud->gauche = NULL;
  noeud->droit = NULL;
 
  return noeud;
}

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void copie(Arbre src, Arbre dst)
{
  if(src!=NULL)
    {
 
      if(dst == NULL)
	dst = CreerNoeud(src->info);
 
      if(src->gauche != NULL)
	{
	  dst->gauche = CreerNoeud(src->gauche->info);
	  copie(src->gauche,dst->gauche);	    
	}
 
      if(src->droit != NULL)
	{
	  dst->droit = CreerNoeud(src->droit->info);
	  copie(src->droit,dst->droit);	    
	}
 
    }
}

31/12/2005, 09h17
PRomu@ld

Code:

noeud->info = info;

Il y a juste ça où je ne sais pas si c'est possible mais sinon ça n'a pas l'air mal.
31/12/2005, 09h31
Gryzzly

Citation:

Envoyé par PRomu@ld

Code:

noeud->info = info;

Il y a juste ça où je ne sais pas si c'est possible mais sinon ça n'a pas l'air mal.

Sinon,il faut que je vérifies si j'ai à faire à un operateur ou une constante mais comment ?
J'ai cru qu'il était possible d'affecter directement.
31/12/2005, 09h34
PRomu@ld

En fait, j'ai peur que l'affectation ne soit pas possible directement. Je pense qu'il faudrait que tu testes si c'est une constante ou un opérateur et en fonction de celà tu affecte la bonne valeur de l'union.

Citation:

Envoyé par PRomu@ld

En fait, j'ai peur que l'affectation ne soit pas possible directement. Je pense qu'il faudrait que tu testes si c'est une constante ou un opérateur et en fonction de celà tu affecte la bonne valeur de l'union.

Pour que je puisse recuperer l'arbre copier,est ce qu'il suffit que je fasse return dest?

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Arbre copie(Arbre src, Arbre dst)
{
  if(src!=NULL)
    {
 
      if(dst == NULL)
	dst = CreerNoeud(src->info);
 
      if(src->gauche != NULL)
	{
	  dst->gauche = CreerNoeud(src->gauche->info);
	  copie(src->gauche,dst->gauche);	    
	}
 
      if(src->droit != NULL)
	{
	  dst->droit = CreerNoeud(src->droit->info);
	  copie(src->droit,dst->droit);	    
	}
 
    }
return dest;
}

De plus ,dans la fonction Remplace que j'avais écrit.
Est ce qu'il est nécessaire de mettre Arbre *arbre ou je peux mettre Arbre arbre?
Si cela est permis ,la ligne suivante ,ou tu indiquait qu'il y avait un problème est correcte?

Code:

1
2
 Arbre tmp;
tmp = *arbre;

devient

Code:

tmp = arbre;

Code:

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
 
void Remplace_aux(Arbre *arbre, char *mot, Arbre arbremot)
{
    if(*arbre != NULL)
       {
          if(strcmp((*arbre)->mot,mot) == 0)
             {
                (*arbre)->mot = arbremot->mot;
                (*arbre)->gauche = arbremot->gauche;
                (*arbre)->droit = arbremot->droit;
             }
         else
            {
                Remplace_aux(&((*arbre)->gauche),mot,arbremot);
                Remplace_aux(&((*arbre->droit),mot,arbremot);
            }
      }
}
 
 
Arbre Remplace(Arbre *arbre, char *mot, Arbre arbremot)
{
   Arbre tmp;
   tmp = *arbre;
   Remplacement_aux(&tmp,mot,arbremot);
return tmp;
}

31/12/2005, 10h44
PRomu@ld
Citation:

Pour que je puisse recuperer l'arbre copier,est ce qu'il suffit que je fasse return dest?

Non, ton arbre est un pointeur, ne l'oublie pas, par conséquent dst est modifié sur place. Du coup ta fonction devient :
Code:

1 2 3 4 5 6 7 8 9 10 11 Arbre Remplace(Arbre *arbre, char *mot, Arbre arbremot) { Arbre tmp; tmp = NULL; copie(arbre,tmp); Remplacement_aux(&tmp,mot,arbremot); return tmp; }