Адресный тип-указатель, ссылочные переменные, простейшие действия с указателями.

⇐ ПредыдущаяСтр 2 из 3Следующая ⇒

Динамическими структурами данных считаются такие, размер которых заранее неизвестен и определяется и изменяется в процессе работы программы. Необходимость в динамических структурах данных возникает в следующих случаях:

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

адрес 1

Выделение памяти (ячеек памяти)

Процедура New(a);

Процедура New(b);

a a^ b b^

адрес 2

адрес 1

Занесение информации в ячейки памяти

a^: =1;

b^: =2;

a a^ b b^

адрес 2

1 2

адрес 1

Копирование информации из ячейки в ячейку

a^: =b^;

a a^ a^=b^ b b^ a< > b

адрес 2

Копирование адреса ячейки

a: =b;

a a^=b^ a^ b b^ a=b

адрес 2

Освобождение ячейки памяти

Процедура Dispose(a);

a: =b;

А a^ b b^

nil

адрес 2

Освобождение указателя

b: =nil;

a a^ b b^

Пример простых действий с указателями (программа инициализации массива):

Вариант 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^

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 возвращает длину в байтах самого длинного свободного блока}

if sizeof(Dim)> Psize then

begin

writeln(‘Массив р^ не может быть размещен целиком’);

GetMem(p, Psize); {отводим сколько есть Psize байт}

Writeln(‘Размещено’, Psize div sl, ’элементов’);

End

Else begin

New(p); {массив размещен, места достаточно}

Psize: =sizeof(Dim); {объем массива p^}

End;

FreeMem(p, Psize); {освобождение массива}

End.

⇐ Предыдущая 123 Следующая ⇒