Discussion :

[daoudasylla]

Bonjour tout le monde!
j'ai un projet que notre prof m'a donné, il s'agit des arbres binaires de recherche (la gestion des étudiants chaque étudiant muni de son CNE, nom_pren etc...).
les fonctions à faire sont:ajouter des étudiants, suprimer un étudiant et chercher un étudiant à partir de son CNE.
le plus dure encore c'est qu'il m'a dit de ne utiliser le formalisme pointeur sur le fils gauche et droit mais plutôt deux entier gauche et droite; en d'autre termes utiliser la gestion statique au lieu de la gestion dynamique. Dans ce cas mes enregistrement seront contiguës comme des tableaux.
Merci!

[Médinoc]

Si tu connais la taille maximale de l'arbre à l'avance, c'est facile. Et encore plus si l'arbre ne peut pas être modifié une fois construit.

[daoudasylla]

la taille maximal est 100 et concernant la modification, il doit être modifier car si on inscrit des étudiants on pourra par la suite supprimer ou modifier par exemple sa date de naissance ou bien encore réinscrire un nouvel étudiant.
je ne sais pas si vous comprenez???
Merci!!

[Médinoc]

Si la taille est limitée à 100, et qu'on peut facilement identifier un étudiant comme "non-initialisé" (que ce soit par un champ age, sexe, ou simplement un pour dire "existe"), c'est facile.

La seule chose importante, c'est utiliser -1 au lieu de zéro comme adresse "nulle" (ce qui signifie qu'il faut explicitement comparer if(ix != INDEX_NULL) au lieu de if(ix)).

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
#include <stddef.h>
#define INDEX_NULL ((size_t)(ptrdiff_t)-1)
#define TAILLE_ARBRE (100)
 
struct noeudEtudiant
{
	int bExiste; /*Utiliser un _Bool à la place si tu as accès/droit à un compilo C99*/
	char nom_prenom[ /*taille max nom prenom*/ ];
	char cne[ /*taille cne*/ ];
	size_t ixFilsGauche;
	size_t ixFilsDroit;
};
 
void InitTousEtudiants(struct noeudEtudiant tab[TAILLE_ARBRE])
{
	struct noeudEtudiant dummy = {0 /*ou false*/, "", "", INDEX_NULL, INDEX_NULL };
	size_t i;
	for(i=0 ; i<TAILLE_ARBRE ; i++)
		tab[i] = dummy;
}
 
/*etc.*/

Et quand tu parcoures/modifies/etc. l'arbre, tu utilises les indexes (ou INDEX_NULL) au lieu de pointeurs.

Pour allouer dans le tableau, il suffit de trouver le premier objet où bExiste est faux. Pour optimiser, tu peux mémoriser l'index du dernier étudiant alloué:

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
struct arbreEtudiants
{
	struct noeudEtudiant tab[TAILLE_ARBRE];
	size_t ixDernierAlloue;  //Initialiser à zéro
};
 
size_t allocEtudiant(struct arbreEtudiants *pTas)
{
	/*on commence au dernier alloué et non pas au suivant,
	car il peut avoir été libéré entretemps*/
	size_t ixCourant = pTas->ixDernierAlloue; 
	size_t i;
	/*On parcoure tout le tableau,
	mais avec ixDernierAlloue comme point de départ et arrivée*/
	for(i = 0 ; i<TAILLE_ARBRE ; i++,ixCourant++)
	{
		/*Il faut mettre le wrap ici, car ixCourant est incrémenté dans la troisième partie du for*/
		if(ixCourant == TAILLE_ARBRE)
			ixCourant = 0;
 
		if( ! pTas->tab[ixCourant].bExiste)
		{
			/*Trouvé! 
			On marque la structure comme allouée (en vidant le reste) et on retourne son index
			On mémorise aussi qu'on s'est arrêté là, pour la prochaine alloc.*/
			struct noeudEtudiant dummyAlloue = {1 /*ou true*/, "", "", INDEX_NULL, INDEX_NULL };
			pTas->tab[ixCourant] = dummyAlloue;
			pTas->ixDernierAlloue = ixCourant;
			return ixCourant;
		}
	}
	return INDEX_NULL;
}

[daoudasylla]

Médinoc, je n'arrive pas à comprendre la notation size_t ixilsgauche est ce la même chose si j'utilise int Filsgauche?? également la constante INDEX_NULL, dummy, ptrdiff_t et le rôle de la variable bExiste???
oui la bibliothèque stddef.h aussi je l'ai jamais utilisé!
Pouvez-vous utilisé les déclaration simple?? car je ne suis pas trop avancé en C Merci d'avantage!!

[Médinoc]

size_t, c'est le type qu'on est censé utiliser pour les indexes dans les tableaux. En gros, c'est un entier non-signé de la taille d'un pointeur.

Tu peux utiliser int FilsGauche à la place si tu veux, mais tu devrais au moins appeler ta variable int indexFilsGauche (personnellement j'utilise ix comme abbréviation de "index").

INDEX_NULL, c'est parce que 0 est une valeur valide pour un index dans un tableau. Puisqu' il faut une valeur invalide pour signifier qu'il n'y a pas de fils, j'utilise -1 (ou son équivalent non-signé) à la place.
Problème: size_t est un type non-signé qui peut être plus grand qu'un int. Si je caste directement -1 en size_t, en 64 bits je risque de me retrouver avec un index qui vaut 0x00000000FFFFFFFF au lieu de 0xFFFFFFFFFFFFFFFF. Pour être sûr d'avoir la bonne valeur et la bonne taille, je passe par le type ptrdiff_t qui a lui ausis la taille d'un pointeur, mais est signé.

Si tu utilises des int comme indexes, tu peux juste utiliser -1 à la place. Mais je te conseillerais au moins de faire un #define, comme ça si tu dois améliorer le programme plus tard tu n'auras pas besoin de remplacer manuellement tes -1 par autre chose.

La variable dummy, c'est un "truc" utile pour initialiser une ou plusieurs structures avec les valeurs voulues: Comme on ne peut initialiser ainsi que dans une déclaration, on procède en deux étapes: D'abord on déclare une nouvelle structure qu'on initialise avec les données voulues, puis on recopie cette structure dans la structure de destination.

La variable bExiste sert à distinguer rapidement, dans le tableau, les éléments alloués des éléments non-alloués. Ça évite d'allouer deux fois le même élément.

Je crois que stddef.h peut être remplacé ici par stdlib.h dans causer de problème.