Удаление всех вхождений элемента из связанной очереди

Question

Мне было поручено создать функцию, которая удаляет все вхождения ключа в связанной очереди, определенной как:

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

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

Я пришел с кодом, приведенным ниже, который проходит тесты I 'мы создали для пустой очереди и очереди только с одним элементом по тайм-ауту, когда в очереди есть несколько элементов с одним вхождением ключа в очередь.

let delete (elt: 'a) (q: 'a queue) : unit =
if not (valid q) then failwith "delete: given invalid queue";
let rec loop (qn: 'a qnode option) (qn2: 'a qnode option) (elt: 'a) : unit =
  begin match qn, qn2 with
  | None, None -> ()
  | None, Some x   -> if x.v = elt && x.next = None then
                      (q.head <- x.next; q.tail <- x.next)
                      else if x.v = elt && x.next <> None then
                      (q.head <- x.next; q.tail <- x.next; loop x.next q.tail elt)
                      else loop x.next q.tail elt
  | Some x, Some y -> if y.v = elt && y.next = None then 
                      (x.next <- y.next; q.tail <- y.next)
                      else if y.v = elt && y.next <> None then 
                      (x.next <- y.next; q.tail <- y.next; loop y.next q.tail elt)
                      else loop y.next q.tail elt
  | Some x, None -> ()
  end
in loop None q.head elt

У меня проблемы с поиском, где именно яможет иметь бесконечный цикл или неэффективную реализацию, поэтому любая помощь будет оценена по достоинству.

Answer 1

Основной план для вашего цикла - разрешить qn2 диапазон во всех узлах очереди.При каждом вызове qn представляет узел, предшествующий qn2 в очереди.Этот предыдущий узел необходим для правильного обновления ссылок, когда вы находите интересующие вас узлы.

Когда qn2 является первым узлом очереди, предыдущего узла нет.Таким образом, qn должно быть None в этом случае.

Для каждого вызова нужно подумать о двух вещах: во-первых, какую обработку сделать на узле qn2.Возможно, он удален или не удален.

Во-вторых, как перейти к следующему узлу очереди.Другими словами, как должен выглядеть рекурсивный вызов?Вам нужно передать узел "prev" (который будет новым qn) и текущий узел (новый qn2).

Давайте сосредоточимся на этой второй части проблемы, на спецификерекурсивный вызов.Предположим, что qn2 не является None, т. Е. Что есть узел, на который нужно посмотреть.Вы должны увидеть, что если qn2 удалено, то текущий qn также будет узлом prev для следующего вызова.Если qn2 не удален, сам qn2 будет узлом prev для следующего вызова.В любом случае поле next узла qn2 будет новым узлом для просмотра (qn2 для следующего вызова).

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

Кроме того, если очередь не пуста, тогда q.tail всегда будет узлом (не None).Следовательно, цикл никогда не прекратится.