(define ql (make-queue))

(insert-queue! ql a) ((a) a)

(insert-queue! ql b) ((a b) b)

(delete-queue! ql)

((b) b)

(delete-queue! ql)

(() b)

«Ничего не работает! - жалуется он. - Ответ интерпретатора показывает, что последний элемент попадает в очередь два раза. А когда я оба элемента уничтожаю, второе b по-прежнему там сидит, так что очередь не становится пустой, хотя должна бы». Ева Лу Атор говорит, что Бен просто не понимает, что происходит. «Дело не в том, что элементы два раза оказываются в очереди, - объясняет она. - Дело в том, что стандартная лисповская печаталка не знает, как устроено представление очереди. Если ты хочешь, чтобы очередь правильно печаталась, придется написать специальную процедуру распечатки очередей». Объясните, что имеет в виду Ева Лу. В частности, объясните, почему в примерах Бена на печать выдается именно такой результат. Определите процедуру print-queue, которая берет на входе очередь и выводит на печать последовательность ее элементов.

Упражнение 3.22.

Вместо того, чтобы представлять очередь как пару указателей, можно построить ее в виде процедуры с внутренним состоянием. Это состояние будет включать указатели на начало и конец обыкновенного списка. Таким образом, make-queue будет иметь вид

(define (make-queue) (let ((front-ptr ...) (rear-ptr ...)) (определения внутренних процедур) (define (dispatch m) ...) dispatch))

Закончите определение make-queue и реализуйте операции над очередями с помощью этого представления.

Упражнение 3.23.

Дек (deque, double-ended queue, «двусторонняя очередь») представляет собой последовательность, элементы в которой могут добавляться и уничтожаться как с головы, так и с хвоста. На деках определены такие операции: конструктор make-deque, предикат empty-deque?, селекторы front-deque и rear-deque, и мутаторы frontinsert-deque! , rear-insert-deque! , front-delete-deque! и rear-delete-deque! . Покажите, как представить дек при помощи пар, и напишите реализацию операций.23Все операции должны выполняться за в(1) шагов.

23 Осторожно, не заставьте ненароком интерпретатор печатать циклическую структуру (см. упр. 3.13).

table

V

*table*

a 1 b 2 c 3

Рис. 3.22: Таблица, представленная в виде списка с заголовком.

3.3.3 Представление таблиц

Когда в главе 2 мы изучали различные способы представления множеств, то в разделе 2.3.3 была упомянута задача поддержания таблицы с идентифицирующими ключами. При реализации программирования, управляемого данными, в разделе 2.4.3, активно использовались двумерные таблицы, в которых информация заносится и ищется с использованием двух ключей. Теперь мы увидим, как такие таблицы можно строить при помощи изменяемых списковых структур.

Сначала рассмотрим одномерную таблицу, где каждый элемент хранится под отдельным ключом. Ее мы реализуем как список записей, каждая из которых представляет собой пару, состоящую из ключа и связанного с ним значения. Пары связаны вместе в список при помощи цепочки пар, в каждой из которых car указывают на одну из записей. Эти связующие пары называются хребтом (backbone) таблицы. Для того, чтобы у нас было место, которое мы будем изменять при добавлении новой записи, таблицу мы строим как список с заголовком (headed list). У такого списка есть в начале специальная хребтовая пара, в которой хранится фиктивная «запись» - в данном случае произвольно выбранный символ *table*. На рисунке 3.22 изображена стрелочная диаграмма для таблицы

a: 1 b: 2 c: 3

Информацию из таблицы можно извлекать при помощи процедуры lookup, которая получает ключ в качестве аргумента, а возвращает связанное с ним значение (либо ложь, если в таблице с этим ключом никакого значения не связано). Lookup определена при помощи операции assoc, которая требует в виде аргументов ключ и список записей. Обратите внимание, что assoc не видит фиктивной записи. Assoc возвращает запись, которая содержит в car искомый ключ.24 Затем lookup проверяет, что запись, возвращенная assoc, не есть ложь, и возвращает значение (то есть cdr) записи.

(define (lookup key table)

(let ((record (assoc key (cdr table))))

24Поскольку assoc пользуется equal?, в качестве ключей она может распознавать символы, числа и списковые структуры.

(if record

(cdr record)

false)))

(assoc key records) ((null? records) false)

((equal? key (caar records)) (car records)) (else (assoc key (cdr records)))))

Чтобы вставить в таблицу значение под данным ключом, сначала мы с помощью assoc проверяем, нет ли уже в таблице записи с этим ключом. Если нет, мы формируем новую запись, «сconsивая» ключ со значением, и вставляем ее в начало списка записей таблицы, после фиктивной записи. Если же в таблице уже была запись с этим ключом, мы переставляем cdr записи на указанное новое значение. Заголовок таблицы используется как неподвижное место, которое мы можем изменять при порождении новой записи.25

(define (insert! key value table)

(let ((record (assoc key (cdr table)))) (if record

(set-cdr! record value) (set-cdr! table

(cons (cons key value) (cdr table)))))

ok)

Для того, чтобы создать таблицу, мы просто порождаем список, содержащий символ *table*:

(define (make-table) (list *table*))

Двумерные таблицы

В двумерной таблице каждое значение индексируется двумя ключами. Такую таблицу мы можем построить как одномерную таблицу, в которой каждый ключ определяет подтаблицу. На рисунке 3.23 изображена стрелочная диаграмма для таблицы

math:

+ : 43

-: 45

*: 42 letters:

a: 97

b: 98

содержащей две подтаблицы (подтаблицам не требуется специального заголовочного символа, поскольку для этой цели служит ключ, идентифицирующий подтаблицу).

25Таким образом, первая хребтовая пара является объектом, который представляет «саму» таблицу; то есть, указатель на таблицу - это указатель на эту пару. Таблица всегда начинается с одной и той же хребтовой пары. Будь это устроено иначе, пришлось бы возвращать из insert! новое начало таблицы в том случае, когда создается новая запись.

(define (cond