Элементы, связанные в цепь

К исходному линейному списку не предъявляется никаких требований. К нему достраиваются дополнительные списки – индексы - в количестве, соответствующем числу вторичных ключей доступа. Элементы таких списков имеют два поля: первое – значение вторичного ключа из основного списка, второе – ссылка на первый элемент в основном списке с таким же значением вторичного ключа. Сами элементы основного списка также модифицируются: они дополняются полями в количестве, соответствующем числу вторичных ключей доступа. Каждое поле служит для организации цепочек записей с одним значением вторичного ключа.

Пример 11. Пусть основной линейный список имеет вид таблицы 23:

Таблица 23

№ п/п	ФИО студента	Шифр учебной группы	Дисциплина	Оценка
	Иванов И.И.	01-ИЭ	Информатика
	Петров П.П.	02-ВТ	Программирование
	Сидоров С.С.	01-ИЭ	Информатика
	Федоров Ф.Ф.	01-АС	Программирование
	Яковлев Я.Я.	01-ИЭ	Физика

Вторичными ключами являются Шифр учебной группы, Дисциплина, Оценка. Построим индексы для этих ключей (таблицы 24 – 26):

Таблица 24 Таблица 25 Таблица 26

№ п/п	Шифр учебной группы	Ссылка		№ п/п	Дисциплина	Ссылка		№ п/п	Оценка	Ссылка
	01-АС				Информатика
	01-ИЭ				Программирование
	02-ВТ				Физика

Как видно из таблиц 24 – 26, каждый индекс содержит поле со всеми значениями соответствующего вторичного ключа из основного списка и поле (озаглавлено Ссылка), в котором указывается номер элемента основного списка, где впервые встречается соответствующее значение вторичного ключа. Значения вторичных ключей в индексах упорядочены по возрастанию, так что с индексами можно работать как с упорядоченными линейными списками (в роли первичных ключей таких списков выступают вторичные ключи основных списков).

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

Таблица 27

№ п/п	ФИО студента	Шифр учебной группы	Ссылка	Дисциплина	Ссылка	Оценка	Ссылка
	Иванов И.И.	01-ИЭ		Информатика
	Петров П.П.	02-ВТ	-	Программирование
	Сидоров С.С.	01-ИЭ		Информатика	-		-
	Федоров Ф.Ф.	01-АС	-	Программирование	-		-
	Яковлев Я.Я.	01-ИЭ	-	Физика	-		-

Рассмотрим, например, как сформировано поле Ссылка для вторичного ключа Шифр учебной группы:

1. элемент с номером 1 имеет ссылку на элемент с номером 3: это следующий элемент основного списка со значением шифра группы 01-ИЭ;

2. элемент с номером 3 имеет ссылку на элемент с номером 5: это следующий элемент основного списка со значением шифра группы 01-ИЭ;

3. элемент с номером 5 – последний в основном списке со значением вторичного ключа Шифр учебной группы, равным 01-ИЭ. Поэтому он имеет пустую ссылку «-»;

4. элемент с номером 2 - единственный в основном списке со значением вторичного ключа 02-ВТ, поэтому он имеет пустую ссылку «-»;

5. элемент с номером 4 - единственный в основном списке со значением вторичного ключа 01-АС, поэтому он имеет пустую ссылку «-».

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

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

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

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

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

3. в основном списке выбирается первый элемент. Выводится фамилия и инициалы студента – это Иванов И.И.;

4. в соответствии со значением поля Ссылка для поля Дисциплина определяется номер следующего элемента основного списка с аналогичным значением вторичного ключа – это элемент № 3;

5. выбирается третий элемент. Выводится фамилия и инициалы студента – это Сидоров С.С.;

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

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

Пример 13. Пусть в основной список таблицы 27 надо добавить элемент со структурой:

ФИО студента	Шифр учебной группы	Дисциплина	Оценка
Ковалев К.К.	02-ВТ	Программирование

т.е. q^{добавление} = (ФИО студента = Ковалев К.К., Шифр учебной группы = 02-ВТ, Дисциплина = Программирование, Оценка = 2), где К_доступ = Ковалев К.К.

Поскольку процедуры добавления подробно рассматривались ранее, проследим, как в результате модифицировались основной список и три индекса (таблицы 28 – 31). Измененные значения ссылок выделены заливкой; новые элементы в основном списке и в таблице 31 выделены полужирным шрифтом:

Таблица 28

№ п/п	ФИО студента	Шифр учебной группы	Ссылка	Дисциплина	Ссылка	Оценка	Ссылка
	Иванов И.И.	01-ИЭ		Информатика
	Ковалев К.К.	02-ВТ		Программирование			-
	Петров П.П.	02-ВТ	-	Программирование
	Сидоров С.С.	01-ИЭ		Информатика	-		-
	Федоров Ф.Ф.	01-АС	-	Программирование	-		-
	Яковлев Я.Я.	01-ИЭ	-	Физика	-		-

Таблица 29 Таблица 30 Таблица 31