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 {element valeur;
  14                         struct cellule *suivant; } Cellule, *Liste;
  15
  16 typedef struct {Liste T[M]; } t_table;
  17
  18 int h(element x) {return x%M; }
  19 /* "mauvaise" fonction de hachage - juste pour tester le programme */
  20
  21 t_table init_table()
  22         {t_table t;
  23          int i;
  24          for (i=0; i<M; i++) t.T[i]=NULL;
  25          return t;}
  26
  27
  28 int rechercher(element x, t_table t)
  29       {int i=h(x);
  30        Cellule *p=t.T[i];
  31        while (p) if (x==p->valeur) return 1;
  32                  else p=p->suivant;
  33        return 0;
  34       }
  35
  36 int inserer(element x, t_table *t)
  37 /* retourne 0 si x est deja dans la table */
  38       {int i=h(x);
  39        Cellule *p=t->T[i], *preced=NULL;
  40        while (p) if (x==p->valeur) return 0;
  41                  else {preced = p; p=p->suivant; }
  42        if (preced==NULL) {t->T[i]=(Cellule *)malloc(sizeof(Cellule));
  43                           t->T[i]->valeur=x;
  44                           t->T[i]->suivant=NULL;
  45                           }
  46        else {preced->suivant=(Cellule *)malloc(sizeof(Cellule));
  47              preced->suivant->valeur=x;
  48              preced->suivant->suivant=NULL;
  49              }
  50        return 1;
  51       }
  52
  53 void visu(Liste L)
  54      {if (L){printf("%d\t",L->valeur);
  55              visu(L->suivant);
  56             }
  57      }
  58
  59 void afficher(t_table t)
  60       {Cellule *p;
  61        int i;
  62        for (i=0; i<M ; i++)
  63            if (t.T[i]) {printf("t[%d]=\t",i); visu(t.T[i]); printf("\n");}
  64         printf("\n");
  65        }
  66
  67 /******************************************************************************/
  68 int main ()
  69 {t_table t;
  70
  71 t=init_table();
  72 afficher(t);
  73 inserer(3,&t);  afficher(t);
  74 printf("%d\n",rechercher(3,t));
  75 printf("%d\n",rechercher(12,t));
  76 inserer(5,&t);  afficher(t);
  77 inserer(13,&t); afficher(t);
  78 inserer(9,&t);  afficher(t);
  79 inserer(19,&t); afficher(t);
  80 inserer(23,&t); afficher(t);
  81 }
  82 /*****************************************************************************
  83 Etat de la table a la fin du programme
  84 --------------------------------------
  85 t[0]=   5
  86 t[3]=   3       13      23
  87 t[4]=   9       19
  88 *****************************************************************************/