Discussion :

[tompote]

Bonjour à tous !
Je suis actuellement en 1ère année d'école d'ingénieur en informatique et je fais appel à vous pour une question qui parait simple, mais qui n'est pas si évident pour moi.

Je dois réaliser un algorithme de compression de Huffman adaptatif, jusque la sur la méthode pas de problème.
Le principe est qu'a chaque caractère lu je dois mettre a jour mon arbre pour qu'il respect ce qui s'appelle l'ordre de Gallager.
Mon problème réside dans l'échange de deux noeud mal positionnés.

La structure de mon arbre est comme ceci:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
typedef struct Noeud
{
	int poids;
	int chara;
	int place;
	int placeG;
	struct Noeud * pere;
	struct Noeud * fils_droite;
	struct Noeud * fils_gauche;
}t_noeud,*noeud;

Je n'arrive pas a comprendre ce qu'il se passe réellement quand je fais ceci:

Code :

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

1
2
3
4
5
 
noeud n1, n2, aux;
aux=n1;
n1=n2;
n2=aux;

D'après ce que j'ai lu, les struct sont copiés terme à terme.
Comment faire un echange simple de 2 noeuds ?
En ce sens j'entends que le père de n2 devra maintenant entre le père de n1 et vice-versa, mais que n1 et n2 garderons les mêmes fils (et ces fils eux même garderons le même père).

Je ne sais pas si je me suis bien expliqué mais si vous avez des questions pour rentrer plus en détails n'hésitez pas.

Je vous remercie d'avance pour vos réponses, en esperant que ma question en soit pas trop bête.

[quetzacoatl]

Eh bien vous pouvez faire:

Code :

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

1
2
3
aux=n1->pere;
n1->pere=n2->pere;
n2->pere=aux;

Lorsqu'on a deux pointeurs de structures et que l'on fait:

Code :

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

pointeur_struct1=pointeur_struct2;

On fait simplement pointer le pointeur_struct1 sur la 2eme structure pointée par pointeur_struct2

D'après ce que j'ai lu, les struct sont copiés terme à terme.

Votre phrase serait valable si vous faisiez une affectation avec deux structures, mais ici vous manipulez des pointeurs de structures(si j'ai bien compris)

[diogene]

En ce sens j'entends que le père de n2 devra maintenant entre le père de n1 et vice-versa, mais que n1 et n2 garderons les mêmes fils (et ces fils eux même garderons le même père).

Si je comprend bien, il s'agit plutôt d'échanger la position des sous-arbres de racine n1 et n2. (Cela peut amener à quelque chose qui n'est pas un arbre : introduction de cycles).

Pour faire cela, on peut

- échanger n1->pere et n2->pere
- si n1->pere-> fils_gauche == n2 alors n1->pere-> fils_gauche = n1
sinon n1->pere-> fils_droit= n1
- si n2->pere-> fils_gauche == n1 alors n2->pere-> fils_gauche = n2
sinon n2->pere-> fils_droit= n2