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

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

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

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

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

Таблица 47

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рисунок 8

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

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