Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
К исходному линейному списку не предъявляется никаких требований. К нему достраиваются дополнительные списки – индексы - в количестве, соответствующем числу вторичных ключей доступа. Элементы таких списков имеют два поля: первое – значение вторичного ключа из основного списка, второе – ссылка на первый элемент в основном списке с таким же значением вторичного ключа. Сами элементы основного списка также модифицируются: они дополняются полями в количестве, соответствующем числу вторичных ключей доступа. Каждое поле служит для организации цепочек записей с одним значением вторичного ключа.
Пример 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
Дата публикования: 2015-09-17; Прочитано: 249 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!