//Tous les codes sources sont en bas du post.

Bonjour,

Je dois, depuis un fichier contenant des mots, mettre tous les mots du fichier dans un arbre lexicographique. Ensuite je dois afficher les mots de cet arbre (donc le dictionnaire) et faire des recherches lexicographiques de certains mots via l'arbre pour étudier le temps d'exécution. 

Seulement j'ai plusieurs problèmes tout d'abord dans la fonction lire_dico(), je ne pense pas arriver à inscrire tous les mots du fichier dans l'arbre. En effet lorsque j'exécute mon programme :

time ./main_arbre.c 100000 zoologistes

Le terminal m'indique que le mot n'a pas été trouvé.

Ensuite dans la fonction d'affichage afficher_dico(), soit aucun mot s'affiche soit le terminal défile sans rien afficher. De plus j'ai une segmentation faut :

==12954== Invalid read of size 4
==12954==    at 0x100001B17: afficher_mots (arbre_lexicographique.c:82)
==12954==    by 0x100001B73: afficher_mots (arbre_lexicographique.c:85)
==12954==    by 0x100001B54: afficher_mots (arbre_lexicographique.c:84)
==12954==    by 0x100001B54: afficher_mots (arbre_lexicographique.c:84)
==12954==    by 0x100001B73: afficher_mots (arbre_lexicographique.c:85)
==12954==    by 0x100001B54: afficher_mots (arbre_lexicographique.c:84)
==12954==    by 0x100001B73: afficher_mots (arbre_lexicographique.c:85)
==12954==    by 0x100001B54: afficher_mots (arbre_lexicographique.c:84)
==12954==    by 0x100001B54: afficher_mots (arbre_lexicographique.c:84)
==12954==    by 0x100001B54: afficher_mots (arbre_lexicographique.c:84)
==12954==    by 0x100001B73: afficher_mots (arbre_lexicographique.c:85)
==12954==    by 0x100001BD5: afficher_dico (arbre_lexicographique.c:96)
==12954==  Address 0x4 is not stack'd, malloc'd or (recently) free'd

Apparement mon code ne s'arrête pas lorsque le mot est arrivé à sa fin et donc continue d'essayer de lire les lettres après (qui n'existent pas).

Seulement ma condition m'a l'air bonne et je ne vois pas le problème.

Voici les codes :

arbre_lexicographique.c : 

#include "arbre_lexicographique.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

PNoeud creer_noeud(char lettre){
  PNoeud pn=(PNoeud)malloc(sizeof(Noeud));
  if (pn==NULL) {
    printf("Impossible d'allouer un noeud\n");
    return NULL;
  }
 
  pn->lettre=lettre;
  pn->fin_de_mot=non_fin;
  pn->frere_suivant=NULL;
  pn->fils=NULL;
  return pn;
}

void inserer_lettre(PNoeud* racine, PNoeud* n_lettre, char lettre) {
  PNoeud prec=NULL;
  PNoeud n=*racine;
  if (n==NULL) {
    *racine=creer_noeud(lettre);
    *n_lettre=*racine;
    return;
  }

  while(n!=NULL) {
    if (n->lettre == lettre) {
      *n_lettre=n;
      return;
    }
    if (n->lettre>lettre) {
      // on doit inserer avant n
      if (prec==NULL) {
        // insertion en tete
        prec=creer_noeud(lettre);
        prec->frere_suivant=n;
        *racine=prec;
        *n_lettre=*racine;
      }
      else {
        *n_lettre=creer_noeud(lettre);
        prec->frere_suivant=*n_lettre;
        (*n_lettre)->frere_suivant=n;
      }
      return;
    }
    prec=n;
    n = n->frere_suivant;
  }
  *n_lettre=creer_noeud(lettre);
  prec->frere_suivant=*n_lettre;
}

PNoeud ajouter_mot(PNoeud racine, char *mot) {
  PNoeud n=NULL;
  if (strlen(mot)==0) {
    return NULL;
  }
  inserer_lettre(&racine,&n,mot[0]);
  if (strlen(mot)==1) {
    n->fin_de_mot=fin;
  }
  else {
    n->fils=ajouter_mot(n->fils,mot+1);
  }
  return racine;
}

int taille(PNoeud racine) {
  if (racine==NULL) {
    return 0;
  }
  else {
    return 1+taille(racine->frere_suivant);
  }
}

void afficher_mots(PNoeud n, char mot_en_cours[], int index) {
  if(n->fin_de_mot != fin){
    mot_en_cours[index] = n->lettre;
    afficher_mots(n->fils, mot_en_cours, index++);
    afficher_mots(n->frere_suivant, mot_en_cours, index++);
  }
  else{
    mot_en_cours[index] = '\0';
    printf("%s\n",mot_en_cours);
  }
}

void afficher_dico(PNoeud racine) {
  if (racine){
    char* mot_en_cours = malloc(HAUTEUR);//sizeof(char) = 1
    afficher_mots(racine, mot_en_cours, 0);
  }
}

void detruire_dico(PNoeud dico) {
  if(dico){
    detruire_dico(dico->fils);
    detruire_dico(dico->frere_suivant);
    free(dico);
  }
}

PNoeud chercher_lettre(PNoeud n, char lettre) {
  if (n==NULL) {
    return NULL;
  }
  if (n->lettre==lettre) {
    return n;
  }
  if (n->lettre>lettre) {
    return NULL;
  }
  return chercher_lettre(n->frere_suivant,lettre);
}

int rechercher_mot(PNoeud dico, char *mot) {
  PNoeud n=chercher_lettre(dico,mot[0]);
  if (n==NULL) {
    return 0;
  }
  if (strlen(mot)==1) {
    return n->fin_de_mot == fin;
  }
  return rechercher_mot(n->fils,mot+1);
}

PNoeud lire_dico(const char *nom_fichier) {
  PNoeud dico = NULL;
  FILE* p_fichier;
  if (p_fichier = fopen(nom_fichier,"r")){
    char* mot = malloc(HAUTEUR);
    while(fgets(mot,100,p_fichier)){
      mot[HAUTEUR-1] = '\0';
      dico = ajouter_mot(dico,mot);
    }
    return dico;
  }
  else{
    printf("Erreur lors de l'ouverture du fichier\n");
    return dico;
  }
}

arbre_lexicographique.h :

#ifndef _ARBRE_LEXICOGRAPHIQUE_H_
#define _ARBRE_LEXICOGRAPHIQUE_H_

#include "commun.h"

#define HAUTEUR 26 //hauteur choisie arbitrairement à partir du plus long mot de la langue française (anticonstitutionnellement) 

typedef struct noeud *PNoeud;
typedef struct noeud {
  char lettre;
  FDM fin_de_mot;
  PNoeud fils;
  PNoeud frere_suivant;
} Noeud;

PNoeud creer_noeud(char lettre);
void inserer_lettre(PNoeud *racine, PNoeud *n_lettre, char lettre);
PNoeud ajouter_mot(PNoeud racine, char *mot);
void afficher_mots(PNoeud n, char mot_en_cours[], int index);
void afficher_dico(PNoeud racine);
void detruire_dico(PNoeud dico);
int rechercher_mot(PNoeud dico, char *mot);

PNoeud lire_dico(const char *nom_fichier);

#endif

main_arbre.c :

#include <stdio.h>
#include <stdlib.h>
#include "arbre_lexicographique.h"


int main(int argc, char **argv){
	if (argc != 3){
		printf("Nombre d'argument incorrect\n");
		return 0;
	}
	//On commence par afficher le dictionnaire :
	PNoeud dico = lire_dico("french_za");
	/*afficher_dico(dico);*/
	
	//On fait des recherches dans le dictionnaire :
	int tmp,i;
	for (i = 0; i < atoi(argv[1]); i++){
		tmp = rechercher_mot(dico,argv[2]);
	}
	if (tmp){
		printf("Le mot \"%s\" a été trouvé %d fois\n",argv[2],atoi(argv[1]));
	}
	else printf("Le mot \"%s\" n'a pas été trouvé\n",argv[2]);

	//On libère la mémoire :
	detruire_dico(dico);
 	return 0;
}

Le fichier dictionnaire faisant plus de 100 000 lignes, je vous l'épargne

Voilà, n'hésitez pas si vous avez besoin de plus de précisions.

Merci de votre temps

Hello,

alors comme ça en diagonale :

void afficher_mots(PNoeud n, char mot_en_cours[], int index) {
  if(n->fin_de_mot != fin){
    mot_en_cours[index] = n->lettre;
    afficher_mots(n->fils, mot_en_cours, index++);
    afficher_mots(n->frere_suivant, mot_en_cours, index++);
  }
  else{
    mot_en_cours[index] = '\0';
    printf("%s\n",mot_en_cours);
  }
}

tu ne testes jamais si le PNoeud est NULL ?

White Crow a écrit:

Hello,

alors comme ça en diagonale :

void afficher_mots(PNoeud n, char mot_en_cours[], int index) {
  if(n->fin_de_mot != fin){
    mot_en_cours[index] = n->lettre;
    afficher_mots(n->fils, mot_en_cours, index++);
    afficher_mots(n->frere_suivant, mot_en_cours, index++);
  }
  else{
    mot_en_cours[index] = '\0';
    printf("%s\n",mot_en_cours);
  }
}

tu ne testes jamais si le PNoeud est NULL ?

Oui autant pour moi :

void afficher_mots(PNoeud n, char mot_en_cours[], int index) {
  if (n == NULL){
    return;
  }
  if(n->fin_de_mot != fin){
    mot_en_cours[index] = n->lettre;
    afficher_mots(n->fils, mot_en_cours, index++);
    afficher_mots(n->frere_suivant, mot_en_cours, index++);
  }
  else{
    mot_en_cours[index] = '\0';
    printf("%s\n",mot_en_cours);
  }
}

Ah désolé, j'avoue que ma réponse n'était pas très explicite.

Le problème ne change pas, enfaite je passer un arbre qui n'était pas vide à chaque fois en paramètre. Donc l'erreur ne vient pas de là.

et ? en utilisant gdb ? le rapport valgrind ne change pas ?

un moment donné pourtant n->fils ou n->frere doivent être NULL

White Crow a écrit:

et ? en utilisant gdb ? le rapport valgrind ne change pas ?

un moment donné pourtant n->fils ou n->frere doivent être NULL

n->fils->fin_de_mot ou n->frere->fin_de_mot = fin à un moment oui.

C'est pour ça que je ne vois pas l'erreur;

as-tu essayé un debuger plus classique comme gdb (ou ddd ou nemiver ou …) plutôt que le daf (débuguage assisté par forum) ? La sortie valgrind n'est pas changée ? Avec gdb (ou autre) tu peux remonter la trace donnée par valgrind.

Plus prosaïquement, pourquoi avoir un marqueur «fin de mot» comme champ et non pas simplement une lettre indiquant la fin d'un mot ? les traitements s'en trouveraient simplifiés.

Si tu es dans le projet de scrabble, je te conseille la lecture de documents décrivant l'utilisation de DAG=directed acyclic graph (une structure très similaire à ton arbre binaire fils gauche/frere droit) mais plus compacte et plus efficace : le dawg (directed acyclic word graph). Il y a de bons articles sur les gaddag mais là c'est déjà plus avancé et un peu overkill.

As-tu un mini dico pour les tests ?

As-tu pensé à implémenter un affichage de ton arbre au format dot, parce qu'ensuite avec graphviz tu peux facilement créer des visualisations pour comprendre où ça coince.

-
Edité par White Crow 24 novembre 2020 à 20:47:00

White Crow a écrit:

as-tu essayé un debuger plus classique comme gdb (ou ddd ou nemiver ou …) plutôt que le daf (débuguage assisté par forum) ? La sortie valgrind n'est pas changée ? Avec gdb (ou autre) tu peux remonter la trace donnée par valgrind.

Plus prosaïquement, pourquoi avoir un marqueur «fin de mot» comme champ et non pas simplement une lettre indiquant la fin d'un mot ? les traitements s'en trouveraient simplifiés.

Si tu es dans le projet de scrabble, je te conseille la lecture de documents décrivant l'utilisation de DAG=directed acyclic graph (une structure très similaire à ton arbre binaire fils gauche/frere droit) mais plus compacte et plus efficace : le dawg (directed acyclic word graph). Il y a de bons articles sur les gaddag mais là c'est déjà plus avancé et un peu overkill.

As-tu un mini dico pour les tests ?

As-tu pensé à implémenter un affichage de ton arbre au format dot, parce qu'ensuite avec graphviz tu peux facilement créer des visualisations pour comprendre où ça coince.

-
Edité par White Crow il y a environ 19 heures

J'ai essayé de debug avec gdb seulement je ne suis pas très à l'aise avec et malgré les tutoriels que j'ai vu je n'arrive pas à faire tourner ma fonction ligne par ligne :

Thread 3 hit Breakpoint 1, main (argc=3, argv=0x7ffeefbffb28)

    at main_arbre.c:13

13if (dico = lire_dico("french_za")){

(gdb) s lire_dico("french_za")

Et à ce moment il tourne sans s'arrêter jusqu'à ce que je fasse ctrl C

Je ne peux donc pas exécuter le code de la fonction ligne par ligne

Et oui j''ai un dictionnaire de 130 000 lignes avec des mots ordonnés par ordre alphabétique

Premier conseil → construis toi un petit dico mais avec des mots bien choisis (quelques lemmes orthographiquement proches mais plusieurs flexions pour chaque lemme).

Deuxième conseil →un tuto quick and dirty pour bien utiliser gdb : utiliser nemiver si tu peux l'installer, c'est graphique et c'est simple ; au pire essaye DDD, c'est toujours graphique mais plus vieillot …

Sinon avec gdb :

• compiler ton code avec les options de debug (-g pas de moins -O) ;
• lancer gdb avec comme paramètre le nom de ton exécutable ;
• une fois dans gdb utiliser la commande break suivi du nom de la fonction que tu désires débuguer en profondeur ;
• lancer la session avec la commande run, elle suspendra l'exécution à l'entrée de la fonction marquée au step précédent ;
• utiliser les commandes print pour consulter la valeur des variables accessibles, step ou next pour avancer d'un cran, continue pour continuer l'exécution jusqu'au prochain break (la différence entre step et next est que step rentre dans les fonctions alors que next s'arrête juste après) ;
• et au pire comme il est écrit dans l'invite de gdb : «For help, type "help".»

Savoir utiliser un debuger (je ne parle pas de maîtriser, simplement de savoir utiliser) est tout autant indispensable au développeur que le jambon l'est au jambon beurre.

En survolant le code je pense a un premier probleme, a la creation de l'arbre ton dico vaut null.

Donc tu appelles inserer_mot avec un dico qui vaut null, mais tu ne geres pas ce cas dans inserer_mot.

thetui a écrit:

En survolant le code je pense a un premier probleme, a la creation de l'arbre ton dico vaut null.

Donc tu appelles inserer_mot avec un dico qui vaut null, mais tu ne geres pas ce cas dans inserer_mot.

Si le cas est géré dans inserer_mot mais merci !

White Crow a écrit:

Premier conseil → construis toi un petit dico mais avec des mots bien choisis (quelques lemmes orthographiquement proches mais plusieurs flexions pour chaque lemme).

Deuxième conseil →un tuto quick and dirty pour bien utiliser gdb : utiliser nemiver si tu peux l'installer, c'est graphique et c'est simple ; au pire essaye DDD, c'est toujours graphique mais plus vieillot …

Sinon avec gdb :

• compiler ton code avec les options de debug (-g pas de moins -O) ;
• lancer gdb avec comme paramètre le nom de ton exécutable ;
• une fois dans gdb utiliser la commande break suivi du nom de la fonction que tu désires débuguer en profondeur ;
• lancer la session avec la commande run, elle suspendra l'exécution à l'entrée de la fonction marquée au step précédent ;
• utiliser les commandes print pour consulter la valeur des variables accessibles, step ou next pour avancer d'un cran, continue pour continuer l'exécution jusqu'au prochain break (la différence entre step et next est que step rentre dans les fonctions alors que next s'arrête juste après) ;
• et au pire comme il est écrit dans l'invite de gdb : «For help, type "help".»

Savoir utiliser un debuger (je ne parle pas de maîtriser, simplement de savoir utiliser) est tout autant indispensable au développeur que le jambon l'est au jambon beurre.

C'est bon j'utilise gdb (bon je suis encore très lent et je passe des heures à debugger) mais j'ai pu corriger quelques trucs qui n'allait pas.

En tout cas merci, je pense que je vais m'y mettre plus souvent pour pouvoir l'utiliser comme il faut.

Seulement je me heurte à un problème et je ne vois pas du tout comment le résoudre, il se situe dans la fonction afficher_mot. Plus précisément l.87 lors de mon appel récursif, enfaite mon index ne s'incrémente pas tout le temps et je ne vois pas du tout d'où ça vient. J'ai essayé de changer index++ par index+1 mais le résultat est le même.

Je vous met ci-dessous mon exécution gdb pour que vous puissiez me donnez vos points de vues :

Thread 3 hit Breakpoint 1, afficher_dico (racine=0x101a4cde0)
    at arbre_lexicographique.c:98
98    if (racine){
(gdb) b afficher_mots
Breakpoint 2 at 0x100001ab3: file arbre_lexicographique.c, line 82.
(gdb) continue
Continuing.

Thread 3 hit Breakpoint 2, afficher_mots (n=0x101a4cde0, 
    mot_en_cours=0x101a64860 "", index=0) at arbre_lexicographique.c:82
82    if(n == NULL){
(gdb) continue
Continuing.
a

Thread 3 hit Breakpoint 2, afficher_mots (n=0x101a04de0, 
    mot_en_cours=0x101a64860 "a", index=0) at arbre_lexicographique.c:82
82    if(n == NULL){
(gdb) continue
Continuing.

Thread 3 hit Breakpoint 2, afficher_mots (n=0x101a39540, 
    mot_en_cours=0x101a64860 "b", index=1) at arbre_lexicographique.c:82
82    if(n == NULL){
(gdb) p n
$1 = (PNoeud) 0x101a39540
(gdb) p n->lettre
$2 = 97 'a'
(gdb) n
85    if(n->fin_de_mot != fin){
(gdb) n
86      mot_en_cours[index] = n->lettre;
(gdb) p mot_en_cours
$3 = 0x101a64860 "b"
(gdb) n
87      afficher_mots(n->fils, mot_en_cours, index+1);
(gdb) p n->fils->lettre
$4 = 98 'b'
(gdb) p ->fils->lettre
A syntax error in expression, near `->fils->lettre'.
(gdb) p n->fils->fils->lettre
$5 = 97 'a'
(gdb) n

Thread 3 hit Breakpoint 2, afficher_mots (n=0x101a4ca00, 
    mot_en_cours=0x101a64860 "ba", index=2) at arbre_lexicographique.c:82
82    if(n == NULL){
(gdb) p mot_en_cours
$6 = 0x101a64860 "ba"
(gdb) continue
Continuing.

Thread 3 hit Breakpoint 2, afficher_mots (n=0x101a4cda0, 
    mot_en_cours=0x101a64860 "bab", index=3) at arbre_lexicographique.c:82
82    if(n == NULL){
(gdb) continue
Continuing.
baba

Thread 3 hit Breakpoint 2, afficher_mots (n=0x101a4cb80, 
    mot_en_cours=0x101a64860 "baba", index=0) at arbre_lexicographique.c:82
82    if(n == NULL){
(gdb) continue
Continuing.

Thread 3 hit Breakpoint 2, afficher_mots (n=0x101a4cc80, 
    mot_en_cours=0x101a64860 "iaba", index=1) at arbre_lexicographique.c:82
82    if(n == NULL){
(gdb) continue
Continuing.
il

Thread 3 hit Breakpoint 2, afficher_mots (n=0x101a4cc20, 
    mot_en_cours=0x101a64860 "il", index=0) at arbre_lexicographique.c:82
82    if(n == NULL){
(gdb) continue
Continuing.

Thread 3 hit Breakpoint 2, afficher_mots (n=0x101a4cc40, 
    mot_en_cours=0x101a64860 "nl", index=1) at arbre_lexicographique.c:82
82    if(n == NULL){
(gdb) continue
Continuing.

Comme ça en passant, si dans ton dico tu as le mot SOL, le nœud qui contient le L est marqué comme fin de mot, mais alors comment fais-tu pour trouver le mot SOLE ? ou SOLS ?

Tu fais tes tests sur un mini dico ?

As-tu la possibilité d'installer nemiver ou DDD ?

White Crow a écrit:

Comme ça en passant, si dans ton dico tu as le mot SOL, le nœud qui contient le L est marqué comme fin de mot, mais alors comment fais-tu pour trouver le mot SOLE ? ou SOLS ?

Tu fais tes tests sur un mini dico ?

As-tu la possibilité d'installer nemiver ou DDD ?

Oui je fais mes tests sur un dico,

En effet c'était ça l'erreur, je l'ai réglé et gdb m'a pas mal aidé. Encore merci ça fonctionne !