Оглавление
Динамическая память. 1
Указатель. 1
Стандартные процедуры размещения и освобождения динамической памяти. 2
Стандартные функции обработки динамической памяти. 3
Примеры работы с памятью.. 4
Работа с динамическими массивами. 4
Контрольные вопросы: 6
Комбинированный урок №19
Тема:Динамические структуры данных и их организация с помощью указателей
Цель: изучить принципы организации памяти, дать понятие указателю, сформировать знания о применяемых процедурах и функциях.
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(указателям, которые не указывают ни на какой определенный тип и совместимы со всеми другими типами указателей) приводит к ошибке.
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.
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;
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.
Контрольные вопросы: