Объявим массив из тысячи таких записей (на первое время хватит).
type TBase = array [1..1000] of TRec;
И посчитаем размер массива, он составит 100 x 1000 = 100000 байтов. Ого! Сто тысяч, – это больше, чем могут позволить вам иные компиляторы (Borland Pascal, например). Но если такой массив и поместится в памяти, немалая его часть по понятным причинам будет пустовать.
А если разместить эти увесистые записи в куче? Тогда в статической памяти останется лишь массив указателей на эти переменные, который займет в памяти 4 x 1000 = 4000 байтов, что вполне приемлемо. А куча? Её вместимость сопоставима с объёмом памяти компьютера и исчисляется мегабайтами. Так мы убьем двух зайцев: сэкономим статическую память программы и выйдем за ограничения, налагаемые компилятором. Рис. 119 поясняет нашу задумку.
Рис.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;
