我们定义了一个双向链表,格式如下:
我已经实现了一个添加头部的函数,代码如下:
请注意,为了实现add head,我使用了单例函数。
我的问题是当我尝试移除一个元素时,我正在尝试编写一个删除函数
到目前为止,这就是我所拥有的内容:
type 'a llist =
| Nil
| Cons of (float *'a) * 'a lcell * 'a lcell
and 'a lcell = ('a llist) ref
我已经实现了一个添加头部的函数,代码如下:
let add_head x head =
match !(!head) with
| Nil -> head := !(singleton x)
| Cons (e, previous, next) ->
let temp = Cons (x, ref Nil, !head) in
previous := temp;
head := previous;;
请注意,为了实现add head,我使用了单例函数。
let singleton (init: float * 'a): 'a lcell ref =
let l = ref (Cons (init, ref Nil, ref Nil)) in
let front = ref l in
front
我的问题是当我尝试移除一个元素时,我正在尝试编写一个删除函数
remove: (float -> bool) -> 'a lcell ref -> unit
,使得remove p head
删除第一个时间戳满足谓词p: float -> bool
的节点。如果没有节点的时间戳满足谓词,则列表应保持不变。到目前为止,这就是我所拥有的内容:
let remove p head =
let rec remove' ll =
match !ll with
| Nil -> head := !head
| Cons ( (d,_), previous, next) ->
if p d then
match (!previous, !next) with
| (Nil, Nil) -> head := ref Nil (* empty list*)
| (Nil, Cons ( d1, p1, n1)) -> (* this is the head, remove it and reassign head*)
head := next;
p1 := Nil
| (Cons ( d2, p2, n2), Cons ( d1, p1, n1)) -> (* this is middle, remove it and fix pointers of previous and next*)
n2 := !next;
p1 := !previous
| (Cons ( d1, p1, n1), Nil) -> (* this is tail, remove it and make previous one the tail*)
n1:= Nil
else remove' next
in
remove' !head
我在删除列表中间的项目(不是头部或尾部)时遇到问题。同时,我还遇到了删除多个元素的麻烦。有人可以帮我一下吗?我觉得我在匹配情况方面漏掉了什么。