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

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

Var

i,j:^Integer;

r: ^Real;

Begin

New (i);

...

End.

После выполнения этого фрагмента указатель приобретет значение, которое перед этим имел указатель кучи HeapPtr, а сам HeapPtr увеличит свое значение на 2, так как длина внутреннего представления типа Integer, с которым связан указатель i, составляет 2 байта (на самом деле это не совсем так: память под любую переменную, выделяется порциями, кратными 8 байтам). Оператор

New(r);

вызовет еще раз смещение указателя HeapPtr, но теперь уже на 6 байт, потому что такова длина внутреннего представления типа RealАналогичным образом выделяется память и для переменной любого другого типа. После того, как указатель приобрел некоторое значение, т.е. стал указывать на конкретный физический байт памяти, по этому адресу можно разместить любое значение соответствующего типа. Для этого сразу за указателем без каких – либо пробелов ставится значок ^, например:

i^:= 2; {В область памяти i помещено, значение 2}

Таким образом, значение, на которое указывает указатель, т.е. собственно данные, размещенные в куче, обозначаются значком ^, который ставится сразу за указателем. Если за указателем нет значка ^, то имеется в виду адрес, по которому размещены данные.

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

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

Dispose (r);

Dispose (i);

вернут в кучу 8 байт, которые ранее были выделены указателям i и R. Процедура Dispose(PTR)не изменяет значения указателя PTR, а лишь возвращает в кучу память, ранее связанную с этим указателем. Освободившийся указатель можно пометить зарезервированным словом Nil. Помечен ли какой-либо указатель или нет, можно проверить следующим образом:

Const

р:^Rеаl=NIL;

Begin

If р=NIL then new(p);

…

Dispose(р);

р:= NIL;

End.

Никакие другие операции сравнения над указателями не разрешены.

Чередование обращений к процедурам New и Disposeобычно приводит к «ячеистой» структуре памяти, изображенной на следующей схеме:

Состояние динамический памяти после действия различных процедур.

Использование указателей для обработки массивов

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

Program Demo_ukaz;

Type

mas=array[1..7000] of Integer;

Var

A:^mas; {указатель для работы с массивом}

c:^Integer; {указатель для работы с числом}

i,n:Integer;

Begin

Write('Размерность массива n=');

ReadLn (n);

New(A); {выделили память для массива}

New(c); {выделили память для числа}

Write('Введите число c=');

ReadLn (c^);

WriteLn('Введите элементы вектора А:');

For i:=1 to n do

ReadLn(A^[i]);

WriteLn ('Вектор А:');

For i:=1 to n do

Write(A^[i]:3);

WriteLn;

WriteLn ('Вектор cА:');

For i:=1 to n do

Write(A^[i]*c^:3);

Dispose(A); {освобождаем память}

Dispose(c);

End.

Использование указателей для работы со списками

Указатели являются эффективным средством построения списков.

Списком называется упорядоченная структура, каждый элемент которой содержит ссылку, связывающую его со следующим элементом. Для организации списков используются записи, состоящие из двух смысловых частей: основной и дополнительной. Основная часть содержит подлежащую обработке информацию, в дополнительной находится указатель на следующую запись списка. Начало списка указывается в переменной, которая всегда присутствует в программе обработки списков. Если в списке нет элементов, т.е. список пустой, последний элемент содержит значение Nil.

Основными операциями, которые можно выполнять над списками, являются операции включения записи в список и удаления её из списка.

Наибольшее распространение получили следующие виды списков: стеки, очереди.

1. Стек – это список с одной точкой доступа к его элементам, которая называется вершиной стека. Добавить или убрать элемент можно только через его вершину. Принцип работы стека – LIFO (Last In First Out), т.е. последний вошел, первый вышел. Для стека определены операции занесения элемента в стек и извлечении элемента из стека. Операция занесения элемента в стек определяется только значением элемента. Извлечение элемента заключается в присвоении переменной значения первого элемента стека и удалении этого элемента.

Схема работы стека

Пример программы работы со стеком: формирование стека, добавление, удаление и просмотр элементов.

Program Demo_Stack;

Type

Ukaz=^Stack;

Stack=record

Inf:Integer; {информационная часть}

Next:Ukaz {дополнительная часть}

end;

Var

Top,Kon:Ukaz;

Value:Integer;

{организация стека}

Procedure Sozd;

{тип элементов стека – Integer, ввод элементов прекращается, если введено значение 999}

Begin

Top:=Nil;

While True do

Begin

ReadLn(Value);

If Value=999 then Exit;

New(Kon); {Выделили память}

Kon^.Next:=Top; {В дополнительную часть занесли адрес

предыдущего элемента, для первого элемента значение Nil}

Kon^.Inf:=Value {В дополнительную часть занесли

значение введенного элемента}

Top:=Kon; {Запомнили адрес введенного элемента}

End

End;

{Добавление элементов в стек}

Procedure Dobavl;

{тип элементов стека – Integer, ввод элементов прекращается, если введено значение 999}

Begin

While True do

Begin

ReadLn(Value);

If Value=999 then Exit;

New(Kon); {Выделили память}

Kon^.Next:=Top; {В дополнительную часть занесли адрес

предыдущего элемента}

Kon^.Inf:=Value {В дополнительную часть занесли

значение введенного элемента}

Top:=Kon; {Запомнили адрес введенного элемента}

End

End;

{Удаление элемента стека}

Procedure Udal;

Begin

Top:=Top^.Next; {смещаем указатель на предыдущий элемент}

End;

{Просмотр элементов стека}

Procedure Pasp;

{Вывод элементов стека происходит в обратном порядке}

Begin

Kon:=Top;

While Kon<>Nil do {пока не дошли до конца}

Begin

WriteLn (Kon^.Inf); {выводим значение элемента}

Kon:=Kon^.Next; {смещаем указатель на следующий

элемент}

End

End;

{Основная программа}

Begin

Sozd;

Dobav;

Udal;

Rasp;

End.

2. Очередь – это структура данных, в один конец которой добавляются элементы, а с другого конца извлекаются. Принцип работы очереди FIFO (First In First Out) – «первым пришел, первым вышел». Для организации такой структуры используются две переменные: для указания начала и конца очереди, например Left и Right. При добавлении элемента в очередь он располагается в памяти в соответствии со значением Right, а значение Right изменяется и указывает на следующее свободное место памяти. Выборка элемента из очереди происходит исходя из значения n, которое изменяется и указывает на следующий элемент очереди. Когда очередь пуста, значения Left и Right равны. Как и для стека, для очереди определены операции занесения элемента в очередь и его извлечения из очереди. Схема работы очереди:

ГРАФИЧЕСКИЕ ВОЗМОЖНОСТИ

ЯЗЫКА Pascal