Справочники. Связи между элементами дерева формируют отдельное описание в виде линейного списка - справочник.

Связи между элементами дерева формируют отдельное описание в виде линейного списка - справочник.

Например, пусть исходное дерево имеет вид рисунка 7. Сформируем для него справочник (таблица 58):

Таблица 58

Если элементы дерева не содержат дополнительных данных, то такого описания дерева в целом достаточно. Если же элементы дерева имеют структуру, то их описание хранится отдельно в списке элементов. Например, если для элементов дерева рисунка 7 надо также хранить информацию таблиц 48 и 49, то эти данные помещаются в таблицы, подобные таблицам 59 и 60:

Таблица 59 Таблица 60

Справочник в таком случае модифицируется (таблица 61): в него добавляется графа Ссылка на элемент, в которой указывается таблица с информацией (например, Т59 для обозначения таблицы 59), и номер элемента с описанием в этой таблице:

Таблица 61

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

Рассмотрим, как решаются в этих структурах задачи просмотраэлементов дерева.

Пример 24. Пусть требуется сформировать список студентов, учащихся в группе 01-АС, т.е. q^{просмотр} = (Шифр учебной группы =01-АС, ФИО студента), где К_доступ = 01-АС. Элементы дерева имеют структуру, показанную в таблицах 59, 60, дерево описано в таблице 61.

Решение задачи:

1. по справочнику (таблица 61) определяем элемент дерева 01-АС – это элемент с номером 1;

2. определяем порожденные элементы для него (графа Порожденные элементы) – это элемент той же таблицы с номером 3;

3. обращаемся к элементу с номером 3 и выводим фамилию и инициалы – Федоров Ф.Ф. Алгоритм заканчивает работу.

Пример 25. Пусть требуется определить, в какой группе учится студент Сидоров С.С. т.е. q^{просмотр} = (ФИО студента =Сидоров С.С., Шифр учебной группы), где К_доступ = Сидоров С.С.

Решение задачи:

1. по справочнику (таблица 61) находим нужного студента – это элемент с номером 5;

2. по полю Родительский элемент определяем соответствующую ссылку – это элемент с номером 2;

3. обращаемся к элементу с номером 2 и выводим шифр группы – 01-ИЭ. Алгоритм заканчивает работу.

Рассмотрим задачу добавлениянового элемента.

Пример 26. Пусть в дереве рисунка 7 (описание дерева соответствует таблице 58) надо разместить элемент со структурой:

т.е. q^{добавление} = (ФИО студента =Комаров К.К., Шифр учебной группы =01-АС), где К_доступ = Комаров К.К., 01-АС.

После включения элемента дерево приобретет вид рисунка 8, а его описание будет соответствовать таблице 62 (измененные и новые данные выделены заливкой):

Таблица 62