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

诺姆·苏伊萨(Noam Suissa)

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

我的密码

(* 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})})})}}
佩德罗·弗莱雷

所以,这是正在发生的事情:

我们有内存块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

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章