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

Указатель – переменная, которая  в качестве своего значения содержит адрес байта памяти. Указатель занимает 4 байта. Как правило, указатель связывается с некоторым типом данных. В таком случае он называется типизированным. Для его объявления используется знак ^, который помещается перед соответствующим типом, например:

type massiv=array [1..2500] of real;

var a:^integer; b,c:^real; d:^massiv;

В языке Free Pascal можно объявлять  указатель, не связывая его с конкретным типом данных. Для этого служит стандартный тип pointer, например:

var p,c,h: pointer;

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

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

Вся динамическая память во Free Pascal представляет собой сплошной массив байтов, называемый кучей. Физически куча располагается за областью памяти, которую занимает тело программы.

Начало кучи хранится в стандартной  переменной heaporg, конец – в переменной heapend. Текущая граница незанятой  динамической памяти хранится в указателе heapprt.

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

Например:

var 
i,j:^integer; 
r:^real; 
begin 
new(i); 
new(R); 
new(j);

 

В результате выполнения первого оператора  указатель i принимает значение, которое  перед этим имел указатель кучи heapprt. Сам heapprt увеличивает свое значение на 4, так как длина внутреннего представления типа integer, связанного с указателем i, составляет 4 байта. Оператор new(r) вызывает еще одно смещение указателя heapprt, но уже на 8 байтов, потому что такова длина внутреннего представления типа real. Аналогичная процедура применяется и для переменной любого другого типа. После того как указатель стал определять конкретный физический байт памяти, по этому адресу можно разместить любое значение соответствующего типа, для чего сразу за указателем без каких-либо пробелов ставится значок ^, например:

i^:=4+3; 
j^:=17; 
r^:=2 * pi;

Таким образом, значение, на которое  указывает указатель, то есть собственно данные, размещенные в куче, обозначаются значком ^. Значок ^ ставится сразу за указателем. Если после указателя значок ^ отсутствует, то имеется в виду адрес, по которому размещаются данные. Динамически размещенные данные (но не их адрес!) можно использовать для констант и переменных соответствующего типа в любом месте, где это допустимо, например:

r^:=sqr(r^)+sin(r^+i^)-2.3

Невозможен оператор

r:=sqr(r^)+i^;

так как указателю r нельзя присвоить  значение вещественного типа. Точно  так же недопустим оператор

r^:=sqr(r);

поскольку значением указателя r является адрес, и его (в отличие от того значения, которое размещено по данному адресу) нельзя возводить в квадрат. Ошибочным будет и присваивание r^:=i, так как вещественным данным, на которые указывает r^, нельзя давать значение указателя (адрес). Динамическую память можно не только забирать из кучи, но и возвращать обратно. Для этого используется процедура dispose(p), где р – указатель, который не изменяет значение указателя, а лишь возвращает в кучу память, ранее связанную с указателем.

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

Другая возможность состоит в освобождении целого фрагмента кучи. С этой целью перед началом выделения динамической памяти текущее значение указателя heapptr запоминается в переменной указателе с помощью процедуры mark. Теперь можно в любой момент освободить фрагмент кучи, начиная с того адреса, который запомнила процедура mark, и до конца динамической памяти. Для этого используется процедура release. Процедура mark запоминает текущее указание кучи heapptr (обращение mark(ptr), где ptr – указатель любого типа, в котором будет возвращено текущее значение heapptr). Процедура release(ptr), где ptr – указатель любого типа, освобождает участок кучи от адреса, хранящегося в указателе до конца кучи.

Для работы с указателями любого типа используются процедуры getmem, freemem. Процедура getmem(p,size), где р – указатель, size – размер в байтах выделяемого фрагмента динамической памяти (size типа word), резервирует за указателем фрагмент динамической памяти требуемого размера.

Процедура freemem(p,size), где р – указатель, size – размер в байтах освобождаемого фрагмента динамической памяти (size типа word), возвращает в кучу фрагмент динамической памяти, который был зарезервирован за указателем. При применении процедуры к уже освобожденному участку памяти возникает ошибка.

После рассмотрения основных принципов и процедур работы с указателями возникает вопрос: а зачем это нужно? В основном для того, чтобы работать с так называемыми динамическими массивами. Последние представляют собой массивы переменной длины, память под которые может выделяться (и изменяться) в процессе выполнения программы, как при каждом новом запуске программы, так и в разных её частях. Обращение к  
i-му элементу динамического массива х имеет вид x^[i].

Рассмотрим процесс функционирования динамических массивов на примере решения следующей задачи: найти максимальный и минимальный элементы массива X(N).

Рассмотрим процесс решения  задачи с использованием указателей. Распределение памяти проводим с  помощью процедур new–dispose:

program din_mas1; 
type massiw= array[1..150]of real; 
var 
x:^massiw; 
i,n:integer; 
max,min:real; 
begin 
{Выделяем память под динамический массив из 150 вещественных чисел.} 
new(x); 
writeln('Введите размер массива'); 
readln(n); 
for i:=1 to N do 
begin 
write('x(',i,')='); 
readln(x^[i]); 
end; 
max:=x^[1];min:=x^[1]; 
for i:=2 to N do 
begin 
if x^[i] > max then max:=x^[i]; 
if x^[i] < min then min:=x^[i]; 
end; 
writeln('максимум=',max:1:4, ' минимум=',min:1:4); 
{ Освобождаем память. } 
dispose(x); 
end.

Распределение памяти проводим с помощью  процедур getmem–freemem:

program din_mas2; 
type 
massiw=array[1..150]of real; 
var 
x:^massiw; 
i,n:integer;max,min:real; 
begin 
writeln(‘Введите размер массива’); 
readln(n); 
{ Выделяем память под n элементов массива. } 
getmem(x,n*sizeof(real)); 
for i:=1 to N do 
begin 
write('x(',i,')='); 
readln(x^[i]); 
end; 
max:=x^[1];min:=x^[1]; 
for i:=2 to N do 
begin 
if x^[i] > max then max:=x^[i]; 
if x^[i] < min then min:=x^[i]; 
end; 
writeln(' максимум=',max:1:4,' минимум=',min:1:4); 
{ Освобождаем память. } 
freemem(x,n*sizeof(real)); 
end.

 

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

1. Описать указатели.
2. Выделить память под массив (функции new или getmem).
3. Обработать динамический массив.
4. Освободить память (функции dispose или freemem).

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

 

Заключение

Современное программирование сложно представить без динамических массивов. Они присутствуют практически во всех языках программирования. Использование динамических массивов позволяет с максимальной эффективностью использовать вычислительные мощности компьютеров (или серверов). «На лету» загружать в оперативную память необходимые данные, обрабатывать их и освобождать место под новую порцию.

Free Pascal позволяет работать с оперативной памятью посредством указателей. Используя это, можно динамически размещать данные в ОЗУ. И хотя в данной версии языка программирования нет нативной поддержки динамических массивов мы можем динамически выделять место в памяти под новые данные или очищать от неиспользуемых.

Прямая работа с оперативной  памятью добавляет некоторые  требования к программисту. Необходимо чётко представлять процессы, происходящие там. Неправильное или невнимательное использование оперативной памяти может привести к различным ошибкам. Например к чрезмерному росту используемого объёма памяти (утечка), если не очищать место от неиспользуемых данных. Другой вариант – возможно искажение данных, если области памяти переменных или массивов пересекутся.

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

 

Список литературы

 

1. Вирт, Никлаус. Алгоритмы и структуры данных. СПб.: Невский диалект. 2001.
2. Вирт, Никлаус. Паскаль. Руководство для пользователя и описание языка. М.: Финансы и статистика, 1982.
3. Алексеев Е.Р. Самоучитель по программированию на Free Pascal и Lazarus / Алексеев Е.Р., Чеснокова О.В., Кучер Т.В. Донецк: Унитех, 2009.
4. Документация Free Pascal: http://www.freepascal.org/docs.var