Удаление с использованием очередей связанных списков в OCAML - PullRequest
Новая
       27

Удаление с использованием очередей связанных списков в OCAML

0 голосов
/ 21 февраля 2019

Я пытаюсь реализовать односвязный список (очередь) в OCAML, что очень сложно и не так интуитивно понятно, как я думал.Позвольте мне сначала указать инварианты очереди, которую я реализую: 

q.head and q.tail are either both None, or
   - q.head and q.tail both point to Some nodes, and
     - q.tail is reachable by following 'next' pointers
       from q.head
     - q.tail's next pointer is None.

Очереди и связанные с ними узлы объявлены с использованием параметров следующим образом: 

type 'a qnode = { v: 'a;
                    mutable next: 'a qnode option }

  type 'a queue = { mutable head: 'a qnode option;
                    mutable tail: 'a qnode option }

У меня много тестовслучаи, но в первую очередь происходит сбой: 

let test (): bool = 
  let q = from_list [5; 6; 7] in
  delete 5 q;
  valid q && to_list q = [6; 7]
;; run_test "delete element from front of queue" test

Valid () просто проверяет, удовлетворяет ли очередь инвариантам.И вот моя реализация: 

let delete (elt: 'a) (q: 'a queue) : unit =
    if not (valid q) then failwith "delete: given invalid queue";
    let rec loop_delete (elt: 'a) (no: 'a qnode option) : unit = 
      begin match no with 
      |None -> ()
      |Some n -> (*Item to delete is only item in queue*)
               if n.v = elt && n.next = None then 
               (q.head <- None; q.tail <- None) 
               else if n.v = elt && n.next = Some n 
               then (q.head <- n.next; n.next <- None) else loop_delete elt n.next
      end
    in loop_delete elt q.head

Почему n.next не обновляется надлежащим образом?Более того, я уверен, что в моей реализации много других проблем.Любая помощь приветствуется.

РЕДАКТИРОВАТЬ:

В соответствии с предложениями ниже, я сделал следующие корректировки.Комментарии указывают на оставшиеся недоразумения. 

let delete (elt: 'a) (q: 'a queue) : unit =
    if not (valid q) then failwith "delete: given invalid queue";
    let rec loop_delete (elt: 'a) (prev: 'a qnode option) 
    (curr: 'a qnode option) : unit = 
      begin match prev, curr with 
      |_, None -> ()
      |None, Some n -> if n.v = elt && n.next = None then (q.head <- None; q.tail <- None) (*One element in list only...right??*)
      else if n.v = elt && n.next != None then (*How to continuously update prev and curr??* else ()
      |Some n, Some n1 -> (*??*)
      end
    in loop_delete elt None q.head

1 Ответ

0 голосов
/ 21 февраля 2019

(Извините, мой предыдущий ответ был неверным. Я пропустил, что вы используете q непосредственно в своей вспомогательной функции.)

Ваша функция loop_delete ищет соответствующий узел, но когда находитСоответствующий узел, кажется, делает необоснованные предположения.Если соответствующий узел n находится в конце очереди (n.next = None), он предполагает, что это был единственный элемент очереди (он устанавливает q.head и q.tail в None).Если совпадающий узел не находится в конце очереди, кажется, предполагается, что совпадающий узел был в начале очереди (он устанавливает q.head в n.next).

В качестве отдельногопроблема, это не разумный тест: 

n.next = Some n

Он проверяет, указывает ли указатель next на n на n.Если вы просто хотите узнать, указывает ли n.next на какой-либо узел, вы можете сказать n.next <> None.

В качестве еще более общего комментария при удалении из односвязного списка вам, как правило, необходимо отслеживать два узла.интересующий вас узел и предыдущий узел в списке.Когда вы найдете узел, который хотите удалить, вам нужно изменить значение next предыдущего узла.

Вам не нужно думать о указателях при кодировании в OCaml, но это не так уж и неправильно.воспринимать None как нулевой указатель и Some n как указатель на узел n.Для первого вызова у вас нет предыдущего узла, поэтому вызов может выглядеть следующим образом: 

loop_delete elt None q.head

Когда вы хотите перейти к следующему узлу внутри loop_delete, вызов может выглядеть примерно так:this: 

loop_delete elt no n.next

По сути вы передаете два значения типа 'a qnode option.Они представляют предыдущий узел и текущий узел.Если предыдущего узла нет, то это потому, что вы находитесь в начале списка.Если текущего узла нет, то это потому, что вы находитесь в конце списка.

Извините за бесполезные комментарии ранее.Может быть, это немного лучше.

...