pour une fois, c'est moi qui poserais les questions...
je cherche à construire une liste doublement chainée modifiable, afin de pouvoir partager l'espace mémoire des différences listes intermédiaires, et bénéficier de la concaténation en temps constant
en revanche, j'ai un petit soucis en ce qui concerne le parcours d'une telle liste... comment faire pour avoir déterminer qu'on est revenu au début ?
j'ai tenté un test d'égalité sur la première cellule, mais étant donné la structure cyclique, le test caml plante avec un joli Out_of_memory (on boucle infiniment dans le test )
pour infos, dans un langage comme C, j'aurais utilisé l'adresse de la première cellule pour comparer, mais ici, je ne vois pas comment m'y prendre
Code ocaml : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63 (* vim:set ts=4 sw=4: *) type 'a cellule = {head : 'a; mutable next : 'a liste; mutable prev : 'a liste} and 'a liste = Nil | Liste of 'a cellule ;; let cons a l = let res = {head=a ; next=l; prev=Nil} in let p = match l with Nil -> Liste(res) |Liste(c) -> c.prev in let _ = res.prev <- p in let _ = match l with Nil -> () |Liste(c) -> c.prev <- Liste(res) in let _ = if res.next = Nil then res.next <- Liste(res) in Liste(res) ;; let concat l1 l2 = match (l1,l2) with (Nil,_) -> l2 |(_,Nil) -> l1 |(Liste(c1),Liste(c2)) -> let Liste(c1_p) = c1.prev in let Liste(c2_p) = c2.prev in c1_p.next <- l2 ; c2.prev <- Liste(c1_p) ; c2_p.next <- l1 ; c1.prev <- Liste(c2_p) ; l1 ;; let rec print print_elt l = let first = match l with Nil -> {head=0;next=Nil;prev=Nil} |Liste(c) -> c in let rec aux l = match l with Nil -> print_string "nil" |Liste(c) -> print_elt (c.head); print_string " "; aux (c.next) in aux l ; print_newline () ;; let main () = let l = Nil in print print_int l ; let l1 = (cons 2 l) in let l2 = (cons 3 l) in print print_int (concat l1 l2) ;; main ();;
par avance
Partager