Глава 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