Книга: Песни о Паскале

Глава 53 Массив указателей

Глава 53

Массив указателей

Мы научились создавать переменные по мере надобности – динамически. Эти переменные поселяются в куче, но доступны через указатели, что расположены в секции данных или в стеке – статической памяти программы. Взглянете на рис. 118, где каждая клеточка соответствует байту.

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

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

type TRec = record { структура записи о владельце автомобиля }
      mNum : integer;       { номер авто – 2 байта }
      mFam : string[31];       { фамилия владельца – 32 байта }
      mAddr: string[63];       { адрес – 64 байта }
      mTel : integer;       { телефон – 2 байта }
      end;

Для экономии памяти отведем под фамилию и адрес укороченные строки: 31 байт – для фамилии и 63 – для адреса. Легко посчитать, что для размещения такой записи потребуется: 2+32+64+2 = 100 байтов (размер строки на единицу больше объявленной длины, вы помните об этом?).

Объявим массив из тысячи таких записей (на первое время хватит).

type TBase = array [1..1000] of TRec;

И посчитаем размер массива, он составит 100 x 1000 = 100000 байтов. Ого! Сто тысяч, – это больше, чем могут позволить вам иные компиляторы (Borland Pascal, например). Но если такой массив и поместится в памяти, немалая его часть по понятным причинам будет пустовать.

А если разместить эти увесистые записи в куче? Тогда в статической памяти останется лишь массив указателей на эти переменные, который займет в памяти 4 x 1000 = 4000 байтов, что вполне приемлемо. А куча? Её вместимость сопоставима с объёмом памяти компьютера и исчисляется мегабайтами. Так мы убьем двух зайцев: сэкономим статическую память программы и выйдем за ограничения, налагаемые компилятором. Рис. 119 поясняет нашу задумку.

Кстати, вы заметили какой-либо порядок записей в куче? Переменные разбросаны там и сям без всякой системы. Кучей, как вы помните, заведует операционная система, и требовать какого-то порядка от неё неуместно.

Итак, исполняя задуманное, учредим ещё один тип данных – указатель на запись.

type PRec = ^TRec;

Тогда база данных в статической памяти представится массивом.

type TBase = array [1..1000] of PRec;

Уловив идею будущей программы, приступим к деталям. План дальнейших действий таков. Сначала создадим вспомогательную программу с двумя процедурами: одна из них – для ввода базы данных из текста в кучу, а другая – для распечатки этой базы. Эта программа будет фундаментом для следующей, где добавим процедуру сортировки записей.

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

      6723 Иванов
      2199 Петров

Первый вариант программы «P_53_1» перед вами, рассмотрим его.

{ P_53_1 – Ввод и вывод полицейской базы данных }
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;
var N : integer;       { номер авто }
      S : string;       { фамилия }
      P : PRec;       { временный указатель на запись }
      i : integer;       { счетчик записей }
begin
Reset(F); i:=0;
while not Eof(F) and (i<CSize) do begin
Inc(i); { i+1 }
{ Читаем строку с номером и фамилией }
Read(F, N); Readln(F, S);
{ Удаляем пробелы в начале строки с фамилией }
while (S[1]=' ') do Delete(S,1,1);
New(P); { Создаем новую запись в куче }
{ Заполняем поля записи }
P^.mNumber := N; P^.mFam := S;
{ Указатель на запись помещаем в массив }
DataBase[i]:= P;
end;
Close(F); ReadData:= i;
end;
procedure ExpoDataBase;       { Распечатка базы данных }
var i : integer;
begin
i:=1;
{ Пока индекс в пределах массива и указатель не пуст }
while (i<=CSize) and Assigned(DataBase[i]) do begin
{ Печатаем номер, четыре пробела и фамилию }
Writeln(DataBase[i]^.mNumber :6, '':4, DataBase[i]^.mFam);
Inc(i); { i+1 }
end;
end;
var F : text; i : integer;
begin       {--- Главная программа ---}
for i:= 1 to CSize do DataBase[i]:= nil;
Assign(F,'P_50_1.in');
Count:= ReadData(F);
Writeln ('Всего записей: ',Count);
ExpoDataBase; Readln;
end.

Типы данных объявлены так, как уговорено выше. Предельный размер базы данных задан константой CSize=1000.

Функция ReadData читает строки текстового файла и помещает данные в кучу. После ввода номера автомобиля оператором Read(F,N) указатель чтения в файле остановится на первом пробеле за числом. Следующий оператор Readln(F,S) дочитает остаток строки. Так в переменной S окажется фамилия с пробелами в начале строки, – они потом удаляются.

Последующие операторы внутри функции 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. Это предотвращает обращение к несуществующим динамическим переменным.

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

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

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

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

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

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

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

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

Оглавление книги