Discussion :

[jay67]

Bonsoir à tous.
Et bonne année

Je vous écris car je dois insérer des mots dans un arbre, et ce, dans l'ordre alphabétique.
Pour cela j'ai donc créé une fonction permettant l'ajout de noeud (donc de lettre) dans l'arbre.
Mais j'ai quelques problèmes concernant cette fonction.

Pour info, "#" est le caractère fin de mot.
"AI" et "AS" sont des frères (même racine "A")
"BON" est le fils de "BO"

Voici le code de ma fonction:

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
noeud* ajouter_lettre (noeud *A, char c)
{
	noeud *O, *T, *R;
	O = malloc(sizeof(*O));
	O->lettre = c;
	O->frere = NULL;
	O->fils = NULL;
	int *i;
	i = 0;
 
	if (A->lettre == '#')                        //si on rencontre # on va alors créer un frere de ce mot
	{
		if (A->frere == NULL)                //s'il n y en a pas
		{
			A->frere = O;
		}
		else
		{
			A = A->frere;                //sinon on passe au frere de ce mot et on tente la même opération
			R = ajouter_lettre (A, c);
		}
	}
	else
	{
		if (A->lettre == c)                 //si on rencontre la lettre qu'on veut insérer, on arrête car la lettre est déjà présente dans l'arbre
		{
			R = A;
		}
		else
		{
			if (A->lettre < c)          //si on rencontre une lettre plus petite que celle que l'on veut insérer
			{
				T = A->frere;       //on décale le frere en insérant le nouveau noued
				A->frere = O;
				O->frere = T;
				R = O;
				i++;
			}
			else
			{
				if (i = 0)         //si on arrive tout de suite a une lettre plus grande que celle qu'on veut insérer
				                   //on décale le frere en insérant le nouveau noued
					O->lettre = A->lettre;
					O->frere = A->frere;
					O-fils = A->fils;
					A->lettre = c;
					R = ajouter_lettre (A, c);
				}
			}
		}
	}
	return R;
}

Voili voilà,
ça ne marche pas tout à fait comme il faudrait..
Et d'après les tests effectué cet après-midi, les autres fonctions ne seraient pas en causes.
Si quelqu'un arrivait à m'aiguiller, ça me sortirait de mon impasse.
Merci d'avance, et bonne soirée à tout le monde !!

[olibara]

Salut

Pour eviter toute ambiguité je te conseille d'ecrire

Code :

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

1
2
3
O = malloc(sizeof(noeud));
// au lieu de
O = malloc(sizeof(*O));

Il me semble voir une grosse betise

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
if (A->lettre == '#')                        //si on rencontre # on va alors créer un frere de ce mot
{
   if (A->frere == NULL)                //s'il n y en a pas
  {
	A->frere = O;
  }
  else
  {
// Ceci n'a aucun effet dans la fonction a mon avis !!
// et si tu veux le recuperer au retour A devrait etre **sur noeud
	A = A->frere;                //sinon on passe au frere de ce mot et on tente la même opération
	R = ajouter_lettre (A, c);
  }
}

[jay67]

Voici le code de ma fonction mise à jour:

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
noeud* ajouter_lettre (noeud *A, char c)
{
	noeud *D, *R;
	D = malloc(sizeof(*D));
 
	D->lettre = c;
	D->frere = NULL;
	D->fils = NULL;
 
if (A == NULL )
	{
		R = D;
	}
else
	{
	if (A->fils == NULL)
		{
		A->fils=D;
		R = D;
		}
	else
	{
		noeud *C, *P;
		C = malloc(sizeof(*C));
 
		P = A;
		A=A->fils;
 
		while ( (A->lettre < c) && (A->frere != NULL) )
		{
			C=A;
			A = A->frere;
		}
 
		if (A->frere == NULL)
		{
			if (A->lettre == c)
			{
				R = A;
			}
			else	if (A->lettre > c)
					{
						A->frere = D;
						R = D;
					}
				else if (A->lettre < c)
					{
						D->frere = A;
						if(C != NULL)
						{
							C->frere = D;
						}
						else
						{
							P->fils = D;
						}
						R = D;
					}
		}
		else	if (A->lettre > c)
			{
				C->frere = D;
				D->frere = A;
				R = D;
			}
			else	if (A->lettre == c)
				{
				R = A;
				}
		//free(C);
	}
}
return R;
}

Ca compile, mais il y a presque toujours une erreur.
Il manque un mot, ou plusieurs,
l'ordre alphabétique n'est pas toujours respecté.

Après les tests de cet aprem, les autres fonctions marchent (normalement) parfaitement.
Il ne reste que ce bout de code qui me pose problème.

Si quelqu'un pouvait me filer un coup de pouce, ça m'aiderais a finir enfin cet exo!!

Merci d'avance et bonne soirée à tous.

[olibara]

Salut

1- tu continue a faire des allocation ambigues

Code :

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

1
2
3
4
malloc(sizeof(*D));
malloc(sizeof(*C));

plutot que calloc(noeud);

3- Je releve encore d'autres erreur d'ecriture mais j'ai franchement pas envie de lire un code si mal indenté. Fais déja un effort de presentation de ton code
Personellement je mets les tab stop a deux et j'utilise des space plutot que des tabs

[Pouet_forever]

1- tu continue a faire des allocation ambigues

Il n'y a aucune allocation ambigüe. Cette écriture est préférable à sizeof(noeud).

@ jay67 : Tu as plein de if, else if, else redondants, je pense que tu peux sûrement factoriser

[olibara]

Il n'y a aucune allocation ambigüe. Cette écriture est préférable à sizeof(noeud).

Pas tu tout ! -1

Ce qu'il alloue c'est une structure de type noeud
Donc la maniere la plus normale et lisible de est de faire systématiquement une allocation de la taille du type et non de la taille de la variable pointée car c'est avec ce type de bricolage que l'on finit par allouer la taille du pointeur sans s'en rendre compte

Je conseille aussi de faire un calloc afin d'eviter les betises d'oubli d'initialisation du contenu de la structure

Tu as plein de if, else if, else redondants, je pense que tu peux sûrement factoriser

+1 Absolument

[Pouet_forever]

Pas tu tout ! -1

Bon je t'explique pourquoi cette écriture est préférable.
Ca permet une plus grande flexibilité. Si jamais au début tu as une variable de type int et que tu fais des mallocs un peu partout (bon j'exagère mais imagine un gros projet), si jamais tu changes le type, de int en unsigned long (par ex.) tu seras obligé de modifier tous tes mallocs. Tu risques fort d'en oublier, et ça te fait perdre du temps.
Si tu fais sizeof(*var) tu ne touches à rien le type de ta variable est automatiquement changée et tu n'as même plus besoin de t'en occuper; même si tu changes le type de ta variable.