Песни о Паскале

Деревенец Олег Виленович

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

Базу данных – в кучу

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

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

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 поясняет нашу задумку.

Рис.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 окажется фамилия с пробелами в начале строки, – они потом удаляются.