该代码正在运行,没有任何错误,但未按预期输出。
class Node
attr_accessor :data, :next
def initialize(value)
@data = value
@next = nil
end
end
合并排序方法:
def mergesort(head)
return head if !head || !head.next
a, b = frontbacksplit(head)
mergesort(a)
mergesort(b)
c = sortedmerge(a, b) #something is going wrong here
end
此方法用于将列表分为两个子列表:
def frontbacksplit(head)
slow = head
fast = head.next
until fast.nil?
fast = fast.next
unless fast.nil?
slow = slow.next
fast = fast.next
end
end
a = head
b = slow.next
slow.next = nil
[a, b]
end
此方法可能有误:
def sortedmerge(a, b)
result = nil
if a.nil?
return b
elsif b.nil?
return a
end
if a.data <= b.data
result = a
result.next = sortedmerge(a.next, b)
else
result = b
result.next = sortedmerge(a, b.next)
end
result
end
问题出在mergesort
方法上。原始实现定义为:
void MergeSort(Node** headRef)
{
...
MergeSort(&a);
MergeSort(&b);
*headRef = SortedMerge(a, b);
}
这意味着它正在改变的内容a
和b
。
由于Ruby没有这种通过引用语义进行调用的方法,因此您只是忘记了将结果分配回Ruby版本a
和b
在Ruby版本中重复这种行为。
解决方法:
def mergesort(head)
...
a = mergesort(a)
b = mergesort(b)
sortedmerge(a, b)
end
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句