Таким образом, для каждой позиции таблицы данных необходимо создать дополнительно пять полей связи:

PREV (связь с предыдущей позицией с тем же именем, если таковая имеется);

PARENT (связь с наименьшей группой, если таковая имеется, содержащей элемент) ;

NAME (связь с позицией таблицы символов элемента); CHILD (связь с первым подэлементом группы);

SIB (связь со следующим подэлементом группы, содержащей элемент). Ясно, что структуры данных в языке COBOL, подобные приведенным выше структурам SALES и PURCHASES, являются деревьями, а связи наподобие PARENT, CHILD и SIB уже знакомы нам из предыдущего материала. (Представление дерева в виде обычного бинарного дерева основано на связях CHILD и SIB, а при добавлении связи PARENT получим "трижды связанное дерево". Пять упомянутых выше связей состоят из этих трех связей вместе со связями PREV и NAME, которые несут дополнительную информацию о данной древовидной структуре.)

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

1 А 1 И

3 В 5 F

7 С 8 G

7 D 5 В

3 Е 5 С

3 F 9 Е

4 G 9 D

Их следует представить в виде (5) (со связями, указанными в символьной форме). Поле LINK в каждой позиции таблицы символов указьшает на последнюю из встреченных позиций таблицы данных с символьным именем из позиции таблицы символов.

Сначала потребуется создать алгоритм для построения таблицы данных такого типа. Обратите внимание на то, что в языке COBOL предусмотрена гибкость выбора номеров уровней. Левая структура (4) полностью эквивалентна структуре

1 А 2 В

3 D , 2 Е 2 F

поскольку номера уровней необязательно должны быть последовательными числами.

Таблица символов

Таблица данных

Однако некоторые последовательности номеров уровней недопустимы. Например, если номер уровня для элемента D в (4) был бы заменен номером 6 (в любом месте), была бы получена бессмысленная конфигурация данных, нарушающая правило, в соответствии с которым все элементы группы должны иметь одинаковые номера. Поэтому в следующем алгоритме вьшолняется проверка, соблюдается ли правило (а) языка COBOL.

Алгоритм А (Построение таблицы данных). Этот алгоритм позволяет получить последовательность пар (L, Р), где L - положительное целое число, обозначающее номер уровня, а Р - позиция таблицы символов, соответствующая таким структурам данных COBOL, как (4). Данный алгоритм создает таблицу данных, подобную приведенной выше, в примере (5). Когда Р указьшает на позицию таблицы символов, которая прежде не встречалась, связь LINK(P) становится равной А. В этом алгоритме используется вспомогательный стек, который обрабатывается, как обычный стек (на основе последовательного распределения памяти, как в разделе 2.2.2, или на основе связанного распределения памяти, как в разделе 2.2.3).

А1. [Инициализация.] Ввести в стек элемент (О, А). (В этом алгоритме стек будет содержать пары (L,P), где L - целое число, а Р - указатель. В ходе работы алгоритма стек содержит номер уровня и указатели на последние позиции данных на всех уровнях данного дерева, которые располагаются выше текущего уровня. Например, в приведенном примере до появления пары 3 F стек будет содержать пары

(О, А) (1,А1) (3,ЕЗ)

в направлении снизу вверх.)

А2. [Следующий элемент.] Пусть (L,P)-это следующий элемент данных, взятый из входного потока. После исчерпания входного потока вьшолнение алгоритма прекращается. Усыновить Q <= AVAIL (т. е. пусть Q - адрес нового узла, Э котором можно разместить следующую позицию таблицы данных),

A3. [Установка связей для символьных имен.] Установить

PREV(Q) LINK(P), LINK(P) Q, NAME(Q) <- P. (Так будут заданы значения для двух связей из пяти в узле NODE(Q). Теперь нужно соответствующим образом установить значения связей PARENT, CHILD и SIB.)

А4. [Сравнение уровней.] Пусть пара (L1, Р1) является верхним элементом стека. Если LKL, установить CHILD (Р1) f- Q (или, если Р1 = Л, установить FIRST <- Q, где FIRST - переменная, которая будет указывать на первый элемент таблицы данных) и перейти к шагу А6.

Аб. [Удаление верхнего элемента.] Если L1 > L, то удалить верхний элемент стека. Пусть, например, (L1,P1) - новый элемент, который только что был удален из верхней части стека, Затем повторить шаг А5. Если L1 < L (т. е. на одном уровне обнаружены разные номера), выдать сообщение об ошибке, В противном случае, а именно - при L1 = L, установить SIB(Pl) Q и удалить верхний элемент стека. Пусть, например, пара (L1,P1) является парой, которая только что была удалена из верхней части стека.

Аб. [Установка связей семьи.] Установить PARENT(Q) <- PI, CHILD(Q) +- Л, SIB(Q) A.

A7. [Ввести элемент в стек.] Поместить пару (L,Q) в верхнюю часть стека и вернуться к шагу А2. I

Благодаря введению вспомогательного стека, который описан на шаге Al, данный алгоритм настолько упрощается, что не требует дополнительных разъяснений.

Следующая задача заключается в поиске позиции таблицы данных, соответствующей ссылке

Ло OF Л1 OF ... OF An, n>Q. (6)

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

Алгоритм В (Проверка квалифицированной ссылки), В соответствии со ссылкой (6) программа таблицы символов найдет указатели Po,Pi,...,P„ на позиции таблицы символов Ло, Al,,,., Л„ соответственно.

Назначение данного алгоритма заключается в проверке Pq,Pi, ... ,Рп и либо определении того, что ссылка (6) ошибочна, либо в установлении для значения переменной Q адреса позиции таблицы данных для элемента, на который ссылается (6).

81. [Инициализация.] Установить Q Л, Р LINK(Pq).

82. [Готово?] Если Р = Л, то вьшолнение алгоритма прекращается; в этот момент Q равно А, если (6) не соответствует никакой позиции таблицы данных. Но если