我正在尝试基于列表中的节点是否满足返回布尔值的函数,从双向链接列表中删除元素。由于某种原因,替换节点的前一个指针(已删除节点的下一个)不会更新,而是指向自身。
我的密码
(* 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] 删除。
我来说两句