1

すべての通常の操作（merge、delete-minなど）で「ペアリングヒープ」を実装しようとしましたが、新しく構築したヒープ実装を使用してリストを並べ替える関数を作成するように要求されました。残念ながら、何かがうまくいかないようです...

関連するコードは次のとおりです。

(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>)

..どうすれば修正できますか？

よろしく、スーパーグアイ

4

1 に答える 1

2

これは宿題なので、バグを見つけるために使用したプロセスを説明します。まだ行き詰まっている場合はお知らせください。

正直なところ、これは Stack Overflow の質問で詳細に分析するにはコードが多すぎます*。したがって、出力からの手がかりを使用する必要があります。具体的には、空欄のあるリストがあります。そして、それは不適切なリストの最後にあります。これは、次の 2 つのことを意味します。

  1. 値を返さない関数があります。これを引き起こす 2 つの原因は、(1)ifブランチを 1 つだけ使用して を作成する (elseブランチは void を返す)、または (2) displayvoid を返す で関数を終了することです。
  2. あなたが最後にしたことは、cons. コンスを続けるつもりだったのかもしれませんし、リストを適切に終わらせるために '() をコンスするつもりだったのかもしれません。

したがって、最初のステップは、 のすべての使用についてコードを検索することですcons。あなたのセレクターはうまく見えます。heap-mergeこれにより、 inとconsinの 2 つのブランチが残りheapsortます。cons関数を使用してcdr.

したがって、次のステップは、値を返さないコード パスがあるかどうかを確認することですheap-get-subheaps。aux誤ってデバッグ ステートメントが残っている可能性があります。またはif、true ブランチしかない があり、false ブランチを忘れている可能性があります。

*注意: ほとんどのスキームにはデバッグ機能がほとんどないため、とにかくヒューリスティックが最善の策です。習得スキルです。

于 2010-04-09T13:26:24.100 に答える