Ocaml - 从双向链表中删除中间节点

Question

我正在尝试从双向链表中删除一个元素，该元素基于该列表中的节点是否满足返回布尔值的函数。 由于某种原因，替换节点的上一个指针(已删除的下一个(不会更新，而是引用回自身。

我的代码

(* The type of linked lists. *)
type 'a llist =
| Nil
| Cons of (float * 'a) * 'a lcell * 'a lcell
and 'a lcell = ('a llist) ref
let remove p head =
let rec remove' ll =
match !ll with
|Nil -> head := !head (*no node match*)
|Cons ((a, _), c, d) -> 
if p a then
match (!c, !d) with
|(Nil, Nil) -> head := ref Nil (*singleton match*)
|(Cons(_, c', d'), Nil) -> (*last node match*)
d' := Nil 
|(Nil, Cons(_, c', d')) -> (*first node match*)
head := d;
c':= Nil
|(Cons(_, _, d'), Cons(_, e', _))-> (*middle match; Does not work*)
e' := !c;
d' := !d
else
remove' d
in
remove' !head

测试结果

Initial value of head is
{contents =
@1:{contents =
Cons ((-1.689, 3),
@2:{contents = Nil},
@3:{contents =
Cons ((0.910, -1),
<@1>,
@4:{contents =
Cons ((0.647, 3),
<@3>,
@5:{contents =
Cons ((4.531, -1),
<@4>,
@6:{contents = Nil})})})})}}
Calling remove (fun x -> close x 0.646639313413) head (*close compares values accuracy up to two decimal digits*)
The value of head is now
{contents =
@1:{contents =
Cons ((-1.689, 3),
@2:{contents = Nil},
@3:{contents =
Cons ((0.910, -1),
<@1>,
@4:{contents =
Cons ((4.531, -1), <@4>, @5:{contents = Nil})})})}}

Answer 1

所以，这是正在发生的事情：

我们有内存块 M1、M2、M3：

• M1 包含对象 Cons((v1， x1(， l1， M2( = Cons(_， _， d'(;

• M2 包含对象 Cons((v2， x2(， M1， M3( = Cons(_， c， d(;

• M3 包含对象 Cons((v3， x3(， M2， r3( = Cons(_， e'， _(;

然后，当我们做e' := !c; d' := !d时，我们正在做的是：

• *M2 = *M1 ：在 M1 中复制对象，并将其存储在 M2 中;

• *M2 = *M3 ：在 M3 中复制对象，并将其存储在 M2 中;

因此，我们得到的结果是：

• M1 包含对象 Cons((v1， x1(， l1， M2(;

• M2 包含对象 Cons((v3， x3(， M2， r3(;

• M3 包含对象 Cons((v3， x3(， M2， r3(;

这是我们在测试中看到的结果。

要正确更改链表，我们可以做的是在 M2 中创建一个新对象，该对象的值存储在 M3 中，但使用更新的左指针(另一种选择是在 M1 和 M3 中创建新对象(。

这就是我要做的：

let remove p head =
let aux node_ref =
match !node_ref with
| Nil -> ()
| Cons((k, _), l, r) ->
if p k then
node_ref := (
match !r with
| Nil -> Nil
| Cons((nk, nx), nl, nr) -> Cons((nk, nx), l, nr)
)
else
aux r
in
aux head