(1 2 3. # <void>) - порт - PullRequest
Новая
       19

(1 2 3. # <void>) - порт

1 голос
/ 09 апреля 2010

Я попытался реализовать «кучу сопряжения» со всеми обычными операциями (слияние, удаление-минут и т. Д.), Затем меня попросили написать функцию, которая будет сортировать список, используя мою недавно созданную реализацию кучи. К сожалению, кажется, что что-то идет не так ...

Вот соответствующий код: 

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

.. КАК Я МОГУ УСТАНОВИТЬ ЕГО?

С уважением, Супергвай

1 Ответ

2 голосов
/ 09 апреля 2010

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

Честно говоря, это слишком много кода для * глубокого анализа в вопросе переполнения стека. Поэтому я должен использовать подсказки из вывода. В частности, у вас есть список с пустотой в нем. И это в конце, в неправильном списке. Это означает две вещи:

  1. У вас есть функция, которая не возвращает значение. Это вызвано двумя причинами: (1) написание if только с одной веткой - ветвь else вернет void - или (2) завершением вашей функции display, которая возвращает void.
  2. Последнее, что вы сделали, было cons. Возможно, вы хотели сохранить или, возможно, хотели использовать '() вместо того, чтобы правильно завершить список.

Итак: первый шаг - поиск кода для всех случаев использования cons. Ваши селекторы выглядят хорошо. Это оставляет две ветви в heap-merge и cons в heapsort. Все три вызова cons используют функции для получения cdr.

Итак: следующий шаг - посмотреть на heap-get-subheaps и aux, чтобы увидеть, есть ли у одного из путей кода, который не возвращает значение. Возможно, у вас есть некоторые отладочные сообщения, оставленные по ошибке. Или, может быть, у вас есть if, который имеет только истинную ветвь, и вы забыли ложную ветвь.

* Примечание. Большинство схем имеют так мало функций отладки, что эвристика в любом случае является вашим лучшим выбором. Это приобретенный навык.

...