Конспект лекций для специальности «Прикладная информатика в экономике» (стр. 6 )

Рассмотрим, как выполняется задача поиска нужной записи.

Пусть надо определить список всех сотрудников, работающих в должности доцента, Кдоступ = <название (должности) = доцент>. Поиск осуществляется последовательным выполнением шагов:

1)  по индексу для ключа (название должности) находится соответствующий элемент: это вторая запись в файле;

2)  выбираются ссылки для этой записи: это множество {1, 2};

3)  по основному файлу выбираются последовательно записи с номерами 1 и 2 и выводится содержимое поля ФИО для этих записей; получаем список - и Петров алгоритма закончена.

3.4.2. Методы физического проектирования для иерархических моделей

Традиционными способами организации хранения иерархических моделей являются: множественные ссылки на порожденные записи, ссылки на порожденные и подобные записи; кольцевые структуры; справочники, битовые отображения.

3.4.2.1. Множественные ссылки на порожденные записи

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

Рассмотрим данную организацию хранения элементов для дерева, описывающего состав кафедр некоторого факультета:

 

Поскольку в этом дереве есть два множества подобных элементов (кафедры и сотрудники), сформируем для них таблицы:

сотрудник кафедра

ФИО	ученая степень	научное звание	контактные данные		название	шифр в вузе
	к. т.н.	доцент	234567		СУиВТ	239
	к. т.н.	нет	456789		ТАМ	145
	нет	нет	123456
	д. т.н.	профессор	345678

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

название	шифр в вузе	ссылки
СУиВТ	239	1, 3
ТАМ	145	2, 4

В таком дереве «хорошо» решаются задачи поиска записей в направлении от корня к терминальным вершинам.

Пусть надо сформировать список сотрудников кафедры СУиВТ (эта задача подобна задаче поиска по вторичному ключу для линейных списков), т. е. Кдоступ = <название (кафедры) = СУиВТ>. Задача решается следующим образом:

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

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

3)  по линейному списку с фамилиями сотрудников обращаются к элементам с номерами 1и 3. Получают список сотрудников: , Сидоров заканчивает работу.

3.4.2.2. Ссылки на подобные и порожденные записи

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

Рассмотрим данную организацию хранения элементов для дерева:

 

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

сотрудник кафедра

ФИО	ученая степень	научное звание	контактные данные	ссылки		название	шифр в вузе	ссылки
	к. т.н.	доцент	234567	3		СУиВТ	239	1
	к. т.н.	нет	456789	4		ТАМ	145	2
	нет	нет	123456	-
	д. т.н.	профессор	345678	-

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

3.4.2.3. Кольцевые структуры

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

Представим данным методом дерево:

 

Его описание сведем в таблицы:

сотрудник кафедра

ФИО	ученая степень	научное звание	контактные данные	ссылки на подобные	ссылки на родительские		название	шифр в вузе	ссылки
	к. т.н.	доцент	234567	3	1		СУиВТ	239	1
	к. т.н.	нет	456789	4	2		ТАМ	145	2
	нет	нет	123456	1	1
	д. т.н.	профессор	345678	4	2

Как видно, в таблице сотрудников отсутствуют пустые ссылки. Это означает, что конечные записи в цепочках подобных записей ссылаются на первые записи в этих цепочках. Так получаются «горизонтальные» кольца. Наличие таких колец позволяет решать задачи, требующие многократного просмотра записей от начала к концу. Подобная задача, например, имеет место при сортировке файла некоторыми методами. Например, когда требуется отсортировать список сотрудников кафедры СУиВТ по возрастанию значений ключа, а кафедры ТАМ – по убыванию. В то же время совокупность ссылок на порожденные и родительские записи формирует «вертикальные» кольца. Они позволяют переходить от порожденных записей к родительским, чего не было в предыдущих методах.

3.4.2.4. Справочники

Связи между записями дерева формируют отдельное описание в виде файла-справочника.

Пусть исходное дерево имеет вид:

 

Описание сотрудников и кафедр располагается в таблицах:

сотрудник кафедра

ФИО	ученая степень	научное звание	контактные данные		название	шифр в вузе
	к. т.н.	доцент	234567		СУиВТ	239
	к. т.н.	нет	456789		ТАМ	145
	нет	нет	123456
	д. т.н.	профессор	345678

Сформируем для дерева справочник:

обозначение поля	элемент дерева	родительская запись	порожденная запись
название (кафедры)	СУиВТ	-	3, 5
название (кафедры)	ТАМ	-	4, 6
ФИО		1	-
ФИО		2	-
ФИО		1	-
ФИО		2	-

3.4.2.5. Битовые отображения

Структура дерева представляется бинарной матрицей. Вначале формируются обозначения столбцов и строк матрицы следующим образом: