TP6: Add search function to arbre_n_aire.c

[Algorithmic_C.git] / TP6 / arbres / arbre-n-aire / arbre_n_aire_a_completer.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 */
  /* TODO */
  if (p == NULL)
    p = insere_fin (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 */
  /* TODO */
}

/* 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;
}

/* 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);	/* TODO il faut finir "insere" pour que "charge_dico" fonctionne */
    }
  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)
{
  /* TODO */
  /* ressemble beaucoup a "affiche", avec le parametre en plus "fp" qui est un FILE* */
}

/* 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);	/* TODO il faut finir la fonction "affiche_fich" pour que "sauve_dico" fonctionne */
  fclose (fp);
}

/*****************************************************************************/
int
main (int argc, char *argv[])
{

  char mot[N];
  NOEUD *arbre = NULL;
  printf ("saisir un mot : ");
  gets (mot);
  printf ("\ninsertion de %s\n", mot);
  arbre = insere (arbre, mot, 0);
  printf ("\naffichage arbre :\n");
  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 ...

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