Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 59
Текст из файла (страница 59)
Если очередь была пуста, мы перенаправляем на эту пару и головной, и хвостовой указатели. В противном случае, мы изменяемпоследнюю пару очереди так, чтобы следующей была новая пара, и хвостовой указательтоже перенаправляем на нее же.(define (insert-queue! queue item)(let ((new-pair (cons item ’())))(cond ((empty-queue? queue)(set-front-ptr! queue new-pair)(set-rear-ptr! queue new-pair)queue)(else(set-cdr! (rear-ptr queue) new-pair)(set-rear-ptr! queue new-pair)queue))))Чтобы уничтожить элемент в голове очереди, мы просто переставляем головнойуказатель на второй элемент очереди, а его можно найти в cdr первого элемента3.3.
Моделирование при помощи изменяемых данных253qrear-ptrfront-ptrabcdРис. 3.20. Результат применения (insert-queue! q ’d) к очереди с рисунка 3.19qrear-ptrfront-ptrabcdРис. 3.21. Результат применения (delete-queue! q) к очереди с рис. 3.20.(см. рис. 3.21)22 :(define (delete-queue! queue)(cond ((empty-queue? queue)(error "DELETE! вызвана с пустой очередью" queue))(else(set-front-ptr! queue (cdr (front-ptr queue)))queue)))Упражнение 3.21.Бен Битобор решает протестировать вышеописанную реализацию.
Он вводит процедуры в интерпретаторе Лиспа и тестирует их:(define q1 (make-queue))(insert-queue! q1 ’a)((a) a)(insert-queue! q1 ’b)22 В случае, если первый элемент — одновременно и последний, после его уничтожения головной указательокажется пустым списком, и это будет означать, что очередь пуста; нам незачем заботиться о хвостовом указателе, который по-прежнему будет указывать на уничтоженный элемент, поскольку empty-queue? смотриттолько на голову.Глава 3. Модульность, объекты и состояние254((a b) b)(delete-queue! q1)((b) b)(delete-queue! q1)(() b)«Ничего не работает! — жалуется он. — Ответ интерпретатора показывает, что последний элементпопадает в очередь два раза. А когда я оба элемента уничтожаю, второе b по-прежнему там сидит,так что очередь не становится пустой, хотя должна бы».
Ева Лу Атор говорит, что Бен простоне понимает, что происходит. «Дело не в том, что элементы два раза оказываются в очереди, —объясняет она. — Дело в том, что стандартная лисповская печаталка не знает, как устроенопредставление очереди. Если ты хочешь, чтобы очередь правильно печаталась, придется написатьспециальную процедуру распечатки очередей». Объясните, что имеет в виду Ева Лу.
В частности,объясните, почему в примерах Бена на печать выдается именно такой результат. Определитепроцедуру print-queue, которая берет на входе очередь и выводит на печать последовательностьее элементов.Упражнение 3.22.Вместо того, чтобы представлять очередь как пару указателей, можно построить ее в виде процедуры с внутренним состоянием. Это состояние будет включать указатели на начало и конецобыкновенного списка. Таким образом, make-queue будет иметь вид(define (make-queue)(let ((front-ptr ...)(rear-ptr ...))hопределения внутренних процедурi(define (dispatch m) ...)dispatch))Закончите определение make-queue и реализуйте операции над очередями с помощью этогопредставления.Упражнение 3.23.Дек (deque, double-ended queue, «двусторонняя очередь») представляет собой последовательность,элементы в которой могут добавляться и уничтожаться как с головы, так и с хвоста.
На деках определены такие операции: конструктор make-deque, предикат empty-deque?, селекторы front-deque и rear-deque, и мутаторы frontinsertdeque!, rear-insert-deque!,front-delete-deque! и rear-delete-deque!. Покажите, как представить дек при помощипар, и напишите реализацию операций23 .Все операции должны выполняться за Θ(1) шагов.3.3.3. Представление таблицКогда в главе 2 мы изучали различные способы представления множеств, то в разделе 2.3.3 была упомянута задача поддержания таблицы с идентифицирующими ключами.При реализации программирования, управляемого данными, в разделе 2.4.3, активно23 Осторожно,не заставьте ненароком интерпретатор печатать циклическую структуру (см.
упр. 3.13).3.3. Моделирование при помощи изменяемых данных255table*table*a1b2c3Рис. 3.22. Таблица, представленная в виде списка с заголовком.использовались двумерные таблицы, в которых информация заносится и ищется с использованием двух ключей. Теперь мы увидим, как такие таблицы можно строить припомощи изменяемых списковых структур.Сначала рассмотрим одномерную таблицу, где каждый элемент хранится под отдельным ключом. Ее мы реализуем как список записей, каждая из которых представляетсобой пару, состоящую из ключа и связанного с ним значения.
Пары связаны вместе всписок при помощи цепочки пар, в каждой из которых car указывают на одну из записей. Эти связующие пары называются хребтом (backbone) таблицы. Для того, чтобы унас было место, которое мы будем изменять при добавлении новой записи, таблицу мыстроим как список с заголовком (headed list). У такого списка есть в начале специальнаяхребтовая пара, в которой хранится фиктивная «запись» — в данном случае произвольновыбранный символ *table*.
На рисунке 3.22 изображена стрелочная диаграмма длятаблицыa: 1b: 2c: 3Информацию из таблицы можно извлекать при помощи процедуры lookup, которая получает ключ в качестве аргумента, а возвращает связанное с ним значение (либоложь, если в таблице с этим ключом никакого значения не связано). Lookup определена при помощи операции assoc, которая требует в виде аргументов ключ и списокзаписей. Обратите внимание, что assoc не видит фиктивной записи.
Assoc возвращаетзапись, которая содержит в car искомый ключ24 . Затем lookup проверяет, что запись,возвращенная assoc, не есть ложь, и возвращает значение (то есть cdr) записи.(define (lookup key table)(let ((record (assoc key (cdr table))))(if record(cdr record)false)))24 Поскольку assoc пользуется equal?, в качестве ключей она может распознавать символы, числа исписковые структуры.256Глава 3. Модульность, объекты и состояние(define (assoc key records)(cond ((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*: 42letters:a: 97b: 98содержащей две подтаблицы (подтаблицам не требуется специального заголовочногосимвола, поскольку для этой цели служит ключ, идентифицирующий подтаблицу).Когда мы ищем в таблице элемент, сначала при помощи первого ключа мы находимнужную подтаблицу. Затем при помощи второго ключа мы определяем запись внутриподтаблицы.25 Таким образом, первая хребтовая пара является объектом, который представляет «саму» таблицу; то есть,указатель на таблицу — это указатель на эту пару.
Таблица всегда начинается с одной и той же хребтовойпары. Будь это устроено иначе, пришлось бы возвращать из insert! новое начало таблицы в том случае,когда создается новая запись.3.3. Моделирование при помощи изменяемых данных257table*table*lettersa97-45a98math+43Рис. 3.23. Двумерная таблица.*42258Глава 3.
Модульность, объекты и состояние(define (lookup key-1 key-2 table)(let ((subtable (assoc key-1 (cdr table))))(if subtable(let ((record (assoc key-2 (cdr subtable))))(if record(cdr record)false))false)))Чтобы вставить в таблицу новый элемент под двумя ключами, мы при помощи assocпроверяем, соответствует ли какая-нибудь подтаблица первому ключу. Если нет, строимновую подтаблицу, содержащую единственную запись (key-2, value), и заносим ее втаблицу под первым ключом. Если для первого ключа уже существует подтаблица, мывставляем новую запись в эту подтаблицу, используя вышеописанный метод вставки дляодномерных таблиц:(define (insert! key-1 key-2 value table)(let ((subtable (assoc key-1 (cdr table))))(if subtable(let ((record (assoc key-2 (cdr subtable))))(if record(set-cdr! record value)(set-cdr! subtable(cons (cons key-2 value)(cdr subtable)))))(set-cdr! table(cons (list key-1(cons key-2 value))(cdr table)))))’ok)Создание локальных таблицОперации lookup и insert!, которые мы определили, принимают таблицу в качестве аргумента.
Это позволяет писать программы, которые обращаются более, чем кодной таблице. Другой способ работы с множественными таблицами заключается в том,чтобы иметь для каждой из них свои отдельные процедуры lookup и insert!. Мыможем этого добиться, представив таблицу в процедурном виде, как объект, которыйподдерживает внутреннюю таблицу как часть своего локального состояния. Когда емупосылают соответствующее сообщение, этот «табличный объект» выдает процедуру, спомощью которой можно работать с его внутренним состоянием. Вот генератор двумерных таблиц, представленных таким способом:(define (make-table)(let ((local-table (list ’*table*)))(define (lookup key-1 key-2)(let ((subtable (assoc key-1 (cdr local-table))))(if subtable(let ((record (assoc key-2 (cdr subtable))))3.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
