вставить элемент в отсортированный связанный список

Question

нам пришлось реализовать функцию вставки, которая может вставлять ячейки в отсортированный связанный список.Моя идея реализации состояла в том, чтобы иметь два списка, называемых предыдущий и текущий, которые будут использоваться для перебора списка.В начале вызова функции предыдущий rlist будет содержать случайное целое число, а его следующее поле указывает на текущую ячейку, которая является главой связанного списка.Я думаю, что это проблематично.Я закончил реализацию своей идеи.Я думаю, что метод добавит правильное целое число в нужном месте в связанном списке.Тем не менее, если вставленный элемент находится в начале списка, то этот список остается старым при использовании отображения на экране, но старый список действительно имеет ячейку, указывающую на него, и эта ячейка имеет вставленное целое число,Так что я не знаю, как с этим справиться.Я проверил свой метод, и он не работает, как я описал.Вот что я сделал: вставил -9 в конец с3.с3 действительно получает -9 в конце списка.А потом я добавил 4 внутри с5.Но тогда с5 теперь становится [5; 4; -9].Так что это неправильно, вместо этого должно быть [5; 4; 3; 2; 1; -9].Так что я не знаю, что не так.

Я посмотрел в Интернете о том, как реализовать метод, чтобы они могли дать мне некоторое вдохновение или подсказку, но решения, которые они предоставляли, обычно на Java или других языках программирования.

type cell = { data : int; next : rlist}
and rlist = cell option ref 

let c1 = {data = 1; next = ref None}
let c2 = {data = 2; next = ref (Some c1)}
let c3 = {data = 3; next = ref (Some c2)}
let c5 = {data = 5; next = ref (Some c3)} 

let rec displayList (c : rlist) =
  match !c with
  | None -> []
  | Some { data = d; next = l } -> d :: (displayList l) 

let cell2rlist (c : cell) :rlist = ref (Some c) 

let bigger((x:int), (y:int)) = (x > y) 



let insert (comp : (int * int) -> bool) (item : int) (listt :rlist)=
  let itemm = {data=item ; next = ref None} in
  let rec helper (prev : rlist) (item : cell) (current: rlist) funcc =
    match !current with
    |None -> (match !prev with 
        |Some w -> w.next := (Some itemm))
    |Some q -> if comp (item.data, q.data) then (itemm.next := (Some q) ; match !prev with 
      |Some w -> w.next := (Some itemm))
        else  prev := !current; current:= !(q.next); (helper prev item current funcc)
  in let previous = ref (Some {data=0; next = listt}) in
  helper previous itemm listt comp

Вот примеры правильных возвращаемых значений для кода в действии:

 let l5 = cell2rlist c5;;
val l5 : rlist = ....
(* Messy display deleted. *)



 displayList l5;;
- : int list = [5; 3; 2; 1]


 displayList l5;;
- : int list = [5; 3; 2; 1]


 insert bigger 4 l5;;
- : unit = ()


 displayList l5;;
- : int list = [5; 4; 3; 2; 1]


 insert bigger 9 l5;;
- : unit = ()


 displayList l5;;
- : int list = [9; 5; 4; 3; 2; 1]


 insert bigger 0 l5;;
- : unit = ()


 displayList l5;;
- : int list = [9; 5; 4; 3; 2; 1; 0]

Но когда я запустил свои коды, вот что я получаю:

insert bigger 10 (ref(Some c5)) ;;
- : unit = ()

c5 ;;
- : cell =
{data = 5;
 next =
  {contents =
    Some
     {data = 3;
      next =
       {contents =
         Some
          {data = 2;
           next = {contents = Some {data = 1; next = {contents = None}}}}}}}}

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

Вот еще один пример,

insert bigger 4 (ref(Some c5)) ;;
- : unit = ()

c5 ;;
- : cell =
{data = 5;
 next =
  {contents =
    Some
     {data = 4;
      next = {contents = Some {data = 1; next = {contents = None}}}}}}

Итак, как вы видите, код вообще не работает, так как обновленный список должен иметь значения [5;4;3;2;1], но вместо него [5;4;1].

Вот еще один пример:

insert bigger (-9) (ref(Some c3)) ;;
- : unit = ()

c3 ;;
- : cell =
{data = 3;
 next =
  {contents =
    Some
     {data = 2;
      next =
       {contents =
         Some
          {data = 1;
           next = {contents = Some {data = -9; next = {contents = None}}}}}}}}

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

Answer 1

Для справки, вот сеанс, показывающий сбой вашего кода:

# let (l: rlist) = ref None;;
val l : rlist = {contents = None}
# insert bigger 1 l;;
- : unit = ()
# l;;
- : rlist = {contents = Some {data = 1; next = {contents = None}}}
# insert bigger 0 l;;
- : unit = ()
# l;;
- : rlist = {contents = None}

Для чего бы это ни стоило, было бы хорошо, если бы ваш код был с отступом.

Вво всяком случае, то, что я вижу, когда я смотрю на ваш код в течение короткого времени, это фрагмент:

current:= !(q.next);
helper prev item current funcc

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

Возможно, вы захотите что-то вроде этого:

helper prev item q.next funcc

Есть и другие проблемы в вашем коде.Например, кажется странным, что часть then заключена в скобки, а часть else не заключена в скобки.