Кольцевые структуры. В отличие от предыдущих методов позволяют от порожденных элементов переходить к родительским элементам

В отличие от предыдущих методов позволяют от порожденных элементов переходить к родительским элементам. Для этого в структуре элементов поддерживаются специальные ссылки на родительские элементы.

Представим данным методом дерево рисунка 7. Его описание сведем в таблицы 56, 57:

Таблица 56 Таблица 57

Как видно, в таблицах 56 и 57 отсутствуют пустые ссылки. Это означает, что конечные элементы в цепочках подобных элементов ссылаются на первые элементы в этих цепочках. Так получаются «горизонтальные» кольца. Наличие таких колец позволяет решать задачи, требующие многократного просмотра списка от начала к концу. Подобная задача, например, имеет место при сортировке линейного списка некоторыми методами. Например, когда требуется отсортировать список студентов группы 01-ИЭ по возрастанию значений ключа, а группы 01-АС – по убыванию.

В то же время совокупность ссылок на порожденные и родительские элементы формирует «вертикальные» кольца. Они позволяют переходить от порожденных элементов к родительским, чего не было в предыдущих методах.

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

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

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

1. по списку студентов (таблица 57) определяется элемент, соответствующий искомой фамилии и инициалам – это элемент с номером 1;

2. в поле Ссылка на родительский элемент таблицы 57 определяется номер его родительского элемента в списке учебных групп – это номер 2;

3. в списке учебных групп (таблица 56) ищется элемент с номером 2 и выводится шифр группы – 01-ИЭ.

Поисковые задачи, аналогичные формированию списка студентов заданной группы, решаются подобно предыдущим примерам.

Добавление нового элемента выполняется аналогично предыдущим методам (рассмотреть самостоятельно).