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 {
  14     int cle;
  15     int etat;
  16 } t_elem;
  17
  18 void affiche_tab(t_elem * tab)
  19 {
  20     int i;
  21
  22     for (i = 0; i < M; i++)
  23         printf("<%2d,%2d>", tab[i].cle, tab[i].etat);
  24     printf("\n");
  25 }
  26
  27 int h(int x)
  28 {                               /* mauvaise fonction de hachage - juste pour tester  */
  29     return x % M;
  30 }
  31
  32 int rechercher(int x, t_elem * tab)
  33 /* retourne l'indice de x dans la table si x est present, -1 sinon */
  34 {
  35     int i = 0, v = h(x);
  36
  37     while (i < M)
  38         if ((tab[v].etat == VIDE) || ((tab[v].etat == OCCUPE) &&
  39                                       (tab[v].cle == x)))
  40             break;
  41         else {
  42             i++;
  43             v++;
  44             if (v >= M)
  45                 v = 0;
  46         };
  47
  48     if ((tab[v].etat == OCCUPE) && (tab[v].cle == x))   /* x présent */
  49         return v;
  50     else                        /* x absent */
  51         return -1;
  52 }
  53
  54 int supprimer(int x, t_elem * tab)
  55 /* supprime x de la table, s'il est présent (et alors retourne son indice),
  56    et ne fait rien si x est absent (et alors retourne -1) */
  57 {
  58     int v = rechercher(x, tab);
  59
  60     if (v != -1) {              /*x present */
  61         tab[v].etat = LIBERE;
  62         return v;
  63     } else                      /* x absent */
  64         return -1;
  65 }
  66
  67 int inserer(int x, t_elem * tab)
  68 /* si x n'est pas dans la table, on l'insère a la première place vide ou liberee
  69    rencontrée au cours des essais successifs (et on retourne son indice);
  70    si x est déjà dans la table, on ne fait rien (et on retourne son indice);
  71    si le tableau est plein, c'est que x n'a pu être insèré et on retourne -1  */
  72 {
  73     int i = 0, lib = -1, v = h(x);
  74
  75     while (i < M) {
  76         if (tab[v].etat == VIDE)
  77             break;
  78         /* x absent, on arrête le parcours du tableau */
  79         if ((tab[v].etat == OCCUPE) && (tab[v].cle == x))
  80             return v;
  81         /* x déjà présent, on ne fait rien */
  82         if ((tab[v].etat == LIBERE) && (lib == -1))
  83             lib = v;
  84         /* on mémorise l'indice de la première place libérée */
  85         i++;
  86         v++;
  87         if (v >= M)
  88             v = 0;
  89         /* on continue tant qu'on ne trouve pas x ou une place vide */
  90     }
  91
  92     if (tab[v].etat == VIDE)
  93         if (lib == -1) {
  94             tab[v].cle = x;
  95             tab[v].etat = OCCUPE;
  96             return v;
  97         } else {
  98             tab[lib].cle = x;
  99             tab[lib].etat = OCCUPE;
 100             return lib;
 101     } else
 102         return -1;
 103 }
 104
 105 int main()
 106 {
 107     int i;
 108     t_elem *tab;
 109
 110     tab = (t_elem *) calloc((M), sizeof(t_elem));
 111     if (tab == NULL) {
 112         printf("memoire insuffisante\n");
 113         exit(-1);
 114     }
 115
 116     for (i = 0; i < M; i++)
 117         tab[i].etat = VIDE;
 118
 119     affiche_tab(tab);
 120     printf("%d\n", inserer(3, tab));
 121     affiche_tab(tab);
 122     printf("%d\n", inserer(5, tab));
 123     affiche_tab(tab);
 124     printf("%d\n", inserer(13, tab));
 125     affiche_tab(tab);
 126     printf("%d\n", inserer(9, tab));
 127     affiche_tab(tab);
 128     printf("%d\n", inserer(19, tab));
 129     affiche_tab(tab);
 130     printf("%d\n", supprimer(3, tab));
 131     affiche_tab(tab);
 132     printf("%d\n", rechercher(3, tab));
 133     affiche_tab(tab);
 134     printf("%d\n", inserer(23, tab));
 135     affiche_tab(tab);
 136     printf("%d\n", inserer(3, tab));
 137     affiche_tab(tab);
 138 }
 139
 140 /*****************************************************************************
 141         <0,0>  <0,0>  <0,0>  <0,0>  <0,0>  <0,0>  <0,0>  <0,0>  <0,0>  <0,0>
 142  3
 143         <0,0>  <0,0>  <0,0>  <3,1>  <0,0>  <0,0>  <0,0>  <0,0>  <0,0>  <0,0>
 144  5
 145         <0,0>  <0,0>  <0,0>  <3,1>  <0,0>  <5,1>  <0,0>  <0,0>  <0,0>  <0,0>
 146  4
 147         <0,0>  <0,0>  <0,0>  <3,1>  <13,1> <5,1>  <0,0>  <0,0>  <0,0>  <0,0>
 148  9
 149         <0,0>  <0,0>  <0,0>  <3,1>  <13,1> <5,1>  <0,0>  <0,0>  <0,0>  <9,1>
 150  0
 151         <19,1> <0,0>  <0,0>  <3,1>  <13,1> <5,1>  <0,0>  <0,0>  <0,0>  <9,1>
 152  3
 153         <19,1> <0,0>  <0,0>  <3,-1> <13,1> <5,1>  <0,0>  <0,0>  <0,0>  <9,1>
 154 -1
 155         <19,1> <0,0>  <0,0>  <3,-1> <13,1> <5,1>  <0,0>  <0,0>  <0,0>  <9,1>
 156  3
 157         <19,1> <0,0>  <0,0>  <23,1> <13,1> <5,1>  <0,0>  <0,0>  <0,0>  <9,1>
 158  6
 159         <19,1> <0,0>  <0,0>  <23,1> <13,1> <5,1>  <3,1>  <0,0>  <0,0>  <9,1>
 160
 161 *****************************************************************************/