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 | { | |
c43303a3 | 24 | /* "mauvaise" fonction de hachage - juste pour tester le programme */ |
61056410 JB |
25 | return x % M; |
26 | } | |
27 | ||
61056410 JB |
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 | } | |
249ff697 JB |
37 | |
38 | int rechercher(element x, t_table t) | |
61056410 JB |
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) | |
249ff697 | 52 | /* retourne 0 si x est deja dans la table */ |
61056410 JB |
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 | } | |
249ff697 JB |
75 | |
76 | void visu(Liste L) | |
61056410 JB |
77 | { |
78 | if (L) { | |
79 | printf("%d\t", L->valeur); | |
80 | visu(L->suivant); | |
81 | } | |
82 | } | |
83 | ||
249ff697 | 84 | void afficher(t_table t) |
61056410 JB |
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 | ||
249ff697 | 98 | /******************************************************************************/ |
61056410 JB |
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); | |
249ff697 | 119 | } |
61056410 | 120 | |
249ff697 JB |
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 | |
61056410 | 127 | *****************************************************************************/ |