Programmes en Caml

Programmes en Caml(* Tri par sélection, page X *)
#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 initialise 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 main () =
let a = make_vect nMax 0 in
initialisation (a);
tri_sélection (a);
impression (a);
exit 0;;
(* Tri bulle, voir page X *)
let tri_bulle a =
let j = ref 0 in
let v = ref 0 in
for i = vect_length a - 1 downto 0 do
for j = 1 to i do
if a.(j-1) > a.(j) then let t = ref a.(j-1) in begin
a.(j-1) <- a.(j); a.(j) <- !t
end
done
done;;
(* Tri par insertion, voir page X *)
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);
decr j
done;
a.(!j) <- !v;
done;;
(* Tri Shell, voir page X *)
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;;
(* Recherche 1, voir page X *)
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, voir page X *)
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;;
exception Found of int;;

let bottin =
[| "paul", 2811;
"roger", 4501;
"laure", 2701;
"anne", 2702;
"pierre", 2805;
"yves", 2806
|];;

// Encore une autre manière d'écrire la fonction recherche
let recherche s bottin = begin
try
do_vect
(function nom, tel ->
if nom = s then raise (Found tel))
bottin;
raise Not_found
with Found t -> t
end;;

(* Lecture des données *)
while true do
printf "%d\n"
(recherche (input_line stdin) bottin)
done;;
(* Recherche dichotomique, voir page X *)
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);;
(* Insertion 1, voir page X *)
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, voir page X *)
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, voir page X *)
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;;
(* Insertion avec hachage, voir page X *)
let nom = make_vect nMax "";;
let tel = make_vect nMax 0;;
let col = make_vect nMax (-1);;

let n = ref 0;;

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

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

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