Строковые массивы. Алгоритмы поиска

Лекция А2

Строковые массивы. Алгоритмы поиска

1. Мы не оговаривали специально, что массивы могут состоять не только из чисел,  но и из символьных строк. На этой лекции мы разберем несколько типичных задач,  связанных с обработкой строковых массивов.

Описание такого  массива в программе строится по общим правилам: <Имя_массива> : array[<n1>..<n2>] of string[<длина>]

2. Всякая  задача  обработки  информации начинается с того, что эту информацию нужно ввести в память компьютера. Начнем и мы с этого.

Пусть, например,  наша программа  обслуживает  регистратуру поликлиники.  О  каждом пациенте нам требуется хранить следующую информацию: фамилию, год рождения и диагноз. Проще всего хранить эти данные в трех различных массивах Fam, God и Diag. Под одинаковыми номерами будут храниться данные  об  одном  пациенте,  то есть элементы Fam[i], God[i] и Diag[i] будут содержать соответственно фамилию, год рождения и диагноз пациента с номером i.

Размеры массивов удобно предусмотреть достаточно большими "с запасом",  а сколько будет введено пациентов каждый раз будет определяться в процессе работы: как только все данные исчерпаны, вместо ввода фамилии мы будем просто нажимать клавишу <Enter>.

Ввод данных удобно оформить в виде самостоятельной процедуры без параметров:

Program Hospital;

Const N = 100;

Var Fam  : array[1..N] of String[20];  {фамилии}

God  : array[1..N] of Integer;     {год рождения}

Diag : array[1..N] of String[20];  {Диагноз}

Procedure WwodMas;

Var

F   : String[20];

i,k : Integer;

begin

i := 0;         { номер вводимой записи }

writeln('Вводите данные: ' );

write('Фамилия   : ');

readln(F);      { ввод первой фамилии (для входа в цикл) }

while F <> '' do

begin

i := i+1;         { номер вводимой записи }

Fam[i] := F;      { занесение фамилии в массив }

Write('Год рождения: ');

readln(God[i]);   { ввод года рождения         }

Write('Диагноз     : ');

readln(Diag[i]);  { ввод диагноза              }

write('Фамилия     : ');

readln(F);        { ввод следующей фамилии     }

end;

end;

{ ======================================================== }

begin

{ тело программы}

end.

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

Решение этой задачи можно также оформить в  виде  отдельной процедуры:

Program Hospital;

Const N = 100;

Var Fam  : array[1..N] of String[20];

God  : array[1..N] of Integer;

Diag : array[1..N] of String[20];

Procedure Poisk;

Var F   : String[20];

i   : Integer;

begin

write('Введите фамилию: ' );

readln(F);

i:=1;

while (i<N) and (Fam[i]<>F) do i:=i+1;  {поиск номера фамилии}

if i<N then

writeLn('Пациент ',Fam[i],'. Его диагноз: ',Diag[i])

else WriteLn('Такого пациента в имеющемся списке нет.');

end;

{ ======================================================== }

begin

{ головная программа}

end.

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

Процедура двоичного поиска:

Program Example;

Const N = 100;

Var Fam  : array[1..N] of String[20];

God  : array[1..N] of Integer;

Diag : array[1..N] of String[20];

Procedure Poisk2;

Var F          : String[20];

i1,i2,k,pr : Integer;

begin

pr := 0;

writeln('Введите фамилию' );

readln(F);

i1 := 1;   { начало                 }

i2 := N;   { и конец участка поиска }

while i1 < i2 do { пока начало и конец участка поиска не слились }

begin

k := trunc((i1+i2)/2); { середина участка поиска }

if Fam[k] = F  { пациент найден }

then

begin

writeln(Diag[k]);  { вывод диагноза     }

pr := 1; { установка признака того, что пациент найден}

end

else if F < Fam[k]

{ если нужная фамилия находится в первой половине списка, }

then i2 := k-1  { то отбрасывается вторая половина,       }

else i1 := k+1; { в противном случае отбрасывается первая.}

end;

if pr = 0    { ни разу не выполнилось условие Fam[i] = F }

then writeln('Такой пациент отсутствует');

end;

{ ======================================================== }

begin

{ головная программа}

end.