Песни о Паскале
Шрифт:
Последующие операторы внутри функции ReadData создают динамическую переменную (запись), адрес которой содержится в указателе P. Затем поля записи заполняем номером автомобиля и фамилией владельца, после чего указатель P копируем в очередной элемент массива указателей. Эти действия можно записать короче – без вспомогательного указателя P, вот так:
New(DataBase[i]); { создаем переменную-запись, указатель в массиве }
DataBase[i]^.mNumber := N; { копируем номер }
DataBase[i]^.mFam := S; { и фамилию }
Но
Теперь обратимся к процедуре ExpoDataBase – она распечатывает данные, размещенные в куче. Выражение Assigned(DataBase[i]) в условии цикла WHILE равнозначно выражению DataBase[i]<>NIL и проверяет, ссылается ли указатель на динамическую переменную. Такая проверка исключает ошибку обращения через пустой указатель.
В главной программе заслуживает внимание строка, заполняющая пустым значением NIL все указатели массива. Ведь пока динамические переменные не созданы, указатели на них следует «заглушить» константой NIL.
for i:= 1 to CSize do DataBase[i]:= nil;
То же самое делается проще и быстрее процедурой FillChar.
FillChar(DataBase, SizeOf(DataBase), 0);
Но указатели – не обычные числа, возможно ли заполнять их нулями? Здесь проявляется универсальность процедуры FillChar, которая способна работать с данными любого типа. А ноль как раз и соответствует внутреннему представлению константы NIL.
Прежде, чем двинуться дальше, подготовьте файл с исходными данными и хорошенько проверьте работу программы «P_53_1».
Сортировка массива указателей
Переходим ко второму этапу, где мы добавим процедуру сортировки массива указателей. Напомню, что в сортированном массиве работает быстрый двоичный поиск, – этим и привлекает нас сортировка. Вот программа «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. Это предотвращает обращение к несуществующим динамическим переменным.
• Сортировка массива указателей похожа на сортировку других типов данных, но выполняется, как правило, быстрее. При этом сортируют лишь непустые указатели.
А слабо?