Download pointeurs-corrige.pdf

Contents : (* ******************************************************************************* *) (* Tas de Tarjan / union find *) type element Representant Reductible of int type classes element array let isoles n Array.make n Representant let rec find classes elt match classes.(elt) with Representant elt Reductible i let representant find classes i in classes.(elt) Reductible representant representant let union classes elt1 elt2 let r1 find classes elt1 in let r2 find classes elt2 in if r1 r2 then classes.(r1) Reductible r2 (* test *) let foo isoles 10 union foo 6 3 foo union foo 3 0 foo union foo 9 6 foo union foo 8 5 foo union foo 5 2 foo find foo 8 foo (* version recursive terminale de find *) let find classes elt let rec find rec elt accu match classes.(elt) with Representant List.iter (fun i classes.(i) Reductible elt) accu elt Reductible i find rec i (elt :: accu) in find rec elt (* ********************************************************************** *) (* Arbre aleatoire *) type tree Leaf Node of tree * tree let random tree vect n let result Array.make (2*n +1) None in result.(0) Some (1 2) for i 1 to pred n do let index Random.int (2*i +1) in let node result.(index) in if Random.bool () then (result.(2*i +1) None result.(2*i +2) node) else (result.(2*i +1) node result.(2*i +2) None) result.(index) Some (2*i+1 2*i+2) done result let tree of vect v let rec parcours i match v.(i) with None Leaf Some (j k) Node (parcours j parcours k) in parcours 0 let random tree n tree of vect (random tree vect n) #load "graphics.cma" #load "draw tree.cmo" let rec ab of tree function Leaf Draw tree.Feuille () Node (a b) Draw tree.Noeud (() ab of tree a ab of tree b) let Graphics.open graph " 1024x768" for i 1 to 10 do Graphics.clear graph () Draw tree.drawt points (ab of tree (random tree 700)) ignore (Graphics.read key ()) done Graphics.close graph () (* ********************************************************************** *) (* Listes doublement chainees *) type a cell mutable a: a mutable prec: a cell option mutable suiv: a cell option type a liste mutable deb: a cell option mutable fin: a cell option exception Empty let empty () deb None fin None let singleton elt let cell Some a elt prec None suiv None in deb cell fin cell let add deb liste elt match liste.deb with None assert (liste.fin None) let cell Some a elt prec None suiv None in liste.deb cell liste.fin cell Some deb let cell Some a elt prec None suiv liste.deb in deb.prec cell liste.deb cell let add fin liste elt match liste.fin with None assert (liste.deb None) let cell Some a elt prec None suiv None in liste.deb cell liste.fin cell Some fin let cell Some a elt prec liste.fin suiv None in fin.suiv cell liste.fin cell let take deb liste match liste.deb with None raise Empty Some a result suiv s liste.deb s (match s with Some cell cell.prec None None liste.fin None) result let take fin liste match liste.fin with None raise Empty Some a result prec p liste.fin p (match p with Some cell cell.suiv None None liste.deb None) result let to list let rec to list cell accu function prec Some prec a a to list cell (a::accu) prec prec None a a a::accu in function fin None fin Some fin to list cell fin let rec of list function empty () a::q let result of list q in add deb result a result (* version recursive terminale: *) let of list liste let rec of list accu function accu a::q add fin accu a of list accu q in of list (empty ()) liste let rev liste liste let rec rev cell option function None () Some ( suiv s as c) c.suiv c.prec c.prec s rev cell option s in let deb liste.deb in rev cell option deb liste.deb liste.fin liste.fin deb let a add deb add deb to list empty () in a 3 add fin a 4 a 2 add deb a 1 a let b singleton 42 in add deb b 12 add deb b 12 Printf.printf "%i n%!" (take fin b) add fin b 32 Printf.printf "%i %i n%!" (take deb b) (take deb b) to list b let c of list 1 2 3 4 5 in add deb c 0 to list c let d of list 0 1 2 3 4 5 in rev liste d to list d

INFO HASH : 4bca4ff31d5c0285073842e4e4016fc6e84933d6

Download now

File Size: 11.5 kb