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

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

Глава 54

Односвязные списки

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

Чудесное сочетание

Ключ к безупречному решению – в сочетании записи с указателем. Запись может содержать в своей обёртке разнородные элементы: числа, символы, строки, массивы и так далее. А если внедрить в неё указатель на другую запись этого же типа? Тогда мы сможем погрузить в кучу цепочку элементов так, как показано на рис. 120.

Рис.120 – Связывание записей указателями

Здесь в кучу погружены три элемента данных (три записи), а в статической памяти программы торчит лишь «поплавок» – указатель на первый элемент этой цепочки. Все последующие записи сцеплены друг с другом указателями, встроенными в них же. Последняя запись содержит NIL, – как говорится, сколько веревочке не виться… Наряду с указателями, записи содержат, разумеется, и данные, необходимые для решаемой задачи. Такую структуру называют односвязным списком. Односвязным, – потому что элементы сцеплены лишь одной связью (при желании таких связей можно сделать больше). Мы будем называть эту динамическую структуру просто списком, по-английски – List.

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

Проблема курицы и яйца

Построим элемент односвязного списка для полицейской базы данных. Вот объявления нужных нам типов данных: записи и указателя на неё.