Discussion :

[Gryzzly]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

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
 
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

[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 ?

[PRomu@ld]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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).

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.

[Gryzzly]

Bonsoir,

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

[PRomu@ld]

Je pense à un truc récursif du genre :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

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
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) );
}

[Trap D]

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 :

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
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.

[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)

[Trap D]

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

[Gryzzly]

Bojour,

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

Merci d'avance

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

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
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);	    
	}
 
    }
}

[PRomu@ld]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[Gryzzly]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[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.

[Gryzzly]

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 :

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
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 :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 Arbre tmp;
tmp = *arbre;

devient

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

tmp = arbre;

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
 
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;
}

[PRomu@ld]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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;
}