From: Jérôme Benoit <jerome.benoit@piment-noir.org>
Date: Wed, 29 Mar 2017 11:30:15 +0000 (+0200)
Subject: TP6: Add ABR and tree n
X-Git-Url: https://git.piment-noir.org/?p=Algorithmic_C.git;a=commitdiff_plain;h=5f72f302ec8c14ce895f993e2d2ca33df95c94ee

TP6: Add ABR and tree n

Signed-off-by: Jérôme Benoit <jerome.benoit@piment-noir.org>
---

diff --git a/TP6/arbres/ABR/ABR.c b/TP6/arbres/ABR/ABR.c
new file mode 100644
index 0000000..6064c00
--- /dev/null
+++ b/TP6/arbres/ABR/ABR.c
@@ -0,0 +1,317 @@
+/*****************************************************************************/
+/*                      ABR : arbres binaires de recherche                   */
+/*****************************************************************************/
+
+#include <stdio.h>
+#include <stdlib.h>
+
+typedef int element;
+
+typedef struct noeud {
+ element valeur;
+ struct noeud *gauche;
+ struct noeud *droit;
+} NOEUD, *ABR;
+
+
+/* Creation d'un ABR vide */
+NOEUD *arbre_vide() 
+{
+ return NULL;
+}
+
+
+/* Insertion/Ajout d'un nouvel element dans l'ABR */
+NOEUD *insere(NOEUD *p, element x)
+{
+ if(p == NULL) 
+ {
+  p = (NOEUD *)malloc(sizeof(NOEUD));
+  p->valeur = x;
+  p->gauche = NULL;
+  p->droit = NULL;
+ }
+ else if (x == p->valeur) printf("%d est deja dans l'arbre\n",x);
+      else if (x < p->valeur)  p->gauche = insere(p->gauche,x);
+           else p->droit  = insere(p->droit,x);			  
+ return p;			  
+}
+
+
+/* Recherche d'un element dans l'ABR */
+int recherche(NOEUD *p, element x)
+{
+ if(p == NULL) return 0;
+ if(x == p->valeur) return 1;
+ if(x < p->valeur) return recherche(p->gauche,x);
+ else return recherche(p->droit,x);
+}
+
+
+/* Affichage du contenu de l'ABR en ordre croissant (par parcours profondeur infixe) */
+void affiche(NOEUD *p)
+{
+ if(p)
+ {
+  affiche(p->gauche);
+  printf("%d ",p->valeur);
+  affiche(p->droit);
+ }  	
+}
+
+
+/* Affichage de l'arbre (sous forme arborescente) */
+void affiche_arbre(NOEUD *p, int col)
+{
+ int i;
+ if(p)
+ {
+  affiche_arbre(p->droit,col+1);
+  for (i=0;i<col;i++) printf("   ");
+  printf("%d\n",p->valeur);
+  affiche_arbre(p->gauche,col+1);
+ }  	
+}
+
+
+/* Copie d'arbre (on cree physiquement le double de l'arbre de racine p) */
+NOEUD *copie_arbre(NOEUD *p) 
+{
+ NOEUD *q;
+ if(p == NULL) return NULL;
+ else 
+  {
+   q = (NOEUD *)malloc(sizeof(NOEUD));
+   q->valeur = p->valeur;
+   q->gauche = copie_arbre(p->gauche);
+   q->droit  = copie_arbre(p->droit);
+   return q;
+  }
+} 
+
+
+/* Destruction de l'arbre 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->gauche = detruis_arbre(p->gauche);
+   p->droit  = detruis_arbre(p->droit);
+   free(p);
+   p = NULL;
+   return p;
+  }
+}
+
+
+/* Maximum d'un sous-arbre de racine p (i.e., le noeud le plus a droite) */
+NOEUD *max(NOEUD *p, NOEUD *r)
+{
+ NOEUD *q;
+ if (r->droit == NULL) 
+ {
+  p->valeur = r->valeur;
+  q = r; /* q : l'element a supprimer par free */
+  r = r->gauche;
+  free(q);
+ }
+ else r->droit = max(p,r->droit);
+ return r;
+}
+
+
+/* Suppression du noeud de valeur x dans l'arbre de racine p.
+ Suppression d'un noeud interne : la valeur du noeud a supprimer est
+ remplacee par celle du noeud le plus a droite de son sous-arbre gauche */
+NOEUD *supprime(NOEUD *p, element x)
+{
+ NOEUD *q;
+ if(p == NULL) printf("%d  n'est pas dans l'arbre\n",x);
+ else
+   if(x == p->valeur)
+     { /* suppression de p */
+      if (p->droit == NULL) {q = p ; p = p->gauche; free(q); }
+      else if (p->gauche == NULL) {q = p ; p = p->droit; free (q); }
+           else p-> gauche = max(p,p->gauche);
+     }
+   else if (x < p->valeur) p->gauche = supprime(p->gauche,x);
+        else p->droit  = supprime(p->droit,x);
+ return p;
+}
+
+
+/* Chargement d'un arbre depuis un fichier */
+NOEUD *charge(NOEUD *p, FILE *fich)
+{
+ if (p) {p = (NOEUD *)malloc(sizeof(NOEUD));
+         fread(p,sizeof(NOEUD),1,fich);
+	 p->gauche = charge(p->gauche,fich);
+	 p->droit =  charge(p->droit,fich);
+        }
+ return p;
+}
+
+
+/* Sauvegarde d'un arbre dans un fichier */
+NOEUD *sauve(NOEUD *p, FILE *fich)
+{
+ if (p) {fwrite(p,sizeof(NOEUD),1,fich);
+	 p->gauche = sauve(p->gauche,fich);
+	 p->droit =  sauve(p->droit,fich);
+        }
+ return p;
+}
+
+
+
+
+/*****************************************************************************/
+main()
+{
+ NOEUD *abr; /* on peut travailler sur 3 arbres */
+ NOEUD *abr2 = NULL;
+ char c;
+ int i, j;
+ element x;
+ char nom_fich[20];
+ FILE *fich;
+
+printf("Commandes (une lettre) possibles : v arbre_vide ; r rechercher ; i inserer ; c copier ; d detruire ; a afficher contenu ; A affiche arborescence ; s supprimer ; C charger ; S sauvegarder)\n");
+
+ do {
+     printf("Commande ? "); 
+     c = getchar();
+     switch(c)
+     {
+      case 'v' : abr = arbre_vide(); break;
+
+      case 'r' : printf("indiquer l'element a rechercher : ");
+		 scanf("%d",&x);
+                 if (recherche(abr,x) == 0) printf("pas trouve\n");
+                 else printf("trouve\n"); 
+		 break;
+
+      case 'i' : printf("indiquer l'element a inserer : ");
+		 scanf("%d",&x); 
+		 abr = insere(abr,x); 
+		 break;
+
+      case 'c' : abr2 = copie_arbre(abr); 
+		 break;
+
+      case 'd' : abr = detruis_arbre(abr); 
+		 if(abr2) abr2 = detruis_arbre(abr2); 
+		 break;
+
+      case 'a' : affiche(abr); 
+		 if(abr2) {printf("\nLa copie : \n"); 
+	 	           affiche(abr2);}; 
+		 break;
+
+      case 'A' : affiche_arbre(abr,1); 
+		 if(abr2) {printf("\nLa copie : \n"); 
+			   affiche_arbre(abr2,1);}; 
+		 break;     
+
+      case 's' : printf("indiquer l'element a supprimer : ");
+		 scanf("%d",&x); 
+		 abr = supprime(abr,x); 
+		 break;
+
+      case 'C' : printf("indiquer le nom de fichier pour le chargement : ");
+		 scanf("%s",nom_fich);
+                 if ((fich = fopen(nom_fich,"rb")) != NULL) 
+		  {abr =  (NOEUD *)malloc(sizeof(NOEUD));
+		   abr = charge(abr,fich);
+		   fclose(fich);
+		  };
+		 break;
+      
+      case 'S' : printf("indiquer le nom de fichier pour la sauvegarde : ");
+		 scanf("%s",nom_fich);
+                 if ((fich = fopen(nom_fich,"wb")) != NULL) 
+		  {abr = sauve(abr,fich);
+		   abr = NULL;
+		   fclose(fich);
+		  };  
+		 break;
+
+      case 'q' : exit(0); 
+     }
+     printf("\n"); c = getchar();
+ }
+ while (1);
+}
+
+
+/* Trace d'execution ************************************** 	
+Commandes (une lettre) possibles : v arbre_vide ; r rechercher ; i inserer ; c copier ; d detruire ; a afficher contenu ; A affiche arborescence ; s supprimer ; C charger ; S sauvegarder)
+Commande ? v
+
+Commande ? i
+indiquer l'element a inserer : 2
+
+Commande ? i
+indiquer l'element a inserer : 6
+
+Commande ? i
+indiquer l'element a inserer : 4
+
+Commande ? i
+indiquer l'element a inserer : 5
+
+Commande ? i
+indiquer l'element a inserer : 1
+
+Commande ? i
+indiquer l'element a inserer : 0
+
+Commande ? a
+0 1 2 4 5 6 
+Commande ? A
+      6
+            5
+         4
+   2
+      1
+         0
+
+Commande ? r
+indiquer l'element a rechercher : 4
+trouve
+
+Commande ? r
+indiquer l'element a rechercher : 3
+pas trouve
+
+Commande ? s
+indiquer l'element a supprimer : 4
+
+Commande ? a
+0 1 2 5 6 
+Commande ? A
+      6
+         5
+   2
+      1
+         0
+
+Commande ? S
+indiquer le nom de fichier pour la sauvegarde : sauv.txt
+
+Commande ? C
+indiquer le nom de fichier pour le chargement : sauv.txt
+
+Commande ? a
+0 1 2 5 6 
+Commande ? A
+      6
+         5
+   2
+      1
+         0
+
+Commande ? q
+
+******************************************************************************/
diff --git a/TP6/arbres/ABR/Makefile b/TP6/arbres/ABR/Makefile
new file mode 100644
index 0000000..2a8b729
--- /dev/null
+++ b/TP6/arbres/ABR/Makefile
@@ -0,0 +1,79 @@
+# Sample Makefile to build simple project.
+#
+# This Makefile expect all source files (.c) to be at the same level, in the
+# current working directory.
+#
+# It will automatically generate dependencies, compile all files, and produce a
+# binary using the provided name.
+#
+# Set BINARY_NAME to the name of the binary file to build.
+# Set BUILD_TYPE to either debug or release
+#
+# Automatic dependencies code from:
+# http://make.mad-scientist.net/papers/advanced-auto-dependency-generation/#tldr
+BINARY_NAME=ABR
+BUILD_TYPE=debug
+
+# ====================================
+# DO NOT CHANGE STUFF BEYOND THIS LINE
+# ====================================
+
+all: $(BINARY_NAME)
+
+CC=gcc
+LD=gcc
+
+WARN_FLAGS = -Wall -Wextra
+STD_FLAG = -std=c11
+
+ifeq ($(BUILD_TYPE),debug)
+BUILDDIR := .build/debug
+DEBUG_FLAG = -g
+STRIP_FLAG =
+OPTI_FLAG = -O0
+else
+BUILDDIR := .build/release
+DEBUG_FLAG =
+STRIP_FLAG = -s
+OPTI_FLAG = -O3
+endif
+
+CFLAGS := $(CFLAGS) $(WARN_FLAGS) $(STD_FLAG) $(OPTI_FLAG) $(DEBUG_FLAG)
+LDFLAGS := $(LDFLAGS) $(STRIP_FLAG)
+
+OBJDIR := $(BUILDDIR)/objs
+$(shell mkdir -p $(OBJDIR))
+
+SRCS=$(wildcard *.c)
+OBJS=$(patsubst %.c,$(OBJDIR)/%.o,$(SRCS))
+
+DEPDIR := $(BUILDDIR)/deps
+$(shell mkdir -p $(DEPDIR))
+DEPFLAGS = -MT $@ -MMD -MP -MF $(DEPDIR)/$*.Td
+POSTCOMPILE = mv -f $(DEPDIR)/$*.Td $(DEPDIR)/$*.d
+
+$(BINARY_NAME): $(OBJS)
+	@echo "[LD ] $@"
+	@$(LD) $(CFLAGS) $(LDFLAGS) $^ $(LDLIBS) -o $@
+
+$(OBJDIR)/%.o: %.c $(DEPDIR)/%.d
+	@echo "[C  ] $*"
+	@$(CC) $(DEPFLAGS) $(CFLAGS) -c $< -o $@
+	@$(POSTCOMPILE)
+
+$(DEPDIR)/%.d: ;
+
+.PRECIOUS: $(DEPDIR)/%.d
+
+include $(wildcard $(patsubst %,$(DEPDIR)/%.d,$(basename $(SRCS))))
+
+clean:
+	@echo "[CLN]"
+	-@rm -r $(BUILDDIR)
+	-@rm $(BINARY_NAME)
+
+disassemble: $(BINARY_NAME)
+	objdump -d $< | less
+
+symbols: $(BINARY_NAME)
+	objdump -t $< | sort | less
diff --git a/TP6/arbres/arbre-n-aire/Makefile b/TP6/arbres/arbre-n-aire/Makefile
new file mode 100644
index 0000000..6b0ec52
--- /dev/null
+++ b/TP6/arbres/arbre-n-aire/Makefile
@@ -0,0 +1,79 @@
+# Sample Makefile to build simple project.
+#
+# This Makefile expect all source files (.c) to be at the same level, in the
+# current working directory.
+#
+# It will automatically generate dependencies, compile all files, and produce a
+# binary using the provided name.
+#
+# Set BINARY_NAME to the name of the binary file to build.
+# Set BUILD_TYPE to either debug or release
+#
+# Automatic dependencies code from:
+# http://make.mad-scientist.net/papers/advanced-auto-dependency-generation/#tldr
+BINARY_NAME=arbre_n_aire
+BUILD_TYPE=debug
+
+# ====================================
+# DO NOT CHANGE STUFF BEYOND THIS LINE
+# ====================================
+
+all: $(BINARY_NAME)
+
+CC=gcc
+LD=gcc
+
+WARN_FLAGS = -Wall -Wextra
+STD_FLAG = -std=c11
+
+ifeq ($(BUILD_TYPE),debug)
+BUILDDIR := .build/debug
+DEBUG_FLAG = -g
+STRIP_FLAG =
+OPTI_FLAG = -O0
+else
+BUILDDIR := .build/release
+DEBUG_FLAG =
+STRIP_FLAG = -s
+OPTI_FLAG = -O3
+endif
+
+CFLAGS := $(CFLAGS) $(WARN_FLAGS) $(STD_FLAG) $(OPTI_FLAG) $(DEBUG_FLAG)
+LDFLAGS := $(LDFLAGS) $(STRIP_FLAG)
+
+OBJDIR := $(BUILDDIR)/objs
+$(shell mkdir -p $(OBJDIR))
+
+SRCS=$(wildcard *.c)
+OBJS=$(patsubst %.c,$(OBJDIR)/%.o,$(SRCS))
+
+DEPDIR := $(BUILDDIR)/deps
+$(shell mkdir -p $(DEPDIR))
+DEPFLAGS = -MT $@ -MMD -MP -MF $(DEPDIR)/$*.Td
+POSTCOMPILE = mv -f $(DEPDIR)/$*.Td $(DEPDIR)/$*.d
+
+$(BINARY_NAME): $(OBJS)
+	@echo "[LD ] $@"
+	@$(LD) $(CFLAGS) $(LDFLAGS) $^ $(LDLIBS) -o $@
+
+$(OBJDIR)/%.o: %.c $(DEPDIR)/%.d
+	@echo "[C  ] $*"
+	@$(CC) $(DEPFLAGS) $(CFLAGS) -c $< -o $@
+	@$(POSTCOMPILE)
+
+$(DEPDIR)/%.d: ;
+
+.PRECIOUS: $(DEPDIR)/%.d
+
+include $(wildcard $(patsubst %,$(DEPDIR)/%.d,$(basename $(SRCS))))
+
+clean:
+	@echo "[CLN]"
+	-@rm -r $(BUILDDIR)
+	-@rm $(BINARY_NAME)
+
+disassemble: $(BINARY_NAME)
+	objdump -d $< | less
+
+symbols: $(BINARY_NAME)
+	objdump -t $< | sort | less
diff --git a/TP6/arbres/arbre-n-aire/arbre_n_aire_a_completer.c b/TP6/arbres/arbre-n-aire/arbre_n_aire_a_completer.c
new file mode 100644
index 0000000..4d4b97f
--- /dev/null
+++ b/TP6/arbres/arbre-n-aire/arbre_n_aire_a_completer.c
@@ -0,0 +1,178 @@
+/*****************************************************************************/
+/*                          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>
+
+
+/* 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 *****************************************/ 	
+int recherche(NOEUD *p, char *mot, int i)
+{
+ /* TODO */
+ return 0;
+}
+
+
+
+/* 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 ...
+
+**********************************************************/ 	
+