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

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

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

2. выписываются обозначения столбцов, начиная с первого столбца, - им соответствуют ключевые поля элементов предыдущего уровня иерархии дерева;

3. процесс выписывания обозначений строк и столбцов продолжается, чередуясь, пока ни будут выбраны все уровни иерархии дерева.

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

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

	СУиВТ	239				ТАМ	145
Иванов И.И.	к.т.н.	доцент	234567		Петров П.П.	к.т.н.	нет	456789
Сидоров С.С.	нет	нет	123456		Яковлев Я.Я.	д.т.н.	профессор	345678

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

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

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

Связи между вершинами дерева фиксируются в битовой матрице:

Обозначения строк	Обозначения столбцов
	СУиВТ	ТАМ
Иванов И.И.	1	0
Петров П.П.	0	1
Сидоров С.С.	1	0
Яковлев Я.Я.	0	1

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

№ п/п	ФИО	название
1	Иванов И.И.	СУиВТ
2	Петров П.П.	ТАМ
3	Сидоров С.С.	СУиВТ
4	Яковлев Я.Я.	ТАМ

Пусть надо определить, каков шифр кафедры, на которой работает сотрудник по фамилии и инициалам Сидоров С.С., т.е. К_доступ=<ФИО=Сидоров С.С.>. Задача решается следующим образом:

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

2. выбирают значение поля название – это СУиВТ;

3. по таблице (файлу) кафедра ищется строка (запись) с ключом СУиВТ – это запись с номером 1;

4. выводится значение поля шифр в вузе – это 239. Алгоритм заканчивает работу.

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

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

2. выбирают значение поля ФИО – это Иванов И.И.;

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

4. по физической модели битовой матрицы путем последовательного сканирования находят следующую запись с требуемой кафедрой – это запись с номером 3;

5. выбирают значение поля ФИО – это Сидоров С.С.;

6. по таблице (файлу) сотрудник ищется запись с первичным ключом Сидоров С.С. – это запись с номером 3 – выводится значение поля контактные данные – 123456;

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