SHARE
TWEET

Option info - TD6 Arbres, Piles et Files

csmine Jun 11th, 2019 97 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. type 'a arbre = Vide|Noeud of 'a * 'a arbre * 'a arbre;;
  2.  
  3. let exemple =
  4. Noeud(1,
  5.         Noeud(2,
  6.                 Noeud(4,Vide,Vide),
  7.                 Noeud(5,
  8.                         Noeud(8,Vide,Vide),
  9.                         Noeud(9,Vide,Vide)
  10.                         )),
  11.         Noeud(3,
  12.                 Noeud(6,Vide,Vide),
  13.                 Noeud(7,Vide,Vide)));;
  14.  
  15. (* Un parcours en largeur *)
  16.  
  17. let parcours_largeur arbre =
  18.     let rec auxparcours en_attente a_renvoyer = match en_attente with
  19.         | [] -> a_renvoyer
  20.         | Vide::t -> auxparcours t a_renvoyer
  21.         | Noeud (a,fg,fd)::t -> auxparcours (t@[fg]@[fd]) (a::(a_renvoyer))
  22.         in
  23.         List.rev(auxparcours [arbre] []);;
  24.  
  25.  
  26. (* Deux parcours en profondeur *)
  27.  
  28. let parcours_profondeur arbre =
  29.     let rec auxparcours arbre a_renvoyer = match arbre with
  30.     | Vide -> a_renvoyer
  31.     | Noeud (n,fg,fd) -> auxparcours fd (auxparcours fg (n::a_renvoyer))
  32.     in
  33.     List.rev(auxparcours arbre []);;
  34.  
  35. parcours_profondeur exemple;;
  36.  
  37. let parcours_profondeur_liste arbre =
  38.     let rec aux en_attente a_renvoyer = match en_attente with
  39.         | [] -> a_renvoyer
  40.         | Vide::t -> aux t a_renvoyer
  41.         | Noeud (a,fg,fd)::t -> aux (fg::fd::t) (a::(a_renvoyer))
  42.         in
  43.         List.rev(aux [arbre] []);;
  44.  
  45. parcours_profondeur_liste exemple;;
  46.  
  47.  
  48. (*
  49. La complexité dans le meilleur des cas est O(n) -> t toujours vide, donc linéaire
  50. La complexité dans le pire des cas est O(n²) -> on concatène, donc O(n) par appel.
  51. Il aurait fallu utiliser des files
  52. *)
  53.  
  54.  
  55.  
  56. (* TP 6 Structures de données *)
  57.  
  58. (* Exercice 1 *)
  59. Queue.create crée une nouvelle le, vide au départ. C'est donc l'implémentation de creer_le_vide.
  60. Queue.is_empty teste si une le est vide. C'est donc l'implémentation de est_vide.
  61. Stack.add permet d'emler un élément à la n d'une le. C'est donc l'implémentation de enler.
  62. Queue.take élimine le premier élément dans la le (effet de bord) et le retourne. Si la le est vide, cela provoque l'exception Empty. C'est donc l'implémentation de defiler;;
  63.  
  64.  
  65. (* Une première fonction qui transforme une 'a Queue en 'a liste, et inversément *)
  66.  
  67. let queue_into_list q =
  68. let l = ref [] in
  69. let condition = ref true in
  70. while !condition do
  71.     if (Queue.is_empty q) then condition:=false
  72.     else l:= (Queue.take q)::(!l)
  73.     done;
  74. List.rev(!l);;
  75.  
  76. let list_into_queue l =
  77. let rec aux l q = match l with
  78. |[] -> q
  79. |h::t -> begin (Queue.add h q);
  80.             aux t q;
  81.             end
  82. in aux l ( Queue.create () );;
  83.  
  84. queue_into_list (list_into_queue [1;2;3;4]);;
  85.  
  86.  
  87. (* On réadapte la fonction parcours_en_largeur sur des files ! *)
  88.  
  89. let parcours_largeur_file arbre =
  90.  
  91. let file = Queue.create () in
  92. Queue.add arbre file;
  93.  
  94. let rec aux a_renvoyer =
  95. if Queue.is_empty file then a_renvoyer
  96. else
  97. let arbre = Queue.take file in
  98. match arbre with
  99. |Vide -> aux (a_renvoyer)
  100. |Noeud (n,fg,fd) ->     begin
  101.                             Queue.add fg file;
  102.                             Queue.add fd file;
  103.                             aux (n::a_renvoyer);
  104.                             end
  105. in List.rev (aux []);;
  106.  
  107. parcours_largeur_file exemple;;
  108.  
  109.  
  110. (* Exercice 2.1 *)
  111.  
  112.  
  113. let stack_into_list s =
  114. let l = ref [] in
  115. let condition = ref true in
  116.  
  117. while !condition do
  118.  
  119. if Stack.is_empty s then condition:=false
  120. else l:=(Stack.pop s)::!l
  121. done;
  122. (List.rev !l);;
  123.  
  124.  
  125. let list_into_stack l =
  126. let s = Stack.create () in
  127.  
  128. let rec aux l = match l with
  129. |[] -> s
  130. |h::t -> (Stack.push h s);
  131.             aux t;
  132. in
  133. aux (List.rev l);;
  134.  
  135.  
  136. stack_into_list (list_into_stack [1;2;3;4]);;
  137.  
  138.  
  139.  
  140. (* Exercice 2.2 *)
  141.  
  142. type couleur = Bleue | Rouge and assiette = couleur * int ;;
  143.  
  144.  
  145.  
  146. let range_assiette pile =
  147.  
  148. let pile_rouge = Stack.create () in
  149. let pile_bleue = Stack.create () in
  150.  
  151.  
  152.  
  153. while not (Stack.is_empty pile) do
  154. let assiette = Stack.pop pile in
  155. match assiette with
  156. |(Bleue,a) -> Stack.push (Bleue,a) pile_bleue
  157. |(Rouge,a) -> Stack.push (Rouge,a) pile_rouge
  158. done;
  159.  
  160. while not (Stack.is_empty pile_bleue) do
  161. let assiette = Stack.pop pile_bleue in
  162. Stack.push assiette pile;
  163. done;
  164. while not (Stack.is_empty pile_rouge) do
  165. let assiette = Stack.pop pile_rouge in
  166. Stack.push assiette pile;
  167. done;;
  168.  
  169. let s = list_into_stack [(Bleue,5);(Rouge,6);(Bleue,7);(Rouge,9)];;
  170. range_assiette s;;
  171. stack_into_list s;;
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