Мансуров. Основы программирования в среде Lazarus. 2010
.pdfГлава 4 Типовые алгоритмы обработки информации
____________________________________________________________________
{Подготовка к внутренней сортировке,
считывание записей файла в массив,
в процедуру передается массив, а не файл.}
i:= 0;
while not Eof(f_not_sorted) do begin
Read(f_not_sorted, company); vector[i]:= company; // сортируемый массив i:= i + 1;
end;
QuickSort(vector); // вызов процедуры быстрой сортировки
CloseFile(f_not_sorted);
AssignFile(f_sorted, 'File_sorted.dat');
Rewrite(f_sorted);
for i:= 0 to n - 1 do Write(f_sorted, vector[i]); CloseFile(f_sorted); name_file:= 'File_sorted.dat';
{Вызов процедуры для вывода на экран сводной ведомости.
Процедура находится в модуле OutScr}
output_to_screen(name_file);
write(UTF8ToConsole('Нажмите любую клавишу'));
readkey;
end.
Резюмируя все вышесказанное относительно методов сортировки можно сказать, что наиболее часто используются метод вставок и алгоритм быстрой сортировки Хоара. Что касается других алгоритмов сортировки, то вы можете их найти в специальной литературе [9, 10, 12].
311
4.2 Алгоритмы поиска
____________________________________________________________________
4.2. Алгоритмы поиска
Поиск каких-либо данных, наряду с сортировкой, является одной из наи-
более распространенных задач при разработке сколько-нибудь сложных про-
граммных проектов, в частности при разработке информационно-поисковых и информационно-справочных систем. В любой базе данных присутствуют зада-
чи сортировки и поиска. Алгоритмы поиска являются не менее сложными и ин-
тересными, чем алгоритмы сортировки.
Рассмотрим некоторые алгоритмы поиска в массивах.
4.2.1 Поиск в массивах
Пусть нам дан какой-нибудь массив. Требуется найти элемент массива по заданному ключу. Первое, что приходит на ум, чтобы решить эту задачу, это последовательно сравнивать элементы массива с заданным ключом, пока не бу-
дет найден искомый элемент. Если элемент найден, алгоритм должен выдать номер индекса этого элемента в массиве. Если же такого элемента в массиве нет, то алгоритм должен нам каким-то образом сообщить об этом. Чаще всего в таком случае алгоритм возвращает значение, которого заведомо нет в массиве,
а точнее такого индекса. Такой алгоритм называется алгоритмом линейного по-
иска. Напишем соответствующую функцию в предположении, что поиск ведет-
ся в массиве целых чисел.
function LinearSearch(var a: array of integer;
key: integer): integer;
var
i: integer;
begin
312
Глава 4 Типовые алгоритмы обработки информации
____________________________________________________________________
for i:= 0 to High(a) do
begin
if key = a[i] then
begin
LinearSearch:= i;
exit;
end;
end;
LinearSearch:= -1;
end;
Итак, эта функция возвращает нам номер индекса в массиве, где находится искомый элемент. Возвращать само значение не имеет смысла, мы и так его знаем (значение key). В случае отсутствия искомого элемента функция воз-
вращает -1. Обратите внимание, в самом массиве может быть и есть элемент со значением -1, но функция возвращает индекс элемента в массиве. Как мы зна-
ем, индекс не может быть отрицательным, возврат -1 и говорит нам о том, что искомого элемента в массиве нет.
Программа линейного поиска для целочисленного массива:
program search_in_array; uses
CRT, FileUtil; const SizeOfFile= 9; var
a:array[0..SizeOfFile] of integer = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10); n: integer;
key: integer;
313
4.2 Алгоритмы поиска
____________________________________________________________________
{ ============= Линейный поиск ======== } function LinearSearch(var a:array of integer;
key: integer): integer;
var
i: integer; begin
for i:=0 to SizeOfFile do begin
if key = a[i] then begin
LinearSearch := i; exit;
end;
end; LinearSearch:= -1; end;
{ ======================================== }
begin
writeln(UTF8ToConsole('Введите ключ для поиска')); readln(key);
{вызов функции поиска}
n:= LinearSearch(a, key);
if n= -1 then
writeln(UTF8ToConsole('Такого элемента в массиве нет'))
else
writeln(UTF8ToConsole('Элемент найден, его номер в массиве '),
n);
write(UTF8ToConsole('Нажмите любую клавишу'));
314
Глава 4 Типовые алгоритмы обработки информации
____________________________________________________________________
readkey;
end.
Напишем программу поиска менеджера по фамилии. Для удобства провер-
ки результатов работы программы, одновременно выводится весь файл менед-
жеров и указывается номер искомой записи.
program search_in_file; uses
CRT, FileUtil, SysUtils, OutScr; type
manager= record name: string[18]; comp: integer;
end; var
company: manager;
f_not_sorted: File of manager; // Файловая переменная vector: array of manager;
i, n: integer; name_file: string; name_manager: string;
{ ========= Линейный поиск ======== } function LinearSearch(var not_sorted_array:
array of manager; name_manager: string): integer;
var
i: integer;
315
4.2 Алгоритмы поиска
____________________________________________________________________
begin
for i:= 0 to High(not_sorted_array) do begin
if name_manager = not_sorted_array[i].name then begin
LinearSearch := i; exit;
end;
end; LinearSearch:= -1; end;
{ ================================== }
begin
{При необходимости укажите полный путь к файлу
или скопируйте файл в папку с данным проектом}
if not FileExists('File_not_sorted.dat') then
begin
writeln(UTF8ToConsole('Файл не существует'));
writeln(UTF8ToConsole('Сначала создайте его'));
writeln(UTF8ToConsole('Нажмите любую клавишу'));
readkey;
exit;
end;
AssignFile(f_not_sorted,'File_not_sorted.dat');
Reset(f_not_sorted);
// Определение количества записей в файле
n:= System.FileSize(f_not_sorted);
SetLength(vector, n);
316
Глава 4 Типовые алгоритмы обработки информации
____________________________________________________________________
{Подготовка поиску,
считывание записей файла в массив,
в функцию передается массив, а не файл.}
i:= 0;
while not Eof(f_not_sorted) do begin
Read(f_not_sorted, company);
vector[i]:= company; // массив, в которым будет вестись поиск i:= i + 1;
end; CloseFile(f_not_sorted);
writeln(UTF8ToConsole('Введите фамилию менеджера')); readln(name_manager);
{вызов функции поиска}
n:= LinearSearch(vector, name_manager);
name_file:= 'File_not_sorted.dat';
{Вызов процедуры для вывода на экран списка менеджеров.
Процедура находится в модуле OutScr}
output_to_screen(name_file);
if n= -1 then
writeln(UTF8ToConsole('Такого менеджера нет'))
else
writeln(UTF8ToConsole('Менеджер найден, его номер '),
n+1);
write(UTF8ToConsole('Нажмите любую клавишу'));
readkey;
end.
Очевидно, что время поиска по этому алгоритму зависит от размера масси-
317
4.2 Алгоритмы поиска
____________________________________________________________________
ва – количества его элементов n. Т.е. этот алгоритм принадлежит классу O(n).
Если массив неупорядочен, то единственный способ найти какой-либо элемент, это линейный поиск. Если же массив упорядочен, то существуют бо-
лее быстрые и эффективные алгоритмы. Наиболее часто используемым являет-
ся алгоритм двоичного (бинарного) поиска. Его также часто называют метод деления пополам.
Суть метода в том, что, пользуясь тем, что массив отсортирован, вместо просмотра подряд всех элементов массива, находим элемент, находящийся по-
середине массива. Назовем его средним элементом (не по значению, а по месту в массиве). Затем сравниваем искомый элемент с этим средним элементом. Ес-
ли искомый элемент меньше среднего, то искать теперь его следует только сре-
ди тех, которые меньше среднего. Таким образом, диапазон поиска уменьшает-
ся ровно наполовину. Берем ту половину массива, где следует искать наш эле-
мент и опять находим средний элемент, опять его сравниваем с искомым эле-
ментом и вновь суживаем зону поиска наполовину и т.д. продолжаем процесс до тех пор, пока в рассматриваемых подмассивах не останется один элемент.
Если он равен искомому, значит элемент найден, если не равен, значит такого элемента в массиве нет.
При выполнении алгоритма в каждом следующем цикле размер массива уменьшается в два раза, отсюда оценка скорости работы алгоритма O(log2n).
Напишем программу бинарного поиска в массиве целых чисел:
program search_in_array; {$mode objfpc}{$H+} uses
CRT, FileUtil; const SizeOfFile= 9; var
a: array[0..SizeOfFile] of integer =
318
Глава 4 Типовые алгоритмы обработки информации
____________________________________________________________________
(1, 2, 3, 4, 5, 6, 7, 8, 9, 10); n: integer;
key: integer;
{ ======== Бинарный поиск ======== }
function BinarySearch(var a: array of integer; key: integer): integer;
var
left, right, middle: integer; begin
left:= Low(a); right:= High(a); repeat
middle:= (left + right) div 2; if key < a[middle] then
right:= middle - 1 else
if key > a[middle] then left:= middle + 1
else begin
BinarySearch:= middle; exit;
end;
until left > right; BinarySearch:= -1;
end;
{ ========================================== }
319
4.2 Алгоритмы поиска
____________________________________________________________________
begin
writeln(UTF8ToConsole('Введите ключ для поиска'));
readln(key);
{вызов функции поиска}
n:= BinarySearch(a, key);
if n= -1 then
writeln(UTF8ToConsole('Такого элемента в массиве нет'))
else
writeln(UTF8ToConsole('Элемент найден, его номер '), n); writeln(UTF8ToConsole('Нажмите любую клавишу'));
readkey;
end.
Напишем программу поиска в файле менеджеров по фамилии бинарным методом:
program search_in_file; uses
CRT, FileUtil, SysUtils, OutScr; type
manager= record name: string[18]; comp: integer;
end; var
company: manager;
f_not_sorted, f_sorted: File of manager; vector: array of manager;
i, n: integer;
320