Материал: Мансуров. Основы программирования в среде Lazarus. 2010

Глава 4 Типовые алгоритмы обработки информации

____________________________________________________________________

name_file: string; name_manager: string;

{ ======= Бинарный поиск ======== }

function BinarySearch(var a: array of manager; name_manager: string): integer;

var

left, right, middle: integer; begin

left:= Low(a); right:= High(a); repeat

middle:= (left + right) div 2;

if name_manager < a[middle].name then right:= middle - 1

else

if name_manager > a[middle].name then left:= middle + 1

else begin

BinarySearch:= middle; exit;

end;

until left > right; BinarySearch:= -1;

end;

{ ========================================= } begin

{При необходимости укажите полный путь к файлу

или скопируйте файл в папку с данным проектом}

321

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

____________________________________________________________________

if not FileExists('File_not_sorted.dat') then

begin

writeln(UTF8ToConsole('Файл не существует'));

writeln(UTF8ToConsole('Сначала создайте его'));

writeln(UTF8ToConsole('Нажмите любую клавишу'));

readkey;

exit;

end;

AssignFile(f_sorted,'File_sorted.dat');

Reset(f_sorted);

n:= System.FileSize(f_sorted);

SetLength(vector, n);

{Подготовка к поиску,

считывание записей файла в массив,

в функцию передается массив, а не файл.}

i:= 0;

while not Eof(f_sorted) do begin

Read(f_sorted, company);

vector[i]:= company; // массив, который будет сортироваться i:= i + 1;

end; CloseFile(f_sorted);

writeln(UTF8ToConsole('Введите фамилию менеджера')); readln(name_manager);

{вызов функции поиска}

n:= BinarySearch(vector, name_manager);

name_file:= 'File_sorted.dat';

{Вызов процедуры для вывода на экран сводной ведомости.

322

Глава 4 Типовые алгоритмы обработки информации

____________________________________________________________________

Процедура находится в модуле OutScr}

output_to_screen(name_file);

if n= -1 then

writeln(UTF8ToConsole('Такого менеджера нет'))

else

writeln(UTF8ToConsole('Менеджер найден, его номер '),

n+1);

write(UTF8ToConsole('Нажмите любую клавишу'));

readkey;

end.

4.2.2 Вставка и удаление элементов в упорядоченном массиве

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

ство данных. "Приличная" система должна давать пользователям возможность корректирования введенных данных, т.е. вставки новых данных, изменения уже введенных данных и удаления данных. Задача эта не столь тривиальна, как мо-

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

в упорядоченный по возрастанию массив a[1..n] в место с номером k, где k<n.

Если просто присвоить a[k]:= x;

то элемент с индексом k, который находился там ранее, будет потерян.

Следовательно, предварительно необходимо сдвинуть все элементы a[k], a[k+1], …, a[n] на одну позицию вправо. Это можно сделать с помощью цикла:

for i:= n downto k do

a[i+1]:= a[i];

323

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

____________________________________________________________________

inc(n);

То же самое при удалении элемента из массива. Если удаляется элемент a[k], то все оставшиеся элементы a[k+1], …, a[n] надо сдвинуть на одну пози-

цию влево, чтобы закрыть возникшую "дыру" в k-й позиции массива.

Код для сдвига элементов массива при удалении элемента a[k] будет та-

ким:

for i:= k + 1 to n do

a[i-1]:= a[i];

dec(n);

Напишем программу вставки нового элемента в массив. Предположим, что массив состоит из целых чисел 1, 2, 3, 4. Моделируем ситуацию, когда пользо-

ватель при вводе массива допустил ошибку, пропустил число 3. Поскольку оператор readln "не реагирует" на ввод пустой строки, была введена следую-

щая последовательность чисел: 1, 2, 4, 5. Необходимо дать пользователю воз-

можность откорректировать данные, введенные им в массив.

program project1; uses

CRT, FileUtil; var

i, n: integer;

a: array of integer; NewElement: integer; IndexOfNewElement: integer; SizeOfArray: integer; answ: char;

324

Глава 4 Типовые алгоритмы обработки информации

____________________________________________________________________

begin

writeln(UTF8ToConsole('Введите размер массива')); readln(SizeOfArray);

SetLength(a, SizeOfArray); writeln(UTF8ToConsole('Введите элементы массива')); for i:= 0 to SizeOfArray - 1 do

read(a[i]); writeln(UTF8ToConsole('Введен массив:')); for i:= 0 to SizeOfArray - 1 do write(a[i], ' '); writeln;

writeln(UTF8ToConsole('Откорректируйте данные')); writeln(UTF8ToConsole('Если все правильно, нажмите Enter,')); writeln(UTF8ToConsole('иначе - любую клавишу'));

answ:= readkey;

if answ = #13 then exit; writeln(UTF8ToConsole('Введите новый элемент')); readln(NewElement); writeln(UTF8ToConsole('Введите индекс в массиве,'));

writeln(UTF8ToConsole('куда нужно вставить новый элемент')); readln(IndexOfNewElement);

for i:= SizeOfArray - 1 downto IndexOfNewElement do a[i+1]:= a[i];

a[IndexOfNewElement]:= NewElement;

if IndexOfNewElement= SizeOfArray then inc(SizeOfArray);

writeln(UTF8ToConsole('Массив после вставки нового элемента'));

for i:= 0 to SizeOfArray - 1 do

write(a[i], ' '); writeln;

writeln(UTF8ToConsole('Нажмите любую клавишу'));

325