AOP_Tom1 (1021736), страница 121
Текст из файла (страница 121)
Пусть МОВЕ(1), ..., МОВЕ(М) — однословные узлы с полями ИАНК, АТОН, АОНК и ВЫМЕ, как описано в алгоритме Е. Предположим, что ИАВК = 1 во всех узлах, которые не относятся к мусору. Искомый алгоритм должен таким образом переместить маркированные узлы (в случае необходимости), чтобы они расположились в последовательных ячейках памяти НОВЕ(1),..., МОВЕ(К) . Причем в то же время поля АЕ1МК и ВЕ1МК узлов, которые не являются атомами, необходимо изменить так (в случае необходимости), чтобы сохранилась структура Списка.
ь 10. [з8] Создайте алгоритм для копирования структуры Списка, предполагая, что она имеет внутреннее представление наподобие (7). (Таким образом, прн копировании с помощью этого алгоритма Списка, заголовок которого содержится в верхнем левом углу схемы (7), должно получиться новое множество Списков с 14 узлами со структурой и данными, которые идентичны показанным на схеме (7).) Предположим, что структура Списка хранится в памяти и организована на основе полей Б, Т, ВЕГ. Вь1МК так, как на схеме (9), и что МОВЕ(РО) — это заголовок копируемого Списка.
Также допустим, что поле ВЕг а заголовке каждого Списка равно Л. Чтобы избежать дополнительных расходов памяти, в созданной вами программе копирования должны использоваться поля йети (восле завершения работы программы следует вернуть их исходные значения Л). 11. [МЭО) Любая структура Списка может быть "полностью расширена" до древовидной структуры за счет повторения всех перекрывающихся элементов до тех пор, пока не останется ни одного такого элемента.
Например, при расширении рекурсивного Списка таким образом можно получить бесконечное дерево: при расширении Списка (5) получится бесконечное дерево со следующими первыми четырьмя уровнями: Г~ [ ~// -. /~ /~ [ /~ /Й/~ /~ /~/~/~ [ ® Создайте алгоритм для проверки эквиваленозносгли двух структур Списка в том смысле, что древовидные структуры их полного расширения имеют одну и ту же форму.
Например, Списки А и В в этом смысле эквивалентны. если А = (а: С, Ь, а; (Ь: Р) ); В = (а: (6: В), Ь, а; Е); С = (Ь; (а: С)); В = (а: (Ь: В)); Е = (Ь: (а: С)). 12. [УО) (Задача М. Л. Мински (М. 1. Мшэ1су).) Покажите, что метод сборки мусора может вполне надежно использоваться в "оперативных" приложениях, например, когда компьютер управляет работой некоторого физического устройства, даже если на максимальное время выполнения каждой операции со Списками накладываются очень строгие ограничения.
[Указание. Соблюдая все необходимые в таких случаях предосторожности, можно организовать сборку мусора и операции со Списками в параллельном режиме.[ 2.4. МНОГОСВЯЗНЫЕ СТРУКТУРЫ ТЕПЕРЬз после подробного исследования линейных списков и древовидных структур, принципы представлеиия структурной информации внутри компьютера должны быть очевидны.
В настоящем разделе будет рассмотрено еще одно приложение таких методов, на этот раз — для типичного случая с несколько более сложной структурной информацией. 8 приложениях более высокого уровня обычно используется сразу несколько типов структур. "Многосвязная структура" состоит из узлов с несколькими полями связи в каждом узле, а не только с одним или двумя в структурах из предыдущих примеров. Примеры использования множественных связей приводились выше, например, при моделировании работы лифта в разделе 2.2.5 и работе с полиномами по многим переменным в разделе 2.3.3. Как мы увидим далее, присутствие множества различных типов связей в одном узле не обязательно сопровождается усложнением их создания или восприятия по сравнению с уже рассмотренными алгоритмами.
Кроме того, мы ответим на еще один важный вопрос: В каком объеме структурная информация должна быть представлена в памяти в явном виде? Рассматриваемая здесь задача возникает в связи с созданием программы-компилятора для трансляции программ на языке СОВОЬ и других сходных с ним языков. При работе с языком СОВОЬ программист может присваивать символьные имена переменным программы на нескольких уровнях. Например, программа может иметь дело с файлами данных о продажах и покупках со следующей структурой.
1 БАЬЕБ 1 РНВСНАБЕБ 2 РАТЕ 2 ВАТЕ 3 МОМТН 3 РАТ 3 РАТ 3 МРМТН 3 ТЕАВ 3 ТЕАВ 2 ТВАИБАСТ10М 2 ТВАМБАСТ10М 3 1ТЕМ 3 1ТЕМ (1) 3 ЦРАИТ1ТУ 3 ЦРАИТ1ТУ 3 РВ1СЕ 3 РВ1СЕ 3 ТАХ 3 ТАХ 3 ВРТЕВ 3 БН1РРЕВ 4 МАМЕ 4 МАМЕ 4 АРРВЕББ 4 АВВВЕББ Па этой схеме некоторой конфигурации данных показано, что каждый элемент файла БАЬЕБ (продажи) состоит из двух частей: ВАТЕ (дата) и ТВАИБАСТ10И (транзакция). Причем РАТЕ подразделяется на три части, а ТВАМБАСТ10М вЂ” на пять частей. Аналогичные заме сания относятся и к файлу РРВСНАБЕБ (покусски). Относительный порядок имен указывает порядок, в котором эти величины предстают во внешних представлениях файла (например, на магнитной ленте или распечатанных формах).
Обратите внимание на то, что РАУ и МОМТН в этих двух файлах представлены в разном порядке. Программист приводит и другую не показанную здесь информацию, которая сообщает о том, какое пространство в памяти занимает каждый элемент данных и в каком формате эти данные представлены. Подобные соображения несущественны для темы данного раздела. а потому не будут рассматриваться. ОАУ ОР 0АТЕ ОР БАБАЕВ, ноь вообще-то, не следует придавать величинам больше квалификаций (описаний), чем это действительно необходимо, во избежание неоднозначности. Такиьл образом, выражение ИАИЕ ОР БН1РРЕК ОР ТКАИБАСТ1ОИ ОР РОКСНАБЕБ можно сократить до ИАИЕ ОР БНХРРЕК, поскольку существует только одна часть данных с именем БН1РРЕК.
Эти правила языка СОВОГО могут быть выражены более точно в следующей форме. а) Каждому имени предшествует некоторое связанное с ним положительное целое число, которое называется номером уровня. Имя относится либо к простейпьему элеменьпу, либо к группе нз одного или нескольких элементов со своимн иълелламлл. В последнем случае все элементы группы должны иметь один номер уровня, .который должен быть выше, чем номер уровня для имени группы.
(Например, элементы ВАТЕ и ТКАИБАСТ1ОИ в приведенном примере имеют уровень 2, который выше уровня 1 для элемента БА|ЕБ.) Ь) Для ссылки на простейший элемент или группу элементов с именем Ло используется общая форма ЛООРА ОР...ОРА„, где и > Оь а .4ь является именем элемента, который прямо или косвенно содержится внутри группы с именем А +л для О ( ) ( п.
Должен существовать только один элемент .4о, который удовлетворяет этому условию. с) Есле одно и то же имя Ао появляется в нескольких местах, должен существовать способ ссылки на каждый случай использования такого имени с помощью квалификации (описания). Например, согласно правилу (с) конфигурация данных 1 АА 2 ВВ 3 СС 3 00 2 СС (2) недопустима, так как при втором появлении элемента СС не существует однозначного способа ссылки на элементы с таким именем (см.
упр. 4). Программист при работе с языком СОВОЕ описывает сначала формат файла и другие переменные программы, а затем — алгоритмы, которые оперируют этими величинами. Для ссьлллки на отдельную переменную в приведенном выше примере было бы недостаточно просто указать имя ОАУ, так как не существует способа указания, в каком файле она находится: в БА1ЕБ или РОКСНАБЕБ.
Следовательно, при работе с языком СОВОЬ можно с помощью выражения ОАУ ОР БА|ЕЕ указать, что элемент ОАУ является частью элемента БАБАЕВ. Программист мог бы также записать в более полной форме, что СОВО1. обладает еще одним свойством. которое может оказать влияние на процесс создания компилятора и работу рассматриваемых приложений, а имеммо— возможностью ссылатьая сразу на несколько элементов.
В таком случае программист может записать МОЧЕ СОВВЕБРОИОТИОа ТО,9, что приведет к перемещению всех элементов с соответствующими именами из области данных а в область данных б. Например, команча языка СОВОГО МОЧЕ СОВВЕЯРОИО1ИО ВАТЕ ОР БАДЕЯ ТО ВАТЕ ОР РОВСНАЯЕБ означает, что значениями переменных МОИТН, ОАЧ и АСЕАН из файла БАЛДЕЯ нужно заменить значения переменных ОАУ, МОИТН, ЧЕАВ в файле РОВСНАБЕЯ. (Относительный порядок ОАУ и МОИТН при этом изменяется.) В данном разделе будут рассмотрены три алгоритма, которые можно использовать в компиляторе СОВОЬ и которые предназначены для выполнения перечисленных ниже действий.
Операция 1. Обработать описания имен и номеров уровней, подобных показанным на схеме (1), разместив соответствующую информацию в таблицах внутри компилятора для использования в операциях 2 и 3. Операция 2. Определить. справедлива ли заданная ссылка, квалифицированная согласно правилу (Ь), н, если справедлива, майти соответствующий элемент дамных. Операция 3.
Найти все соответствующие пары элементов, которые указаны в команде СОВВЕЯРОИОТИО. Допустим., что наш компилятор уже имеет 'подпрограмму таблиц символов", которая может преобразовать символьное имя в связь, указывающую на позицию таблицы, соответствующую этому имени. (Более подробно методы построения алгоритмов для обработки таблиц символов обсуждаются в главе 6.) Помимо таблицы символов, имеется таблица большего размера, тааблица данных, содержащая по одной позиции для каждого элемента данных из исходной программы на языке СОВОЬ, которую нужно откомпилировать.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
