SHARE
TWEET

Option info - TP8 Tables de hachage

csmine Jun 25th, 2019 72 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. (* SUJET CENTRALE OPTION INFO 2018 *)
  2.  
  3.  
  4. (* Les listes contiennent ici des couples d'éléments de [| 0,N-1 |] *)
  5.  
  6.  
  7.  
  8.  
  9. let _N=10;;
  10.  
  11. (* Q12 *)
  12. let hachage_liste w q =
  13. (* q est une liste qu'il faut hacher.
  14. Pour cela, on évalue le polynôme donné en N. *)
  15. (* N est variable globale *)
  16.  
  17. let rec aux_somme liste compteur_i = match liste with
  18. |[] -> 0
  19. |(a1,a2)::t ->
  20. (a1 + a2*_N) + _N*(aux_somme t (compteur_i+1));
  21.  
  22. in
  23.  
  24. (aux_somme q 0) mod w;;
  25.  
  26. let w = 997;;
  27.  
  28.  
  29. type ('a,'b) table_hachage =
  30. {hache: int -> int;
  31. donnees: ('a * 'b) list array;
  32. largeur: int};;
  33.  
  34. let fonction (x:int) = (x:int);;
  35. let aaaa = {hache = fonction; donnees = [|[]|]; largeur = 5};;
  36.  
  37. (* Q13 *)
  38. let creer_table h w =
  39. {hache = h; donnees = Array.make w []; largeur = w};;
  40.  
  41. let t=[|2;3|];;
  42.  
  43. (* Q14 *)
  44. let recherche t k =
  45. let indice = t.hache(k) in
  46. let liste_indice = (t.donnees).(indice) in
  47. let rec aux_recherche liste = match liste with
  48. |[] -> false
  49. |(k_liste,e_liste)::t when k_liste=k -> true
  50. |(_,_)::t -> aux_recherche t
  51. in
  52. aux_recherche liste_indice;;
  53.  
  54. (* Q15 *)
  55. let element t k =
  56. let indice = t.hache(k) in
  57. let liste_indice = (t.donnees).(indice) in
  58. let rec aux_recherche liste = match liste with
  59. |[] -> failwith "pas d'élément trouvé"
  60. |(k_liste,e_liste)::t when k_liste=k -> e_liste
  61. |(_,_)::t -> aux_recherche t
  62. in
  63. aux_recherche liste_indice;;
  64.  
  65. (* Q16 *)
  66. let ajout t k e =
  67. let indice=t.hache(k) in
  68. let liste=(t.donnees).(indice) in
  69. (t.donnees).(indice) <- (k,e)::liste;;
  70.  
  71. (* Q17 *)
  72. let suppression t k =
  73. let indice=t.hache(k) in
  74. let liste_indice = (t.donnees).(indice) in
  75. let rec aux_supp_couple renvoie liste_a_voir k = match liste_a_voir with
  76. |[] -> List.rev renvoie;
  77. |(a,b)::t when a=k -> aux_supp_couple (renvoie) t k;
  78. |(a,b)::t -> aux_supp_couple ((a,b)::renvoie) t k;
  79. in
  80. (t.donnees).(indice) <- aux_supp_couple liste_indice liste_indice k;;
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top