Часть IV. Работа с динамическими массивами

О статическом и динамическом распределении памяти

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

Распределение памяти под г лобальные данные (объявленные в разделах программы – см. §2.4) является статическим. При распределении локальных данных подпрограмм имеет место элемент динамизма, так как оно происходит на этапе выполнения программы при вызове подпрограммы. Заметим, что распределение локальных данных не изменяется в процессе выполнения подпрограммы, а при завершении подпрограммы память освобождается.

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

Указатель определяется как абстрактное обобщение адреса (а не как переменную, принимающую значения на множестве адресов), потому что значение адреса зависит от конкретной ЭВМ и условий, в которых происходит работа компилятора. Тип указатель имеется во всех универсальных языках программирования.

Динамическое распределение памяти используется в двух ситуациях:

1) когда статической памяти и стека подпрограмм не хватает для решения задачи;

2) когда характер задачи требует динамического распределения.

Пример второй ситуации рассматривается в §4.3.

Указатели в Паскале

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

Указатели описываются с помощью инструкций:

имя_типированного_указателя: ^ тип_содержимого_ячейки;

имя_нетипированного_указателя: pointer;

В качестве типа содержимого ячейки (базового типа) может быть использован любой стандартный тип или имя нестандартного типа.

Указателю может быть присвоено значение другого указа­теля, причем в операторе присваивания (слева и справа от знака :=) должны участвовать указатели с одинаковым базовым типом или один из указателей должен быть нетипированным.

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

Операция @ означает взятие адреса переменной: @A – адрес переменной A (или адрес первого байта массива или структуры A). Операция ^ означает взятие содержимого: ^b – содержимое ячейки с адресом b (сравните положение значка ^ с тем, что используется при объявлении указателей). ^b можно использовать точно так же, как и переменную базового для указателя b типа.

Пример.

Var C: ^integer; i:integer;

Begin C:=@i; {в ячейку С записан адрес ячейки i}

C^:=1; {в ячейку с адресом С записано значение 1}…End.

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

Процедура new(p), где p – типированный указатель, выделяет область памяти, на которую указывает (т. е. адрес которой хранит) р. При этом p^ представляет собой переменную базового для р типа и называется динамической переменной. Процедура dispose(p) возвращает выделенную с помощью new(p) память в кучу, после применения dispose(p) значение указателя р становится неопределенным (не становится равным nil!). Применение dispose к пустому указателювызываетсообщение об ошибке.

Процедура GetMem(p,n) выделяет область динамической памяти из n байтов, на которую указывает р – типированный или нетипированный указатель. Функция AllocMem(p) возвращает значение нетипированного указателя на область из n байтов; в отличии от GetMem, AllocMem заполняет выделенную область нулями. Процедура FreeMem(p) освобождает память, полученную с помощью GetMem или AllocMem.

Динамические массивы

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

Классический подход к работе с массивами переменной длины, который в настоящее время используется, например, в алгоритмическом языке Си, состоит в следующем. После определения числа n элементов массива (например, посредством ввода) с помощью процедуры, аналогичной GetMem(p,n), выделяется область памяти под массив. Указатель p при этом ссылается на первый элемент массива. Адреса остальных элементов легко вычисляются по их индексам. Например, адрес i-го элемента в одномерном массиве равен p+(i-1)*s, где s – количество байтов, занимаемых одним элементом. В Объектном Паскале такой подход невозможен, так как ограничено использование арифметических операций над указателями. Это ограничение позволяет увеличить надежность программы за счет уменьшения вероятности несанкционированного доступа к памяти из-за неправильного определения адресов.

Как альтернатива описанного выше подхода, в Объектном Паскале для работы с массивами переменной длины определен специальный тип – динамические массивы. Описание динамического массива:

Var имя_массива: Array of Array of…Array of тип_элемента;

Ключевые слова Array of записываются в описании столько раз, сколько индексов у массива. По существу объявленное имя_массива является указателем на массив. Начальное значение индексов динамического массива равно нулю.

Выделение памяти под массив осуществляется с помощью процедуры SetLength (см. также §3.1.2). Вызов этой процедуры имеет вид:

SetLength(имя_массива, размер1, размер2,…,размерM).

В скобках указываются размеры массива по первым M (не обязательно всем) индексам.

Пример 1. В приведенном ниже фрагменте программы выделяется память под вещественный одномерный массив a размером n и под целочисленную матрицу b из n строк и m столбцов. Значения n и m предварительно задаются вводом.

Var a:Array of Real; b:Array of Array of integer; n,m:integer;

Begin

Readln(n,m);

SetLength(a,n); SetLength(b,n,m);…

Для работы с массивами (необязательно динамическими) также используются функции:

Length(a) – возвращает размер массива a по первому индексу;

Low(a) – возвращает наименьший номер компонента массива a (для динамических массивов ноль);

High(a) – возвращает наибольший номер компонента массива a;

SizeOf(a) –возвращает число байтов памяти, занимаемых массивом a.

Для освобождения памяти, отведенной под динамический массив, достаточно присвоить его имени значение nil.

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

program Primer2;

Var a:Array of Array of real; n,m,i,j:integer; {n,m – размеры матрицы}

{i,j – счетчики строк и столбцов}

Begin

writeln(’Input count of rows’); readln(n);

writeln(’Input count of columns’); readln(m);

SetLength(a,n); {отводится память под указатели на строки}

writeln(’Input array ’, n, ’*’,m);

for i:=0 to High(a) do {High(a)=n-1)}

begin

Setlength(a[i],m); { отводится память под элементы строки}

for j:=0 to High(a[i]) do {High(a[i]=m-1}

read(a[i,j]);

end; readln; {закончен ввод динамического массива}

// обработка матрицы – заглушка

writeln(’ output of dynamic array’);

for i:=0 to High(a) do

begin

for j:=0 to High(a[i]) do

write (a[i,j]:7:2); writeln;

a[i]:=nil; {освобождение памяти из-под строки}

end;

a:=nil;{ освобождение памяти из-под указателей на строки }

readln

End.