Ранее мы изучали статические типы данных, память под которые выделялась во время компиляции программы, она не должна была превышать 64 килобайта и количество таких данных не изменялось во время выполнения программы. Однако существует ряд задач, где статические структуры неэффективны. В языке Паскаль имеются средства создания динамических структур данных, которые позволяют во время выполнения программы:
- образовывать объекты; выделять для них память; размер данных может превышать 64 килобайта; уничтожать, когда в них исчезает необходимость.
Определение: Динамические переменные - это переменные, память под которые выделяется во время выполнения программы.
Для получения ясного представления о динамических переменных надо рассмотреть структуру памяти во время выполнения программы на языке Паскаль:
Основным механизмом для организации динамических данных является выделение в специальной области памяти, называемой « heap-областью» или «кучей», непрерывного участка подходящего размера и сохранения адреса начала этого участка в специальной переменной, называемой, ссылочной переменной или ссылкой или указателем.
Определение: Ссылочная переменная (указатель) – переменная, предназначенная для хранения адреса переменной, расположенной в динамической области памяти (heap – области или «куче»).
Сам указатель располагается в статической памяти.
Ссылочная переменная Динамическая переменная
(указатель)
Каждый указатель размещается в сегменте данных или в стеке (если он объявлен в подпрограмме) и занимает там 4 байта (2 слова: номер сегмента и смещение *). Это дополнительные “накладные расходы’ памяти. Поэтому обычные переменные очень редко создают и уничтожают динамически, оставляя эту возможность для больших совокупностей данных. Чем больше размер динамической переменной, тем меньше доля накладных расходов. Например, при хранении в динамической памяти массивов больших размеров лишние 4 байта, затраченные на указатель, несущественны.
*Пояснение: Адресуемое пространство памяти организовано сегментами: последовательными блоками памяти по 64 Кб каждый. Если известен сегмент, то дальнейшее уточнение места объекта в памяти происходит по смещению, т. е. номеру байта от начала сегмента. Любая ячейка памяти определяется парой чисел сегмент: смещение.
Описание ссылочной переменной (указателя)
Формат описания ссылочного типа данных:
Type <тип указателя> = ^ <идентификатор базового типа>,
то есть указатель связан с некоторым типом данных. Такие указатели называются типизированными.
Базовый тип может быть любым, кроме файлового.
Пример описания переменных ссылочного типа:
Type
DinMas=array[1..10000] of real;
p1=^integer;
p2=^real;
P3=^DinMas;
Var
A, B,C:p1;
X, Y,Z:p2;
M:p3;
P:^char;
T:^integer;
Cсылочные переменные A, B, C, T указывают на динамические объекты целого типа, X, Y,Z - вещественного, P – символьного, а M - на массив. Значением ссылочной переменной является адрес в динамически выделенной памяти, где хранится объект этого типа.
Однако в Турбо Паскале можно объявлять указатель и не связывать его с конкретным типом данных. Такой указатель называется нетипизированным. Для его объявления служит стандартный тип pointer. Структура и тип таких данных могут меняться во время выполнения программы.
var <имя_указателя> : Pointer;
Для обращения к ссылочной переменной используют запись “ A^ ”, что означает: ”идти по адресу, хранящемуся в A”.
Рассмотрим на примере отличие ссылочной переменной от статической.
Пусть дано описание:
Var J:^integer;
I:integer;
После выполнения операций:
J^:=15;
I:=15;
Операции, определенные над ссылочной переменной (указателем)
Определение адресаФизический адрес любой переменной можно узнать при помощи стандартной функции Addr:
Addr(<имя_переменной>) : <указатель>
или унарной операции @:
@<имя_переменной>.
В зависимости от значения директивы компилятора {$T}, результатом операции @ будет либо типизированный указатель (если установлено {$T+}), тип которого будет определен в соответствии с типом использованной переменной, либо нетипизированный указатель Pointer (если установлено{$T-}).
Результат функции Addr() совместим с указателями любых типов:
Var x : Real;
p : ^Byte
p := Addr(x);
РазыменованиеДля того, чтобы воспользоваться значением, хранящимся по некоторому адресу, необходимо его оттуда «извлечь». Унарная операция ^ называется разыменованием и записывается по следующему шаблону:
<имя_указателя>^
Результатом операции ^ является значение, хранящееся по указанному адресу. Тип этого значения будет определяться типом (типизированного) указателя.
Определение: Разыменованием ссылки называется получение объекта, на который указывает эта ссылка.
К нетипизированным указателям операцию разыменования применять нельзя.
Операция присваиванияДля указателей действуют гораздо более жёсткие правила совместимости типов, чем для обычных переменных. В операции присваивания могут фигурировать только указатели, адресующие переменные одинаковых типов данных. Нельзя, скажем, записать
p := q; если var p : ^Integer; q : ^Byte
Обойти эти ограничения позволяет универсальность нетипизированного указателя Pointer, совместимого с указателями любых типов:
Var p : ^Integer;
q : ^Byte;
t : Pointer;
t := q;
p := t;
У указателей также существует свой «ноль», который означает, что указатель не указывает никуда:
p := nil;
Замечание: Если указатель не хранит конкретного адреса (его значение не определено), то это вовсе не означает, что он никуда не указывает. Скорее всего, он всё–таки указывает, но только в какую–нибудь неожиданную (хорошо, если не системную) область памяти.
Таким образом:
1) Ссылочной переменной может быть присвоено “пустое” значение адреса, обозначенное служебным словом nil. Nil — это зарезервированная константа. Значение nil - это два нулевых слова. Оно может быть присвоено указателю любого типа.
p:=nil;
2) Ссылочной переменной может быть присвоено значение другой ссылочной переменной, если они ссылаются на объекты одного типа.
p:=q;
Операции сравнения (=, <>)Для указателей определены две операции сравнения: = и <>.
Типизированные указатели можно сравнивать, если они одного типа.
Два значения ссылочного типа равны, если они оба есть nil, либо указывают на один и тот же динамический объект. Во всех остальных случаях имеет место неравенство.
Рассмотрим пример. Пусть в программе описаны следующие указатели:
Var q, p: ^Integer;
Если: p:=Nil; q:= Nil; то условие p=q будет истинным.
Для разнотипных указателей сравнения невозможны:
Var p : ^Byte; q : ^Integer;
попытка записать:
if p = q then WriteLn('yes');
вызовет ошибку уже на этапе компиляции.
Однако сравнивать типизированный и нетипизированный указатели можно.
Можно указатели использовать в условных операторах:
if p=q then… или if p=nil then... {проверка указателя на пустоту}
Процедуры и функции, определенные над ссылочными переменными:
1) Процедура New( var p: Pointer ) - выделяет место в динамической области памяти для размещения динамической переменной p^ и ее адрес присваивает указателю p.
2) Процедура Dispose( var p: Pointer ) - освобождает участок памяти, выделенный для размещения динамической переменной процедурой New, и значение указателя p становится неопределенным.
3) Проуедура GetMem( var p: Pointer; size: Word ) - выделяет участок памяти в heap - области, присваивает адрес его начала указателю p, размер участка в байтах задается параметром size.
4) Процедура FreeMem( var p: Pointer ) - освобождает участок памяти, адрес начала которого определен указателем p. Значение указателя p становится неопределенным.
5) Процедура Mark( var p: Pointer ) - записывает в указатель p адрес начала участка свободной динамической памяти на момент ее вызова.
6) Процедура Release( var p: Pointer ) - освобождает участок динамической памяти, начиная с адреса, записанного в указатель p процедурой Mark, то есть, очищает ту динамическую память, которая была занята после вызова процедуры Mark.
7) Функция MaxAvail: Longint - возвращает длину в байтах самого длинного свободного участка динамической памяти.
8) Функция MemAvail: Longint - полный объем свободной динамической памяти в байтах.
9) Вспомогательная функция SizeOf( X ): Word - возвращает объем в байтах, занимаемый X, причем X может быть либо именем переменной любого типа, либо именем типа.
Внимание! В PascalABC используются только первые четыре процедуры (new, Dispose, Getmem, Freemem).
При работе с указателями обязательны два этапа:
1) объявление указателя;
2) формирование динамических данных, память под которые отводится во время выполнения программы при помощи процедуры New.
Динамические переменные
Под динамически размещаемую переменную во время выполнения программы, память выделяется с помощью вызова процедуры
New(P); Р - указатель.
Данный вызов выполняет два следующих действия:
•обращается к операционной системе для выделения области памяти, необходимой для размещения переменной базового типа;
•устанавливает начальный адрес этой области памяти в качестве значения переменной-указателя.
Вызов New можно выполнять в любом месте программы любое число раз, в том числе – циклически. Это позволяет при выполнении программы динамически создавать любое необходимое число переменных базового типа.
После выделения области памяти в неё можно записать необходимое значение, используя ссылочную переменную и символ ^ после ее имени – это называется операцией разыменования.
С такой переменной можно выполнять все те операции, которые разрешены для базового типа. Например:
Type Mas1 = Array[1..100] Of Integer;
Var P1 : ^Integer;
P2 : ^String;
Pm : ^Mas1;
Здесь P1 — указатель на динамическую величину целого типа; P2 — указатель на динамическую величину строкового типа; Pm — указатель на динамический массив, тип которого задан в разделе Type.
Память под динамическую величину, связанную с указателем, выделяется в результате выполнения стандартной процедуры NEW:
NEW(P1); NEW(P2); NEW(Pm);
После их выполнения в динамической памяти оказывается выделенным место под три величины (две скалярные и один массив), которые имеют идентификаторы:
P1^, P2^, Pm^
Дальнейшая работа с динамическими переменными происходит точно так же, как со статическими переменными соответствующих типов. Им можно присваивать значения, их можно использовать в качестве операндов в выражениях, параметров подпрограмм и пр. Например, если переменной P1^ нужно присвоить число 25, переменной P2^ присвоить значение символа "Write", а массив Pm^ заполнить по порядку целыми числами от 1 до 100, то это делается так:
P1^:= 25;
P2^:= 'Write';
For I:= 1 To 100 Do Pm^[I]:= I;
Надо понимать разницу между ссылочной переменной (переменной –указатель) и динамической переменной. Покажем это на примере:
Var p, q:^integer;
……
new(p); new (q);
p^:=3; q^:=58;
p:=q;
q:=nil;
Если вместо оператора p:=q написать оператор p^:=q^ , то изменится значение динамической переменной, на которую указывает указатель p.
Если динамическая величина теряет свой указатель, то она становится "мусором".
В программировании под этим словом понимают информацию, которая занимает память, но уже не нужна.
В рассмотренном выше примере, динамическая величина, равная 3, потеряла свой указатель и стала недоступной. Однако место в памяти она занимает. Это и есть пример возникновения "мусора". На схеме показано, что произошло в результате выполнения оператора p := q.
В Паскале имеется стандартная процедура, позволяющая освобождать память от данных, потребность в которых отпала. Ее формат:
DISPOSE(<указатель>);
Например, если динамическая переменная p^ больше не нужна, то оператор DISPOSE(P)
удалит ее из памяти. После этого значение указателя p становится неопределенным (НЕ путать с ПУСТЫМ указателем!) и ее нельзя использовать до тех пор, пока она снова не будет инициализирована с помощью вызова New или инструкции присваивания.
Особенно существенным становится эффект экономии памяти при удалении больших массивов.
Внимание! Распределение и освобождение памяти для нетипизированных указателей (pointer) производится с помощью специальных стандартных функций GetMem и FreeMem.
Рассмотрим предыдущий пример с использованием процедуры DISPOSE(P):
Var p, q:^integer;
……
new(p); new (q);
p^:=3; q^:=58;
despose(p);
|
q:=nil;
Таким образом, стандартные процедуры new и dispose позволяют динамически порождать объекты и уничтожать их, что дает возможность использовать память более эффективно.
Процедурой despose(p)надо пользоваться аккуратно. Использование вызова despose(p) может приводить к весьма неприятной ситуации, связанной с появлением так называемых “висячих” указателей: если два указателя адресовали одну и ту же область памяти (а это встречается очень часто), то вызов despose(p) с одной из них оставляет в другой переменной адрес уже освобожденной области памяти и повторное использование этой переменной приведет либо к неверному результату, либо к аварийному завершению программы.
Например:
Var p, q:^integer;
……
new(p); new (q);
p^:=3;
q:=p;
despose(p);
Использование Dispose для освобождения выделенной динамической памяти не является обязательным, после выхода из программы динамическая память освобождается автоматически, но частое использование процедуры выделения памяти без ее освобождения может привести к состоянию невозможности дальнейшего выделения памяти и к остановке программы.
Примеры программ с использованием указателей и динамических переменных
Пример 1.
Program DemoPointer;
var p1,p2,p3:^Integer;
begin
p1:=NIL; p2:=NIL; p3:=NIL;
New(p1); New(p2); New(p3);
p1^:=2; p2^:=4;
p3^:=p1^+Sqr(p2^);
writeln('p1^=',p1^:3,' p2^=',p2^:3,' p3^=',p3^:3);
p1:=p2;
writeln('p1^=',p1^:3,' p2^=',p2^:3)
end.
В результате выполнения программы на экран дисплея будут выведены результаты:
p1^= 2 p2^= 4 p3^= 18
p1^= 4 p2^= 4
Пример 2. В динамическом массиве найти максимальный элемент.
type tm=array[1..10000] of integer;
var a:^tm;
n, i,max:integer;
begin writeln('input n');
readln(n);
randomize;
new(a);
for i:=1 to n do a^[i]:=random(100);
max:=a^[1];
for i:=2 to n do
if a^[i]>max then max:=a^[i];
writeln('max=',max);
dispose(a);
end.
Пример 3. Создать массив указателей и найти в нем минимальное значение.
var a:array[1..100] of ^real;
i, n:integer;
min:real;
begin writeln('input n');
readln(n);
randomize;
for i:=1 to n do
begin new(a[i]);
a[i]^:=random(10)-random;
writeln(a[i]^:6:2)
end;
min:=a[1]^;
for i:=2 to n do
if a[i]^<min then min:=a[i]^;
writeln('min=',min:6:2);
for i:=1 to n do dispose(a[i]);
end.
Пример 4. Дан текстовый файл размером не более 64 Кб, содержащий действительные числа, по одному в каждой строке. Переписать содержимое файла в массив, разместив его в динамически распределяемой памяти. Вычислить среднее значение элементов массива. Очистить динамическую память. Создать целый массив размером 10000, заполнить его случайными целыми числами в диапазоне от –100 до 100 и вычислить его среднее значение.
Program Srednee;
Const NMax = 10000;
Type Diapazon = 1..NMax;
MasInt = Array[Diapazon] Of Integer;
MasReal = Array[Diapazon] Of Real;
Var PInt : ^MasInt; PReal : ^MasReal;
I, Midint, N : longInt;
MidReal : Real;
T : Text;
S : string;
Begin
Write('Введите имя файла: ');
ReadLn(S);
Assign(T, S);
Reset(T);
MidReal := 0; MidInt := 0;
Randomize;
NEW(PReal); {Выделение памяти под вещественный массив}
{Ввод и суммирование вещественного массива}
I:=1;
While Not Eof (T) Do
Begin ReadLn(T, PReal^[I]);
MidReal := MidReal + PReal^[I];
I:=I+1;
End;
DISPOSE(PReal); {Удаление вещественного массива}
N:=I;
Close(T);
NEW(PInt); {Выделение памяти под целый массив}
{Вычисление и суммирование целого массива}
For I := 1 To N Do
Begin PInt^[I] := -100 + Random(201);
MidInt := MidInt + PInt^[I]
End;
{Вывод средних значений}
WriteLn('среднее целое равно: ', MidInt Div N);
WriteLn('среднее вещественное равно: ', (MidReal / N) : 10 : 6)
End.
Заключение
1. Динамические величины не требуют описания в программе, поскольку во время компиляции память под них не выделяется.
2. Во время компиляции память выделяется только под статические величины. Указатели — это статические величины, поэтому они требуют описания.
3. Память под динамическую величину, связанную с указателем, выделяется в результате выполнения стандартной процедуры NEW.
4. До присваивания значения ссылочной переменной (с помощью оператора присваивания или процедуры NEW) она является неопределенной.
5. Ввод и вывод указателей не допускается.
6. Работа с динамическими переменными происходит точно так же, как и со статическими переменными соответствующих типов.
7. Подключение динамической памяти позволяет увеличить объем обрабатываемых данных. В версиях Турбо-Паскаля, работающих под операционной системой MS DOS, под данные одной программы выделяется 64 килобайта памяти (или, если быть точнее, 65520 байт). Это и есть статическая область памяти. При необходимости работать с большими массивами информации этого может оказаться мало. Размер динамической памяти — много больше (сотни килобайт).
8. Если потребность в каких-то данных отпала до окончания программы, то занятую ими память можно освободить для другой информации.
9. Использование динамической памяти позволяет создавать структуры данных переменного размера (списки, очереди, стеки, деревья).
10. Работа с динамическими данными замедляет выполнение программы, т. к. доступ к величине происходит в два этапа: сначала ищется указатель, затем по нему – величина. Выигрыш в памяти компенсируется проигрышем во времени.
11. Использование динамической памяти требует большой осторожности и может быть причиной трудноуловимых ошибок времени выполнения.
Здесь вы можете проверить себя по материалу этой темы.
Контрольные вопросы
Чем отличаются статические и динамические величины? Какая память называется динамически распределяемой? Что такое указатель? Какие виды указателей вам известны? Как определяется адрес переменной? Приведите примеры объявления указателей. Как выделить память под динамическую переменную? Как освободить память от динамической переменной? Что такое "разыменование"? Что в языке Pascal обозначает константа Nil? В каком случае возможно присваивание указателей? Какие ситуации приводят к возникновению в динамически распределяемой памяти "мусора"?Задание
Написать программу, которая создает динамический массив размерностью до 100000 элементов случайным образом и находит в нем первое вхождение отрицательного элемента. Если такой элемент есть, то надо вывести его номер и значение, если таких элементов нет, то сообщить об этом.
Используемые ссылки:
http://*****/Chairs/IMO/pascal/theory/
http://pascal. toom. su
