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

Для хранения подобных элементов в иерархических структурах используются линейные списки. Элементы списков могут иметь одно или несколько полей, среди которых можно выделять первичные и вторичные ключи. Для указания связей, которые образуют иерархические структуры, применяют систему ссылок. В случае, когда это ссылки на порожденные элементы, каждая из них ссылается на некоторый порожденный элемент. Количество таких ссылок соответствует числу порожденных элементов. Поскольку у элементов максимального уровня иерархии дерева нет порожденных элементов, у них отсутствуют какие-либо ссылки.

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

  Таблица 45                       Таблица 46

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

Теперь надо показать связи между элементами, указанные в дереве. Для этого, в соответствии с рассматриваемым способом, сформируем у списка из таблицы 45 дополнительное поле Ссылки, в котором и зафиксируем требуемые связи. Получим таблицу 47:

   Таблица 47

№ п/п	Шифр учебной группы	Ссылки
1	01-АС	3
2	01-ИЭ	1,2,4

                       

Как видно из таблицы 47, ссылки для группы 01-АС относятся к элементу с номером 3 из таблицы 46, в котором хранится информация о студенте Федорове Ф.Ф., а ссылки для группы 01-ИЭ относятся к элементам с номерами 1, 2, 4 из той же таблицы, где хранится информация о студентах, учащихся в данной группе. Таким образом, совокупность таблиц 47 и 46 моделирует дерево рисунка 7.

Следует отметить, что подобные элементы могут иметь в свою очередь некоторую структуру. Например, такую, какая показана в таблицах 48 и 49:

Таблица 48                                           Таблица 49

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

Тем не менее, в графическом изображении дерева (см. рисунок 7), как правило, элементы указываются своими ключевыми полями.

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

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

Задача решается следующим образом:

1. по линейному списку с шифрами учебных групп (таблица 48) находят требуемую группу (для решения этой задачи применимы методы поиска, рассмотренные ранее для линейных списков) – это элемент с номером 2;

1. выбирают ссылки – это множество {1, 2, 4};

1. по линейному списку с фамилиями студентов (таблица 49) обращаются к элементам с номерами 1, 2 и 4. Получают список студентов: Иванов И.И., Федоров Ф.Ф., Яковлев Я.Я. Алгоритм заканчивает работу.

Пример 19. Пусть надо определить, в какой группе учится студент Иванов И.И. (эта задача подобна задаче поиска по первичному ключу в линейном списке), т.е. q^{просмотр} = (ФИО студента = Иванов И.И., Шифр учебной группы), где К_доступ = Иванов И.И. Поскольку при рассматриваемой организации структур хранения отсутствует связь элементов второго уровня дерева  с элементами первого уровня, поиск следует организовать, начиная с учебных групп. Задача решается следующим образом:

1. выбирается первый элемент в списке учебных групп (таблица 48). Это группа с шифром 01-АС;

1. по значению ссылки обращаются к соответствующему элементу (он имеет номер 3) списка студентов (таблица 49);

1. сравнивают фамилию и инициалы студента с искомой фамилией и инициалами. Поскольку Федоров Ф.Ф. ≠ Иванов И.И., управление возвращается к просмотру таблицы 48;

1. в списке учебных групп выбирают следующий (второй) элемент. Это группа с шифром 01-ИЭ;

1. в списке ссылок этой группы выбирают первую ссылку (это 1) и в списке студентов находят первый элемент;

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

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

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

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

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

Очевидно, после включения этого элемента дерево рисунка 7 приобретет другой вид (новый элемент выделен полужирным шрифтом):

                       Рисунок 8

Соответствующие изменения выполнены в таблицах 46 и 47, которые приобретут вид таблиц 51 и 50, соответственно (новые и измененные данные выделены заливкой):

         Таблица 50                           Таблица 51

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