1. Теоретические сведения 27

2. Алгоритм 28

3. Тестовый пример 29

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

5. Варианты заданий 29

6. Содержание отчёта 30

Приложение 1. Код программы 34

Приложение 2. Пример работы программы 36

Литература 36

1. Теоретические сведения 11

2. Алгоритмы 11

3. Тестовый пример 13

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

5. Варианты заданий 13

6. Содержание отчета 14

Приложение 14

Лабораторная работа №3 «Алгоритмы последовательного поиска в таблице записи данных»

Цель работы: изучение алгоритмов последовательного поиска (простого, быстрого и в упорядоченной таблице) с подсчетом числа сравнений.

1. Теоретические сведения

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

Алгоритм поиска использует аргумент K, и задача заключается в нахождении записи, для которой K служит ключом. Результат поиска: успешно (запись, содержащая K, найдена), либо неудачно. При неудачном поиске иногда вносят новую запись (содержащую K) в таблицу, называемую вставкой.

Цель поиска – нахождение информации, хранящейся в ассоциированной с K записи. Поиск является основополагающим действием многих программ и осуществляется над числовыми и символьными значениями.

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

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

2. Алгоритмы поиска

Алгоритм S. Последовательный поиск

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

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

Имеется таблица записей R_0,…,R_N-1, N > 0, где каждая из записей снабжена ключом K_0,…,K_N-1. Переменная i – служебная, используется для указания индекса текущей записи. Алгоритм состоит из четырех шагов, связанных одним циклом.

Шаг 1. [Начальная установка]. Установить i = 0.

Шаг 2. [Сравнение]. Если K = K_i, то поиск завершен, вернуть R_i.

Шаг 3. [Продвижение]. Увеличить i на единицу, то есть i = i + 1.

Шаг 4. [Завершение]. Если i < N (то есть, пройдены не все записи), вернуться к шагу 2, в противном случае поиск заканчивается неудачно.

Схема алгоритма приведена на рис. 1.

Алгоритм Q. Быстрый последовательный поиск

Этот алгоритм представляет усовершенствованный алгоритм S. Имеется аналогичная алгоритму S таблица записей с аналогичным набором ключей, однако в отличие от простого последовательного алгоритма, здесь предполагается, что в конце таблицы помещается вставка R_N, ключ которой K_N = K.

Шаг 1. [Начальная установка]. Установить i = 0, K_N = K.

Шаг 2. [Сравнение]. Если K = K_i, перейти к шагу 4.

Шаг 3. [Продвижение]. Увеличить i на единицу и перейти к шагу 2.

Шаг 4. [Завершение]. Если i < N, алгоритм заканчивается успешно; в противном случае алгоритм заканчивается неудачно.

При переходе от алгоритма S к алгоритму Q использован важный ускоряющий принцип – при нескольких проверках во внутреннем цикле их сводят к одной. Таким образом, с ростом числа записей в таблице наблюдается прирост производительности этого алгоритма по сравнению с предыдущим.

Схема алгоритма приведена на рис. 2.

Алгоритм T. Последовательный поиск в упорядоченной таблице

Имеется таблица записей R_0,…,R_N-1, N > 0, где каждой записи сопоставлен ключ K_i, при этом каждый следующий ключ должен быть численно больше предыдущего, то есть K_i > K_i-1. Для ускорения работы предполагается, что в конце таблицы расположена вставка R_N, ключ которой превышает значения всех остальных ключей: K_N = ∞ > K_i, i = 1,...,N-1.

Шаг 1. [Начальная установка]. Установить i = 0.

Шаг 2. [Сравнение]. Если K < K_i, перейти к шагу 4.

Шаг 3. [Продвижение]. Увеличить i на единицу и перейти к шагу 2.

Шаг 4. [Завершение]. Если K = K_i, алгоритм заканчивается успешно; в противном случае алгоритм заканчивается неудачно.

В предположении, что все входные аргументы-ключи равновероятны, алгоритм по скорости работы в случае успешного поиска аналогичен алгоритму Q; при неудачном же поиске отсутствие нужного ключа определяется примерно вдвое быстрее. Однако требование этого алгоритма – обязательное размещение ключей записей по возрастанию. Часто ключи в таблице так и располагаются, вследствие чего этот алгоритм является одним из наиболее востребованных.

Схема алгоритма приведена на рис. 3.