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

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

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 – это номера запрашиваемых дорожек. Пустая строка говорит об отсутствии запросов в текущий момент времени. Для первой строки файла сделаем исключение, поместив там лишь одно число – период (таймаут) просмотра этой очереди контроллером в квантах.