1

我尝试使用所有常规操作（合并、删除最小等）实现“配对堆”，然后我被要求编写一个函数，该函数将使用我新构建的堆实现对列表进行排序。不幸的是，似乎出了点问题……

以下是相关代码：

(define (heap-merge h1 h2)
  (cond ((heap-empty? h1) h2)
    ((heap-empty? h2) h1)
    (else (let ((min1 (heap-get-min h1))
        (min2 (heap-get-min h2)))
        (if ((heap-get-less h1) min1 min2)
        (make-pairing-heap (heap-get-less h1) min1 (cons h2 (heap-get-subheaps h1)))
        (make-pairing-heap (heap-get-less h1) min2 (cons h1 (heap-get-subheaps h2))))))))

(define (heap-insert element h)
(heap-merge (make-pairing-heap (heap-get-less h) element '())
       h))

(define (heap-delete-min h)
(define (merge-in-pairs less? subheaps)
(cond
  ((null? subheaps) (make-heap less?))
  ((null? (cdr subheaps)) (car subheaps))
  (else (heap-merge (heap-merge (car subheaps) (cadr subheaps))
                            (merge-in-pairs less? (cddr subheaps))))))
(if (heap-empty? h) (error "expected pairing-heap for first argument, got an empty heap ")
  (merge-in-pairs (heap-get-less h) (heap-get-subheaps h)))) 

(define (heapsort l less?)
(let aux ((h (accumulate heap-insert (make-heap less?) l)))
(if (not (heap-empty? h))
     (cons (heap-get-min h) 
    (aux (heap-delete-min h))))))

这些是一些可以帮助您理解代码的选择器：

(define (make-pairing-heap less? min subheaps) 
(cons less? (cons min subheaps)))
(define (make-heap less?)
(cons less? '()))
(define (heap-get-less h)
(car h))
(define (heap-empty? h)
(if (null? (cdr h)) #t #f))

现在让我们来解决问题：当我运行“heapsort”时，它会返回带有“void”的排序列表，如您所见： 

> (heapsort (list 1 2 3) <)
(1 2 3 . #<void>)

..我该如何解决？

问候， Superguay

4

1 回答 1

2

由于这是作业，我将告诉您我用来查找错误的过程。如果您仍然卡住，请告诉我。

老实说，这是太多代码，无法在 Stack Overflow 问题中深入分析*。所以我必须使用输出中的线索。具体来说，您有一个包含空白的列表。它在最后，在一个不正确的列表中。这意味着两件事：

  1. 您有一个不返回值的函数。导致这种情况的两件事是 (1)if只用一个分支编写一个 -else分支将返回 void - 或 (2) 以 a 结束你的函数display，它返回 void。
  2. 你做的最后一件事是cons。您可能打算继续使用，或者您可能打算使用 '() 而不是正确结束列表。

所以：第一步是搜索所有使用的代码cons。你的选择器看起来不错。这留下了两个分支 inheap-merge和consin heapsort。所有三个调用都cons使用函数来获取它们的cdr.

所以：下一步是查看heap-get-subheaps并aux查看是否有任何一个具有不返回值的代码路径。也许您错误地留下了一些调试语句。或者也许你有一个if只有真正的分支而你忘记了错误的分支。

*注意：大多数方案的调试功能非常少，因此启发式是你最好的选择。这是后天习得的技能。

于 2010-04-09T13:26:24.100 回答