Chapitre 1

0em

#open "printf";;

let nmax = 10;;

let a = make_vect nmax 0;;

let initialisation () =
 for i = 0 to nmax - 1 do
  a.(i) <- random__int 100
 done;;

let impression () =
 for i = 0 to nmax - 1 do
  printf "%3d " a.(i)
 done;
 printf "\n";;

let tri_sélection* () =
 let min = ref 0 in
 for i = 0 to nmax - 2 do
  min := i;
  for j = i + 1 to nmax - 1 do
   if a.(j) < a.(!min) then min := j
  done;
  let t = a.(!min) in
  a.(!min) <- a.(i); a.(i) <- t
 done;;

let main () =
 (* On lit le tableau *)
 initialisation ();
 (* On trie *)
 tri_sélection* ();
 (* On imprime le résultat *)
 impression ();
 exit 0;;

(* Style plus Caml *)
let initialisation a =
 for i = 0 to vect_length a - 1 do
  a.(i) <- random__int 100
 done;;

let impression a =
 for i = 0 to vect_length a - 1 do
  print_int a.(i); print_string " ";
 done;
 print_newline();;

let tri_sélection* a =
 let min = ref 0 in
 for i = 0 to vect_length a - 2 do
  min := i;
  for j = i + 1 to vect_length a - 1 do
   if a.(j) < a.(!min) then min := j
  done;
  let t = a.(!min) in
  a.(!min) <- a.(i); a.(i) <- t
 done;;

let a = make_vect 10 0 in
 initialisation a;
 tri_selection* a;
 impression a;;

(* {\em Tri par insertion, voir page \pageref{prog:tri-insertion}} *)
let tri_insertion a =
 let j = ref 0 in
 let v = ref 0 in
 for i = 1 to vect_length a - 1 do
  v := a.(i); j := i;
  while !j > 0 && a.(!j - 1) > !v do
   a.(!j) <- a.(!j - 1);
   j := !j - 1
  done;
  a.(!j) <- !v;
 done;;

(* {\em Tri shell, voir page \pageref{prog:tri-shell}} *)
let tri_shell a =
 let h = ref 1 in
  while !h <= vect_length a - 1 do
   h := 3 * !h + 1
  done;
  while !h > 1 do
   h := !h / 3;
   for i = !h to vect_length a - 1 do
    if a.(i) < a.(i - !h) then begin
     let v = a.(i) in
     let j = ref i in
     while !j >= !h && a.(!j - !h) > v do
      a.(!j) <- a.(!j - !h);
      j := !j - !h
     done;
     a.(!j) <- v 
    end    
   done
  done;;

(* Avec une exception pour sortir de
   la boucle dès qu'on a trouvé *)
let bottin =
 [| "paul",   2811;
    "roger",  4501;
    "laure",  2701;
    "anne",   2702;
    "pierre", 2805;
    "yves",   2806 |];;

exception Found of int;;

let recherche s bottin =
 try 
  for i = 0 to vect_length bottin - 1 do
   let nom, tel = bottin.(i) in
   if nom = s then raise (Found tel)
  done;
  raise Not_found
 with Found tel -> tel;;

(* Recherche 3 *)
let bottin =
 [| "paul",   2811;
    "roger",  4501;
    "laure",  2701;
    "anne",   2702;
    "pierre", 2805;
    "yves",   2806;
    "",       0    |];;

let recherche s bottin =
 nom.(vect_length nom - 1) <- (s, 0);
 let i = ref 0 in
 while fst (bottin.(!i)) <> s do
  incr i
 done;
 if !i = vect_length bottin
 then raise Not_found
 else
  let _, tel = bottin.(!i) in tel;;

(* Lecture des données *)
while true do
 printf "%d\n"
  (recherche (input_line stdin) bottin) 
done;;

(* {\em Recherche dichotomique, voir page \pageref{prog:recherche-dichotomique}} *)
let nom =
 [| "anne"; "laure"; "paul";
    "pierre"; "roger"; "yves" |];;
let tel =
 [| 2702;   2701;    2811;
    2805;     4501;    2806 |];;

let recherche_dichotomique x =
 let g = ref 0
 and d = ref (vect_length nom - 1)
 and i = ref 0 in
 while x <> nom.(!i) && !g <= !d do
  i := (!g + !d) / 2;
  if x < nom.(!i) then d := !i - 1
  else g := !i + 1;
 done;
 if x = nom.(!i) then tel.(!i) else (-1);;

(* {\em Insertion 1, voir page \pageref{prog:insertion1}} *)
let n = ref 0;;

let insertion x val =
 if !n >= vect_length nom
  then failwith "Débordement de la table";
 nom.(n) <- x;
 tel.(n) <- val;
 incr n;;

(* Fonction de hachage *)
let n = vect_length nom - 1
and b = 128;;

let h s =
 let result = ref 0 in
 for i = 0 to string_length s - 1 do
  result :=
   (!result * b + (int_of_char (s.[i]))) mod n
 done;
 !result;;

(* Recherche avec hachage *)
let col = make_vect (vect_length nom)  (-1);;

let recherche x =
 let i = ref (h x) in
 while nom.(!i) <> x &&
       col.(!i) <> -1
 do i := col.(!i) done;
 if x = nom.(!i) then tel.(!i) else -1;;

(* {\em Insertion avec hachage, voir page \pageref{prog:insertion1}} *)
let nom = make_vect nmax "";;
let tel = make_vect nmax 0;;
let col = make_vect nmax (-1);;

let nNoms = ref n;;

let insertion x val =
 let i = h x in
 if nom.(i) = "" then begin
   nom.(i) <- x;
   tel.(i) <- val
 end else begin
 if !nNoms >= nmax
  then failwith "Débordement de la table"
  else begin
   nom.(!nNoms) <- x;
   (* On met la nouvelle entrée en tête *)
   (* de la liste des collisions *)
   (* de sa classe d'équivalence *)
   tel.(!nNoms) <- val;
   col.(!nNoms) <- col.(i);
   col.(i) <- !nNoms
  end;
 end;
 incr nNoms;;

(* Recherche avec adressage ouvert,
   {\em voir page \pageref{prog:recherche-hachage-ouvert}} *)
let recherche x =
 let i = ref (h x) in
 while nom.(!i) <> x && nom.(!i) <> "" do
   i := (!i + 1) mod nmax
 done;
 if nom.(!i) = x then tel.(!i) else -1;;

let insertion x val =
 if !nNoms > nmax
  then failwith "Débordement de la table";
 incr nNoms;
 let i = ref (h x) in
 while nom.(!i) <> x && nom.(!i) <> "" do
   i := (!i + 1) mod nmax
 done;
 nom.(!i) <- x;
 tel.(!i) <- val;;