RECHERCHE D'ANNAGRAMMES

#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);
}