11.7. Как организовать структуры, большие чем 64К?

We use cookies. Read the Privacy and Cookie Policy

Цифра 64K постоянно преследует разработчика больших программ. Сумма размеров всех глобальных переменных и типизированных констант не может превышать 64K. Размер типа тоже не может превышать 64K:

- 213 -

TYPE { матрица 200x200 }

Dim200x200 = Array [1..200, 1..200] of Real;

В таком описании размер типа равен 200x200x6 байт, что составит более 234К. Компилятор этого ни за что не пропустит, и переменная типа Dim200x200, понятно, не может быть объявлена. С другой стороны, эти 240K вполне могли бы разместиться в средних размеров куче. И это можно сделать!

Нужно лишь реорганизовать этот массив так, чтобы он распался на части, не превышающие по отдельности 64K каждая:

TYPE

Dim200 = Array [1..200] of Real;

Dim200Ptr = ^Dim200;

Dim200x200 = Array [1..200] of Dim200Ptr;

VAR

D : Dim200x200;

Здесь мы определяем тип Dim200 (тип строки матрицы) и тип ссылки на строку Dim200Ptr. После этого определяется тип матрицы 200x200 как статический массив из 200 ссылок на динамические массивы по 200 элементов. Последние вполне могут поместиться в куче. Тем более, что для каждого массива понадобится блок длиной 200x6 байт, а сами эти блоки могут размещаться в разных частях кучи. Размещение такой структуры немного усложнилось:

for i:=1 to 200 do New( D[i] );

как и освобождение:

for i:=1 to 200 do Dispose( D[i] );

Обращение к элементу массива D (разыменование) имеет вид D[i]^[j], где i — номер строки, a j — номер столбца.

Описанный прием достаточно эффективен для многомерных массивов и записей. Таким образом, можно заменять части структуры ссылками на них и забыть про предел в 64K. Но с одномерным массивом так поступить уже нельзя. Придется искать какие-либо обходные пути.

Существует несколько способов хранения данных и их структур, которые ограничены лишь свободным объемом памяти (ОЗУ). К ним относятся списочные структуры, деревья (графы). Отдельно можно выделить структуры типа «стек».

Список — это набор записей, каждая из которых имеет поле данных и указатель (ссылку) на следующую запись в списке. Та, в свою очередь, тоже содержит поле данных и ссылку на продолжение списка. Последний элемент списка (хвост) содержит значение

- 214 -

ки* nil, т.е. уже ни на что не ссылается. Списки легко создаются, добавляются с любого конца; их можно размыкать для вставки нового элемента, исключать элементы и т.д.

* Так напечатано. Видимо при печати пропущена часть текста.— Ю. Ш.

Мы не будем здесь рассматривать работу со списками. Большинство учебных и справочных изданий по языку Паскаль содержит основные принципы работы с ними.

Вместо этого мы предлагаем пример модуля, реализующего процедуры работы со стеком. Стек, или магазин, иногда называется списком LIFO (последним вошел — первым вышел). Это структура данных, при которой элемент, первым помещенный в стек, будет извлечен оттуда последним. И наоборот, доступнее всех последний положенный в стек элемент. Аналог стека — детская разборная пирамидка из дисков на штырьках. Надеть диск сверху — значит поместить в стек очередное значение. Снять диск (а снять можно только верхний диск) — значит вытолкнуть значение из стека. Доступ к содержимому стека всегда последователен, причем порядок выгрузки элементов из стека обратен порядку их загрузки в стек.