10. Ускоренный поиск, основанный на использовании общего справочника (2.Ж)

Общий справочник может создаваться на основе неупорядоченного массива, содержащего записи фиксированной или переменной длины. В нем для каждой записи основного массива создается одна справочная запись, называемая статьей. Статья содержит значения ключевого поля и и указатель, определяющий адрес записи в информационном массиве. Статьи в справочнике упорядочиваются по значениям ключа. Поиск реализуется одним из методов ускоренного поиска (двоичный – 2.ж.1, блочный – 2.ж.2) в справочнике, по полученному указателю происходит выбор требуемой записи из информационного массива. При пополнении информационного массива происходит пополнение справочника, при условии сохранения упорядоченности.

Ускоренный поиск, основанный на использовании единого справочника (2.з)

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

2. Лабораторная работа №2

"Программирование алгоритмов ускоренного поиска информации"

Цель работы

Приобретение навыков реализации алгоритмов программного поиска в информационных массивах.

Задание кафедры

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

1. Контрольные вопросы

1. Виды информационного поиска.

2. Методы поиска.

Содержание отчета

1. Титульный лист.

2. Задание кафедры, соответствующее варианту.

3. Цель работы.

4. Краткие теоретические сведения.

5. Формализованный алгоритм.

6. Листинг программы.

7. Контрольный пример.

8. Выводы по работе.

1. Библиографический список

1. Кнут, Д. Э. Искусство программирования, том 3. Сортировка и поиск / Д. Э. Кнут. – М.: "Вильямс", 2000. – 832 с.

2. Ахо, А. В. Структуры данных и алгоритмы / А. В. Ахо, Дж. Хопкрофт, Дж. Д. Ульман. – М.: "Вильямс", 2000. – 384 с.

3. Кондратьева, С. Д. Введение в структуры данных / С. Д. Кондратьева. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2000. – 376 с.

4. Макконнелл, Дж. Основы современных алгоритмов / Дж. Макконнелл. – М.: Техносфера, 2004. – 368 с.

Таблица 2