--- /dev/null
+/*****************************************************************************/
+/* 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);
+ }
+ if (mot[i] > p->lettre) {
+ return _insere(p->frere, mot, i);
+ } else if (mot[i] == p->lettre) {
+ return _insere(p->fils, mot, i + 1);
+ } else if (mot[i] < p->lettre) {
+ return _insere(p->fils, mot, i);
+ }
+}
+
+NOEUD *insere(NOEUD * p, char *mot, int i)
+{
+ p = _insere(p, 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 */
+{
+ /* TODO */
+ 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);
+ 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 ...
+
+**********************************************************/
repositories / Algorithmic_C.git / blobdiff