TP6/hachage/lineaire/hachage_lineaire.c

   1 /******************************************************************************/
   2 /*                    Hachage linéaire avec suppression                       */
   3 /******************************************************************************/
   4
   5 #include <stdio.h>
   6 #include <stdlib.h>
   7
   8 #define VIDE 0
   9 #define OCCUPE 1
  10 #define LIBERE -1
  11 #define M 10
  12
  13 typedef struct {int cle;
  14                 int etat;
  15                } t_elem;
  16
  17 void affiche_tab(t_elem *tab)
  18 {int i;
  19  for (i = 0 ; i <M ; i++) printf("<%2d,%2d>",tab[i].cle,tab[i].etat);
  20  printf("\n");
  21 }
  22
  23 int h(int x)  /* mauvaise fonction de hachage - juste pour tester  */
  24 {return x%M;}
  25
  26 int rechercher(int x,t_elem *tab)
  27 /* retourne l'indice de x dans la table si x est present, -1 sinon */
  28 {int i=0,v=h(x);
  29  while (i<M)
  30        if ((tab[v].etat==VIDE) || ((tab[v].etat==OCCUPE) &&
  31 (tab[v].cle==x)))
  32           break;
  33        else {i++;v++;if (v>=M) v=0;
  34             };
  35
  36 if ((tab[v].etat==OCCUPE) && (tab[v].cle==x)) /* x présent */ return v;
  37  else /* x absent */ return -1;
  38 }
  39
  40 int supprimer(int x,t_elem *tab)
  41 /* supprime x de la table, s'il est présent (et alors retourne son indice),
  42    et ne fait rien si x est absent (et alors retourne -1)
  43 */
  44 {int v = rechercher(x,tab);
  45  if (v!=-1) /*x present */ {tab[v].etat=LIBERE; return v;
  46                        }
  47  else /* x absent */ return -1;
  48 }
  49
  50 int inserer(int x,t_elem *tab)
  51 /* si x n'est pas dans la table, on l'insère a la première place vide ou liberee
  52    rencontrée au cours des essais successifs (et on retourne son indice);
  53    si x est déjà dans la table, on ne fait rien (et on retourne son indice);
  54    si le tableau est plein, c'est que x n'a pu être insèré et on retourne -1  */
  55 {int i=0,lib=-1,v=h(x);
  56  while (i<M)
  57         {if (tab[v].etat==VIDE) break;
  58                                  /*x absent, on arrête le parcours du tableau */
  59          if ((tab[v].etat==OCCUPE) && (tab[v].cle==x)) return v;
  60                                            /* x déjà présent, on ne fait rien */
  61          if ((tab[v].etat==LIBERE) && (lib==-1)) lib=v;
  62                          /* on mémorise l'indice de la première place libérée */
  63          i++;v++;if (v>=M) v=0;
  64                   /* on continue tant qu'on ne trouve pas x ou une place vide */
  65         }
  66
  67  if (tab[v].etat==VIDE)
  68         if (lib==-1) {tab[v].cle=x;tab[v].etat=OCCUPE;return v;}
  69         else         {tab[lib].cle=x;tab[lib].etat=OCCUPE;return lib;}
  70  else return -1;
  71 }
  72
  73 int main ()
  74 {int i;
  75  t_elem *tab;
  76
  77 tab = (t_elem *)calloc((M),sizeof(t_elem));
  78 if (tab == NULL) {printf("memoire insuffisante\n"); exit(-1); }
  79
  80 for (i=0;i<M;i++) tab[i].etat = VIDE;
  81
  82 affiche_tab(tab);
  83 printf("%d\n",inserer(3,tab));     affiche_tab(tab);
  84 printf("%d\n",inserer(5,tab));     affiche_tab(tab);
  85 printf("%d\n",inserer(13,tab));    affiche_tab(tab);
  86 printf("%d\n",inserer(9,tab));     affiche_tab(tab);
  87 printf("%d\n",inserer(19,tab));    affiche_tab(tab);
  88 printf("%d\n",supprimer(3,tab));   affiche_tab(tab);
  89 printf("%d\n",rechercher(3,tab));  affiche_tab(tab);
  90 printf("%d\n",inserer(23,tab));    affiche_tab(tab);
  91 printf("%d\n",inserer(3,tab));     affiche_tab(tab);
  92 }
  93 /*****************************************************************************
  94         <0,0>  <0,0>  <0,0>  <0,0>  <0,0>  <0,0>  <0,0>  <0,0>  <0,0>  <0,0>
  95  3
  96         <0,0>  <0,0>  <0,0>  <3,1>  <0,0>  <0,0>  <0,0>  <0,0>  <0,0>  <0,0>
  97  5
  98         <0,0>  <0,0>  <0,0>  <3,1>  <0,0>  <5,1>  <0,0>  <0,0>  <0,0>  <0,0>
  99  4
 100         <0,0>  <0,0>  <0,0>  <3,1>  <13,1> <5,1>  <0,0>  <0,0>  <0,0>  <0,0>
 101  9
 102         <0,0>  <0,0>  <0,0>  <3,1>  <13,1> <5,1>  <0,0>  <0,0>  <0,0>  <9,1>
 103  0
 104         <19,1> <0,0>  <0,0>  <3,1>  <13,1> <5,1>  <0,0>  <0,0>  <0,0>  <9,1>
 105  3
 106         <19,1> <0,0>  <0,0>  <3,-1> <13,1> <5,1>  <0,0>  <0,0>  <0,0>  <9,1>
 107 -1
 108         <19,1> <0,0>  <0,0>  <3,-1> <13,1> <5,1>  <0,0>  <0,0>  <0,0>  <9,1>
 109  3
 110         <19,1> <0,0>  <0,0>  <23,1> <13,1> <5,1>  <0,0>  <0,0>  <0,0>  <9,1>
 111  6
 112         <19,1> <0,0>  <0,0>  <23,1> <13,1> <5,1>  <3,1>  <0,0>  <0,0>  <9,1>
 113
 114 *****************************************************************************/
 115