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