Ссылки на подобные и порожденные элементы
Аналогично предыдущему методу подобные элементы описываются в линейных списках. Для указания связей применяют два вида ссылок: одна фиксирует связь с первым порожденным элементом, вторая – с подобным. Причем с помощью подобия показывается, каким родительским элементам принадлежат порожденные элементы. Для элементов максимального уровня иерархии поддерживается только одна ссылка (на подобные элементы), поскольку они не имеют порожденных элементов; для элементов первого уровня иерархии также поддерживается одна ссылка (на порожденные элементы), поскольку все они имеют одного родителя – корень. Для остальных элементов поддерживается две ссылки.
Рассмотрим данную организацию хранения элементов для дерева рисунка 7, которое представлено таблицами 52, 53:
Таблица 52 Таблица 53
№ п/п | Шифр учебной группы | Ссылка на порожденный элемент | № п/п | ФИО студента | Ссылка на подобный элемент | |
01-АС | Иванов И.И. | |||||
01-ИЭ | Сидоров С.С. | |||||
Федоров Ф.Ф. | - | |||||
Яковлев Я.Я. | - |
Для элементов уровня учебных групп (первого уровня дерева) устанавливаются только ссылки на порожденные элементы, причем на первые из них в множестве порожденных элементов. Так, для элемента таблицы 52 01-ИЭ ссылка со значением 1 показывает, что первый порожденный элемент (из таблицы 53) имеет номер 1. В таблице 53 для элемента 1 ссылка на подобные элементы имеет значение 2 – это означает, что цепочка подобных элементов продолжается в элементе таблицы 53 с номером 2. В свою очередь, второй элемент таблицы 53 имеет ссылку на элемент с номером 4 той же таблицы, а ссылка этого элемента содержит прочерк, из чего следует, что цепочка подобных элементов исчерпана. Таким образом, прослеженная связь моделирует состав учебной группы 01-ИЭ: в ней числятся студенты Иванов И.И., Сидоров С.С., Яковлев Я.Я.
Преимущество этого метода организации хранения иерархических структур состоит в однотипности списков ссылок: они всегда содержат по одной ссылке (пустой, если цепочка закончена).
Рассмотрим решение задач просмотра элементов дерева.
Пример 21. Пусть надо выявить список студентов, числящихся в группе 01-ИЭ, т.е. qпросмотр = (Шифр учебной группы = 01-ИЭ, ФИО студента), где Кдоступ = 01-ИЭ.
Решение задачи:
1. по списку учебных групп (таблица 52) находят нужный элемент с номером 2;
2. определяют первый порожденный элемент (по полю Ссылка на порожденные элементы) – он имеет номер 1 в списке студентов (таблица 53);
3. выводят соответствующую фамилию и инициалы – Иванов И.И.;
4. по полю Ссылка на подобный элементтаблицы 53 определяется следующий элемент в списке, относящийся к той же группе – это элемент с номером 2;
5. выводится фамилия и инициалы, находящиеся в элементе с номером 2 таблицы 53 – Сидоров С.С.;
6. по полю Ссылка на подобный элемент таблицы 53 определяется следующий элемент в списке, относящийся к той же группе, – это элемент с номером 4;
7. выводится фамилия и инициалы, находящиеся в элементе с номером 4 таблицы 53 – Яковлев Я.Я.;
8. по полю Ссылка на подобный элемент таблицы 53 определяется следующий элемент в списке, относящийся к той же группе. Поскольку ссылка содержит прочерк, цепочка студентов, учащихся в группе 01-ИЭ, закончена. Алгоритм заканчивает работу.
Рассмотрим, как выполняется добавление нового элемента.
Пример 22. Пусть в дерево рисунка 7 (описано в таблицах 52 и 53) надо включить элемент со структурой:
ФИО студента | Шифр учебной группы |
Комаров К.К. | 01-АС |
т.е. qдобавление = (ФИО студента= Комаров К.К., Шифр учебной группы = 01-АС), где Кдоступ = Комаров К.К., 01-АС.
Очевидно, после включения этого элемента дерево рисунка 7 приобретет вид рисунка 8. Соответствующие изменения выполнены в таблицах 52 и 53, которые приобретут вид таблиц 54 и 55, соответственно (новые и измененные данные выделены заливкой):
Таблица 54 Таблица 55
№ п/п | Шифр учебной группы | Ссылка на порожденный элемент | № п/п | ФИО студента | Ссылка на подобный элемент | |
01-АС | Иванов И.И. | |||||
01-ИЭ | Комаров К.К. | |||||
Сидоров С.С. | ||||||
Федоров Ф.Ф. | - | |||||
Яковлев Я.Я. | - |
Дата добавления: 2015-03-03; просмотров: 562;