Олег Деревенец - Песни о Паскале

Переходим ко второму этапу, где мы добавим процедуру сортировки массива указателей. Напомню, что в сортированном массиве работает быстрый двоичный поиск, – этим и привлекает нас сортировка. Вот программа «P_53_2», где процедуры чтения и распечатки базы данных пропущены, – их следует взять из программы «P_53_1».

{ P_53_2 – Сортировка полицейской базы данных }

const CSize = 1000; { Максимальное количество записей в базе данных }

type TRec = record { Тип записи для базы данных }

mNumber : integer; { Номер авто }

mFam : string[31]; { Фамилия владельца }

end;

PRec = ^TRec; { Тип указатель на запись }

TBase = array[1..CSize] of PRec; { Тип массив указателей }

var DataBase : TBase; { База данных – это массив указателей }

Count: integer; { Количество записей в базе }

{ Чтение данных из файла БД }

function ReadData(var F : text): integer;

{ Взять из P_53_1 }

end;

{ Распечатка БД }

procedure ExpoDataBase;

{ Взять из P_53_1 }

end;

{ FarmSort – "Фермерская" сортировка }

procedure FarmSort(var arg: TBase; Right : integer );

var L, R : Integer; T : PRec;

begin

for L := 1 to Right-1 do

{ Сдвигаем правый индекс влево }

for R := Right downto L+1 do begin

{ Если левый элемент оказался больше правого,

то меняем элементы местами }

if arg[L]^.mNumber > arg[R]^.mNumber then begin

{ Перестановка элементов массива }

T:= arg[L]; arg[L]:= arg[R]; arg[R]:= T;

end;

end;

end;

var F : text;

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

FillChar(DataBase, SizeOf(DataBase), 0);

Assign(F,'P_53_1.in');

Count:= ReadData(F); { Ввод данных и подсчет числа записей }

Writeln('До сортировки: ');

ExpoDataBase; Readln;

FarmSort(DataBase, Count); { Сортировка }

Writeln('После сортировки: ');

ExpoDataBase; Readln;

end.

Теперь направим внимание на процедуру сортировки. Для простоты я взял "фермерскую" сортировку – не самый быстрый алгоритм (смотрите главу 43). Отличия нынешнего варианта сортировки от первого невелики, их всего два.

Во-первых, сортируются не записи, а указатели на них. В 49-й главе нам довелось сортировать массив записей (помните футбольный чемпионат?), теперь сравним то решение с этим. Сортировка массива перемещает его элементы. Чем крупнее элемент, тем больше байтов передвигается. Очевидно, что четыре байта указателя двигаются быстрее, чем сотня байтов записи.

Здесь приходит на ум почтальон с пачкой открыток. Если открытки в пачке сложены случайно, почтальон станет бестолково бегать от дома к дому. Для ускорения дела надо что-то отсортировать: то ли дома в порядке сложенных открыток, то ли открытки по номерам домов. Как поступит почтальон? – догадайтесь сами. В нашем случае дома – это записи, а открытки – указатели на них.

Вторая особенность сортировки указателей в том, что обрабатывается не весь массив, а лишь непустые указатели. Обращаться к данным через пустые указатели недопустимо, – это верный способ «уронить» программу. Поэтому в процедуру передается граница сортируемой части через параметр Right – это правый индекс массива, равный фактическому количеству элементов в базе данных.

• Используя массив указателей на динамические переменные, в памяти кучи можно поместить большой объём данных.

• При инициализации массив указателей заполняют значением NIL. Это предотвращает обращение к несуществующим динамическим переменным.

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

А) Дополните запись TRec полями с адресом владельца и его телефоном. Организуйте ввод и вывод этих данных (наряду с другими). Подготовьте надлежащий текстовый файл с исходными данными и проверьте работу этой версии программы.

Б) Напишите процедуру линейного поиска номера автомобиля в несортированном массиве указателей.

В) Напишите процедуру быстрого двоичного поиска в сортированном массиве указателей. Дополните вывод найденных данных, включая фамилию владельца и прочее.

Задачи на темы предыдущих глав

Г) «Глупый» винчестер (об «умном» вы узнаете в задаче 54-Д). Рассмотрим очень упрощенную модель винчестера, «шустрость» которого в значительной степени определяется частотой вращения диска и скоростью перемещения головки чтения-записи. Время одного оборота диска примем за единицу – квант. За это время головка полностью читает или записывает одну дорожку. Количество дорожек на диске – 256, а нумерация идет с нуля (0…255). Время, необходимое для перемещения головки на соседнюю дорожку, тоже примем равным одному кванту.

Винчестером управляет контроллер, работающий куда быстрее механических узлов – диска и головки, поэтому издержками времени на его работу пренебрежем. Через некоторый интервал времени (таймаут) контроллер просматривает входную очередь, содержащую запросы на чтение или запись дорожек. Эта очередь формируется всеми запущенными программами. У нас это будет текстовый файл, каждая строка которого содержит по несколько чисел в диапазоне от 0 до 255 – это номера запрашиваемых дорожек. Пустая строка говорит об отсутствии запросов в текущий момент времени. Для первой строки файла сделаем исключение, поместив там лишь одно число – период (таймаут) просмотра этой очереди контроллером в квантах.

Контроллер «рулит» так. Прочитав список запросов (очередную строку файла), он перемещает их в свою внутреннюю очередь и далее обрабатывает её в порядке прихода запросов: смещает головку в нужную позицию и выполняет чтение-запись. Одновременно он следит за таймаутом, и, по истечении оного, читает следующую порцию входной очереди (то есть, строку файла). Ваша программа должна подсчитать общее время обработки запросов, заданных во входном файле (время измеряется в квантах).

Создав массив указателей на динамические переменные, мы сбросили в кучу уйму данных. Результат неплох, но где пределы совершенству? Как ни крути, размер массива ограничен, сколько указателей нам запасти? Побольше? Но тогда значительная часть массива будет пустовать. Одним словом, постоянный размер массива вяжет нас. Идеальное решение в том, чтобы отвести под данные столько памяти, сколько им требуется, – не больше и не меньше. Мы стремимся к этому решению и сейчас в шаге от цели.