AOP_Tom1 (1021736), страница 122
Текст из файла (страница 122)
Очевидно, что нельзя создать алгоритм выполнения операции 1 до тех пор, пока неизвестно, какого рода информацию предполагается хранить в таблице данных. Причем форма таблицы данных зависит от типа информации, необходимой для выполнения операций 2 и 3. Таким образом, прежде всего следует обратить внимание на операции 2 и 3. Для определения значения ссылки на языке СОВОЬ Аа ОР .4~ ОГ... ОР А„, п > О, (3) сначала необходимо найти имя Ао в таблице символов.
Причем должем существовать ряд связей от позиции таблицы символов ко всем позициям таблицы данных, которые относятся к этому имени, Затем для каждой позиции таблицы данных потребуется установить связь с элементом-группой, в которую он входит.
Тогда, если существует поле связи от позиций таблицы данных к таблице символов, нетрудно сообразить, как следует организовать обработку ссылок наподобие (3). Более того, чтобы найти пары, заданные в команде МОЧЕ СОВВЕБРОИО1ИО, потребуется установить некоторые связи от позиций таблицы данных для каждого элемента-группы к отдельным элемемтам этой группы. 1 А 3 В 7 С 7 В 3 Е 3 Р 4 0 1 Н 5 Р 8 С Б В Б С 9 Е 9 В 9 6 (4) Их следует представить в виде (5) (со связями, указанными в символьной форме).
Поле Е1МК в каждой позиции таблицы символов указывает на последнюю из встреченных позиций таблицы данных с символьным именем из позиции таблицы символов. Сначала потребуется создать алгоритм для построения таблицы данных такого типа. Обратите внимание на то, что в языке СОВОЬ предусмотрена гибкость выбора номеров уровней.
Левая структура (4) полностью эквивалентна структуре 1 А 2 В 3 С 3 В 2 Е 2 Г 3 С поскольку номера уровней необязательно должны быть последовательными числа- ми. Таким образом, для каждой позиции таблицы данных необходимо создать дополнительно пять полей связи: РКЕУ (связь с предыдущей позицией с тем же именем, если таковая имеется); РАНЕМТ (связь с наименьшей группой, если таковая имеется, содержащей элемент); МАНЕ (связь с позицией таблицы символов элемента); СН1Ю (связь с первым подэлементом группы); Б1В (связь со следующим подэлементом группы, содержащей элемент). Ясно, что структуры данных в языке СОВОГО, подобные приведенным выше структурам БАБАЕВ и РВНСНАБЕБ, являются деревьями, а связи наподобие РАНЕМТ, СН1ЕВ и Б1В уже знакомы нам из предыдущего материала.
(Представление дерева в виде обычного бинарного дерева основано на связях СН1ЕВ и БТВ, а при добавлении связи РАНЕМТ получим "трижды связанное дерево". Пять упомянутых выше связей состоят из этих трех связей вместе со связями РНЕУ и МАНЕ, которые несут дополнительную информацию о данной древовидной структуре.) Вероятно, не все пять связей являются необходимыми, или достаточными, но попробуем создать алгоритм с исходным предположением о том, что элементы таблицы данных содержат все пять полей (и дополнительную информацию, которая не имеет отношения к данной проблеме).
В качестве примера множественного связывания рассмотрим такие две структуры данных языка СОВОГО: Таблица символов Таблица данных 1.1МК РВЕЧ РАВЕМТ МАМЕ СН1Ю БХВ А ВЗ: С7: О7: Е (5) Н1: 09 Однако некоторые последовательности номеров уровней недопустимы. Например, если номер уровня для элемента В в (4) был бы заменен номером б (в любом месте), была бы получена бессмысленная конфигурация данных, нарушающая правило, в соответствии с которым все элементы группы должны иметь одинаковые номера. Поэтому в следующем алгоритме выполняется проверка, соблюдается ли правило (а) языка СОВ01..
Алгоритм А (Построение таблицы данных). Этот алгоритм позволяет получить последовательность пар (1.,Р)< где 1.— положительное целое число, обозначающее номер уровня, а Р— позиция таблицы символов, соответствующая таким структурам данных СОВОЕ, как (4). Данный алгоритм создает таблицу данных, подобную приведенной выше, в примере (5). Когда Р указывает на позицию таблицы символов, которая прежде не встречалась, связь Е1МК(Р) становится равной Л.
В этом алгоритме используется вспомогательный стек, который обрабатывается, как обычный стек (на основе последовательного распределения памяти, как в разделе 2.2.2, нли на основе связанного распределения памяти, как в разделе 2.2.3). А1. [Инициализация.] Ввести в стек элемент (О, Л). (В этом алгоритме стек будет содержать пары (Е,Р), где Е --целое число, а Р— указатель.
В ходе работы алгоритма стек содержит номер уровня и указатели на последние позиции данных на всех уровнях данного дерева, которые располагаются выше текущего уровня. Например, в приведенном примере до появления пары 3 Р стек будет содержать пары (О,Л) (1,А1) (3<ЕЗ) в направлении снизу вверх.) В пустых клетках содержится информация, не нмеюи[ая отношения к данной задаче Г5; 08: В5: С5: Е9: А2. [Следующий элемент.1 Пусть (1., Р) — это следующий элемент данных, взятый из входного патока, После исчерпания входного потока выполнение алгоритма прекращается. Уа(вновить Ц ~ ауа1Ь (т.
е. пугть Ц вЂ” адрес нового узла, «котором можно размес~ить следующую позицию таблицы данных), Ай, [Установка связей для символьных имен.] Установить РНЕЧ(Ц) +- 1.1МК(Р), !.1МК(Р) ~- Ц, МАМЕ(Ц) <- Р. (Твк будут заданы значения для двух связей из пяти в узле МОВЕ(Ц). Теперь нужно соответствующим образом установить значения связей РайЕМТ, СН1ЬО и 61В.) А4. [Сравнение уровней.] Пусть пара (1.!, Р1) является верхним элементом стека. Егли !.1( 1., установить СН1ЬО(Р1) в- Ц (или, если Р1= Л, установить Р1НВТ <- Ц, где Р1НВТ вЂ” переменная, которая будет указывать на первый элемент таблицы данных) и перейти к шагу А6.
Аб, [Удаление верхнего элемента.] Если Ь! > 1., то удалить верхний элемент стека. Пусть, например, (Ь1,Р1) — новый элемент, который только что был удален нз веркней части стека, Затем повторить шаг А5. Если Ь! ( Ь (т. е. на одном уровне обнаружены разные номера), выдать сообщение об ошибке. В противном случае, а именна — при ЬТ = Ь, установить 81В(Р1) +- Ц и удалить верхний элемент стека. Пусть, например, пара (Ь1, Р1) является парой, которая талька что была удалена из верхней части стека. А6.[Установка связей семьи.) Установить РАНЕМТ(Ц) <- Р1, СН1ЬО(Ц) <- Л, 61В(Ц) е- Л. АТ.
[Ввести элемент в стек.] Поместить пару (Ь, Ц) в верхнюю часть стека и вернуться к шагу Л2. 1 Благодаря введению вспомогательного стека, который описан на шаге А1, данный алгоритм настолько упрощается, чта не требует дополнительных разъяснений, Следующая задача заключается в поиске позиции таблицы данных, соответствующей ссылке Ао ОР.41 ОР, ОР А„, и > О. (6) В хорошем компиляторе следует также предусмотреть проверку недвусмысленнасти такой ссылки. В этом случае сразу.
же напрашивается следующий алгоритм (рис. 40). Все, чта теперь необходимо сделать, — просмотреть список позиций таблицы данных для имени Ао и убедиться в том, чта в точности одна из них соответствует квалификации Аы..., Аи. Алгоритм В (Проверки квилифицвровинной ссмлкн). В соответствии со ссылкой (6) программа таблицы символов найдет указатели Ро, Р„..., Рв на позиции таблицы символов Ао, Аы ..,, А„ соответственно. Назначение даннога алгоритма заключается в проверке Ро, Ры, .., Рв и либо определении тога, что ссылка (6) ошибочна, либо в установлении для значения переменной Ц адреса позиции таблицы данных для элемента, на который ссылается (6).
В1. [Инициализация.] Установить Ц +- Л, Р 1- ЬТМК(Рв), В2. [Гатавоу] Если Р = Л, та выполнение алгоритма прекращается; в этот момент Ц равна Л, если (6) не соответствует никакой позиции таблицы данных. Но если Рис. 40. Алгоритм для проверки ссылок в языке СОВО1.. Р ф Л, установить Б Р и й <- О. (Б †переменн-указатель, значения которой меняются от Р и ведут вверх по дереву по связям РАЕЕМТ; й †целочисленн переменная, которая принимает значения от 0 к и, На практике указатели Ро,, Рв часто содержатся в связанном списке, и тогда вместо А используется перемеииая-указатель, которая совершает обход этого списка; см. упр.
5.) ВЗ. [Соответствие пайдеиоу] Если к < и, то перейти к шагу В4. В противном случае найдена соответствующая позиция таблицы данных. Если О ф Л, то найдена вторая такая позиция, и поэтому нужно отослать сообщение об ошибке. Установить О Р, Р < — РЕЕЧ(Р) и перейти к шагу В2. В4. [Увеличеиие )с.] Установить А < — /с+ 1. ВБ. [Продвижение вверх по дереву.] Установить Б ~ — РАЕЕМТ(Б). Если Б = Л, то соответствие найти не удалось; установить Р = РКЕЧ(Р) и перейти к шагу В2. Вб. [Аь соответствует?] Если МАМЕ(Б) = Рь, перейти к шагу ВЗ; в противном случае перейти к шагу В5. 1 Обратите виимапие, что связи СН110 и Б1В в этом алгоритме не использовались.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
