Construction d'un arbre à partir d'un fichier

Résolu
Signaler
Messages postés
42
Date d'inscription
mercredi 9 juin 2004
Statut
Membre
Dernière intervention
17 août 2010
-
Messages postés
149
Date d'inscription
mercredi 28 mars 2007
Statut
Membre
Dernière intervention
17 mai 2007
-
Bonjour a tous,


Ma question est comment construire un arbre contenant des données
stockées dans un fichier. C'est pour un logiciel de devinette d'animaux.


Dans mon fichier, exemple.txt :


A1(chat,4,oui,...)

A2(dauphin,0,non...)

A3(serpent,0,non...)

A4(chien,4,non...)

A5(corbeau,2,non...)

...


J'ai déclaré une structure animal


typedef struct animal_s

{

char[20] nom; (chat)

int nbpatte; (4)

char[3] moustache; (mammifère)

...
}animal;


En fait le but du jeu c'est ,pour chaque question posé et selon la
réponse de l'utilisateur, de construire un arbre permettant à la fin de
deviner l'animal.


Exemple :

Question 1:combien a -t-il de pattes ?

Reponse possible:0,2,4


Si la réponse est 0, les fils de l'arbre seront A2,A3

Si la réponse est 2, le fils de l'arbre est A5

Si la réponse est 4, les fils seront A1 et A4


Si la réponse est 2, le programme renverra comme réponse A5 donc le corbeau.

Si l'utilisateur a repondu 0 ou 4, une deuxième question sera posé. Par exemple, Est ce qu'il a des moustaches?(oui / non)


Si l'utilisateur a repondu 0 puis oui, le programme renverra qu'aucun animal a étté trouvé. S'il a repondu non, une troisième question sera posé pour savoir si c'est le serpent ou le dauphin.

Si l'utilisateur a repondu 4 puis oui, le programme renvera comme réponse le chat, sinon le chien.


Voila, donc je ne vois pas trop comment créer l'arbre à partir des données contenus dans mon fichier.


Si vous avez une idée.


Merci

3 réponses

Messages postés
149
Date d'inscription
mercredi 28 mars 2007
Statut
Membre
Dernière intervention
17 mai 2007
2
Salut,

Alors il faut que tu fasses un arbre dans lequel chaque noeud contient une question et pour chaque réponse possible il y a un noeud différent
Par exemple pour le noeud N0, la question est : "Combien de pattes ?" et si la réponse est 0 ca va au noeud N1, si la réponse est 2 ca va au noeud N2, si la réponse est 4 ça va au noeud N3
-- le noeud N2 ne contient que corbeau pour le moment donc on a notre structure de noeuds qui se construit car un noeud peut être une question ou un animal.

struct noeud {
  char noeudOuAnimal;
  char * question;
  struct list * noeudFils;
  struct animal * reponse;
}

Tu pourrais faire une union mais disons que non pour l'instant pour noeudFils faut faire une structure de données du type :

( (0, N1) , (2, N2), (4, N4) )
 mais aussi
( (oui, N5) , (non, N6) )
donc faut que le premier champ soit int ou char *

Bon mais là tu as que ta structure de données, comment créer l'arbre ?

- faut faire un algorithme récursif je dirais, qui fonctionne comme ça :

  liste-animaux <--- tous les animaux
  arbre <--- arbre vide
  tantque liste-animaux non vide faire
  chercher un critere C qui permet d'avoir au moins deux reponses différentes
  classer tous les animaux de liste-arbre selon le critère C 

Mettre tous les animaux dans les différentes catégories dans l'arbre.

ERF! Pas fait en récursif, je le refait, lol.

Donc:

traitement-animaux ( arbre A, liste-animaux L) {
  trouver une question qui génère au moins deux réponses différentes
  pourtoutes les réponses R possibles faire
    L2 <-- tous les animaux de L qui répondent à R
    traitement-animaux (A-->R, L2)
  finpourtoute
 }

Voilà, c'est mieux.

@++

Une autruche ne se cuit pas aux petits lardons.
Messages postés
42
Date d'inscription
mercredi 9 juin 2004
Statut
Membre
Dernière intervention
17 août 2010

Merci pour ton aide. Mais peux tu me dire comment créer un liste chaînée contenant les données d'un fichier.

Exemple :

Dans mon fichier, j'ai :

Q1(Quel est sa couleur ?)
Q2(Combien de pattes ?)
Q3(A-t-il des moustaches ?)

Comment faire pour construire une liste chaînée avec ces questions ?

Voila ma structure:
typedef struct question_s
{
    int num;
    char question[70];
    question *suiv;
}question;

Merci
Messages postés
149
Date d'inscription
mercredi 28 mars 2007
Statut
Membre
Dernière intervention
17 mai 2007
2
Salut,

Oui tu peux faire une liste chaînée comme ça :

typedef struct reponse {
  char reponse[10];
  struct noeud * noeud;
  struct question * next;
} question;

Car attention c'est les réponses qu'il faut chaîner dans chaque noeud de l'arbre
Un noeud de l'arbre a une seule question mais une liste de réponse
Puis après il faut trouver le noeud correspondant à la réponse donnée de la manière suivante:

struct noeud * trouverNoeudFils(struct noeud * pere, char * reponse) {
  struct reponse * r;
 r = pere->reponses;
  int trouve = 0;
while ((!trouve) && (r!=NULL)) {
  if (strcmp(r->reponse, reponse)==0) {
   return r->noeud;
 }
 } // fin du while
  return NULL; // aucun noeud correspondant
}
 (tu as pas besoin de la variable trouve)
oops attend j'ai fait erreur dans la structure du debut
Donc oui faut bien mettre "reponse" partout, pas "question"
Sinon oui, c'est bien aussi d'avoir une liste de questions pour pouvoir stocker l'ordre.

@++

Une autruche ne se cuit pas aux petits lardons.