Ocaml

Question

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

我的代码

(* 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

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

Ocaml - Removing middle node from doubly-linked list

linked-list

doubly-linked-list