从双链表中删除中间节点

Question

我试图从基于阉羊的双链表中删除一个元素，该列表中的节点满足返回bool的函数。由于某种原因，替换节点的前一个指针（下一个被删除）不更新，而是引用回它自己。

我的代码

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

>

M2包含对象Cons（（v2， x2）， M1， M3）=Cons（_， c， d）；

M3包含对象Cons（（v3，x3），M2，r3）=Cons（u，e'，u）；

然后，当我们做e'：=！Cd'：=！d，我们正在做的是：

>

*M2=*M3：以M3为单位复制对象，并以M2为单位存储；

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

>

M1包含对象Cons（（v1，x1），l1，M2）；

M2包含对象Cons（（v3，x3），M2，r3）；

M3包含对象Cons（（v3，x3），M2，r3）；

这是我们在html" target="_blank">测试中看到的结果。

要正确更改链表，我们可以在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