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

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

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

Таблица 23

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

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

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

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

Таблица 27

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

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 надо добавить элемент со структурой:

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

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

Таблица 28

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