Arbres Lexicographiques

Version imprimable

14/05/2006, 15h30
Legio

Arbres Lexicographiques
Voila je travaille sur les arbres lexicographiques et j'ai un probleme de fonction.
Mon arbre représente un dictionnaire les element sont des char .
La structure de mon arbre est la suivant :
Code:

1 2 3 4 5 6 typedef struct noeud { ELEMENT etiq; struct noeud * ag, * ad ; } NOEUD; /* un arbre binaire est un pointeur sur son Noeud racine */ typedef NOEUD* DICO ;
La fonction qui me pose probleme est une fonction de recherche qui recherche un mot dans mon dictionnaire(arbre) et qui me renvoie 1 si celui ci y est et 0 sinon .
Sauf que la ma fonction ne trouve aucun mot dans l'arbre meme ceux qui y sont :(
je travaille avec des TDA ELEMENTS et LEXICO mais je ne peux pas tout vous mettre mais si quelqu'un voit d'ou vient mon erreur ca m'aiderai beaucoup . Vous pouvez me poser des questions si il manque quelquechose

Code:

La fin d'un mot est représentée par '*' , et l'absence de mot par '~' .
14/05/2006, 17h04
HanLee

Ca ressemble à l'épreuve d'Informatique qui est tombée à Polytechnique ce vendredi lol...

Moi j'voudrais savoir comment il fonctionne ton dictionnaire ?

ELEMENT c'est quoi ?

ELEMENT est un char
je rentre mes mots de cette facon

Code:

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
DICO DicoLire(DICO A) {
	char c;
	char buffer[50];
	int i=0,cpt=0;
	FILE *fichier;
 
	if ((fichier = fopen("dico.txt", "r"))!= NULL)
	{
	while((c = fgetc(fichier)) != EOF)
	{
		if( (c == ' ' || c == '\n') && ( i > 0 ) )
		{
			buffer[i] = '*';
			i++;
			buffer[i] = '\0';
		A=DicoInserer(buffer,A);
		cpt++;
		}
		else if( c != '\n' && c != ' ' )
		{
			buffer[i] = c;
			i++;
		}
	}
		buffer[i] = '*';
		i++;
		buffer[i] = '\0';
		A= DicoInserer(buffer,A);
		cpt++;
       }
	fclose(fichier);
	printf("\nIl y a actuellement %d mots dans le dictionnaire\n",cpt);
}

Ma fonction de recherche me fait planter mon programme en fait :?

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int DicoRechercher (char *x, DICO a) { 
/* retourne 1 si le mot x dans le dictionnaire et 0 sinon */ 
int i=0;
   	if( ElementIdentique(x[i], '\0') )
   		return 1;
   	else
   	{   		
			if( ElementIdentique(a->etiq, x[i]) ){
			i++;
				return DicoRechercher(x, ArbinGauche(a));}
			else if( a->etiq < x[i] )
				return DicoRechercher(x, ArbinDroit(a));
			else
				return 0;
   	}
}

14/05/2006, 17h33
HanLee

Dangereux le fait que tu contrôles pas le dépassement de tampon.

Sinon ça me dit pas comment ton arbre représente un dictionnaire.

Un truc en français, pas en C pour le moment.

Ya juste insérer le mot dans le dictionnaire, et moi si j'sais pas comment il marche ton dictionnaire, je peux pas chercher dedans 8-).

EDIT : hey t'as édité !

EDIT 2 : ElementIdentique(c,b) il dit oui si c == b ?
14/05/2006, 17h40
Legio

Je ne sais pas trop comment t'expliquer ca

Un mot est un chemin allant de la racine ( ou d'un fils droit ) a une feuille .
Deux noeuds de l'arbre reliés par
- une relation gauche correspondant a des lettres consécutives d 'un mot
- une relation droite correspondant a des lettres alternatives pour former deux mots distincts .

le '*' sert de marqueur de fin de mot
le '~' sert de marqueur de fin de parcours a droite dans l'arbre .

Aie je sais pas si j'ai été clair :roll:

[EDIT] oui pour elementIdentique

Et oui j'ai editer car j'ai changer un peu ma fonction de recherche je l'ai mis en dessous ;)

Je tente un dessin :mrgreen:
a
|
m-r--~
| |
o t--~
| |
u *
| |
r ~
|
*
|
~

Avec a chaque fois vers la droite si il n'y as pas d'alternatives un ~
14/05/2006, 17h54
HanLee

Oui d'accord c'est bien ce que je me disais =), c'est le même arbre qu'on a eu à étudier.

Mets plutôt un pointeur vers NULL au lieu d'un noeud qui contient '~'.

Bon laisse moi réfléchir à tes fonctions, j'vais regarder ça de plus près.

Le '*' et le '~' sont imposé en fait :roll:

Mon programme plante quand j'essaye de rechercher un mot dans l'arbre ou que j'essaye d'afficher mon arbre :(

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void DicoAfficher (DICO a) {
 char *chaine_vide=(char*)malloc(100*sizeof(char));;
    strcpy(chaine_vide, "\0");
    AfficherPrive(a, chaine_vide);  
    free(chaine_vide); 
}
 
void AfficherPrive(DICO a,char* m){
	if( ElementIdentique(a->etiq, '*') ) {
		printf("%s\n", m); 
		AfficherPrive(ArbinDroit(a), m);
	}
	else if( !ElementIdentique(a->etiq, '~') ) {
		AfficherPrive(ArbinGauche(a), strcat(m, &a->etiq));
		*(m+(strlen(m) - 1)) = '\0';
		AfficherPrive(ArbinDroit(a), m);
	}
}

Et la fonction rechercher qui est au dessus :?

C'est normal que ça plante, tu ne vérifies pas si ton arbre est vide ou pas (c'est à dire si le pointeur a est nul).

Il faudrait que tu bosses sur la définition inductive de l'arbre plus soigneusement avant de coder ta fonction ;).

Ta récursivité ne prévoit pas tous les cas.

Tiens, j'ai une solution qui devrait marcher pour DicoRechercher :

Code:

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
34
35
36
37
38
39
40
41
 
int DicoRechercher(char * mot, DICO dico)
{
    // Le dictionnaire est vide ou bien on a vu l'étiquette '~'
    if (dico == NULL || dico->etiq == '~')
    {
        return 0;
    }
    // Si le pointeur est != NULL (ce qui devrait toujours être le cas)
    else if (mot != NULL)
    {
        // On a atteint la fin du mot
        if (mot[0] == '\0')
        {
            return (dico->etiq == '*') || DicoRechercher(mot, dico->ad);
        }
        // Le mot n'a pas encore été entièrement lu
        else
        {
            // La première lettre coincide avec le noeud en cours.
            // Il reste à vérifier si le reste du mot existe dans le dico
            // donc à gauche
            if (mot[0] == dico->etiq)
            {
                return DicoRechercher(mot + 1, dico->ag);
            }
            // La première lettre ne coincide pas
            // L'algorithme se ramène au traitement du même mot 
            // et au sous-dictionnaire droit.
            else
            {
                return DicoRechercher(mot, dico->ad);
            }
        }
    }
    // C'est juste pour dire que ya un bug...
    else
    {
        return -1;
    }
}

Inspire toi de ça pour les autres.

14/05/2006, 19h27
Legio

Merci pour la fonction c'est vrai je ne fait pas assez de test (vide ou pas ...)
Mais mon programme plante encore avec cette version de DicoRechercher :?
Je ne comprend meme pas ou est le probleme ...
14/05/2006, 19h39
HanLee

Déjà essaie de t'assurer que t'arrive à construire un arbre conformément à l'algorithme indiqué.

Ensuite, ta fonction DicoLire, elle a l'air d'être du vent : tu lui passes un DICO en copie, et ta fonction modifie cette copie =P.

Je sais pas ce que tu fabriques dans DicoInsérer, mais bon, je me doute bien qu'il y a des problèmes =). Si ton DICO est vide au début, il sera toujours vide avec ton algorithme. Il faudrait passer un pointeur vers DICO.

Ah lala... T'es obligé de le faire en C ?

Parce qu'algorithmiquement il y a des erreurs, et s'il faut ajouter des difficultés liées au C, il est fou ton prof si c'est un devoir.

Montre moi DicoInsérer.

C'est mon projet en C oui , et encore ce n'est pas grand chose dans le projet il fallait que je fasse un correcteur orthographique de trois facon differents ( Lexico, arbre binaire de recherche et table de hachage ) (en deux mois ...)
Code:

1 2 3 4 5 6 DICO DicoInserer (char *x, DICO a) { DICO D = DicoCreer(); D = DicoLocaliser(&x, a); EntrerNouvelleRacine(x, D); return a; }
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 DICO EntrerNouvelleRacine(char *m, DICO a){ if(*m != '\0') { DICO b = DicoCreer(); b->ag= ArbinGauche(a); b->ad = ArbinDroit(a); ArbinModifierEtiquette(ArbinEtiquette(a), b); a->ad = b; ArbinModifierEtiquette(*m, a); a->ag = DicoCreer(); EntrerNouvelleRacine(++m, a->ag); } return a; }
J'ai trouvé l'origine du plantage, mon programme marche mais la fonction rechercher me renvoie toujours 0 apparement . Peut-etre effectivement qu'il y a un probleme au niveau de la création de mon dico a partir du fichier

14/05/2006, 20h25
Legio
Je lis un fichier texte ou se trouve les mots : salut bonsoir montre
Apres un :
Code:

1 2 3 dico=DicoCreer(); dico=DicoLire(dico); DicoAfficher(dico);
ca m'ecrit les mots comme cela :

http://flyingcolourz.free.fr/forum/test.JPG

Ah bah oui c'est moi qui t'ai répondu l'autre jour sur le correcteur orthographique.

Ptin, t'as beaucoup de fonctions...

Alors j'ai tout recodé moi même, j'ai converti mon code Caml en C...

J'ai finalement réussi. Ca m'a pris un peu beaucoup plus de temps, à cause des free, malloc et tout ça...

Ta fonction pour ajouter, elle est bizarre.

Moi j'ai mis un Dico vide c'est le pointeur NULL

Tiens j't'ai mis le code de ma fonction en enlevant les tests d'erreurs, pour pas que ça t'embrouille l'esprit :

Code:

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 
// La fonction prend en argument un mot, le dictionnaire
// et retourne le dictionnaire avec le mot rajouté
// Insérer dans le dictionnaire
DICO DicoAjoute(const char * mot, DICO dico)
{
    if (mot != NULL)
    {
        if (mot[0] == '\0' && dico == NULL)
        {
            NOEUD* fin       = (NOEUD*) malloc( sizeof(NOEUD) );
            NOEUD* nouv_dico = (NOEUD*) malloc( sizeof(NOEUD) );
 
            fin->lettre = '~';
            fin->ag        = NULL;
            fin->ad        = NULL;
 
            nouv_dico->lettre = '*';
            nouv_dico->ag      = NULL;
            nouv_dico->ad      = fin;
 
            return nouv_dico;
        }
        else if (mot[0] != '\0' && dico == NULL)
        {
            NOEUD* nouv_dico = (NOEUD*) malloc( sizeof(NOEUD) );
 
            nouv_dico->lettre = mot[0];
            nouv_dico->ag      = DicoAjoute(mot + 1, NULL);
            nouv_dico->ad      = NULL;
 
            return nouv_dico;
        }
        else if (mot[0] == '\0' && dico != NULL)
        {
            if ( dico->lettre == '*' )
                return dico;
            else
            {
                dico->ad = DicoAjoute(mot, dico->ad);
                return dico;
            }
        }
        else
        {
            if ( mot[0] == dico->lettre )
                dico->ag = DicoAjoute(mot + 1, dico->ag);
            else
                dico->ad = DicoAjoute(mot, dico->ad);
 
            return dico;
        }
    }
    else
    {
        return dico;
    }
}

Tu comprends l'algorithme ou non ?

Alors notre arbre binaire se définit comme ça formellement : Vide (= NULL) est un arbre binaire, et si ag, ad sont des arbres binaires, alors pour tout char etiq, le triplet (etiq, ag, ad) est aussi un arbre binaire.

Ce qu'il faut que t'arrives à faire, c'est de coder un algorithme juste, simplement en regardant la structure de l'arbre.

Attention, ne confonds pas le dictionnaire vide avec un dictionnaire qui contient le mot vide (c'est à dire que le dictionnaire est égal à ('*', Vide, Vide) ).

J'vais décomposer l'algorithme que je t'ai passé, on l'appelle DicoAjoute qui prend en argument une chaîne de caractère mot, dictionnaire dico :

Code:

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
34
35
36
37
38
39
40
41
 DicoAjoute(mot, dico) =
  Si mot est vide et que dico = Vide Alors

    On renvoie ('*', Vide, (Vide, '~', Vide))

  SinonSi mot est vide et que dico != Vide Alors

    Si dico->etiq = '*' Alors

      On renvoie dico car il n'y a rien à rajouter

    Sinon

      On renvoie (dico->etiq, dico->ag, DicoAjoute(mot, dico->ad)) car
      cela revient à rajouter le mot vide dans le fils droit de dico

    FinSi

  SinonSi mot n'est pas vide et dico = Vide Alors

    On renvoie (mot[0], DicoAjoute(la fin du mot, Vide), Vide) car
    on rajoute la fin de mot dans un arbre Vide, qu'on accroche à la branche gauche de notre noeud nouvellement créé

  Sinon (* Dans ce cas, le mot n'est pas vide et le dictionnaire non plus *)

    Si dico->etiq = mot[0] Alors

      On renvoie (dico->etiq, DicoAjoute(fin de mot, dico->ag), dico->ad)
      car cela revient à rajouter la fin de mot dans le fils gauche du dico

    Sinon

      On renvoie (dico->etiq, DicoAjoute(mot, dico->ad)) car cela revient
      à rajouter mot dans le fils droit de dico

    FinSi

  FinSi

 FinSi

C'est toujours le même principe avec les définitions inductives comme ça.

Merci enormement , je regarde ca de plus pres pour tout comprendre et de le tester
Je crois que j'ai compris oui :roll:
Mais alors maintenant plus rien ne rentre dans mon dico , c'est parceque ma fonction DicoLire renvoie un char buffer[50] a DicoAjoute et il faudrai que je passe un pointeur ou c'est autre chose?
Code:

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 34 35 36 DICO DicoLire(DICO A) { char c; char buffer[50]; int i=0,cpt=0; FILE *fichier; if ((fichier = fopen("dico.txt", "r"))!= NULL) { while((c = fgetc(fichier)) != EOF) { if( (c == ' ' || c == '\n') && ( i > 0 ) ) { buffer[i] = '*'; i++; buffer[i] = '\0'; A=DicoInserer(buffer,A); cpt++; i=0; buffer[i] = '\0'; } else if( c != '\n' && c != ' ' ) { buffer[i] = c; i++; } } buffer[i] = '*'; i++; buffer[i] = '\0'; A= DicoInserer(buffer,A); cpt++; } fclose(fichier); printf("\nIl y a actuellement %d mots dans le dictionnaire\n",cpt); return A; }
Sachant que DicoInserer et ta fonction DicoAjoute sont les memes

Tu as des erreurs dans DicoLire en effet.
D'abord j'ai mis une constante dans un define.

1. Ca ne sert à rien de rajouter '*' à ton buffer, parce que c'est la fonction DicoInsere qui le rajoute automatiquement.

2. Tu oublies de vérifier que i ne dépasse pas la fin du tableau : j'ai rajouté une sentinelle, et on ajoute le '\0' final uniquement.

3. Pareil pour le second if, j'ai rajouté une sentinelle.

4. Juste après le while, tu as une erreur. Tu rajoutes encore '*', et tu ne testes pas la valeur de i. Si i est nul après le while, c'est qu'on a rajouté un mot au dictionnaire, et qu'il n'y avait rien d'autre après.
Si i est non nul, il est également < SIZE, donc, il y a un mot à rajouter à notre dictionnaire, si et seulement si i différent de 0.

Sinon le reste est bon, j'ai rajouté des ptits trucs.

Bon après, tu fais gaffe à pas mettre de tabulations dans ton fichier. =P
Code:

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 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 #define SIZE 50 DICO DicoLire(DICO dico) { char c; char buffer[SIZE]; int i = 0; int cpt = 0; FILE *fichier = NULL; if ( (fichier = fopen("dico.txt", "r"))!= NULL) { while ((c = fgetc(fichier)) != EOF) { if ( (c == ' ' || c == '\n') && (0 < i) && (i < SIZE) ) { buffer[i] = '\0'; i++; dico = DicoInsere(buffer, dico); cpt++; i = 0; buffer[0] = '\0'; } else if (c != '\n' && c != ' ' && (i < SIZE - 1)) { buffer[i] = c; i++; } } if (i > 0) { buffer[i] = '\0'; dico = DicoInsere(buffer, dico); cpt++; } fclose(fichier); printf("Il y a actuellement %d mots dans le dictionnaire.\n", cpt); } else printf("Pas reussi à ouvrir le fichier !\n"); return dico; }

15/05/2006, 02h28
Legio

Merci beaucoup HanLee mes programmes marchent , ils ont beaucoup de mal mais bon ca marche . Je rend demain mon projet apparement ils n'attendaient pas des trucs geniaux de notre part.
Sur ce bonne nuit :mrgreen: