Ocaml - удаление среднего узла из двусвязного списка - PullRequest
Новая
       17

Ocaml - удаление среднего узла из двусвязного списка

1 голос
/ 17 октября 2019

Я пытаюсь удалить элемент из двусвязного списка, основываясь на том, удовлетворяет ли узел в этом списке функции, возвращающей логическое значение. По какой-то причине предыдущий указатель замещающего узла (следующий из удаленных) не обновляется, а вместо этого ссылается на себя.

Мой код 

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

1 Ответ

1 голос
/ 20 октября 2019

Итак, вот что происходит:

У нас есть блоки памяти 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
...