常见的LISP合并排序分解
-
14-11-2019 - |
题
我已经挑战自己在常见的LISP中做我的算法类中的所有作业。我是学习丽斯的一天,我遇到了一个障碍。
赋值是在获得任意子集长度(Timsort)时,创建一个合并转换为插入的合并排序。插入部分完美地工作,但在程序必须分割两次时,合并的分割部分仅适用。我知道它必须用Lisp中的工作方式表明,我太新了,无法确定问题。
我认为它要么击中无限循环......我不确定,因为当我用调试语句运行它时,它们永远不会在集合有太多元素时打印。
我不是在这里乞求具体的答案,也不在这里写下我的代码。也许一个解释或正确方向的点会有所帮助!
我的代码:
;; Insertion sort method call (returns sorted list)
(defun insert-sort (lst) ... )
;; Merge sort method call
(defun merge-sort (lst)
(print 'Merge)
(print lst)
(if (< (length lst) 7) ; Check to see if list is small enough to insert sort
(insert-sort lst) ; Do so
(progn ; else
(setf b (merge-split lst)) ; Split the list, store into b
(setf (car b) (merge-sort (car b))) ; Merge sort on first half
;; --- I think it's happening here ---
(setf (cdr b) (merge-sort (cdr b))) ; Merge sort on second half
(merge 'list (car b) (cdr b) #'<)))) ; Merge the two lists together (using API)
;; Split a list into two parts
(defun merge-split (lst)
(progn
(setf b lst) ; Set b to first index
(setf a (cdr lst)) ; Set a to the rest of the list
(loop while a do ; Loop while a != null
(setf a (cdr a)) ; Make a equal next list node
(if a ; If it still exists
(progn
(setf a (cdr a)) ; Inc a again
(setf b (cdr b))))) ; Also inc b (b should always be half of a)
(setf a (cdr b)) ; Set a to the list after b
(setf (cdr b) NIL) ; Delete link after b
(cons lst a))) ; Return in a cons
.
注意:这是我写的代码,没有得到互联网......你可以告诉虽然哈哈
解决方案
您被动态范围的变量被咬伤。您第一次调用setf设置a,b您隐式创建全局,动态范围范围。使用让不要声明它们。让您允许您包含要执行的表达式列表,就像预报一样,所以我的提示是您可以通过将2个预报更改为LETS来解决此问题。如果您需要更多,请告诉我,以便unstuck。
不隶属于 StackOverflow