Страница 8: ГОСТ 28270-89. Системы обработки информации. Спецификация файла описания данных для обмена информацией (76845)

^Примеры упорядоченных корневых деревьев

Черт. 13

Метод, использованный здесь для представления структур корневых деревьев, тесно связан с точкой зрения пользователя на данные, а не с общепринятым машин­ным представлением древовидных структур, которое соответствует бинарному дереву (см. черт. 14 и 16) .

Метки полей служат в качестве идентификаторов узлов (т.е. полей данных). Структура дерева должна быть описана двумя частями информации:

1. упорядоченные пары идентификаторов узлов (меток полей) общей струк­туры в порядке сверху вниз от исходного к порожденному;

2. упорядоченный список идентификаторов узлов (меток полей) в последова­тельности прямого обхода.

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

Общая структура логической записи

Она имеет набор упорядоченных пар меток полей RH, НЕ, ЕА, ЕВ, HF, HG, GC, GD, где R- метка поля уникального идентификатора записи, 0 ... 1.

Последовательность прямого обхода меток полей этой структуры есть - RHEABFGCD и каждый узел употребляется однократно.

Характерный пример предыдущей общей структуры, имеющей множество случа­ев употребления полей данных с одной и той же меткой поля, представлен на черт. 15

Пример дерева данных пользователя

Н(1) Н (2) Н(3)

F (l) G(1) Е (2) Е (3) G (2) Е (4) F (2) F (3)

А(1) В(1) D(1) D(2) D(3) В (2)

Черт. 15

где R является меткой поля уникального идентификатора записи, а упорядоченные индексы (в скобках) для повторяющихся меток полей добавлены для ясности. По­следовательность прямого обхода будет - RH(1) Е(1) А (1) B(l) F(l) G(l) D(l) Н(2) Е(2) Е(3) G(2) D (2) D(3) Н(3) Е(4) В(2) F(2) F(3), которую можно записать без индек­сов в скобках, не потеряв смысла. Отметим, что только корневой узел R уникален, а поля Н, Е, А и т.д. могут встретиться несколько раз, и в этом случае они обозначены повторением одной и той же метки ПОЛЯ.

Последовательность прямого обхода обычно объединяется с информацией о свя­зях, чтобы представить структуру дерева. В большинстве случаев используется соот­ветствующее бинарное дерево. Это бинарное дерево имеет ту же последовательность прямого обхода, что и упорядоченное дерево, и связь с первым поддеревом узла об­разует левостороннюю связь в бинарном дереве, а все смежные узлы одного уровня соединены по порядку правосторонними связями между себе подобными. Эти новые связи легко выводятся из списка пар меток полей и последовательности прямого об­хода. Пользователь может затем создавать все, что требуется его системе соглаше­нием о связях.

Алгоритм, который образует лево- и правосторонние связи соответствующего бинарного дерева, приведен ниже, где общее дерево данного приложения использо­вано в качестве примера.

АЛГОРИТМ L. Дано, что Р (q) является бинарным отношением на наборе узлов, q выражает направленные допустимые связи между узлами, а Т (q) - последователь­ность прямого обхода дерева или группы деревьев.

Построить L и R векторы индексов в Т, выражающие лево- и правосторонние связи соответствующего бинарного дерева:

Примечание. „-Е” читать как ,,не элемент из” а ,, II ” — как „соединяется с”.

L0 [ Инициализировать] ш -►число пар в Р п *- число узлов в Т

S «- 0, рабочий стек, содержащий индексы в Т узлов пути от корня к узлу, Т (S (j)).

L+-0

_х R-0

L1 [ Установить стек на корневой узел] j *- 1, S(l) +- 1

L2 [ Установить индекс узла на корневой узел] і«- 1

L3 [ Продвинуть к следующему узлу] і *- і + 1

L4 [ Проверить на заполнение Т] if i> и end

L5 І Проверить парный узел стека и і-й узел] if T(S(j)) II T(i) - Е Р go to L8

L6 ] Запомнить левую связь для узла стека] L(S(j)) *- і

L7 [ Добавить і-й узел в стек] j j +1, S(j)«- і, go to L3

L8 [ Проверить парный предпоследний узел стека и і-й узел]

if T(S(j - 1)) II T(i) - Е Р go to LI 1

L9 [ Запомнить правую связь для узла стека] R(S(j)) «- і

LIO I Восстановить узел стека] S(j)«- і, go to L3

Lil {Вернуться к низшему узлу в пути] j *-j - 1

L12 [ Проверить узел на разрыв (новое дерево) ] if j = 0 go to L9

LI3 [ Проверить повторно новую пару узлов] go to L8

Пример.

Алгоритм действует для корневых ориентированных деревьев с или без повто­ряющихся меток полей в узлах. Он обрабатывает упорядоченный набор деревьев. Ветвь „истинно” в L12 может быть установлена на ошибку, если требуется ограничить обработку для деревьев.

На черт. 16 представлено соответствующее бинарное дерево для упорядоченного корневого дерева, показанного на черт. 14*.

Бинарное дерево, соответствующее корневому дереву,
приведенному на черт. 14*

ПРИЛОЖЕНИЕ 1
Справочное

СПИСОК ОПЕЧАТОК И НЕТОЧНОСТЕЙ В АНГЛИЙСКОМ
ОРИГИНАЛЕ ИСО 8211-85

ПРИЛОЖЕНИЕ 2

Справочное

АЛФАВИТНЫЙ УКАЗАТЕЛЬ ТЕРМИНОВ НА РУССКОМ ЯЗЫКЕ
И ИХ ЭКВИВАЛЕНТЫ НА АНГЛИЙСКОМ ЯЗЫКЕ

ИНФОРМАЦИОННЫЕ ДАННЫЕ

1. ИСПОЛНИТЕЛИ

М.М. Ефимова; А.А. Мкртумян; О.А. Антошкова; Ю.А. Васильев; Н.А. Чельцо- ва; В.И. Федосимов

2. Постановлением Государственного комитета СССР по стандартам от 27.09.89 № 2942 стандарт Совета Экономической Взаимопомощи СТ СЭВ 6366—8$ „Системы обработки информации. Спецификация фай­ла описания данных для обмена информацией”, в качестве которого не­посредственно применен международный стандарт ИСО 8211—85, введен в действие непосредственно в качестве государственного стандарта СССР с 01.07.90

3. Срок проверки — 1995 г.; периодичность проверки — 5 лет

4. ССЫЛОЧНЫЕ НОРМАТИВНО-ТЕХНИЧЕСКИЕ ДОКУМЕНТЫ

СОДЕРЖАНИЕ

0. Введение 3

1. ■ Назначение и область применения 5

2. Соответствие 5

3. Ссылки 6

4. Термины и определения 6

5. Файл обмена . 9

6. Описание типов и структур данных пользователя 22

7. Расширения набора кодированных символов 30

Приложение А. Руководство по применению 32

Приложение В. Примеры поля данных . 36

Приложение С. Модель ФОД и структура логической записи 39

Приложение 1. Список опечаток и неточностей в английском оригинале ИСО 8211-85 42

Приложение 2. Алфавитный указатель терминов на русском языке и их экви­валенты на английском языке 43

Редактор Огурцов В.П.

Технический редактор Власова О.Н.

Корректор Прокофьева А.В.

Сдано в набор 16.10.89 Подп. в печ.25.12.89 3,0 печ. л. 3,0усл. кр.-отт. 3,36 уч.-изд. л.

Тираж 11000 экз. Цена 15 к. Зак. 23

Ордена „Знак Почета” Издательство стандартов, 123840, Москва,ГСП,
Новопресненский пер., 3

Набрано в Издательстве стандартов на НПУ
Вильнюсская типография Издательства стандартов
Вильнюс, ул. Даряус и Гирено, 39

1)Алфавитный указатель терминов на русском языке и их эквиваленты на анг­лийском языке приведены в приложении 2.