Стандартные процедуры размещения и освобождения динамической памяти

Оглавление

Динамическая память. 1

Указатель. 1

Стандартные процедуры размещения и освобождения динамической памяти. 2

Стандартные функции обработки динамической памяти. 3

Примеры работы с памятью.. 4

Работа с динамическими массивами. 4

Контрольные вопросы: 6

Комбинированный урок №19

Тема:Динамические структуры данных и их организация с помощью указателей

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

Динамическая память

Можно отметить следующие достоинства динамической памяти: - экономичность и эффективность ее использования; - возможность динамического изменения числа элементов в связанных структурах, например, списках (в статической памяти…

Указатель

Формат описания типа «указатель» следующий: TYPE<идентификатор указателя>=^<тип>; Примеры объявления типов «указатель» и переменных типа «указатель».

END;

В формате объявления типа «указатель» должен быть указан идентификатор типа, поэтому стандартные идентификаторы (INTEGER, REAL и т.д.) можно указывать непосредственно в описаниях типа «указатель». Ошибки в описаниях типов P5, P6 и P7 будут отмечены компилятором из-за того, что, в таких случаях надо прежде описать идентификатор типа, а затем использовать его в других описаниях.

Следующие описания будут правильными:

TYPE MAS = ARRAY[1..10] OF REAL;

ST = STRING[25];

REC = RECORD

FIELD1 : STRING [15];

FIELD2 : REAL;

END;

VAR

P5 : ^MAS;

P6 : ^ST;

P7 : ^REC;

Указатель может находиться в одном из трех состояний, а именно:

1) еще не инициализирован;

2) содержит адрес размещения;

3) содержит значение предопределенной константы NIL; такой указатель называется пустым, то есть не указывает ни на какую переменную. Указатель со значением NILсодержит 0 в каждом из четырех байтов. Указатели можно сравнивать с другими указателями ( =, <> ), присваивать им адрес или значение другого указателя, передавать как параметр. Указатель нельзя отпечатать или вывести на экран.

Обращение к выделенной динамический памяти кодируется следующим образом:

<идентификатор указателя>^.

Рассмотрим пример обращения к переменным, размещенным в динамической памяти:

TYPE SYM=^CHAR;

ZAP=RECORD

FIELD1, FIELD2: REAL;

END;

M=ARRAY[0..9] OF WORD;

VAR CH : SYM;

REC : ^ZAP;

MAS : ^M;

Begin

CH^:='*';{обращение к динамической переменной типа CHAR, запись в эту область символа звездочка}

READLN (REC^.FIELD1);{обращение к полю FIELD1динамической записи, ввод в него данных с клавиатуры}

WRITELN (MAS[5]^);{обращение к элементу MAS[5]динамического массива, вывод на экран значения указанного элемента}

End.

Фактически можно говорить, что CH^, REC^.FIELD1и MAS[5]^исполняют роль имён динамических объектов в программе, адреса которых хранятся в указателях СH, RECи MASсоответственно.Следует отметить, что обращение к переменным типа POINTER(указателям, которые не указывают ни на какой определенный тип и совместимы со всеми другими типами указателей) приводит к ошибке.

Стандартные процедуры размещения и освобождения динамической памяти

Динамическая память может быть выделена двумя способами: 1. С помощью стандартной процедуры New (P); где Р- переменная типа… 2. С помощью стандартной процедуры GetMem (P,size); где P- переменная типа «указатель» требуемого типа; size-…

END;

PTR_REC = ^ REC;

VAR P : PTR_REC;

BEGIN

GETMEM(Р,SIZEOF(REC));{Выделение памяти, адрес выделенного участка фиксируется в Р; размер этой памяти в байтах определяет и возвращает стандартная функция SizeOf, примененная к описанному типу данных; однако, зная размеры внутреннего представления используемых полей, можно было бы подсчитать размер памяти «вручную» и записать в виде константы вместо SizeOf(Rec)}

...

{использование памяти}

...

FREEMEM(P, SIZEOF(REC));{освобождение уже ненужной памяти}

...

Динамическая память может быть освобождена четырьмя способами.

1. Автоматически по завершении всей программы.

2. С помощью стандартной процедуры Dispose (P); где P- переменная типа «указатель» (типизированный).

В результате работы процедуры DISPOSE(P)участок памяти, связанный с указателем P, помечается как свободный для возможных дальнейших размещений. При этом физической чистки указателя Pи связанной с ним памяти не происходит, поэтому, даже удалив этот экземпляр записи, можно все же получить значения ее полей, однако использовать это обстоятельство не рекомендуется. Ввиду различия в способах реализации процедуру DISPOSEне следует использовать совместно с процедурами MARKи RELEASE.

3. С помощью стандартной процедуры FreeMem (P, size); где P- переменная типа «указатель», size- целочисленное выражение размера памяти в байтах для освобождения.

Эта процедура помечает память размером, равным значению выражения SIZE, связанную с указателем P, как свободную (см. пример для GETMEM).

4. С помощью стандартных процедур Mark (P); Release (P); где P- переменная типа «указатель»;

MARK- запоминает состояние динамической области в переменной-указателе Р;

RELEASE- освобождает всю динамическую память, которая выделена процедурами NEWили GETMEMпосле запоминания текущего значения указателя Рпроцедурой MARK.

Обращения к MARKи RELEASEнельзя чередовать с обращениями к DISPOSEи FRЕЕМЕMввиду различий в их реализации.

Например:

VAR P:POINTER;

P1, P2, P3:^INTEGER;

BEGIN

NEW(P1); P1^:=10;

MARK(P); {пометка динамической области}

NEW(P2); P2^:=25;

NEW(P3); P3^:=P2^+P1^;

WRITELN (P3^);

RELEASE(P);{память, связанная с P2^ и P3^, освобождена, а P1^может использоваться}

END.

Стандартные функции обработки динамической памяти

MaxAvail; - эта функция возвращает размер в байтах наибольшего свободного в данный момент участка в динамической области. По этому размеру можно… TYPE ZAP=RECORD FIELD1: STRING [20];

END;

VAR P: POINTER;

BEGIN

...

IF MAXAVAIL <SIZEOF(ZAP) THEN

WRITELN ('HE ХВАТАЕТ ПАМЯТИ!')

ELSE

GETMEM(Р, SIZEOF(ZAP));

...

MemAvail; - эта функция возвращает общее число свободных байтов динамической памяти, то есть суммируются размеры всех свободных участков и объем свободной динамической области. Тип возвращаемого значения - longint.

...

WRITELN('Доступно', MEMAVAIL, 'байтов');

WRITELN('Наибольший свободный участок=', MAXAVAIL, 'байтов');

...

Это решение основано на следующем обстоятельстве. Динамическая область размещается в специально выделяемой области, которая носит название «куча» (HEAP). Куча занимает всю или часть свободной памяти, оставшейся после загрузки программы. Размер кучи можно установить с помощью директивы компилятора М: {$М<стек>, <минимум кучи>, <максимум кучи>}, где <стек>- определяет размер сегмента стека в байтах. По умолчанию размер стека 16 384 байт, а максимальный размер стека 65 538 байт. <минимум кучи>- определяет минимально требуемый размер кучи в байтах; по умолчанию минимальный размер 0 байт. <максимум кучи>- определяет максимальное значение памяти в байтах для размещения кучи; по умолчанию оно равно 655 360 байт, что в большинстве случаев выделяет в куче всю доступную память; это значение должно быть не меньше наименьшего размера кучи.

Все значения задаются в десятичной или шестнадцатеричной формах. Например, следующие две директивы эквивалентны:

{$М 16384,0,655360}

{$M $4000, $0, $A000}

Если указанный минимальный объем памяти недоступен, то программа выполняться не будет.

Управление размещением в динамической памяти осуществляет администратор кучи, являющийся одной из управляющих программ модуля System.

Примеры работы с памятью

Рассмотрим пример размещения и освобождения разнотипных динамических переменных в куче.

TYPE ST1=STRING[7];

ST2=STRING[3];

VAR I,I1,I2,I3,I4:^INTEGER;

R^:REAL;

S1:^ST1;

S2:^ST2;

BEGIN

NEW(I);

I1^:=1;

NEW(I2);

I2^:=2;

NEW(I3);

I3^=3;

NEW(I4);

DISРОSЕ (I2);{освобождается второе размещение} NEW (I);{память нужного размера (в данном случае два байта) выделяется на… I^:=5; (*2*)

END.

 

В следующем примере используется массив указателей.

USES CRT;

VAR R: ARRAY [1..10] OF ^REAL;

I : 1..10;

BEGIN

RANDOMIZE;{инициализация генератора случайных чисел}

FOR I:=1 TO 10 DO

BEGIN

NEW(R[I]);

R[I]^:=RANDOM;{генерация случайных вещ.чисел в диапазоне 0 <= r[i]^ < 1}

WRITELN(R[I]^);{Вывод случайных чисел в экспоненциальной форме}

END;

END.

Работа с динамическими массивами

При работе с массивами практически всегда возникает задача настройки программы на фактическое количество элементов массива. В зависимости от применяемых средств решение этой задачи бывает различным.

Первый вариант -использование констант для задания размерности массива.

PROGRAM FIRST;

CONST N : INTEGER = 10; { либо N = 10; }

VAR A : ARRAY [1..N] OF REAL;

I : INTEGER;

BEGIN

FOR I := 1 TO N DO

BEGIN

WRITELN ('Введите ', I , '-ый элемент массива ');

READLN (A[I])

END; { И далее все циклы работы с массивом используют N}

Такой способ требует перекомпиляции программы при каждом изменении числа обрабатываемых элементов.

Второй вариант- программист планирует некоторое условно максимальное (теоретическое) количество элементов, которое и используется при объявлении массива. При выполнении программа запрашивает у пользователя фактическое количество элементов массива, которое должно быть не больше теоретического. На это значение и настраиваются все циклы работы с массивом.

PROGRAM SECOND;

VAR A : ARRAY [1..25] OF REAL;

I, NF : INTEGER;

BEGIN

WRITELN ('Введите фактическое число элементов массива <= 25 ');

READLN (NF);

FOR I:= 1 TO NF DO

BEGIN

WRITELN ('Введите ', I, ' -ый элемент массива ');

READLN (A[I])

END;{ И далее все циклы работы с массивом используют NF}

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

Вариант третий- в нужный момент времени надо выделить динамическую память в требуемом объеме, а после того, как она станет не нужна, освободить ее.

PROGRAM DYNAM_MEMORY;

TYPE MAS = ARRAY [1..2] OF <требуемый_тип_элемента >;

MS = ^MAS;

VAR A : MS;

I, NF : INTEGER;

BEGIN

WRITELN ('Введите фактическое число элементов массива');

READLN (NF);

GETMEM (A, SIZEOF( <требуемый_тип_элемента>)*NF);

FOR I := 1 TO NF DO

BEGIN

WRITELN('Введите ', I , ' -ый элемент массива ');

READLN(A^[I])

END;{И далее все циклы работы с массивом используют NF}

. . . . .

FREEMEM (A, NF*SIZEOF (<требуемый_тип_элемента>));

END.

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

USES CRT;

TYPE T1=ARRAY[1..1] OF INTEGER;

VAR A:^T1;

N,M,I,J,K,P:INTEGER;

MAX:INTEGER;

BEGIN

CLRSCR;

WRITE('N='); READLN (N);

WRITE('M='); READLN (M);

GETMEM (A,SIZEOF(INTEGER)*N*M);

FOR I:=1 TO N*M DO READ(A^[I]);

MAX:=A^[1]; K:=1; P:=1;

FOR I:=1 TO N DO

FOR J:=1 TO M DO

IF A^[(I-1)*M+J] > MAX THEN

BEGIN

MAX:=A^[(I-1)*M+J];

K:=I; P:=J

END;

WRITE('строка=',K:2,' столбец=',P:2);

FREEMEM(A,2*N*M);

READKEY;

END.

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

местами.

USES CRT;

TYPE VK=^T1;

T1=ARRAY[1..1] OF INTEGER;

MT=^T2;

T2=ARRAY[1..1] OF VK;

VAR A:MT;

M,N,I,J,K,L:INTEGER;

MAX,MIN:INTEGER;

R:POINTER;

BEGIN

CLRSCR;

READLN (N,M);

GETMEM(A,SIZEOF (POINTER)*M); {выделение памяти под указатели столбцов матрицы}

FOR J:=1 TO M DO

GETMEM (A^[J],SIZEOF(INTEGER)*N); {выделение памяти под элементы столбцов}

FOR I:=1 TO N DO

FOR J:=1 TO M DO

READ(A^[J]^[I]);

FOR I:=1 TO N DO

BEGIN

FOR J:=1 TO M DO

WRITE (A^[J]^[I]:4);

WRITELN

END;

MAX:=A^[1]^[1]; K:=1; MIN:=MAX; L:=1;

FOR J:=1 TO M DO

FOR I:=1 TO N DO

IF A^[J]^[I]<MIN THEN

Begin MIN:=A^[J]^[I]; L:=J; end

ELSE

IF A^[J]^[I]>MAX THEN

BEGIN MAX:=A^[J]^[I]; K:=J; END;

{для обмена столбцов достаточно поменять указатели на столбцы}

IF K<>L THEN R:=A^[K]; A^[K]:=A^[L]; A^[L]:=R

FOR I:=1 TO N DO

BEGIN

FOR J:=1 TO M DO

WRITE(A^[J]^[I]:3,' ');

WRITELN

END;

FOR I:=1 TO M DO

FREEMEM (A^[I],N*SIZEOF(INTEGER));

FREEMEM (A,M*SIZEOF(POINTER))

END.

Контрольные вопросы:

1. Назначение динамической памяти. В чем состоит отличие динамической памяти от статической?
2. Дайте определение понятию «указатель». Формат описания. Примеры. Какие состояния может принимать указатель?
3. Как выполняется обращение к выделенной динамической памяти? Примеры.
4. Процедуры и функции для работы с динамическими данными. Примеры.
5. Где размещается динамическая область? Как устанавливается размер «кучи»? Единица измерения размера «кучи».
6. Работа с динамическими массивами. Дать описание всем вариантам.