Динамическими структурами данных считаются такие, размер которых заблаговременно малоизвестен и определяется и изменяется в ходе работы программы. Необходимость в динамических структурах данных появляется в следующих случаях:
1. В то время, когда нужен массив либо другая структура, размер которой изменяется в широких пределах.
2. В то время, когда в определённых частях программы требуется взять дополнительную память под переменные большого размера.
3. В то время, когда размер переменной (массива либо записи) превышает 64 килобайта.
Во всех этих случаях появляющиеся неприятности возможно решить, используя динамические переменные и ссылочные типы данных. Для организации динамических данных выделяется особая область памяти, именуемая кучей (heap), постоянный участок определённого размера. Наряду с этим в особой переменной сохраняется адрес начала этого участка. Такие переменные именуют ссылочными переменными. Синоним этого термина — указатель (pointer).
В Турбо Паскале 7.0 для определения ссылочной переменной необходимо обрисовать её как переменную, имеющую ссылочный тип. В качестве ссылочного возможно применять встроенный тип Pointer либо каждый тип, определяемый пользователем следующим образом:
TYPE Имя_ссылочного_типа=^Имя_базового_типа;
где Имя_базового_типа – любой идентификатор типа.
В следствии для того чтобы определения создаваемые после этого ссылочные переменные будут указы-вать на объекты базисного типа, определяя тем самым динамические переменные базисного
типа. К примеру: {базисные типы} Type DimType = array [1..100] of Byte;
MyRecType = record
a: real; b: integer;
end;
{ссылочные типы} IntPtr=^Integer; {ссылка на целое значение}
DimPtr=^DimType; {ссылка на массив данных}
RecPtr=^MyRecType; {ссылка на запись}
Компилятор отводит под указатель четыре байта статической памяти. Переменная типа указатель занимает в памяти двойное слово, в котором младшее слово содержит адрес смещения, а старшее – адрес сегмента размещения, связанного с указателем участка динамической памяти.
Указатель (указательная переменная P) может быть в трёх состояниях:
1. Неизвестное состояние в начале работы программы (указатель ещё не инициализирован) рис 1.1 а.
2. Содержит адрес какой-либо переменной (адрес размещения) рис 1.1 б.
3. Содержит значения предопределённой константы nil, таковой указатель именуют безлюдным, т.е. он не показывает ни на какую переменную и содержит 0 в каждом из четырёх байтов рис 1.1 в.
| nil |
Р P P^ Р
?
| адрес |
| ? |
Рис 1.1 а Рис 1.1 б Рис 1.1 в
Указатели возможно сравнивать между собой, присваивать указателю адрес другого указателя, передавать указатель как параметр.
Применение идентификатора указателя в программе свидетельствует обращение к
адресу ячейки памяти, на которую он показывает. Для обращения к содержимому
ячейки, на которую показывает указатель, требуется по окончании его идентификатора
поставить знак ^. Эта операция именуется операцией разименовывания.
Пример: var P:^Byte; Begin P^:=1; end;
Несложные действия с указателями представлены в таблице 1.1 [2].
Таблица 1.1
| Воздействие | Итог |
| 1. Объявление type Plnt=^integer; var a,b: Plnt; | а ? b ? |
2.  |
| адрес 2 |
| адрес 1 |
Выделение памяти (ячеек памяти)
Процедура New(a);
Процедура New(b);
| адрес 2 |
| адрес 1 |
Занесение информации в ячейки памяти
a^:=1;
b^:=2;
| адрес 2 |
| 1 2 |
| адрес 1 |
Копирование информации из ячейки в ячейку
a^:=b^;
| адрес 2 |
| адрес 2 |
Копирование адреса ячейки
a:=b;
| адрес 2 |
| адрес 2 |
Освобождение ячейки памяти
Процедура Dispose(a);
a:=b;
| nil |
| адрес 2 |
Освобождение указателя
b:=nil;
Пример несложных действий с указателями (программа инициализации массива):
Вариант 1. Простые переменные. Вариант 2.Динамические переменные
type Vect=array[1..3] of Byte; type Vect=array[1..3] of Byte;
var X: Vect; var PX:^Vect;
i: Byte; i: Byte;
begin begin
New(PX);
for i:=1 to 3 do for i:=1 to 3 do
X[i]:=i; PX^[i]:=i; Dispose(PX);
end. end.
1.2 Динамическое распределение памяти в области кучи, процедуры управления кучей, несвязанные динамические эти.
На рис.1.2 представлено распределение памяти области куча при работе программ, написанных на Турбо Паскале 7.0. Куча первоначально в любой момент свободна и заполняется от нижних адресов. Настоящий размер кучи зависит от большого и минимального её значений, каковые возможно установить посредством директивы компилятора $М: {$Mстек, минимум кучи, максимум кучи}, где стек специфицирует размер сегмента в байтах. По умолчанию размер стека 16384 байт. Большой размер стека 65538 байт.
Верхняя граница памяти MS–DOS
| FreePtr | Перечень свободных блоков в куче с их размером и адресом | Старшие адреса |
| HeapPtr | Свободная память кучи | |
| HeapOrg | Применяемая часть кучи (растёт вверх) | OvrHeapEnd |
| Оверлейный буфер | ||
| Стек, сегмент данных, рабочий код ЕХЕ-файла | Младшие адреса |
Рис.1.2
Минимум кучи–специфицирует минимально требуемый размер кучи в байтах (по умолчанию 0 байт). Максимум кучи–специфицирует большое значение памяти
(по умолчанию 655360 байт) наряду с этим минимум кучи
Все значения задаются в десятичной либо шестнадцатеричной формах. Эквивалентные директивы: {$M16384,0,655360} {$M$4000,$0,$A000}
Управление размещением динамической памяти осуществляет монитор кучи, являющийся одной из управляющих программ модуля System. В стандартном модуле System совокупности Турбо Паскаль 7.0 обрисованы переменные типа Pointer, применяемые монитором кучи для реализации программ распределения динамической памяти:
| HeapOrg – | указатель начала кучи (рис.1.2), её значение, в большинстве случаев, неизменно и не изменяется в ходе исполнения программы; |
| HeapPtr – | показывает на нижнюю границу свободного пространства в кучe. При размещении новой динамической переменной указатель перемещается на размер данной переменной. Наряду с этим он приводится к виду СЕГМЕНТ: СМЕЩЕНИЕ так, что смещение находится в диапазоне от 0 до $F(15); |
| FreePtr – | указатель перечня свободных блоков; |
| HeapError – | указатель установки обработки неточностей кучи; |
| FreeMin – | минимальный размер перечня свободных блоков (тип Word); |
| OvrHeapOrg – | указатель финиша оверлейного буфера. |
Куча является структурой , похожую на стек. Нижняя граница кучи запоминается в указателе HeapOrg, а верхняя граница кучи, соответствующая нижней границе свободной памяти, хранится в текущем указателе кучи HeapPtr.
При выделении динамической памяти вероятны следующие варианты:
– в начале исполнения программы куча безлюдна, тогда монитор куча
– заполняет её последовательно в порядке запросов на память процедурами New и GetMem. При каждом выделении динамической памяти монитор кучи передвигает указатель кучи вверх (к младшим адресам) на размер запрошенной памяти;
– куча фрагментирована и в случае, если в ходе работы появились свободные участки памяти, тогда монитор куча, следуя принципу оптимизации применения памяти, просматривает перечень свободных областей с целью отыскать таковой вольный участок памяти, дабы отличие между размерами свободного и запрашиваемого участка памяти была минимальной. В любом случае указатель кучи постоянно стоит на первом свободном байте за последним размещением в куче.
В случае, если куча заполнена, то очередной запрос на выделение динамической памяти ведет к сообщению об неточности: 203 Heap overflow error . Несложный выход из данной ситуации может заключаться в повышении памяти посредством директивы компилятора $М.
В таблице 1.2 [3] приведены функции и процедуры управления кучей.
Таблица 1.2
| функции и Процедуры | Назначение |
| New (var P: Pointer) | Отводит место для хранения динамической переменной P^ и присваивает её адрес ссылке P. |
| Dispose (var P: Pointer) | Уничтожает сообщение, созданную ранее New, между ссылкой P и значением, на которое она ссылалась. |
| GetMem(var P: Pointer; Size: Word) | Отводит место размером Size байт в куче, присваивая адрес его начала указателю (ссылке) Р. |
| FreeMem (var P: Pointer; Size: Word) | Освобождает Size байт в куче, начиная с адреса, записанного в указателе (ссылке) Р. |
| Mark (var P: Pointer) | Запоминает в указателе Р текущее состояние кучи. |
| Release (var P: Pointer) | Возвращает кучу в состояние, запомненное ранее в указателе Р вызовом процедуры Mark(P). |
| MaxAvail: LongInt | Возвращает длину (в байтах) самого долгого свободного участка памяти в куче. |
| MemAvail: LongInt | Возвращает сумму длин всех собственных свободных участков памяти (в байтах). |
Пример анализа динамики выделения памяти в куче:
var P1, P2, P3, P4: real;
P: Pointer;
begin
New (P1); New (P2); Mark (P); New (P3); New (P4);
end.
По окончании исполнения процедур данной программы состояние кучи возможно отобразить как продемонстрировано на рис.1.3.
| Верхняя граница |
Рис.1.3
Процедура Mark(Р) фиксирует состояние кучи перед размещением динамической переменной Р3^, копируя значение текущего указателя кучи в указатель Р. В случае, если дополнить в конце данную программу процедурой Release(Р), то куча будет смотреться как продемонстрировано на рис.1.4а.
 |
|||
 |
|||
| HeapPtr |
| P2^ |
P2
| P1^ |
P1
Рис.1.4 а Рис.1.4 б
Наряду с этим освобождается память, выделенная по окончании обращения к процедуре Mark. В случае, если же выполнить процедуру Release(HeapOrg), то куча будет очищена абсолютно, поскольку указатель HeapOrg содержит адрес начала кучи. Одновременно с этим, в случае, если вместо процедуры Release применять в программе процедуру Dispose(Р3), то в середине кучи образуется свободное пространство (“дырка”), как продемонстрировано на рис.1.4 б.
Адреса и размеры свободных блоков, созданных при операциях Dispose и FrееМем, сохраняются в перечне свободных блоков, что возрастает вниз, начиная со старших адресов памяти, в сегменте динамически распределяемой области. Любой раз перед вы-делением памяти для динамической переменной, перед тем, как динамически распределя-емая область будет расширена, проверяется перечень свободных блоков. В случае, если имеется блок соответствующего размера (другими словами размер которого больше либо равен требуемому раз-меру), то он употребляется.
Процедура Rеlеаsе постоянно очищает перечень свободных блоков. Так, программа динамического распределения памяти забывает о незанятых блоках, каковые смогут существовать ниже указателя динамически распределяемой области. Если вы чере-дуете обращения к процедурам Маrk и Rеlеаsе с обращениями к процедурам Dispose и FrееМем, то необходимо обеспечить отсутствие таких свободных блоков.
Переменная FreeList модуля System показывает на первый вольный блок динами-чески распределяемой области памяти. Этот блок содержит указатель на следующий вольный блок и т.д. Последний вольный блок содержит указатель на вершину дина-мически распределяемой области (другими словами адрес, заданный HeapPtr). В случае, если свободных блоков в перечне свободных нет, то FreeList будет равняется HeapPtr.
Формат первых восьми байт свободного блока задается типом TFreeRec:
type PFreeRec = ^TFreeRec;
TFreeRec = record
Next: PFreeRec;
Size: Pointer;
end;
Поле Next показывает на следующий вольный блок, либо на туже ячейку, что и HeapPtr, в случае, если блок есть последним свободным блоком. В поле Size записан размер свободного блока. Значение в поле Size представляет собой не простое 32-битовое зна-чение, а нормализованное значение-указатель с числом свободных параграфов (16-бай-товых блоков) в старшем слове и счетчиком свободных байт (от 0 до 15) в младшем слове. Следующая функция BlockSize преобразует значение поля Size в простое значение типа Longint:
function BlockSize(Size: Pointer): Longint;
type
PtrRec = record Lo, Hi: Word end;
begin
BlockSize := Longint(PtrRec(Size)).Hi)*16+PtrRec(Size).Lo
end;
В начале свободного блока постоянно имеется место для TFreePtr, в обеспечение этого система управления динамически распределяемой областью памяти округляет размер каждого блока, выделенного подпрограммами New и GetMem до 8-ми байтовой границы. Так, 8 байт выделяется для блоков размером 1-8 байт, 16 байт — для блоков раз-мером 9-16 и т.д. Сперва это думается непроизводительной тратой памяти. Это в действительности так, если бы любой блок был размером 1 байт, но в большинстве случаев блоки имеют больший размер, исходя из этого относительный размер неиспользуемого пространства меньше. Восьми-байтовый коэффициент раздробленности снабжает то, что при солидном числе освобождения и случайного выделения блоков довольно маленького размера не ведет к сильной фрагментации динамически распределяемой области.
1.3 Практические примеры работы с несвязанными динамическими данными.
Пример 1. Определение адреса переменных и создание адреса.
Требуется выяснить адрес переменных i и x и создать ссылку (организовать адрес) на место в памяти, где находится переменная i.
Program Segment;
Uses crt;
Var x:string; i:integer; k:^integer; p,p1:pointer; k2:^string;
addr_p,addr_p1,addr_k2:longint;
begin
x:=’Вeatles’; i:=66; clrscr;
p:=addr(i); p1:=@(x);
{функция addr(i) либо операция взятия адреса @(i) помогает для ‘привязывания’ динамических переменных к статическим. В противном случае говоря, выдает значение типа Pointer, т.е. ссылку на начало объекта (переменной i) в памяти}
k:=ptr(seg(p^),ofs(p^));
{seg(p^)-выдает адрес сегмента, в котором хранится объект (переменная i); ofs(p^)-смещение в сегменте, в котором хранится объект (переменная i); ptr-функция, противоположная addr, организует ссылку на место в памяти, определяемое смещением и сегментом (формирует адрес).}
р1:=addr(p1^); {addr(p1^), @p1^,seg(p1^),ofs(p1^) – возврат содержимого
ссылки.}
k2:=p1; {работа с адресами, адреса равны и показывают на одинаковый объект
(переменную i)}
addr_p:=longInt(p); {приведение адреса (ссылки) к данному целому типу, к
десятичной совокупности счисления}
addr_p1:=longInt(p1);
addr_k2:=longInt(k2);
writeln(‘p=’,addr_p,’p1=’,addr_p1,’k2=’,addr_k2); {распечатаем адреса переменной i (ссылка р) и переменной х(ссылка р1 и к2) в десятичной совокупности счисления}
writeln(‘Адрес переменной х: сегмент’,seg(p),’смещение’,ofs(p));
{распечатаем адрес переменной х еще раз, применяя функции ofs(p):word и seg(p):word}
writeln(k2^,’ ‘,k^); {распечатаем значения самих переменных}
readkey; end.
{итог, выданный на печать}
р=434110802 р1=434110546 к2=434110546
Адрес переменной х: сегмент 6624 смещениe 348
beatles 66
В интегрированной среде программирования Турбо Паскаль 7.0 в окне
параметров Watch возможно заметить адреса переменных i и х в шестнадцатиричной
совокупности счисления (рис.1.5).
Watch
p:Ptr($19E0,$152)
p1:Ptr($19E0,$52)
k2:Ptr($19E0,$52)
рис.1.5
Пример 2: Организация динамических структур, открывающих доступ к большей оперативной памяти.
Требуется организовать динамическую структуру данных типа двумерный массив, трудящуюся с базисным типом real и размером более 64килобайт оперативной памяти.
Схематично структурная организация для того чтобы массива в оперативной памяти представлена на рис.1.6.
1-ая строчок из 298 ячеек по 6 байт
2-ая строчок из 298 ячеек по 6 байт
3-ья …
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
оверлейный буфер
сегмент данных.
Статический массив из 298 ссылок d:ptr298
 |
|||
Рис.1.6
Program BIG_KUCHA;
Uses crt;
Type Str298=array[1..298] of real;{тип строчка матрицы}
Str298_ptr=^str298;{ссылка на строчок матрицы}
Ptr298=array[1..298] of str298_ptr; {статический массив из 298 ссылок на
динамические массивы по 298 элементов типа real}
var d:ptr298;
i,j,k:integer;
begin
for i:=1 to 298 do new(d[i]); {выделение памяти в куче под вещественные строчки}
for i:=1 to 298 do
for j:=1 to 298 do d[i]^[j]:=random*1000; {заполнение массива строчков}
writeln(d[1]^[1]:6:4,d[298]^[298]:6:4);
for i:=1 to 298 do dispose(d[i]); {освобождение памяти в кучe, занятой
строчками}
readKey; end.
Так оперативная память, выделенная в следствии таковой организации, образовывает: 298*298*6 байт=532824 байта=520 килобайт.
Пример 3. Анализ состояния кучи.
Требуется выяснить ресурсы памяти перед размещением динамических переменных [2].
Program Test;
Type Dim=array[1..5000] of LongInt;
Var p:^Dim; {ссылка на базисный тип-массив}
Psize:LongInt;
Const sl=sizeof(LongInt);{размер одного элемента массива}
Begin
Writeln(‘В куче вольно’,MemAvail,’байт’);
{функция MemAvail выдает полный количество свободного пространства}
psize:=sl*(MaxAvail div sl);
{функция MaxAvail возвращает длину в байтах самого долгого свободного блока}
begin
writeln(‘Массив р^ не может быть размещен полностью’);
GetMem(p,Psize);{отводим какое количество имеется Psize байт}
Writeln(‘Размещено’,Psize div sl,’элементов’);
End
Else begin
New(p);{массив размещен, места достаточно}
Psize:=sizeof(Dim);{количество массива p^}
End;
FreeMem(p,Psize);{освобождение массива}
End.