+++ /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 {
- return insere_fin(mot, i);
- }
-}
-
-/*****************************************************************************/
-/* 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)
-{
- /* 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];
- 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");
- detruis_arbre(arbre);
- /* 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