Option info - TP8 Tables de hachage

(* SUJET CENTRALE OPTION INFO 2018 *)


(* Les listes contiennent ici des couples d'éléments de [| 0,N-1 |] *)




let _N=10;;

(* Q12 *)
let hachage_liste w q =
(* q est une liste qu'il faut hacher.
Pour cela, on évalue le polynôme donné en N. *)
(* N est variable globale *)

let rec aux_somme liste compteur_i = match liste with
|[] -> 0
|(a1,a2)::t ->
(a1 + a2*_N) + _N*(aux_somme t (compteur_i+1));

in

(aux_somme q 0) mod w;;

let w = 997;;


type ('a,'b) table_hachage =
{hache: int -> int;
donnees: ('a * 'b) list array;
largeur: int};;

let fonction (x:int) = (x:int);;
let aaaa = {hache = fonction; donnees = [|[]|]; largeur = 5};;

(* Q13 *)
let creer_table h w =
{hache = h; donnees = Array.make w []; largeur = w};;

let t=[|2;3|];;

(* Q14 *)
let recherche t k =
let indice = t.hache(k) in
let liste_indice = (t.donnees).(indice) in
let rec aux_recherche liste = match liste with
|[] -> false
|(k_liste,e_liste)::t when k_liste=k -> true
|(_,_)::t -> aux_recherche t
in
aux_recherche liste_indice;;

(* Q15 *)
let element t k =
let indice = t.hache(k) in
let liste_indice = (t.donnees).(indice) in
let rec aux_recherche liste = match liste with
|[] -> failwith "pas d'élément trouvé"
|(k_liste,e_liste)::t when k_liste=k -> e_liste
|(_,_)::t -> aux_recherche t
in
aux_recherche liste_indice;;

(* Q16 *)
let ajout t k e =
let indice=t.hache(k) in
let liste=(t.donnees).(indice) in
(t.donnees).(indice) <- (k,e)::liste;;

(* Q17 *)
let suppression t k =
let indice=t.hache(k) in
let liste_indice = (t.donnees).(indice) in
let rec aux_supp_couple renvoie liste_a_voir k = match liste_a_voir with
|[] -> List.rev renvoie;
|(a,b)::t when a=k -> aux_supp_couple (renvoie) t k;
|(a,b)::t -> aux_supp_couple ((a,b)::renvoie) t k;
in
(t.donnees).(indice) <- aux_supp_couple liste_indice liste_indice k;;