TP6: Fix to the n ary tree.

[Algorithmic_C.git] / TP6 / arbres / arbre_n_aire / arbre_n_aire.c

/*****************************************************************************/
/*                          arbre_n_aire.c                                   */
/*     Representation d'un ensemble de mots sous forme d'arbre n-aire        */
/*****************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

/* nombre de caracteres max dans un mot */
#define N 30

typedef struct noeud {
    char lettre;
    struct noeud *fils;
    struct noeud *frere;
} NOEUD;

/* Recherche d'un mot dans l'arbre *****************************************/
bool recherche(NOEUD * p, char *mot, int i)
{
    if (p == NULL)
	return false;
    if (mot[i] == p->lettre) {
	if (mot[i] == '\0') {
	    return true;
	} else {
	    return recherche(p->fils, mot, i + 1);
	}
    } else {
	if (p->lettre > mot[i]) {
	    return false;
	} else {
	    return recherche(p->frere, mot, i);
	}
    }
}

/* Creation d'une fin de mot (liste chainee suivant le lien fils) **********/
NOEUD *insere_fin(char *mot, int i)
{
    /* i est l'indice de la lettre courante dans le mot */
    printf("insere_fin %c, %i\n", mot[i], i);
    NOEUD *p = (NOEUD *) malloc(sizeof(NOEUD));
    if (p == NULL)
	exit(-1);
    p->lettre = mot[i];
    p->fils = NULL;
    p->frere = NULL;
    if (mot[i])
	p->fils = insere_fin(mot, i + 1);
    return p;
}

/* Insertion d'un mot dans l'arbre ******************************************/
/* (on respecte l'ordre lexicographique des freres)**************************/
NOEUD *insere(NOEUD * p, char *mot, int i)
{
    /* i est l'indice de la lettre courante dans le mot */
    if (p == NULL) {
	return insere_fin(mot, i);
    } else if (p->lettre == mot[i]) {
	if (mot[i] != '\0') {
	    p->fils = insere(p->fils, mot, i + 1);
	} else {
	    printf("The word is already here\n");
	}
    } else if (p->lettre > mot[i]) {
	NOEUD *p1 = insere_fin(mot, i);
	p1->frere = p;
	p = p1;
    } else {
	p->frere = insere(p->frere, mot, i);
    }
    return p;
}

/*****************************************************************************/
/* Affichage par ordre alphabetique de tous les mots stockes dans l'arbre    */
void affiche(NOEUD * p, char *mot, int i)
{
    /* i est l'indice de la lettre courante dans le mot */
    if (p != NULL) {
	mot[i] = p->lettre;
	affiche(p->fils, mot, i + 1);
	if (mot[i] == '\0') {
	    printf("%s\n", mot);
	}
	affiche(p->frere, mot, i);
    }
}

/* Visualisation de l'arbre n-aire *******************************************/
void affiche_arbre(NOEUD * p, int prof)
/* prof est utilise pour decaller l'affichage avec des espaces (selon le niveau dans l'arbre) */
{
    int i;

    if (p) {
	affiche_arbre(p->frere, prof);
	for (i = 0; i < prof; i++)
	    printf(" ");
	printf("%c\n", p->lettre);
	affiche_arbre(p->fils, prof + 1);
    }
}

/* Suppression d'un mot de l'arbre ********************************************/
/* Attention a ne supprimer que la fin du mot qui n'est partagee par aucun autre mot de l'arbre */
NOEUD *supprime(NOEUD * p, char *mot, int i)
/* i est l'indice de la lettre courante dans le mot */
{
    if (p) {
	if (p->lettre < mot[i]) {
	    p->frere = supprime(p->frere, mot, i);
	} else if (p->lettre == mot[i]) {
	    p->fils = supprime(p->fils, mot, i + 1);
	    if (!p->fils) {
		NOEUD *p1 = p;
		p = p->frere;
		free(p1);
	    }
	    return p;
	}
    }
}

/* Destruction des arbres de racine p en recuperant la place occupee (free) par chacun des noeuds  */
NOEUD *detruis_arbre(NOEUD * p)
{
    if (p == NULL)
	return p;
    else {
	p->fils = detruis_arbre(p->fils);
	p->frere = detruis_arbre(p->frere);
	free(p);
	p = NULL;
	return p;
    }
}

/* Chargement des mots d'un fichier (vu comme un dictionnaire) dans l'arbre **/
NOEUD *charge_dico(char *nom_fichier, int *nb_mots)
{
    NOEUD *p;
    FILE *fp;
    char mot[N];
    int i;
    p = NULL;

    fp = fopen(nom_fichier, "rt");
    if (fp == NULL)
	exit(-1);
    fscanf(fp, "%d", nb_mots);	/* sur la 1ere ligne du fichier, le nombre de mots */
    for (i = 0; i < *nb_mots; i++) {
	fscanf(fp, "%s", mot);
	p = insere(p, mot, 0);
    }
    fclose(fp);
    return p;
}

/* Ecriture dans fp de tous les mots stockes dans l'arbre ********************/
void affiche_fich(FILE * fp, NOEUD * p, char *mot, int i)
{
    /* i est l'indice de la lettre courante dans le mot */
    if (p != NULL) {
	mot[i] = p->lettre;
	affiche_fich(fp, p->fils, mot, i + 1);
	if (mot[i] == '\0') {
	    fprintf(fp, "%s\n", mot);
	}
	affiche_fich(fp, p->frere, mot, i);
    }
}

/* Sauvegarde des mots de l'arbre dans un fichier ****************************/
void sauve_dico(NOEUD * p, char *nom_fichier, int nb_mots)
{
    FILE *fp;
    char mot[N];

    fp = fopen(nom_fichier, "wt");
    if (fp == NULL)
	exit(-1);
    fprintf(fp, "%d\n", nb_mots);
    affiche_fich(fp, p, mot, 0);
    fclose(fp);
}

/*****************************************************************************/
int main(int argc, char *argv[])
{
    char mot[N];
    int nb_mots = 0;
    NOEUD *arbre = NULL;

    //printf ("saisir un mot : ");
    //gets (mot);
    //printf ("\ninsertion de %s\n", mot);
    //arbre = insere (arbre, mot, 0);
    arbre = charge_dico("dictionnaire", &nb_mots);
    printf("\naffichage mots :\n");
    affiche(arbre, mot, 0);
    printf("\naffichage arbre :\n");
    affiche_arbre(arbre, 0);
    if (recherche(arbre, "salut", 0))
	printf("mot \"salut\" present\n");
    sauve_dico(arbre, "dictionnaire_debug", nb_mots);
    supprime(arbre, "zazou", 0);
    affiche_arbre(arbre, 0);
    detruis_arbre(arbre);
    if (!arbre)
	affiche_arbre(arbre, 0);
    /* TODO */
}

/* Exemple de trace d'execution *************************

saisir un mot : salut

insertion de salut
insere_fin s, 0
insere_fin a, 1
insere_fin l, 2
insere_fin u, 3
insere_fin t, 4
insere_fin , 5

affichage arbre :
s
 a
  l
   u
    t
     
... TODO ...

**********************************************************/