Aller au contenu


Photo
- - - - -

Créer un arbre en c


  • Veuillez vous connecter pour répondre
11 réponses à ce sujet

#1 R2D21995

R2D21995

    Membre passionné

  • Membres
  • PipPipPip
  • 366 messages

Posté 08 septembre 2016 - 10:16

Bonsoir,

j'ai une petite question.

J'aimerai créer un arbre en c avec des chaînes de caractère et ensuite pouvoir parcourir en fonction d'un mots clef ou d'une phrase.

 

Par ex:

 

                                  Est-ce que je mange du chocolat

                                                  /                  \

                                                 /                    \

                                                /                      \

                                  Est-ce   que je          mange du chocolat

                                    /           \                     /         \

                                   /             \                   /           \

                                 /                \                 /             \

                              Est-ce          que je      mange      du chocolat

                                                   /      \                        /       \

                                                  /        \                      /         \

                                                 /          \                    /           \

                                              que        je                du       chocolat

 

Et ensuite si je tape Est-ce ça me propose que puis je et ainsi de suite.

 

Je ne sais pas si j'ai été suffisamment clair.
Merci d'avance et bonne soirée.


Modifié par R2D21995, 08 septembre 2016 - 10:26 .

 

Il faut toujours viser la lune, car même en cas d’échec, on atterrit dans les étoiles

 

Soutenez mon projet:

https://wweeddoo.com...cture-numerique


#2 macerobotics

macerobotics

    Membre occasionnel

  • Membres
  • Pip
  • 126 messages
  • Gender:Not Telling
  • Location:Bretagne

Posté 09 septembre 2016 - 05:55

Salut,

 

Pour faire des arbres en C, tu peux utiliser les structures et les pointeurs. Un peu comme les listes chaînées.

Une branche représenté par un pointeur et donc chaque nœud de ton arbre peut être représenter par deux pointeurs.


Mace Robotics - mobile platform for education makers and research.

www.macerobotics.com


#3 Oracid

Oracid

    Pilier du forum

  • Modérateur
  • PipPipPipPipPip
  • 4 425 messages
  • Gender:Male

Posté 09 septembre 2016 - 06:24

Intuitivement, je dirais que tu devrais aller voir du coté des bibliothèques de fonctions pour structure XML.
Mais je ne pourrais pas t'en dire plus...
Ma chaine vidéo YouTube : https://www.youtube....wMz-IzZqyvqEUek

#4 R2D21995

R2D21995

    Membre passionné

  • Membres
  • PipPipPip
  • 366 messages

Posté 09 septembre 2016 - 09:01

struct noeud {
  char *val;
  struct noeud *g;
  struct noeud *d;
};

typedef struct noeud *ab;

/*creation dun neoud*/

ab creat(char *v, ab ls, ab rs)
{
  ab res;
  res  = (ab) malloc(sizeof(struct noeud));
  if (res == NULL) {
    fprintf(stderr, "Impossible d'allouer le noeud");
    return NULL;
  }

  res-> val = v;
  res->g = ls;
  res->d = rs;

  return res;
}
void ajout(ab* pr, char *elt)
{
  if (pr==NULL) {
    printf("Erreur.");
    exit(1);
  }
  else if ((*pr) == NULL)
    *pr = creat(elt,NULL,NULL);
  else if ((*pr)->g == NULL)
    (*pr)->g = creat(elt,NULL,NULL);
  else if ((*pr)->d == NULL)
    (*pr)->d = creat(elt,NULL,NULL);
  else ajout( &((*pr)->g), elt);
}

void afficheracine(ab n)
{ if (n != NULL) {
    printf("%s\n", n->val);}
}
void parcourirArbre(ab n)
{
  if (n != NULL) {
    //printf("%d ", n->val);                                                                                                                                                                                 
    if((n->g) != NULL)
      printf("%s\n", n->g->val);
    if((n->d) != NULL)
      printf("%s\n", n->d->val);
    parcourirArbre(n->g);
  }
}
int main(void)
{
  ab ls = NULL;
  ab rs = NULL;

  rs = creat("a", ls, rs);
  afficheracine(rs);
  ajout(&rs, "Bonjour");
  ajout(&rs, "tout");
  ajout(&rs, "le");
  ajout(&rs, "monde");
  parcourirArbre(rs);
  return 0;
}

après je bloques pour l'algo de recherche de l'abre


 

Il faut toujours viser la lune, car même en cas d’échec, on atterrit dans les étoiles

 

Soutenez mon projet:

https://wweeddoo.com...cture-numerique


#5 levend

levend

    Pilier du forum

  • Membres
  • PipPipPipPipPip
  • 4 484 messages
  • Gender:Male
  • Location:Vendée
  • Interests:Robotique, informatique, architecture et patrimoine...

Posté 09 septembre 2016 - 05:52

Un arbre a les branches en haut :o :D, là je ne sais plus ce que c'est.

 

Pour l'algo de recherche, ce serait bien de savoir ce qu'il y a réellement dans ton arbre, ça pourrait nous aidez..



#6 Path

Path

    Made By Humans

  • Modérateur
  • PipPipPipPipPip
  • 2 396 messages
  • Gender:Male
  • Location:Paris

Posté 09 septembre 2016 - 07:29

Tiens, c'est bonheur :)
http://rperrot.developpez.com/articles/algo/structures/arbres/

Podcast Made By Humans

Je cherche des volontaires de tous niveaux pour nos petites conversations entre hobbyistes.

Accès aux salles secrètes

 


#7 R2D21995

R2D21995

    Membre passionné

  • Membres
  • PipPipPip
  • 366 messages

Posté 09 septembre 2016 - 07:42

Merci pour le lien. En faite ce serai pour faire un arbre syntaxique mais ça à l'air trop compliqué pour mon niveau.


 

Il faut toujours viser la lune, car même en cas d’échec, on atterrit dans les étoiles

 

Soutenez mon projet:

https://wweeddoo.com...cture-numerique


#8 Path

Path

    Made By Humans

  • Modérateur
  • PipPipPipPipPip
  • 2 396 messages
  • Gender:Male
  • Location:Paris

Posté 09 septembre 2016 - 07:44

Le parcours d'arbre, c'est pas simple :)

Podcast Made By Humans

Je cherche des volontaires de tous niveaux pour nos petites conversations entre hobbyistes.

Accès aux salles secrètes

 


#9 cocothebo

cocothebo

    Membre passionné

  • Membres
  • PipPipPip
  • 341 messages
  • Gender:Male

Posté 12 septembre 2016 - 04:10

Salut,

 

La recherche si j'ai bien compris ce que tu veux faire ne sera surement pas très compliquée à faire d'une manière peut être un peu naïve: tu parcours ton arbre en profondeur pour t'arrêter ou tu as besoin OU en largeur (à définir selon ce qui semble le plus rapide pour trouver ce que tu cherches).

 

Une recherche en profondeur = tu pars de la racine et tu vas jusqu'a la première feuille puis tu remontes et la deuxième feuille, etc. bref un exemple en prenant ton arbre niveau parcours sera:

"Est-ce que je mange du chocolat" -> "Est-ce que je" -> "Est-ce" -> "Est-ce que je" -> "que je" -> "que" -> "que je" -> "je" -> etc etc.

 

Une recherche en largeur est une recherche "horizontale", tu pars de la racine puis tu parcours tous les fils de la racine puis tous ceux du niveau du dessous etc.

"Est-ce que je mange du chocolat" -> "Est-ce que je" -> "mange du chocolat" -> "Est-ce que je mange du chocolat" -> "Est-ce que je" -> "Est-ce" -> "que je" -> etc

 

Bien sur la j'ai fait avec juste les liens qui existent sur ton arbre, on pourrait penser à optimiser un peu l'arbre pour éviter de toujours devoir revenir en arrière...c'est bien pour  parcourir l'arbre, mais c'est très vite galère quand tu dois mettre à jour l'arbre (ajout/supression de noeuds ou feuille)

 

 

Après la grande question est de savoir si cette représentation d'une phrase sous forme d'un arbre comme tu le décris est adapté à ce que tu veux faire...La j'aurai tendance à dire (plus une intuition vu qu'on ne sait pas trop ton use case) que non c'est surement pas le plus adapté.

Un arbre de ce style souvent ça permet de classer des choses qui ont des liens entre eux et qui permettent après d'appliquer des algos pour trouver la partie la plus interessante (genre alpha-beta ou mini-max pour ceux de base bien connus, qui permettent de faire une "IA" pour faire jouer un ordinateur par exemple).

 

Après tu parles d'arbre syntaxique qui la effectivement comme son nom l'indique est un arbre, mais dans ce cas la relation entre les noeuds est la syntaxde de ta phrase, ce qui n'est pas vraiment le cas dans ton exemple.



#10 R2D21995

R2D21995

    Membre passionné

  • Membres
  • PipPipPip
  • 366 messages

Posté 12 septembre 2016 - 04:22

Merci beaucoup pour ta réponse.


 

Il faut toujours viser la lune, car même en cas d’échec, on atterrit dans les étoiles

 

Soutenez mon projet:

https://wweeddoo.com...cture-numerique


#11 Newbies

Newbies

    Membre passionné

  • Membres
  • PipPipPip
  • 487 messages
  • Gender:Male
  • Location:Paris
  • Interests:Programmation et robotique

Posté 02 février 2017 - 09:06

La meilleure façon de faire un algo de recherche dans un arbre est d'utiliser la récursivité (rappeler la fonction dans laquelle on se trouve). 

 

Par exemple, pour afficher tout les éléments de ton arbre à partir de l'élement en bas à gauche, tu peux écrire la fonction récursive suivante:

bool print_tree(struct *leaf) {
  if (!leaf)
    return (false);
  print_tree(leaf->left);
  printf("data : %s\n", leaf->data);
  print_tree(leaf->right);
}


#12 cocothebo

cocothebo

    Membre passionné

  • Membres
  • PipPipPip
  • 341 messages
  • Gender:Male

Posté 04 février 2017 - 06:59

Salut,

 

Quelques remarques:

  • la récursivité c'est bien, mais ça dépend sur quoi on tourne, autant quand ya beaucoup de RAM ya pas de soucis, autant en embarqué style arduino, ya des gros risques d'exploser la pile dès que l'arbre a quelques niveaux de profondeur.
  • en revanche effectivement en terme de ligne de code c'est plutôt efficace
  • la récursivité peut être dangereuse concernant les risques de boucles infinies ou presque (bien étudier les conditions de fin)
  • quelques remarques plus sur la forme de la proposition
    • a quoi sert le booléen en retour?
    • d'habitude "leaf" est utilisé comme so nom l'indique pour les "feuilles", je pense qu'il vaut mieux parler de "noeud"
    • il me semble intéressant pour les débutants d'expliciter la structure utilisée





0 utilisateur(s) li(sen)t ce sujet

0 members, 0 guests, 0 anonymous users