1 /******************************************************************************/
2 /* Hachage linéaire avec suppression */
3 /******************************************************************************/
18 void affiche_tab(t_elem
* tab
)
22 for (i
= 0; i
< M
; i
++)
23 printf("<%2d,%2d>", tab
[i
].cle
, tab
[i
].etat
);
28 { /* mauvaise fonction de hachage - juste pour tester */
32 int rechercher(int x
, t_elem
* tab
)
33 /* retourne l'indice de x dans la table si x est present, -1 sinon */
38 if ((tab
[v
].etat
== VIDE
) || ((tab
[v
].etat
== OCCUPE
) &&
48 if ((tab
[v
].etat
== OCCUPE
) && (tab
[v
].cle
== x
)) /* x présent */
54 int supprimer(int x
, t_elem
* tab
)
55 /* supprime x de la table, s'il est présent (et alors retourne son indice),
56 et ne fait rien si x est absent (et alors retourne -1) */
58 int v
= rechercher(x
, tab
);
60 if (v
!= -1) { /*x present */
67 int inserer(int x
, t_elem
* tab
)
68 /* si x n'est pas dans la table, on l'insère a la première place vide ou liberee
69 rencontrée au cours des essais successifs (et on retourne son indice);
70 si x est déjà dans la table, on ne fait rien (et on retourne son indice);
71 si le tableau est plein, c'est que x n'a pu être insèré et on retourne -1 */
73 int i
= 0, lib
= -1, v
= h(x
);
76 if (tab
[v
].etat
== VIDE
)
78 /*x absent, on arrête le parcours du tableau */
79 if ((tab
[v
].etat
== OCCUPE
) && (tab
[v
].cle
== x
))
81 /* x déjà présent, on ne fait rien */
82 if ((tab
[v
].etat
== LIBERE
) && (lib
== -1))
84 /* on mémorise l'indice de la première place libérée */
89 /* on continue tant qu'on ne trouve pas x ou une place vide */
92 if (tab
[v
].etat
== VIDE
)
99 tab
[lib
].etat
= OCCUPE
;
110 tab
= (t_elem
*) calloc((M
), sizeof(t_elem
));
112 printf("memoire insuffisante\n");
116 for (i
= 0; i
< M
; i
++)
120 printf("%d\n", inserer(3, tab
));
122 printf("%d\n", inserer(5, tab
));
124 printf("%d\n", inserer(13, tab
));
126 printf("%d\n", inserer(9, tab
));
128 printf("%d\n", inserer(19, tab
));
130 printf("%d\n", supprimer(3, tab
));
132 printf("%d\n", rechercher(3, tab
));
134 printf("%d\n", inserer(23, tab
));
136 printf("%d\n", inserer(3, tab
));
140 /*****************************************************************************
141 <0,0> <0,0> <0,0> <0,0> <0,0> <0,0> <0,0> <0,0> <0,0> <0,0>
143 <0,0> <0,0> <0,0> <3,1> <0,0> <0,0> <0,0> <0,0> <0,0> <0,0>
145 <0,0> <0,0> <0,0> <3,1> <0,0> <5,1> <0,0> <0,0> <0,0> <0,0>
147 <0,0> <0,0> <0,0> <3,1> <13,1> <5,1> <0,0> <0,0> <0,0> <0,0>
149 <0,0> <0,0> <0,0> <3,1> <13,1> <5,1> <0,0> <0,0> <0,0> <9,1>
151 <19,1> <0,0> <0,0> <3,1> <13,1> <5,1> <0,0> <0,0> <0,0> <9,1>
153 <19,1> <0,0> <0,0> <3,-1> <13,1> <5,1> <0,0> <0,0> <0,0> <9,1>
155 <19,1> <0,0> <0,0> <3,-1> <13,1> <5,1> <0,0> <0,0> <0,0> <9,1>
157 <19,1> <0,0> <0,0> <23,1> <13,1> <5,1> <0,0> <0,0> <0,0> <9,1>
159 <19,1> <0,0> <0,0> <23,1> <13,1> <5,1> <3,1> <0,0> <0,0> <9,1>
161 *****************************************************************************/