Recherche d'annagrammes

Soyez le premier à donner votre avis sur cette source.

Vue 7 409 fois - Téléchargée 487 fois

Description

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);
  • position = ftell(fp);
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';
  • p_tab_dispo = tab_dispo;
} } 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++;
  • pt_word = '\0';
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); }

Codes Sources

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.