Ссылки на подобные и порожденные элементы

Аналогично предыдущему методу подобные элементы описываются в линейных списках. Для указания связей применяют два вида ссылок: одна фиксирует связь с первым порожденным элементом, вторая – с подобным. Причем с помощью подобия показывается, каким родительским элементам принадлежат порожденные элементы. Для элементов максимального уровня иерархии поддерживается только одна ссылка (на подобные элементы), поскольку они не имеют порожденных элементов; для элементов первого уровня иерархии также поддерживается одна ссылка (на порожденные элементы), поскольку все они имеют одного родителя – корень. Для остальных элементов поддерживается две ссылки.

Рассмотрим данную организацию хранения элементов для дерева рисунка 7, которое представлено таблицами 52, 53:

Таблица 52                                        Таблица 53

№ п/п	Шифр учебной группы	Ссылка на порожденный элемент		№ п/п	ФИО студента	Ссылка на подобный элемент
1	01-АС	3		1	Иванов И.И.	2
2	01-ИЭ	1		2	Сидоров С.С.	4
				3	Федоров Ф.Ф.	-
				4	Яковлев Я.Я.	-

Для элементов уровня учебных групп (первого уровня дерева) устанавливаются только ссылки на порожденные элементы, причем на первые из них в множестве порожденных элементов. Так, для элемента таблицы 52 01-ИЭ ссылка со значением 1 показывает, что первый порожденный элемент (из таблицы 53) имеет номер 1. В таблице 53 для элемента 1 ссылка на подобные элементы имеет значение 2 – это означает, что цепочка подобных элементов продолжается в элементе таблицы 53 с номером 2. В свою очередь, второй элемент таблицы 53 имеет ссылку на элемент с номером 4 той же таблицы, а ссылка этого элемента содержит прочерк, из чего следует, что цепочка подобных элементов исчерпана. Таким образом, прослеженная связь моделирует состав учебной группы 01-ИЭ: в ней числятся студенты Иванов И.И., Сидоров С.С., Яковлев Я.Я.

Преимущество этого метода организации хранения иерархических структур состоит в однотипности списков ссылок: они всегда содержат по одной ссылке (пустой, если цепочка закончена).

Рассмотрим решение задач просмотра элементов дерева.

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

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

1. по списку учебных групп (таблица 52) находят нужный элемент с номером 2;

1. определяют первый порожденный элемент (по полю Ссылка на порожденные элементы) – он имеет номер 1 в списке студентов (таблица 53);

1. выводят соответствующую фамилию и инициалы – Иванов И.И.;

1. по полю Ссылка на подобный элемент таблицы 53 определяется следующий элемент в списке, относящийся к той же группе – это элемент с номером 2;

1. выводится фамилия и инициалы, находящиеся в элементе с номером 2 таблицы 53 – Сидоров С.С.;

1. по полю Ссылка на подобный элемент таблицы 53 определяется следующий элемент в списке, относящийся к той же группе, – это элемент с номером 4;

1. выводится фамилия и инициалы, находящиеся в элементе с номером 4 таблицы 53 – Яковлев Я.Я.;

1. по полю Ссылка на подобный элемент таблицы 53 определяется следующий элемент в списке, относящийся к той же группе. Поскольку ссылка содержит прочерк, цепочка студентов, учащихся в группе 01-ИЭ, закончена. Алгоритм заканчивает работу.

Рассмотрим, как выполняется добавление нового элемента.

Пример 22. Пусть в дерево рисунка 7 (описано в таблицах 52 и 53) надо включить элемент со структурой:

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

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

Очевидно, после включения этого элемента дерево рисунка 7 приобретет вид рисунка 8. Соответствующие изменения выполнены в таблицах 52 и 53, которые приобретут вид таблиц 54 и 55, соответственно (новые и измененные данные выделены заливкой):

Таблица 54                                      Таблица 55

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