Commit | Line | Data |
---|---|---|
249ff697 JB |
1 | /******************************************************************************/ |
2 | /* Hachage par chainage */ | |
3 | /******************************************************************************/ | |
4 | #include <stdlib.h> | |
5 | #include <stdio.h> | |
6 | ||
61056410 | 7 | #define M 5 |
249ff697 JB |
8 | /* on choisit M tres petit pour tester le programme, mais en realite, |
9 | M est tres grand */ | |
10 | ||
11 | typedef int element; | |
12 | ||
61056410 JB |
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 | ||
249ff697 | 27 | /* "mauvaise" fonction de hachage - juste pour tester le programme */ |
61056410 JB |
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 | } | |
249ff697 JB |
38 | |
39 | int rechercher(element x, t_table t) | |
61056410 JB |
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) | |
249ff697 | 53 | /* retourne 0 si x est deja dans la table */ |
61056410 JB |
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 | } | |
249ff697 JB |
76 | |
77 | void visu(Liste L) | |
61056410 JB |
78 | { |
79 | if (L) { | |
80 | printf("%d\t", L->valeur); | |
81 | visu(L->suivant); | |
82 | } | |
83 | } | |
84 | ||
249ff697 | 85 | void afficher(t_table t) |
61056410 JB |
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 | ||
249ff697 | 99 | /******************************************************************************/ |
61056410 JB |
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); | |
249ff697 | 120 | } |
61056410 | 121 | |
249ff697 JB |
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 | |
61056410 | 128 | *****************************************************************************/ |