Олег Деревенец - Песни о Паскале

Мы научились создавать переменные по мере надобности – динамически. Эти переменные поселяются в куче, но доступны через указатели, что расположены в секции данных или в стеке – статической памяти программы. Взглянете на рис. 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; { База данных – это массив указателей }