Add latest implementation of tree algorithm in TP6 directory

[Algorithmic_C.git] / TP6 / hachage / chainage / hachage_chainage.c

diff --git a/TP6/hachage/chainage/hachage_chainage.c b/TP6/hachage/chainage/hachage_chainage.c
new file mode 100644 (file)
index 0000000..b971067
--- /dev/null
+++ b/TP6/hachage/chainage/hachage_chainage.c
@@ -0,0 +1,88 @@
+/******************************************************************************/
+/*                         Hachage par chainage                               */
+/******************************************************************************/
+#include <stdlib.h>
+#include <stdio.h>
+
+#define M 5 
+/* on choisit M tres petit pour tester le programme, mais en realite,
+   M est tres grand */
+
+typedef int element;
+
+typedef struct cellule {element valeur;
+                        struct cellule *suivant; } Cellule, *Liste;
+                        
+typedef struct {Liste T[M]; } t_table;
+               
+int h(element x) {return x%M; } 
+/* "mauvaise" fonction de hachage - juste pour tester le programme */
+              
+t_table init_table() 
+       {t_table t;
+        int i;       
+        for (i=0; i<M; i++) t.T[i]=NULL;
+        return t;}
+                      
+
+int rechercher(element x, t_table t)
+      {int i=h(x); 
+       Cellule *p=t.T[i];
+       while (p) if (x==p->valeur) return 1;
+                 else p=p->suivant;
+       return 0;
+      }
+                
+int inserer(element x, t_table *t) 
+/* retourne 0 si x est deja dans la table */
+      {int i=h(x); 
+       Cellule *p=t->T[i], *preced=NULL;
+       while (p) if (x==p->valeur) return 0;
+                 else {preced = p; p=p->suivant; }
+       if (preced==NULL) {t->T[i]=(Cellule *)malloc(sizeof(Cellule));
+                          t->T[i]->valeur=x;
+                         t->T[i]->suivant=NULL;
+                         }
+       else {preced->suivant=(Cellule *)malloc(sizeof(Cellule));
+             preced->suivant->valeur=x;
+            preced->suivant->suivant=NULL;
+            }
+       return 1;
+      }
+
+void visu(Liste L)
+     {if (L){printf("%d\t",L->valeur);
+             visu(L->suivant);
+           }
+     } 
+     
+void afficher(t_table t)
+      {Cellule *p;
+       int i;
+       for (i=0; i<M ; i++)
+          if (t.T[i]) {printf("t[%d]=\t",i); visu(t.T[i]); printf("\n");}
+        printf("\n");
+       }
+       
+/******************************************************************************/
+int main ()
+{t_table t;
+
+t=init_table();
+afficher(t);
+inserer(3,&t); afficher(t);
+printf("%d\n",rechercher(3,t));
+printf("%d\n",rechercher(12,t));
+inserer(5,&t); afficher(t);
+inserer(13,&t); afficher(t);
+inserer(9,&t);         afficher(t);
+inserer(19,&t); afficher(t);
+inserer(23,&t); afficher(t);
+}
+/*****************************************************************************
+Etat de la table a la fin du programme
+-------------------------------------- 
+t[0]=   5
+t[3]=   3       13      23
+t[4]=   9       19
+*****************************************************************************/