Refine .gitignore some more.
[Algorithmic_C.git] / 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 *****************************************************************************/