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

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

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

Таблица 58

№ п/п	Обозначение поля	Элемент дерева	Родительский элемент	Порожденные элементы
	Шифр учебной группы	01-АС	-
	Шифр учебной группы	01-ИЭ	-	4,5,6
	ФИО студента	Федоров Ф.Ф.		-
	ФИО студента	Иванов И.И.		-
	ФИО студента	Сидоров С.С.		-
	ФИО студента	Яковлев Я.Я.		-

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

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

№ п/п	ФИО старосты группы		№ п/п	Домашний адрес
	Федоров Ф.Ф.			ул. Кирова, 3 - 4
	Яковлев Я.Я.			пр. Мира, 5 - 4
				ул. Репина, 1 - 2
				ул. Маркса, 2 - 2

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

Таблица 61

№ п/п	Обозначение поля	Элемент дерева	Родительский элемент	Порожденные элементы	Ссылка на элемент
	Шифр учебной группы	01-АС	-		Т59,1
	Шифр учебной группы	01-ИЭ	-	4,5,6	Т59,2
	ФИО студента	Федоров Ф.Ф.		-	Т60,3
	ФИО студента	Иванов И.И.		-	Т60,1
	ФИО студента	Сидоров С.С.		-	Т60,2
	ФИО студента	Яковлев Я.Я.		-	Т60,4

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

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

Пример 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) надо разместить элемент со структурой:

ФИО студента	Шифр учебной группы
Комаров К.К.	01-АС

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

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

Таблица 62

№ п/п	Обозначение поля	Элемент дерева	Родительский элемент	Порожденные элементы
	Шифр учебной группы	01-АС	-	3,7
	Шифр учебной группы	01-ИЭ	-	4,5,6
	ФИО студента	Федоров Ф.Ф.		-
	ФИО студента	Иванов И.И.		-
	ФИО студента	Сидоров С.С.		-
	ФИО студента	Яковлев Я.Я.		-
	ФИО студента	Комаров К.К.		-