TP6/hachage/chainage/hachage_chainage.c

   1 /******************************************************************************/
   2 /*                         Hachage par chainage                               */
   3 /******************************************************************************/
   4 #include <stdlib.h>
   5 #include <stdio.h>
   6
   7 #define M 5
   8 /* on choisit M tres petit pour tester le programme, mais en realite,
   9    M est tres grand */
  10
  11 typedef int element;
  12
  13 typedef struct cellule {
  14     element valeur;
  15     struct cellule *suivant;
  16 } Cellule, *Liste;
  17
  18 typedef struct {
  19     Liste T[M];
  20 } t_table;
  21
  22 int h(element x)
  23 {
  24     return x % M;
  25 }
  26
  27 /* "mauvaise" fonction de hachage - juste pour tester le programme */
  28
  29 t_table init_table()
  30 {
  31     t_table t;
  32     int i;
  33
  34     for (i = 0; i < M; i++)
  35         t.T[i] = NULL;
  36     return t;
  37 }
  38
  39 int rechercher(element x, t_table t)
  40 {
  41     int i = h(x);
  42     Cellule *p = t.T[i];
  43
  44     while (p)
  45         if (x == p->valeur)
  46             return 1;
  47         else
  48             p = p->suivant;
  49     return 0;
  50 }
  51
  52 int inserer(element x, t_table * t)
  53 /* retourne 0 si x est deja dans la table */
  54 {
  55     int i = h(x);
  56     Cellule *p = t->T[i], *preced = NULL;
  57
  58     while (p)
  59         if (x == p->valeur)
  60             return 0;
  61         else {
  62             preced = p;
  63             p = p->suivant;
  64         }
  65     if (preced == NULL) {
  66         t->T[i] = (Cellule *) malloc(sizeof(Cellule));
  67         t->T[i]->valeur = x;
  68         t->T[i]->suivant = NULL;
  69     } else {
  70         preced->suivant = (Cellule *) malloc(sizeof(Cellule));
  71         preced->suivant->valeur = x;
  72         preced->suivant->suivant = NULL;
  73     }
  74     return 1;
  75 }
  76
  77 void visu(Liste L)
  78 {
  79     if (L) {
  80         printf("%d\t", L->valeur);
  81         visu(L->suivant);
  82     }
  83 }
  84
  85 void afficher(t_table t)
  86 {
  87     Cellule *p;
  88     int i;
  89
  90     for (i = 0; i < M; i++)
  91         if (t.T[i]) {
  92             printf("t[%d]=\t", i);
  93             visu(t.T[i]);
  94             printf("\n");
  95         }
  96     printf("\n");
  97 }
  98
  99 /******************************************************************************/
 100 int main()
 101 {
 102     t_table t;
 103
 104     t = init_table();
 105     afficher(t);
 106     inserer(3, &t);
 107     afficher(t);
 108     printf("%d\n", rechercher(3, t));
 109     printf("%d\n", rechercher(12, t));
 110     inserer(5, &t);
 111     afficher(t);
 112     inserer(13, &t);
 113     afficher(t);
 114     inserer(9, &t);
 115     afficher(t);
 116     inserer(19, &t);
 117     afficher(t);
 118     inserer(23, &t);
 119     afficher(t);
 120 }
 121
 122 /*****************************************************************************
 123 Etat de la table a la fin du programme
 124 --------------------------------------
 125 t[0]=   5
 126 t[3]=   3       13      23
 127 t[4]=   9       19
 128 *****************************************************************************/