Цифра 64K постоянно преследует разработчика больших программ. Сумма размеров всех глобальных переменных и типизированных констант не может превышать 64K. Размер типа тоже не может превышать 64K: {212}
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. Но с одномерным массивом так поступить уже нельзя. Придется искать какие-либо обходные пути.
Существует несколько способов хранения данных и их структур, которые ограничены лишь свободным объемом памяти (ОЗУ). К ним относятся списочные структуры, деревья (графы). Отдельно можно выделить структуры типа «стек».
Список — это набор записей, каждая из которых имеет поле данных и указатель (ссылку) на следующую запись в списке. Та, в свою очередь, тоже содержит поле данных и ссылку на продолжение списка. Последний элемент списка (хвост) содержит значение {213}ки* nil, т.е. уже ни на что не ссылается. Списки легко создаются, добавляются с любого конца; их можно размыкать для вставки нового элемента, исключать элементы и т.д.
Мы не будем здесь рассматривать работу со списками. Большинство учебных и справочных изданий по языку Паскаль содержит основные принципы работы с ними.
Вместо этого мы предлагаем пример модуля, реализующего процедуры работы со стеком. Стек, или магазин, иногда называется списком LIFO ("последним вошел — первым вышел"). Это структура данных, при которой элемент, первым помещенный в стек, будет извлечен оттуда последним. И наоборот, доступнее всех последний положенный в стек элемент. Аналог стека — детская разборная пирамидка из дисков на штырьках. Надеть диск сверху — значит поместить в стек очередное значение. Снять диск (а снять можно только верхний диск) — значит вытолкнуть значение из стека. Доступ к содержимому стека всегда последователен, причем порядок выгрузки элементов из стека обратен порядку их загрузки в стек.
Практический пример построения стека
Организация стека основана на связном списке, и поэтому стек занимает в памяти только необходимый на данный момент объем. Наглядно структура стека представлена на рис. 11.9.
*—–—–—––→
*
↓
Заголовок стека Список узлов
Head
Size
Info
Next
*–––––––—→
хранимые данные
(ЭЛЕМЕНТ)
Info
Next
хранимые данные
*–––——–—–→
Info
Next
хранимые данные
*––––––––→
*
│
...
↓
*
│
│
↓
nil (“Дно” стека)
Рис. 11.9 {214}
Сумма размеров всех хранимых в стеке данных ограничена только размером свободной памяти в куче, хотя элемент данных по-прежнему не должен превышать 64K. Стек оптимален для случаев, когда требуется просчитать и запомнить большое число структур данных, а потом обработать их в обратном порядке (в других случаях он мало полезен). К недостатку стека и списков, вообще, надо отнести расход памяти под узлы (здесь — 2x4 байта на каждый узел). Но если элемент хранимых данных имеет размер, например, 16K, с восемью байтами можно примириться.
Ниже приведен текст модуля StackManager (рис. 11.10), реализующего операции со стеком и пример программы, использующей его (рис. 11.11). Все тексты написаны и любезно предоставлены Г.П. Шушпановым.
UNIT StackManager; {БИБЛИОТЕКА СРЕДСТВ РАБОТЫ СО СТЕКОМ }
INTERFACE
CONST { коды ошибок, возникающих при работе со стеком }
StackOk =0; { успешное завершение }
StackOverflow =1; { переполнение стека }
StackUnderflow =2; { стек был пуст }
VAR
StackError : Byte; { результат операции со стеком }
TYPE
NodePtr = ^Node; { ссылка на узел }
Node = RECORD { Узел, состоящий из }
Info : Pointer; { ссылки на значение и }
Next : NodePtr; { ссылки на следующий }
END; { узел. }
Stack = RECORD { тип стека - запись }
Head : NodePtr; { ссылка на голову списка }
Size : Word; { размер элемента данных в }
END; { стеке }
PROCEDURE InitStack( VAR S : Stack; Size : Word );
{ формирует стек с элементами размера Size }
PROCEDURE ReInitStack(VAR S : Stack; Size : Word);
{ переопределяет стек для элементов другого размера }
PROCEDURE ClearStack( VAR S : Stack );
{ очищает стек }
PROCEDURE Push( VAR S : Stack; VAR E );
{ помещает значение переменной E в стек S }
Рис. 11.10 {215}
PROCEDURE Pop( VAR S : Stack; VAR E );
{ выталкивает значение из стека в переменную E }
PROCEDURE Top( VAR S : Stack; VAR Е );
{ копирует значение на вершине стека в переменную E }
FUNCTION Empty( VAR S : Stack ) : Boolean;
{ возвращает True, если стек пуст }
IMPLEMENTATION
VAR { переменная для хранения }
SaveHeapError : Pointer; { адреса старой функции }
{ обработки ошибок кучи }
{$F+}
FUNCTION HeapFunc( Size : Word ) : Integer;
BEGIN
HeapFunc := 1;
{вернуть nil, если нельзя разместить переменную в куче}
END;
{$F-}
PROCEDURE InitStack( VAR S : Stack; Size : Word );
BEGIN { сохранение стандартного }
SaveHeapError := HeapError; { обработчика ошибок кучи }
S.Head := nil; { установка вершины }
S.Size := Size; { размер значения }
StackError := StackOk; { все в порядке }
END;
PROCEDURE ReInitStack(VAR S : Stack; Size : Word );
BEGIN
if S.Head <> nil then ClearStack(S); { очистка стека } S.Size := Size; { установка нового размера значения } StackError := StackOk; { все в порядке }
END;
PROCEDURE СlearStack(VAR S : Stack);
VAR Deleted : NodePtr; { удаляемый элемент }
BEGIN
StackError := StackOk;
while S.Head <> nil do begin { Цикл по всем элементам:}
Deleted := S.Head; { удаляемый узел }
S.Head := Deleted^.Next; { продвижение вершины } FreeMem(Deleted^.Info,S.Size); { удаление значения }
Dispose(Deleted); { удаление узла }
end { while }
END;
PROGRAM UsesStack;{ПРОГРАММА, ХРАНЯЩАЯ ЗНАЧЕНИЯ В СТЕКЕ}
USES StackManager; VAR
St : Stack; { переменная структуры типа Stack (стек) }
I : Integer;
R : Real;
В : Byte;
BEGIN
InitStack( St, SizeOf( Integer ) ); { стек целых } { Поместить в стек 100 целых значений: }
for I:=1 to 100 do Push( St, I );
WriteLn( ' ':20, 'Первые 100 чисел' );
WriteLn( ' ': 20, '(целые значения)' );
WriteLn;
while not Empty(St) do begin { Пока стек не пуст: }
for В := 1 to 10 do begin {порциями по 10 элементов}
Pop( St, I ); { вытолкнуть очередное зна- }
Write( I:5 ) { чение и напечатать его }
end; { for В }
WriteLn { закрытие строки 10 чисел }
end; { while }
ReadLn; { пауза до нажатия ввода }
ReInitStack(St,SizeOf(Real)); {изменяется тип данных }
{ Поместить в стек 100 вещественных значений: }
for I := 1 to 100 do begin
R := I; { перевод в тип Real }
Push( St, R ); {и поместить его в стек }
end; { for I }
WriteLn( ' ':20, 'Первые 100 чисел' );
WriteLn( ' ': 17, '(вещественные значения)' );
WriteLn;
while not Empty(St) do begin { Пока стек не пуст: }
for B:=1 to 10 do begin { порциями по 10 элементов: }
Pop( St,R ); { вытолкнуть следующее зна- }
Write( R : 5 : 1 ) { чение и напечатать его }
end; { for В }
WriteLn { закрытие строки 10 чисел }
end; { while }
ReadLn { пауза до нажатия клавиши ввода }
END.
Рис. 11.11
Обращаем внимание на рекурсивность в определении списка (вернее, его узла типа Node на рис. 11.10). В самом деле, тип ссылки на узел (NodePtr) определен, до того как задан сам тип узла Node. {218}
Но в то же время поле Next узла имеет тот же тип NodePtr. Этот парадокс типов Паскаля разрешается самим компилятором. Можно определять ссылки на данные, содержащие элементы того же типа ссылки. Рекомендуется именно такой способ их задания, как в примере. Однако можно было бы перенести описание типа NodePtr за описание типа Node — ничего страшного не произошло бы. {219}
