Discussion :

[Nestarym]

Bonjour,

dans le cadre d'un projet assez long, je me retrouve à devoir utiliser des arbres afin de réaliser une IA. J'aimerais construire l'arbre et le remplir dans une même fonction récursive. J'ai simplifié les algorithmes afin d'avoir quelque chose de lisible.
Je souhaite avoir un arbre comprenant n fils, et chaque fils comprennent eux mêmes n fils, etc... Ce nombre n est calculé avant chaque boucle for mais pour cet exemple je lui fixe directement une valeur.

Voici les structures pour l'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
 
 
struct s_noeud {
	int score;
	struct s_noeud **fils;
	char deplacement[6];
};
 
struct s_arbre {
	struct s_noeud *racine;
};
 
typedef struct s_noeud Noeud;
typedef struct s_arbre Arbre;

J'ai fais un algorithme afin de créer et remplir tous les n fils de la racine, qui fonctionne et donne ceci :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
 
Arbre *ajouterTousLesFils (Arbre *monArbre, int nbCoups) {
	srand(time(NULL));
	Noeud *monNoeud = monArbre->racine;
	monNoeud = malloc(sizeof(Noeud));
	monNoeud->fils = malloc(sizeof(Noeud *) * nbCoups);
	for (int i = 0; i < nbCoups; i++) {
		monNoeud->fils[i] = malloc(sizeof(Noeud));
		monNoeud->fils[i]->score = rand() % 42;
	}
	monArbre->racine = monNoeud;
	return monArbre;
}

Je souhaite donc désormais adapter cet algorithme afin qu'il soit récursif, et qu'il fonctionne pour tous les sous-fils, sous-sous fils, etc jusqu'à une profondeur voulu.Voici ce que j'ai tenté :

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
 
Noeud *construitEtRemplit (Noeud *monNoeud, int hauteur, int nbCoups) {
	srand(time(NULL));
	monNoeud = malloc(sizeof(Noeud));
	if (!hauteur) {
		monNoeud->score = rand() % 42;
	}
	else {
		monNoeud->fils = malloc(sizeof(Noeud *) * nbCoups);
		for (int i = 0; i < nbCoups; i++) {
			monNoeud->fils[i] = malloc(sizeof(Noeud));
			monNoeud = construitEtRemplit(monNoeud->fils[i], hauteur-1, 2);
		}
	}
	return monNoeud;
}

L'appel dans le main n'a rien de particulier :

Code :

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

1
2
3
4
 
Arbre *unArbre = creerArbre();
Noeud *noeud = racine(unArbre);
noeud = construitEtRemplit(noeud, 2, 2);

J'ai un problème de segmentation au niveau de l'algorithme récursif, dans la boucle for. J'ai un peu de mal avec les malloc et la récursion, par exemple doit-on caster les malloc ? Je vois à des endroits que oui, à d'autres que non, ...

Voilà j'espère que vous pourrez m'aider,
bonne soirée,
Nestarym.

[Sve@r]

Bonjour,

Salut

J'ai un peu de mal avec les malloc et la récursion, par exemple doit-on caster les malloc ? Je vois à des endroits que oui, à d'autres que non, ...

C'est effectivement un vaste débat avec des arguments pour et contre dans les deux positions. Et arguments tout à fait valides dans les deux cas. Perso moi je ne caste pas mais je comprends ceux qui le font.
Mais ce n'est pas le cast/no cast qui fera planter ton truc (enfin pas ici quoi).

J'ai un problème de segmentation au niveau de l'algorithme récursif, dans la boucle for

Oui, je vois ça. C'est dû au fait que ta fonction crée le noeud courant (ici monNoeud = malloc(sizeof(Noeud))). De son point de vue, ce noeud est donc équivalent d'une racine locale quoi.
MAIS elle veut aussi créer le fils (ici monNoeud->fils[i] = malloc(sizeof(Noeud))). Puis tu la rappelles sur ce même noeud fils (ici monNoeud = construitEtRemplit(monNoeud->fils[i], hauteur-1, 2, i)). Et là ça ne va pas. Soit la fonction s'occupe du noeud et des fils (et donc tu ne rappelles une instance récursive B pour créer les fils vu qu'ils ont déjà été créés dans l'instance A), soit elle ne s'occupe que de son noeud et ensuite, pour les fils, tu la rappelles en récursif.
D'autant plus qu'écrire ce genre de couple d'instructions

Code C :

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

1
2
3
monNoeud = malloc(sizeof(Noeud));
...
monNoeud = construitEtRemplit(monNoeud->fils[i], hauteur-1, 2, i);

ne peut pas fonctionner En effet, tu ne peux pas écrire var=xxx() puis 3 lignes en dessous var=yyy() sans te poser des questions sur l'efficacité d'affecter deux choses différentes à la même variable. Question de logique quoi...

L'appel dans le main n'a rien de particulier :

Code :

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

1
2
Noeud *noeud = racine(unArbre);
noeud = construitEtRemplit(noeud, 2, 2);

Oui, rien de particulier. Mais c'est pareil. Peut-être qu'il faudrait réfléchir là aussi sur cette affectation en duo...

[Nestarym]

Merci beaucoup d'avoir pris le temps de me répondre.

Je pense avoir cerné le problème, du moins en partie.
D'après ce que j'ai compris, je devrais faire quelque chose comme ça :

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
 
Noeud *construitEtRemplit (Noeud *monNoeud, int hauteur, int nbCoups) {
	srand(time(NULL));
	monNoeud = malloc(sizeof(Noeud));
	if (!hauteur) {
		monNoeud->score = rand() % 42;
	}
	else {
		monNoeud->fils = malloc(sizeof(Noeud *) * nbCoups);
		for (int i = 0; i < nbCoups; i++) {
			monNoeud->fils[i] = construitEtRemplit(monNoeud->fils[i], hauteur-1, 2);
		}
	}
	return monNoeud;
}

donc j'enlève le malloc de monNoeud->fils[i] qui se fera lors de la récursion, et je rappelle sur monNoeud->fils[i] comme ça j'ai ma fonction récursive qui ne s'occupe que de son Noeud puis de chacun de ses fils. J'ai bon ?

Par contre je n'ai pas très bien saisie pourquoi cela :

Code :

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

1
2
3
4
 
monNoeud = malloc(sizeof(Noeud));
...
monNoeud = construitEtRemplit(monNoeud->fils[i], hauteur-1, 2);

ne peut pas fonctionner En effet, tu ne peux pas écrire var=xxx() puis 3 lignes en dessous var=yyy() sans te poser des questions sur l'efficacité d'affecter deux choses différentes à la même variable. Question de logique quoi...

Je ne vois pas pourquoi je ne pourrais pas écrire var=xxx() puis var=yyy() car pour moi ce n'est pas une "affectation" de 2 choses différentes, mais dans un cas je lui donne de la mémoire, et dans l'autre je mets des trucs dedans maintenant qu'il y a de la place. Ou alors j'ai vraiment pas compris les malloc

[Sve@r]

Je pense avoir cerné le problème, du moins en partie.
D'après ce que j'ai compris, je devrais faire quelque chose comme ça :

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 *construitEtRemplit (Noeud *monNoeud, int hauteur, int nbCoups) {
	srand(time(NULL));
	monNoeud = malloc(sizeof(Noeud));
	if (!hauteur) {
		monNoeud->score = rand() % 42;
	}
	else {
		monNoeud->fils = malloc(sizeof(Noeud *) * nbCoups);
		for (int i = 0; i < nbCoups; i++) {
			monNoeud->fils[i] = construitEtRemplit(monNoeud->fils[i], hauteur-1, 2);
		}
	}
	return monNoeud;
}

donc j'enlève le malloc de monNoeud->fils[i] qui se fera lors de la récursion, et je rappelle sur monNoeud->fils[i] comme ça j'ai ma fonction récursive qui ne s'occupe que de son Noeud puis de chacun de ses fils. J'ai bon ?

C'est ça. La fonction s'occupe de son noeud et rien que de son noeud. Et c'est l'instance récursive appelée pour le fils (qui lui-aussi est donc un noeud) qui s'occupe du fils. Chacun s'occupe de ses fesses quoi

Je ne vois pas pourquoi je ne pourrais pas écrire var=xxx() puis var=yyy() car pour moi ce n'est pas une "affectation" de 2 choses différentes

Ah ben si !!! L'opérateur "=" est un opérateur d'affectation (enfin si j'ai bien compris les fondamentaux du C... ).
Si (pour être plus terre à terre) tu écris var=5 puis 3 lignes plus bas var=7, tu affectes deux choses différentes (une fois 5 et une fois 7) dans la même variable. Et comme (sauf dans un ordinateur quantique) une variable ne peut pas contenir deux valeurs différentes en même temps, alors bye-bye le "5". Ensuite si tu n'en as pas besoin tant-mieux (mais dans ce cas pourquoi l'y avoir mis) mais si tu en as besoin alors...

Ou alors j'ai vraiment pas compris les malloc

Non. Ce que je pense que tu n'as pas compris, c'est que malloc n'est pas magique. C'est juste une fonction comme une autre. Tu écris char *zone=malloc(5) comme tu aurais pu écrire int i=carre(5). Et si la fonction "carre()" calcule le carré du paramètre pour renvoyer la valeur résultat du calcul (un simple nombre donc), la fonction "malloc()" réserve un espace mémoire et renvoie l'adresse du début de la zone (là aussi un simple nombre). Rien de moins... mais rien de plus non plus. Et cette fonction n'a même pas créé de mémoire (la mémoire était déjà là avant car elle fait partie de ton ordi), elle a juste posé une espèce de drapeau pour que personne d'autre ne puisse l'utiliser.

Ou alors (dit autrement), au retour de l'instruction char *zone=malloc(5), la variable "zone" contient l'adresse du premier caractère de la zone réservée (par exemple) 0x10. Et cette adresse (adresse d'un char) te permet de placer à cet endroit un... char. Mais comme le système t'a réservé 5 caractères, tu as aussi à ta disposition les adresses 0x11, 0x12, 0x13 et 0x14 qui te permettent d'y placer là aussi des caractères (enfin un par adresse).
Et comme cette zone est contigüe, tu as aussi le droit de l'utiliser comme un tableau (donc taper dans zone[0] jusqu'à zone[4]). Tu peux donc écrire si tu veux strcpy(zone, "toto").

mais dans un cas je lui donne de la mémoire, et dans l'autre je mets des trucs dedans maintenant qu'il y a de la place.

Ok. C'est juste ta façon de coder le "je mets des trucs dedans" qui n'est pas correcte.
Quand l'instruction monNoeud = malloc(sizeof(Noeud)) est terminée, la variable "monNoeud" est devenu l'équivalent d'une "struct s_noeud" (pour être plus exact l'adresse d'une "struct s_noeud"). C'est exactement comme si tu écrivais

Code c :

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

1
2
struct s_noeud xxx;
struct s_noeud *monNoeud=&xxx;

Donc pour "mettre des trucs" dans une structure, on y met en fait des trucs dans ses éléments. Tu peux par exemple mettre des trucs dans l'élément "score" (xxx.score=1000 ou bien monNoeud->score=1000 ou bien encore (n'oublions pas que l'opérateur "flèche" n'est qu'un raccourci syntaxique) (*monNoeud).score=1000). Mais tu ne peux y mettre des trucs en écrivant monNoeud=1000 tout comme tu n'aurais jamais écrit (enfin j'espère) xxx=1000

[Nestarym]

Aaaah c'est un peu plus clair dans ma tête

J'avais compris pour l'affectation c'est juste que je ne pensais pas que le malloc donnait une valeur à la variable, je pensais juste qu'il lui donnait de la place dans trop chercher à comprendre comment ça fonctionnait ^^

Donc je comprends mieux votre remarque précédente !

Et j'ai pu tester ma fonction, maintenant elle fonctionne correctement je vais pouvoir m'en servir, merci beaucoup !