Un programme qui retrouve des mots à partir de lettres qu'on lui donne.
Ca fait longtemps que je ne l'ais pas regardé mais il y a plein de choses à améliorer (beaucoup de mémoire utilisée, construction de l'arbre à chaque chargement).
Source / Exemple :
#include <stdio.h>
#include <stdlib.h>
#define BUFFER 10000 //Constantes...
struct noeud_arbre //Structure du noeud de l'arbre du dico
{
char carac;
struct noeud_arbre *fils_gauche;
struct noeud_arbre *fils_droit;
};
typedef struct noeud_arbre NOEUD;
NOEUD* creernoeud(char carac) //Creer un noeud et le retourner
{
NOEUD *temp;
if(!(temp = malloc(sizeof(NOEUD))))
{
puts("erreur allocation memoire");
exit(1);
}
temp->carac = carac;
temp->fils_gauche = NULL;
temp->fils_droit = NULL;
return temp;
}
void ajoutermotdansarbre(NOEUD *arbre, char *mot)
{
if(arbre->carac == '\0')
{
if(arbre->fils_droit == NULL)
arbre->fils_droit = creernoeud(mot[0]);
ajoutermotdansarbre(arbre->fils_droit, mot);
return;
}
if(mot[0] == arbre->carac)
{
if(arbre->fils_gauche == NULL)
arbre->fils_gauche = creernoeud(mot[1]);
if(mot[1] != '\0')
ajoutermotdansarbre(arbre->fils_gauche, mot+1);
else
return;
}
else
{
if(arbre->fils_droit == NULL)
arbre->fils_droit = creernoeud(mot[0]);
ajoutermotdansarbre(arbre->fils_droit, mot);
}
}
void ajoutermot(NOEUD **arbre, char *mot)
{
if(*arbre == NULL)
- arbre = creernoeud(mot[0]);
ajoutermotdansarbre(*arbre, mot);
}
void freetree(NOEUD *arbre)// Fonction qui libère la mémoire occupée par l'arbre
{
if(arbre->fils_gauche != NULL) // On descend dans l'arbre
freetree(arbre->fils_gauche); // à gauche
if(arbre->fils_droit != NULL) // puis à droite
freetree(arbre->fils_droit); // et on libère en remontant
free(arbre);
}
int loaddico(char *path, char *dico[], int to_load, int *position)
{
FILE *fp;
char c, buffer[256];
int i=0, count=0;
if((fp = fopen(path, "r")) == NULL)
{
puts("fichier dictionnaire introuvable");
exit(1);
}
fseek(fp, *position, SEEK_SET);
do
{
while(((c=fgetc(fp)) != EOF) && (c != '\n'))
buffer[i++]=c;
buffer[i] = '\0'; //remplacement du '\n' par '\0'
i=0;
dico[count] = malloc((sizeof(char)* strlen(buffer)) + 1);
strcpy(dico[count], buffer);
count++;
}while(count < to_load && c != EOF);
return count;
}
void freebufferdico(char *dico[], int count)
{
int i;
for(i=0 ; i < count ; i++)
free(dico[i]);
}
int diffcharsinsz(char *chaine)//Fonction qui renvoit le nombre de caractères différents dans une chaine
{
int i, j, nb_egal=0;
for(i=0 ; i<strlen(chaine) ; i++)
{
for(j=i+1 ; j<strlen(chaine); j++)
{
if(chaine[i] == chaine[j])
{
nb_egal++;
break;
}
}
}
return i - nb_egal;
}
void tabledispochaine(int *p_tab_dispo[], char **p_chaine) //Fonction qui ne laisse que les
{ //caractères différents dans la chaine
int i, j, count=0; //et initialise la table de disponibilité correspondante
char *mot_tmp, *chaine;
int *tab_dispo = *p_tab_dispo;
chaine = *p_chaine;
if(tab_dispo == NULL)
{
tab_dispo = malloc(diffcharsinsz(chaine) * sizeof(int));
for(i=0 ; i<diffcharsinsz(chaine) ; i++)
tab_dispo[i] = 0;
mot_tmp = malloc(diffcharsinsz(chaine) * sizeof(char));
for(i=0 ; i< strlen(chaine); i++)
{
for(j=0 ; j<count ; j++)
{
if(chaine[i] == mot_tmp[j])
{
tab_dispo[j]++;
break;
}
}
if(j==count)
{
count++;
tab_dispo[j]++;
mot_tmp[j] = chaine[i];
}
}
strcpy(chaine, mot_tmp);
free(mot_tmp);
chaine[count] = '\0';
}
}
void testermot(NOEUD *arbre, char *mot)
{
int i;
static NOEUD *premier_noeud;
static char *word, *pt_word;
static int *tab_dispo, results, appel;
if(arbre != NULL)
{
appel++;
if(appel == 1)
premier_noeud = arbre;
if(word == NULL)
{
word = malloc((strlen(mot)+1) * sizeof(char));
pt_word = word;
}
if(tab_dispo == NULL);
tabledispochaine(&tab_dispo, &mot);
if(arbre->carac == 0)
{
results++;
printf("%s ", word);
if(arbre->fils_droit != NULL)
testermot(arbre->fils_droit, mot);
return;
}
for(i=0 ; i<strlen(mot) ; i++)
{
if(arbre->carac == mot[i])
{
if(tab_dispo[i] > 0)
{
if(arbre->fils_gauche != NULL)
{
tab_dispo[i]--;
- (pt_word++) = arbre->carac;
testermot(arbre->fils_gauche, mot);
pt_word--;
tab_dispo[i]++;
}
}
break;
}
}
if(arbre->fils_droit != NULL)
testermot(arbre->fils_droit, mot);
if(premier_noeud == arbre) //Traitement fini
{
free(word);
word = NULL;
free(tab_dispo);
tab_dispo = NULL;
appel = 0;
pt_word = 0;
results = 0;
}
}
}
int comparersousarbres(NOEUD *arbre1, NOEUD *arbre2)//Fonction comparant et sous arbres,
{ //renvoit 1 en cas dégalité, 0 en cas d'inégalité
if(arbre1 == arbre2)
return 1;
if(arbre1->carac == arbre2->carac)
{
if(arbre1->fils_gauche == NULL && arbre2->fils_gauche == NULL) //Les deux fils gauche n'existent pas
return 1;
if((arbre1->fils_gauche != NULL && arbre2->fils_gauche != NULL))//Les deux fils gauche existent
{
if(comparersousarbres(arbre1->fils_gauche, arbre2->fils_gauche) != 1)
return 0;
}
if(arbre1->fils_droit == NULL && arbre2->fils_droit == NULL) //Les deux fils droit n'existent pas
return 1;
if(arbre1->fils_droit != NULL && arbre2->fils_droit != NULL)
{
if(comparersousarbres(arbre1->fils_droit, arbre2->fils_droit) != 1)
return 0;
}
}
else return 0;
}
void generer(int n, NOEUD *arbre) //Fonction generant toutes les combinaisons de lettres
{ //et appel de la fonction de test de mot avec l'arbre
int i, j; //passé en argument
static char *chaine;
static int n_base;
if(chaine==NULL)
{
n_base = n;
chaine = malloc(n*sizeof(char));
for(i=0;i<n;i++)
chaine[i] = 64;
chaine[i] = '\0';
}
for(j=(n_base-n);j<n_base;j++)
{
for(i=0;i<26;i++)
{
chaine[j]++;
if(n==1)
testermot(arbre, chaine);
generer(n-1, arbre);
}
chaine[j] = 64;
}
}
void main(int argc, char **argv)
{
NOEUD *arbre = NULL;
char *dico[BUFFER], buffer[35];
int nbr_mots, i, position_fichier = 0;
do
{
nbr_mots = loaddico("essai.txt", dico, BUFFER, &position_fichier);
for(i=0 ; i < nbr_mots ; i++)
ajoutermot(&arbre, dico[i]);
freebufferdico(dico, nbr_mots);
}while(nbr_mots == BUFFER);
do
{
printf("\nEntrer les lettres\n");
gets(buffer);
strupr(buffer);
testermot(arbre, buffer);
}
while(buffer[0] != 0);
freetree(arbre);
}
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.