RECURSIVITE pour tous les traitements sur les arbres et liste chaînée - Langage
cs_HerveYims
Messages postés3Date d'inscriptionlundi 18 mai 2009StatutMembreDernière intervention25 novembre 2011
-
25 nov. 2011 à 23:15
JulSoft
Messages postés354Date d'inscriptiondimanche 3 juin 2001StatutMembreDernière intervention11 mars 2013
-
2 déc. 2011 à 11:58
Bonjour à tous, SVP j'ai un bug avec mon programme ci-dessous en fait :
Soit un fichier des concerts donnés en 2011 en Europe comprenant les noms des groupes ou artistes, le nom de la salle, le pays, la date, le nombre de spectateurs et le prix moyen de la place. Le nombre de concerts d’un artiste ou d’un groupe est indéterminé. De plus, le nombre de concerts peut être différent d’un artiste à un autre.
Le but est de lire ce fichier et de créer un arbre binaire de recherche qui sera trié sur le nom du groupe ou de l’artiste. Chaque nœud de l’arbre contiendra également un pointeur vers une liste chaînée des concerts auxquels cet artiste a participé pendant l’année 2011ainsi que les informations concernant ce concert (cfr.fichier). En cas d’annulation d’un concert, le nombre de spectateurs sera nul.
Il devra être possible :
1. d’afficher la liste des artistes ou des groupes dans l’ordre alphabétique avec les concerts auxquels ils ont participé ainsi que le nombre de spectateurs présents à chaque concert. Si le nombre de spectateur est nul, un message apparaîtra du style « Concert annulé ».
2. d’a jouter un nouveau concert pour un artiste ou un groupe déterminé ainsi que les informations associées.
3. de donner toutes les dates, les salles et les pays des concerts prestés par un artiste ou un groupe en 2011 trié par ordre croissant de date.
4. de déterminer le classement des artistes ou des groupes par ordre décroissant du nombre de spectateurs en 2011.
5. D’afficher Le groupe ou l’artiste ayant rapporté la recette la plus importante en 2011.
Mon code source se présente comme suit :
#include <stdio.h>
#include <string.h>
#include <limits.h>
struct s_noeud
{
char *nom ;
struct s_element *listeConcert;
struct s_noeud *fg,*fd;
};
struct s_element
{
char *concert;
int spectateur ;
struct s_element *suivant;
};
// >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>//
// Prototype des fonctions que l'on va utiliser //
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>//
// Création d'un noeud
struct s_noeud *creerNoeud(char *nom, struct s_element *tete);
// Création de l'arbre
struct s_noeud *creerArbre(struct s_noeud *racine,char *nom,struct s_element *tete);
// Affichage de l'arbre
void afficherArbre(struct s_noeud *racine,struct s_element *ptrSurElement);
// Lecture du fichier
void lectureFichier(FILE *fich,char *nom);
// Création de la liste chaînée
struct s_element *creerListe(struct s_element *tete,char *concert,int spectateur );
// Création d'un concert dans la liste
struct s_element *creerConcert(struct s_element *tete,char *concert,int spectateur );
// Ajout d'un concert joué pour un artiste donné
struct s_noeud *ajouterConcert(struct s_noeud *racine, char *nomConcert, int classementSpectateur);
// Additione le spectateur de chaque concert
int compterSpectateur(struct s_element *concert);
// Recherche un artiste et renvoit son noeud
struct s_noeud *rechercherArtiste(struct s_noeud *racine,char *nom);
void meilleurArtiste(struct s_noeud *racine,struct s_noeud **meilleur,struct s_element *ptrSurElement,int *MAX);
void freeArbre(struct s_noeud *racine);
void freeListe(struct s_element *element);
void main ()
{
FILE *fich=fopen("concerts.txt","r");
short choix = -1,tmpSpectateur,tmpClassementSpectateur;
char tmpNom[51],tmpNomSalle[51],tmpPays[51],tmpDate[51],tmpNbrSpectateur[51],tmpPrixMoyen[51],tmpConcert[51],tmpNomConcert[51];
struct s_noeud *racine=NULL;
struct s_element *tete=NULL;
struct s_element *ptrSurElement;
int spectateurArtiste = 0;
struct s_noeud *positionArtiste;
int max = -INT_MAX;
if(fich) // Si ouverture du fichier réussi
{
// Boucle de lecture du fichier
while(fscanf(fich,"%s",tmpNom) != EOF)
{
fscanf(fich,"%s",tmpConcert); // Lecture d'amorçe
while(tmpConcert[0] != '.') // Tant qu'on ne tombe pas sur le . on continue
{
fscanf(fich,"%hd",&tmpSpectateur);
tete = creerListe(tete,tmpConcert,tmpSpectateur);
fscanf(fich,"%s",tmpConcert);
}
racine = creerArbre(racine,tmpNom,tete); // On crée l'arbre
tete=NULL; // On remet la liste chaînée créée à NULL
// Sinon on obtiendra une liste contenant tous les concerts
} // joué de tous les artistes.
do
{
printf("1.Afficher les artistes ou les groupes par odre alphabetique\n");
printf("2.Ajouter un/des concert(s) a un artiste ou groupe\n");
printf("3.Afficher les concerts\n");
printf("4.Classement des artistes ou groupes par rapport au nombre de spectateur\n");
printf("5.Groupe ou artiste ayant remporté la recette la plus importante...\n");
printf("0.Quitter\n");
printf("Choix : ");
scanf("%hd",&choix);
system("cls");
switch(choix)
{
case 1 : system("cls");
if (racine == NULL)
{
printf("Aucun groupe ou artiste ! \n");
}
else
{
ptrSurElement = racine->listeConcert;
afficherArbre(racine,ptrSurElement);
}
_getch();
system("cls");
break;
case 2 : system("cls");
printf("Nom de l artiste ou du groupe : ");
fflush(stdin);
gets(tmpNom);
positionArtiste = rechercherArtiste(racine,tmpNom);
if(positionArtiste != NULL)
{
printf("Nom du groupe ou de l artiste : ");
fflush(stdin);
gets(tmpNomConcert);
printf("Spectateur : ");
fflush(stdin);
scanf("%hd",&tmpClassementSpectateur);
ajouterConcert(positionArtiste,tmpNomConcert,tmpClassementSpectateur);
printf("Ajout termine ! \n");
}
else
{
printf("Artiste ou groupe introuvable !\n");
}
_getch();
system("cls");
break;
case 3 : positionArtiste=racine;
meilleurArtiste(racine,&positionArtiste,ptrSurElement,&max);
printf("Le meilleur serveur est %s avec %hd aces",positionArtiste->nom,max);
break;
case 5 : system("cls");
printf("Nom : ");
fflush(stdin);
gets(tmpNom);
system("cls");
positionArtiste = rechercherArtiste(racine,tmpNom);
if(positionArtiste != NULL)
{
spectateurArtiste=compterSpectateur(positionArtiste->listeConcert);
printf("%s a fait %hd spectateur pendant le concert\n",tmpNom,spectateurArtiste);
}
else
{
printf("L'artiste %s est introuvable",tmpNom);
}
_getch();
system("cls");
break;
case 0 : freeArbre(racine);
break;
}
}
while(choix !=6);
}
else
{
printf("Fichier introuvable !\n");
}
}
// >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>//
// Cette fonction permet de créer un noeud en prennant comme paramètre les //
// informations relatives à ce noeuds. //
// Elle allouera l'espèce nécessaire et initialisera les pointeurs fg & fd à NULL. //
// Celà permettra s'il n'y a plus rien à gauche ni à droite d'un noeud d'obtenir //
// NULL comme résultat, c'est-à-dire fin de l'arbre, ou fin d'une branche. //
// >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>//
struct s_noeud *creerNoeud(char *nom, struct s_element *tete)
{
struct s_noeud *noeud;
short taille;
noeud=(struct s_noeud*)malloc(sizeof(struct s_noeud)); // Allocation de la "taille" des pointeurs
// du noeud.
taille=strlen(nom); // Nombre de caractères contenu dans nom
noeud->nom = (char*)malloc(taille * sizeof(char) + sizeof(char)); // Allocation de la taille du nom + 1 caractère
strcpy(noeud->nom,nom); // pour le \0
noeud->fd = NULL;
noeud->fg = NULL;
noeud ->listeConcert = tete;
return noeud;
}
// >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>//
// Fonction récursive qui permettra de se placer au bon endroit dans //
// l'arbre (par rapport au nom et prénom) //
// Si Racine = NULL, celà veut dire que le noeud où l'on se trouve sur //
// un noeud vide. On va donc y créer un noeud avec les informations souhaitées. //
// Par contre s'il y a des informations dans le noeud où l'on se trouve //
// alors on va le comparer avec le nom que l'on veut ajouter. Si racine->nom //
// est plus grand que que nom, alors le noeud contenant le nom sera mit vers //
// le fils gauche du noeud pointé actuellement //
// >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>//
struct s_noeud *creerArbre(struct s_noeud *racine,char *nom,struct s_element *tete)
{
if(racine == NULL)
{
racine = creerNoeud(nom,tete); // On crée et alloue un noeud
}
else
{
if( strcmpi(racine->nom,nom) > 0) // On compare le noeud avec les infos que l'on a
{
racine->fg = creerArbre(racine->fg,nom,tete); // Si la condition respecté, on se déplace dans l'arbre
}
else
{
if(strcmpi(racine->nom,nom) < 0)
{
racine->fd = creerArbre(racine->fd,nom,tete);
}
else
{
if(strcmpi(racine->nom,nom) > 0) // A VOIR
{
racine->fg = creerArbre(racine->fg,nom,tete);
}
else
{
racine->fd = creerArbre(racine->fd,nom,tete);
}
}
}
}
return racine;
}
// >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>//
// Simple fonction récursive par symétrie. //
// On va aller le plus à gauche possible tant que l'on ne quitte pas l'arbre. //
// Si on descend de trop, on va remonter d'un cran et se déplacer vers la droite. //
// Utilisation d'un pointeur temporaire pour ne pas modifier la liste chaînée //
// >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>//
void afficherArbre(struct s_noeud *racine,struct s_element *ptrSurElement)
{
if(racine != NULL)
{
ptrSurElement = racine->listeConcert;
afficherArbre(racine->fg,ptrSurElement);
printf("Nom : %s\n",racine->nom);
while(ptrSurElement != NULL)
{
printf("spectateur : %s",ptrSurElement->concert);
if(ptrSurElement->spectateur == 0)
{
printf("/Aucun spectateur !");
}
else
{
printf("/spectateur : %hd",ptrSurElement->spectateur);
}
ptrSurElement = ptrSurElement->suivant;
printf("\n");
}
printf("\n\n\n");
afficherArbre(racine->fd,ptrSurElement);
}
}
// >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>//
// Fonction récursive permettant de se placer à la fin de la liste chaînée. //
// Elle alloue également la bonne taille pour chaque élément via la fonction //
// creationConcert. //
// >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>//
struct s_element *creerListe(struct s_element *tete,char *concert,int spectateur)
{
if(tete == NULL)
{
tete = creerConcert(tete,concert,spectateur);
}
else
{
tete->suivant = creerListe(tete->suivant,concert,spectateur);
}
return tete;
}
// >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>//
// Fonction de création d'un élément dans la liste, on y alloue la taille //
// nécessaire et on initialise le pointeur vers le prochain élément sur NULL //
// >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>//
struct s_element *creerConcert(struct s_element *tete,char *concert,int spectateur)
{
short taille;
tete = (struct s_element*)malloc(sizeof(struct s_element));
taille = strlen(concert);
tete->concert = (char*)malloc(taille*sizeof(char) + sizeof(char) );
strcpy(tete->concert,concert);
tete->spectateur = spectateur;
tete->suivant = NULL;
return tete;
}
// >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>//
// Procédure qui parcours la liste des concerts pour lequel l'artiste rechercher //
// auparavant a participé . Dés qu'on arrive à la fin de la liste (racine->liste == NULL) //
// alors on est donc arrivé à la fin de celle-ci. //
// On utilise un pointeur temporaire, pour ne pas modifier la liste. (en ne travaillant pas avec la //
// variable racine) //
// >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>//
struct s_noeud *ajouterConcert(struct s_noeud *racine, char *nomConcert, int classementSpectateur)
{
short taille;
struct s_element *nouveau;
struct s_element *ptr;
ptr = racine->listeConcert;
nouveau = (struct s_element*)malloc(sizeof(struct s_element));
taille=strlen(nomConcert);
nouveau->concert = (char*)malloc(taille * sizeof(char) + sizeof(char));
strcpy(nouveau->concert,nomConcert);
nouveau->spectateur = classementSpectateur;
nouveau->suivant = NULL;
if(ptr != NULL)
{
while(ptr->suivant != NULL)
{
ptr = ptr->suivant;
}
ptr->suivant = nouveau;
}
else
{
racine->listeConcert= nouveau;
}
return racine;
}
// >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> //
// Fonction permettant de se placer à la bonne position dans l'arbre et de //
// renvoyer 0 si pas trouver, et s'il a été trouvé renvoyer le position //
// >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>//
struct s_noeud *rechercherArtiste(struct s_noeud *racine,char *nom)
{
if(racine == NULL)
{
return NULL;
}
else
{
if( strcmpi(racine->nom,nom) > 0)
{
return rechercherArtiste(racine->fg,nom);
}
else
{
if( strcmpi(racine->nom,nom) < 0)
{
return rechercherArtiste(racine->fd,nom);
}
else
{
if( strcmpi(racine->nom,nom) > 0) // A VOIR
{
return rechercherArtiste(racine->fg,nom);
}
else
{
if(( strcmpi(racine->nom,nom) < 0)) // A VOIR
{
return rechercherArtiste(racine->fd,nom);
}
else
{
return racine;
}
}
}
}
}
}
// >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>//
// Simple fonction qui va balayer une liste chaînée tout en additionnement //
// le nombre de spectateur que fait un artiste //
// >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>//
int compterSpectateur(struct s_element *concert)
{
int spectateur=0;
while( concert != NULL )
{
spectateur += concert ->spectateur;
concert = concert->suivant;
}
return spectateur;
}
// >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>//
// Fonction recherchant l'artiste ayant obtenu le plus de spectateur au total //
// >>>>>>>>>>>>>> A TERMINER <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<//
// >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>//
void meilleurArtiste(struct s_noeud *racine,struct s_noeud **meilleur,struct s_element *ptrSurElement,int *MAX)
{
int sommeActuel = 0;
if(racine != NULL)
{
ptrSurElement = racine->listeConcert;
meilleurArtiste(racine->fg,meilleur,ptrSurElement,MAX);
while(ptrSurElement != NULL)
{
sommeActuel += ptrSurElement->spectateur;
ptrSurElement = ptrSurElement->suivant;
}
if(*MAX < sommeActuel)
{
*meilleur = racine;
*MAX = sommeActuel;
}
printf("actuel:%hd ",sommeActuel);
printf("max:%hd \n",*MAX);
meilleurArtiste(racine->fd,meilleur,ptrSurElement,MAX);
}
}
// >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>//
// Fonctions libérants la mémoire occupé par l'arbre //
// >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>//
void freeArbre(struct s_noeud *racine)
{
if(racine != NULL)
{
freeArbre(racine->fg);
freeArbre(racine->fd);
free(racine->nom);
free(racine);
}
}
void freeListe(struct s_element *element)
{
if(element->suivant->concert == NULL)
{
printf("aaa");
printf("%s",element->concert);
free(element->concert);
free(element);
}
else
{
freeListe(element->suivant);
}
}
Merci :-)
A voir également:
RECURSIVITE pour tous les traitements sur les arbres et liste chaînée - Langage
BunoCS
Messages postés15475Date d'inscriptionlundi 11 juillet 2005StatutModérateurDernière intervention23 avril 2024103 26 nov. 2011 à 13:50
Hello,
Je pense qu'une petite lecture s'impose...
Je vois, dans ma boule de cristal, où est le bug. Il se situe...entre le clavier et la chaise...
Bon, plus sérieusement, sans question précise et ni code précis, on ne va pas pourvoir t'aider....
@+
Buno
----------------------------------------
L'urgent est fait, l'impossible est en cours. Pour les miracles, prévoir un délai...
JulSoft
Messages postés354Date d'inscriptiondimanche 3 juin 2001StatutMembreDernière intervention11 mars 2013 2 déc. 2011 à 11:58
@buno: Ma boule de crystal me dit que c'est dans la fonction marquée "A TERMINER" qu'il manque quelque chose... Comme quoi c'est pas si mal foutu que ça les données des exercices d'info...
@HerveYims: Ca m'a tout l'air d'être du parcours de listes chainées pur et dur. Vous avez du voir comment on fait ça en cours non?
Un truc du genre
while(courant.suivant!=null){
// traitement sur courant.suivant
// courant = courant.suivant;
}
