Add latest implementation of tree algorithm in TP6 directory

[Algorithmic_C.git] / TP6 / hachage / lineaire / hachage_lineaire.c

diff --git a/TP6/hachage/lineaire/hachage_lineaire.c b/TP6/hachage/lineaire/hachage_lineaire.c
new file mode 100644 (file)
index 0000000..58fcb5c
--- /dev/null
+++ b/TP6/hachage/lineaire/hachage_lineaire.c
@@ -0,0 +1,115 @@
+/******************************************************************************/
+/*                    Hachage linéaire avec suppression                       */
+/******************************************************************************/
+
+#include <stdio.h>
+#include <stdlib.h>
+
+#define VIDE 0
+#define OCCUPE 1
+#define LIBERE -1
+#define M 10
+
+typedef struct {int cle;
+                int etat;
+               } t_elem;
+
+void affiche_tab(t_elem *tab)
+{int i;
+ for (i = 0 ; i <M ; i++) printf("<%2d,%2d>",tab[i].cle,tab[i].etat);
+ printf("\n");
+}
+
+int h(int x)  /* mauvaise fonction de hachage - juste pour tester  */
+{return x%M;}
+
+int rechercher(int x,t_elem *tab)
+/* retourne l'indice de x dans la table si x est present, -1 sinon */
+{int i=0,v=h(x);
+ while (i<M)
+       if ((tab[v].etat==VIDE) || ((tab[v].etat==OCCUPE) && 
+(tab[v].cle==x)))
+                 break;
+       else {i++;v++;if (v>=M) v=0;
+            };
+
+if ((tab[v].etat==OCCUPE) && (tab[v].cle==x)) /* x présent */ return v;
+ else /* x absent */ return -1;
+}
+
+int supprimer(int x,t_elem *tab)
+/* supprime x de la table, s'il est présent (et alors retourne son indice),
+   et ne fait rien si x est absent (et alors retourne -1)                     
+*/
+{int v = rechercher(x,tab);
+ if (v!=-1) /*x present */ {tab[v].etat=LIBERE; return v;
+                       }
+ else /* x absent */ return -1;
+}
+ 
+int inserer(int x,t_elem *tab)
+/* si x n'est pas dans la table, on l'insère a la première place vide ou liberee
+   rencontrée au cours des essais successifs (et on retourne son indice);
+   si x est déjà dans la table, on ne fait rien (et on retourne son indice);
+   si le tableau est plein, c'est que x n'a pu être insèré et on retourne -1  */
+{int i=0,lib=-1,v=h(x);
+ while (i<M)
+       {if (tab[v].etat==VIDE) break; 
+                                /*x absent, on arrête le parcours du tableau */
+         if ((tab[v].etat==OCCUPE) && (tab[v].cle==x)) return v;
+                                          /* x déjà présent, on ne fait rien */
+        if ((tab[v].etat==LIBERE) && (lib==-1)) lib=v;
+                        /* on mémorise l'indice de la première place libérée */
+        i++;v++;if (v>=M) v=0;
+                 /* on continue tant qu'on ne trouve pas x ou une place vide */
+       }
+ 
+ if (tab[v].etat==VIDE) 
+       if (lib==-1) {tab[v].cle=x;tab[v].etat=OCCUPE;return v;}
+        else         {tab[lib].cle=x;tab[lib].etat=OCCUPE;return lib;}
+ else return -1;
+}
+
+int main ()
+{int i;
+ t_elem *tab;
+       
+tab = (t_elem *)calloc((M),sizeof(t_elem));
+if (tab == NULL) {printf("memoire insuffisante\n"); exit(-1); }
+         
+for (i=0;i<M;i++) tab[i].etat = VIDE;
+       
+affiche_tab(tab);
+printf("%d\n",inserer(3,tab));     affiche_tab(tab);
+printf("%d\n",inserer(5,tab));     affiche_tab(tab);
+printf("%d\n",inserer(13,tab));    affiche_tab(tab);
+printf("%d\n",inserer(9,tab));     affiche_tab(tab);
+printf("%d\n",inserer(19,tab));    affiche_tab(tab);
+printf("%d\n",supprimer(3,tab));   affiche_tab(tab);
+printf("%d\n",rechercher(3,tab));  affiche_tab(tab);
+printf("%d\n",inserer(23,tab));    affiche_tab(tab);
+printf("%d\n",inserer(3,tab));     affiche_tab(tab);
+}
+/*****************************************************************************
+       <0,0>  <0,0>  <0,0>  <0,0>  <0,0>  <0,0>  <0,0>  <0,0>  <0,0>  <0,0>
+ 3     
+        <0,0>  <0,0>  <0,0>  <3,1>  <0,0>  <0,0>  <0,0>         <0,0>  <0,0>  <0,0>
+ 5     
+        <0,0>  <0,0>  <0,0>  <3,1>  <0,0>  <5,1>  <0,0>         <0,0>  <0,0>  <0,0>
+ 4     
+        <0,0>  <0,0>  <0,0>  <3,1>  <13,1> <5,1>  <0,0>         <0,0>  <0,0>  <0,0>
+ 9     
+        <0,0>  <0,0>  <0,0>  <3,1>  <13,1> <5,1>  <0,0>         <0,0>  <0,0>  <9,1>
+ 0      
+        <19,1> <0,0>  <0,0>  <3,1>  <13,1> <5,1>  <0,0>         <0,0>  <0,0>  <9,1>
+ 3      
+        <19,1> <0,0>  <0,0>  <3,-1> <13,1> <5,1>  <0,0>  <0,0>  <0,0>  <9,1>
+-1      
+        <19,1> <0,0>  <0,0>  <3,-1> <13,1> <5,1>  <0,0>         <0,0>  <0,0>  <9,1>
+ 3      
+        <19,1> <0,0>  <0,0>  <23,1> <13,1> <5,1>  <0,0>  <0,0>  <0,0>  <9,1>
+ 6      
+        <19,1> <0,0>  <0,0>  <23,1> <13,1> <5,1>  <3,1>         <0,0>  <0,0>  <9,1>
+        
+*****************************************************************************/
+