#racket
Вопрос:
Определите процедуру СХЕМЫ с именем (сортировка по дереву l), которая берет список чисел и выводит тот же список, но в отсортированном порядке. Ваша процедура должна отсортировать список, (а) вставив числа в двоичное дерево поиска, а затем (б) извлекая из двоичного дерева поиска список элементов в отсортированном порядке. Для начала напишите процедуру под названием (insert-list L T), которая берет список чисел L и двоичное дерево поиска T и возвращает дерево, которое получается путем вставки всех чисел из L в T. (Сначала поместите аргумент L, поэтому вызов вашей функции должен иметь форму (вставка-список L T), где L-список, а T — (возможно, пустое) двоичное дерево поиска.) Затем напишите функцию sort-extract, которая берет двоичное дерево поиска и выводит элементы дерева в отсортированном порядке. (Мы делали это в классе!) Наконец, соедините эти две функции вместе для достижения (сортировка по дереву l). (Обратите внимание, что все три эти функции будут классифицированы, поэтому ваши решения должны состоять из трех функций верхнего уровня: вставка-список, сортировка-извлечение и сортировка по дереву.)
(define (insert-list insert-elements T)
(if (null? insert-elements)
T
(insert-list (cdr insert-elements)
(insert-list (car insert-elements) T))))
(insert-list (list 12) (list 15 (list) (list)))
mcdr:
ожидаемое нарушение контракта: mpair?
дано: 12
Комментарии:
1. Предполагается, что вы должны реализовать другую функцию, которая вставляет только один элемент, а затем использовать его в
insert-list.
Ответ №1:
Вы получаете нарушения контракта, потому что звоните insert-list с car номером 12. Так как это не null? так, вы попытаетесь сделать car и cdr из этого. Что такое cdr число 12?
Также мне кажется странным, что вы не вызываете процедуру для добавления элемента в дерево из insert-list . Я не могу придумать ни одной веской причины для объединения этих двух процедур в одну.
Если у вас была процедура, которая принимает значение и дерево и возвращает дерево с добавленной стоимостью, вы можете сделать это:
(define (insert-list lst tree)
(foldl insert tree lst))
Напр..
(insert-list '(5 2 4) '()) ; ==>
(insert 4 (insert 2 (insert 5 '())))