--- /dev/null
+/*****************************************************************************/
+/* arbre_n_aire.c */
+/* Representation de mots sous forme d'arbre n-aire */
+/*****************************************************************************/
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <ctype.h>
+
+#define N 30
+
+
+typedef struct noeud {
+ char lettre;
+ struct noeud *fils;
+ struct noeud *frere;
+} NOEUD;
+
+
+/* Recherche d'un mot dans l'arbre *****************************************/
+NOEUD *cherche(NOEUD * p, char *mot, int i)
+{
+ if (p == NULL)
+ return NULL;
+ if (p->lettre == mot[i]) {
+ if (mot[i])
+ return cherche(p->fils, mot, i + 1);
+ else
+ return p;
+ } else if (p->lettre > mot[i])
+ return NULL;
+ else
+ return cherche(p->frere, mot, i);
+}
+
+/***************************************************************************/
+NOEUD *recherche(NOEUD * p, char *mot)
+{
+ return cherche(p, mot, 0);
+}
+
+
+/* Création d'une fin de mot - liste chaînée suivant le lien fils **********/
+NOEUD *insere_fin(char *mot, int 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 frères **************************/
+NOEUD *insere(NOEUD * p, char *mot, int i)
+{
+ NOEUD *p1;
+
+ if (p == NULL)
+ p = insere_fin(mot, i);
+ else if (p->lettre == mot[i])
+ if (mot[i] != '\0') /* if (mot[i]) */
+ p->fils = insere(p->fils, mot, i + 1);
+ else
+ printf("Le mot est deja dans le dictionnaire\n");
+ else if (p->lettre > mot[i]) {
+ p1 = insere_fin(mot, i);
+ p1->frere = p;
+ p = p1;
+ } else
+ p->frere = insere(p->frere, mot, i);
+ return p;
+}
+
+
+/*****************************************************************************/
+/* Affichage par ordre alphabétique de tous les mots stockés dans l'arbre */
+void affiche_fich(FILE * fp, NOEUD * p, char *mot, int i)
+{
+ int j;
+
+ if (p) {
+ mot[i] = p->lettre;
+ if (!mot[i]) {
+ for (j = 0; j < i; j++)
+ fprintf(fp, "%c", mot[j]);
+ fprintf(fp, "\n");
+ };
+ affiche_fich(fp, p->fils, mot, i + 1);
+ affiche_fich(fp, p->frere, mot, i);
+ }
+}
+
+
+/* Affichage par ordre alphabétique de tous les mots stockés dans l'arbre */
+/* parcours en profondeur d'abord, prefixe (idem si infixe, voir la remarque plus loin) */
+void affiche(NOEUD * p, char *mot, int i)
+{
+ int j;
+
+ if (p) {
+ mot[i] = p->lettre;
+ if (mot[i] == '\0')
+ printf("%s\n", mot); /* ici ou apres l'appel sur le fils ('\0' n'a pas de fils , donc l'appel sur le fils n'affichera rien */
+ affiche(p->fils, mot, i + 1);
+ affiche(p->frere, mot, i);
+ }
+}
+
+
+/*****************************************************************************/
+/* Visualisation de l'arbre n-aire - parcour "frère - racine - fils" */
+void affiche_arbre(NOEUD * p, int prof)
+{
+ 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);
+ }
+}
+
+
+/*****************************************************************************/
+/* Attention à ne supprimer que la fin du mot qui n'est partagée par aucun
+ autre mot de l'arbre */
+NOEUD *supprime(NOEUD * p, char *mot, int i)
+{
+ NOEUD *p1;
+
+ 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) {
+ p1 = p;
+ p = p->frere;
+ free(p1);
+ }
+ } else
+ printf("%s n'est pas present\n", mot);
+ return p;
+}
+
+/*****************************************************************************/
+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 1ère 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;
+}
+
+
+/*****************************************************************************/
+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);
+}
+
+
+/*****************************************************************************/
+char EstSeparateur(char c)
+{
+ return (((c == '\'') || (c == '"') || (c == ',') || (c == ';')
+ || (c == '.') || (c == '\n') || (c == '?') || (c == '!')
+ || (c == ':') || (c == ' ') || (c == '\t') || (c == '-')
+ || (c == '*') || (c == '+') || (c == '=') || (c == '\b')
+ || (c == '{') || (c == '}') || (c == '(') || (c == ')')));
+}
+
+
+/****************************************************************************/
+/* Lit un mot a partir du fichier fd.
+ texte == <separateur>* <mot> <separateur>*
+ mot = <caractere>*.
+ Le mot est retourné sous une forme minuscule.
+ Quant on a atteint la fin de fichier, la fonction retourne 0 */
+int Lectmot(FILE * fp, char *mot)
+{
+ int i = 0;
+ char c;
+
+ /* Lecture des separateurs */
+ while (((c = (char) fgetc(fp)) != (char) EOF) && (EstSeparateur(c)));
+
+ /* Debut du mot */
+ while (c != (char) EOF) {
+ if (!EstSeparateur(c))
+ mot[i++] = tolower(c);
+ else
+ break;
+ c = (char) fgetc(fp);
+ }
+ mot[i] = '\0';
+ return (i);
+}
+
+
+/*****************************************************************************/
+int main(int argc, char *argv[])
+{
+ char mot[N];
+ NOEUD *arbre = NULL;
+
+ /* test insertion */
+ do {
+ printf("\nEntrez un mot a inserer (0 pour arreter) : ");
+ scanf("%s", mot);
+ if (strcmp(mot, "0")) {
+ printf("insertion de %s\n", mot);
+ arbre = insere(arbre, mot, 0);
+ }
+ } while (strcmp(mot, "0"));
+
+ /* test affichage */
+ printf("\naffichage arbre :\n");
+ affiche_arbre(arbre, 0);
+
+ printf("\nmots dans l'arbre :\n");
+ affiche(arbre, mot, 0);
+
+ /* test suppression */
+ do {
+ printf("\nEntrez un mot a supprimer (0 pour arreter) : ");
+ scanf("%s", mot);
+ if (strcmp(mot, "0")) {
+ printf("suppression de %s\n", mot);
+ arbre = supprime(arbre, mot, 0);
+ affiche(arbre, mot, 0);
+ }
+ } while (strcmp(mot, "0"));
+
+ /* affiche_fich(stdout,arbre,mot,0); */
+
+}
+
+/* exemple d'execution ***
+Entrez un mot a inserer (0 pour arreter) : baba
+insertion de baba
+
+Entrez un mot a inserer (0 pour arreter) : baobab
+insertion de baobab
+
+Entrez un mot a inserer (0 pour arreter) : bonjour
+insertion de bonjour
+
+Entrez un mot a inserer (0 pour arreter) : salut
+insertion de salut
+
+Entrez un mot a inserer (0 pour arreter) : salopette
+insertion de salopette
+
+Entrez un mot a inserer (0 pour arreter) : salutation
+insertion de salutation
+
+Entrez un mot a inserer (0 pour arreter) : 0
+
+affichage arbre :
+s
+ a
+ l
+ u
+ t
+ a
+ t
+ i
+ o
+ n
+
+
+ o
+ p
+ e
+ t
+ t
+ e
+
+b
+ o
+ n
+ j
+ o
+ u
+ r
+
+ a
+ o
+ b
+ a
+ b
+
+ b
+ a
+
+
+mots dans l'arbre :
+baba
+baobab
+bonjour
+salopette
+salut
+salutation
+
+Entrez un mot a supprimer (0 pour arreter) : ba
+suppression de ba
+ba n'est pas present
+baba
+baobab
+bonjour
+salopette
+salut
+salutation
+
+Entrez un mot a supprimer (0 pour arreter) : baoba
+suppression de baoba
+baoba n'est pas present
+baba
+baobab
+bonjour
+salopette
+salut
+salutation
+
+Entrez un mot a supprimer (0 pour arreter) : baobab
+suppression de baobab
+baba
+bonjour
+salopette
+salut
+salutation
+Entrez un mot a supprimer (0 pour arreter) : salut
+suppression de salut
+baba
+bonjour
+salopette
+salutation
+
+Entrez un mot a supprimer (0 pour arreter) : 0 */
repositories / Algorithmic_C.git / blobdiff