2.9.2. Оператор with

Этот оператор позволяет сократить обращение к полям записи. Его схема:

WITH имя записи DO оператор;

Всюду внутри оператора WITH можно опускать имя записи в составном имени поля.

Пример. Применение оператора WITH для типа записи Book.

var X: Book; begin

with X do begin

readln (Title, Author, Year);

write (Title, Author, Year);

end;

end.

Пример. Применение оператора WITH в программе вычисления среднего балла.

(*вычисление среднего балла по матанализу в группе ЗИ *) for i:=l to number_student do

begin

with first_course.zi[i] do

for j:=l to number_subject do

begin

if subject[j ] title='матанализ' then

summa:=summa+ subject[j].mark;

end;

end;

Допускается вложенность операторов WITH один в другой. Поэтому данную часть программы можно модифицировать так (*вычисление среднего балла по матанализу в группе ЗИ *) with first_course do

for i:=l to number_student do begin

withzi[i]do

for j:=1 to number_subject do

begin

if subject[j|]].title='матанализ' then

summa:=summa+ subject[j].mark;

end;

end;

2.9.3. Последовательный поиск в массиве записей

Массив записей подходит для хранения большого объема разнородной информации, например для создания телефонного справочника, адресной книгой, библиотечного каталога.

Пример. Описание библиотечного каталога

type

Book = record

Title: string [100];

Author: string [40];

Year: integer;

end;

Catalog = array [1..1000] of Book;

Возникает задача поиска элемента массива, одно из полей которого имеет заданное значение, например, сведений о книге по фамилии автора. Найти - значит определить номер записи в массиве или сообщить об отсутствии такой записи.

Самый простой алгоритм поиска — последовательный. Он состоит в том, что у всех записей последовательно, начиная с первой, проверяется значение признака, по которому ведется поиск. Пусть требуется найти книгу определенного автора. Это можно сделать так

program serial_search;

type

Book = record

Title: string [40];

Author: string [12];

Year: integer;

end;

Catalog = array [1..1000] of Book; var

cat: Catalog;

s:string;

i:integer;

Year: integer;

end;

Catalog = array [1..1000] of Book;

Var

Cat:Catalog;

s: string; i,j,k,m:integer;

begin

Write ('Введите имя автора ');read(s);

i:=l;j:=1000;

k:=0;

while (k=0) and ((j-i)> 1) do

begin

m:=(i+j) div 2;

if(Cat[m].Author = s) then k:=m

else

begin

if Cat[m] .Author < s then i:=m else j :=m;

end;

end;

if (k =0) and (Cat[i].Author = s) then k:=i;

if (k =0) and (CatOLAuthor = s) thenk:=j;

if (k<>0) then writeln('Нужная книга под номером ', k)

else writeln('Hyжнaя книга отсутствует ');

end.

2.9.4. Двоичный поиск в массиве записей

Общим свойством алгоритмов последовательного поиска является то, что время поиска прямо пропорционально количеству записей. Если массив записей отсортирован по значению искомого признака, то можно искать быстрее.

Рассмотрим следующий алгоритм поиска книги нужного автора в каталоге, упорядоченном в алфавитном порядке по фамилиям авторов.

• Открыть каталог посередине.

• Сравнить искомую фамилию с той, что в середине каталога.

• Если фамилии совпадают, поиск завершен.

• Если фамилия в середине по алфавиту позже искомой, продолжить поиск в первой половине каталога.

• Если фамилия в середине по алфавиту раньше искомой, продолжить поиск во второй половине каталога.

Слова «продолжить поиск» означают применение алгоритма в целом к половине каталога, т.е. открыть его посередине и т.д. В конце концов, либо фамилия будет найдена, либо делить пополам будет нечего, значит, фамилии в каталоге нет.

program binary_search;

type

Book = record

Title: string [100]; Author: string [40];

Year: integer;

end;

Catalog = array [1..1000] of Book;

var

cat: Catalog; s: string; i,j,k,m:integer;

begin

Write ('Введите имя автора ');read(s); i:=l;j:=1000;

k:=0;

while (k=0) and ((j-i)> 1) do

begin

m:=(i+j) div 2;

if (Cat[m].Author = s) then k:=m

else

begin

if Cat[m].Author < s then i:=m else j:=m;

end ,

end;

if (k =0) and (Cat[i].Author = s) then k:=i;

if (k =0) and (Cat[j].Author = s) thenk:=j;

if (k<>0) then writeln('Нужная книга под номером ', k)

else writeln('Нужная книга отсутствует ');

end.

Сравним скорость последовательного и двоичного поиска. Первый сокращает область поиска на одну запись за каждый шаг алгоритма. Второй за один шаг уменьшает область поиска в два раза. Следовательно, при удвоении числа записей время последовательного поиска возрастет в два раза, а время двоичного поиска увеличится лишь на один шаг алгоритма.