Далее будем предполагать, что у нас есть N записей, уже упорядоченных по ключам так, что К1<К2<…<КN. Пусть дан ключ К и нужно найти соответствующую запись в файле (безуспешный поиск).
Предположим, что мы обратились к середине файла и обнаружили там ключ Ki. Сравним К и Кi. Если К=Кi, то нужная запись найдена. Если К<Кi, то ключ К должен находиться в части файла, предшествующей Кi (если запись с ключом К вообще существует). Аналогично, если Кi<К, то дальнейший поиск следует вести в части файла, следующей за Кi. Если повторять эту процедуру проверки ключа Кi из середины непросмотренной части файла , тогда каждое безуспешное сравнение К с Кi будет исключать из рассмотрения приблизительно половину непросмотренной части.
Блок-схема этой процедуры, известной под названием двоичный поиск, приведена на рис.13.
Algorithm BSEARCH (Binary search - двоичный поиск) поиска записи с ключом К в файле с N≥2 записями , ключи которых упорядочены по возрастанию К1<К2…<КN.
Шаг 0.[Инициализация] SetFIRST←1; LAST← N. (FIRST и LAST- указатели первого и последнего ключей в еще не просмотренной части файла.)
Шаг 1.[Основной цикл] While LAST≥FIRST do through шаг 4 od.
Шаг 2. [Получение центрального ключа] SetI←|_(FIRST + LAST)/2_| .(Кi- ключ, расположенный в середине или слева от середины еще не просмотренной части файла.)
Шаг 3.[Проверка на успешное завершение ] If К=КI thenPRINT «Успешное окончание, ключ равен КI»;andSTOP fi.
Шаг 4. [Сравнение] If K<KI then set LAST←I-1 else set
FIRST←I+1 fi.
Шаг 5. [Безуспешный поиск] PRINT «безуспешно»; and STOP.
Алгоритм BSEARCH используется для отыскания К=42 на рис. 14.
Метод двоичного поиска можно также применить для того, чтобы представить упорядоченный файл в виде двоичного дерева. Значение ключа, найденное при первом выполнении шага 2 (К(8)=53), является корнем дерева. Интервалы ключей слева (1,7) и справа (9,16) от этого значения помещаются на стек. Верхний интервал снимается со стека и с помощью шага 2 в нем отыскивается средний элемент (или элемент слева от середины). Этот ключ (К(4)=33) становится следующим после корня элементом влево, если его значение меньше значения корня, и следующим вправо в противном случае.
Рис. 13. Блок-схема двоичного поиска.
Алгоритм BSEARCH используется для отыскания К=42 на рис.14.
Подынтервалы этого интервала справа и слева от вновь добавленного ключа [(1,3), (5,7)] помещаются теперь на стек. Эта процедура повторяется до тех пор, пока стек не окажется пустым. На рис.15 показано двоичное дерево, которое было бы построено для 16 упорядоченных ключей с рис. 14.
Двоичный поиск можно теперь интерпретировать как прохождение этого дерева от корня до искомой записи. Если достигнута конечная вершина, а заданный ключ не найден, искомая запись в данном файле отсутствует. Заметим, что число вершин на единственном пути от корня к заданному ключу К равно числу сравнений, выполняемых алгоритмом BSEARCH при попытке отыскания К.
Рис. 14. Использование алгоритма BSEARCH для отыскания записи с ключом 42.
Рис. 15. Представление файла с рис. 17 в виде двоичного дерева,
построенного с помощью алгоритма BSEARCH.
Курсовая работа представляется к защите в виде пояснительной записки и дискеты с файлами программы. Пояснительная записка включает в себя титульный лист (см. приложение 5), задание, содержание, введение, основную часть, заключение и приложения (в том числе, при необходимости, определения, обозначения, сокращения).
Задание выдается преподавателем в первые две недели семестра.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.