Процедуры и функции. Модули

2  Процедуры и функции. Модули.

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

2.1  Процедуры и функции

Принцип модульности является одним из важных принципов программирования. При решении задачи она разбивается на более мелке подзадачи. В модульной программе отдельные ее части, предназначенные для решения частных задач, организованы в подпрограммы. Часто определенная последовательность действий выполняется неоднократно, и при этом различаются только параметры, над которыми эти действия выполняются. При модульной организации один и тот же фрагмент программного кода можно использовать многократно как в одной, так и в разных программах, не делая заново одну и ту же работу. К тому же, программы, написанные небольшими частями, легче читать, тестировать и отлаживать. Как правило, в таких программах более четкая логическая структура. Это имеет большое значение при разработке больших программных проектов, которые программист-одиночка сделать самостоятельно просто не сможет. Большая программа разбивается на отдельные блоки, каждый из которых – логически завершенная часть общей работы. Каждый блок можно оформить в виде одной или нескольких подпрограмм и разработку разных подпрограмм поручить разным программистам[].

Процедуры и функции – это относительно самостоятельные фрагменты программы, оформленные специальным образом и снабженные именем. Упоминание этого имени в тексте программы называется вызовом процедуры (функции). Отличие функции от процедуры в том, что результатом исполнения операторов, образующих тело функции, всегда является некоторое значение, поэтому обращение к функции можно использовать в соответствующих выражениях наряду с переменными и константами. [] Каждая процедура или функция имеет свое уникальное имя. Текст подпрограммы можно поместить в раздел описаний процедур и функций программы или в специальным образом оформленную библиотеку.

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

Все параметры, которые использует подпрограмма, можно разбить на две категории:

1.  локальные параметры, объявленные внутри подпрограммы, и доступные только ей самой.

2.  глобальные – объявленные в основной программе и доступные как программе, так и всем ее подпрограммам.

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

Формальные параметры подпрограммы указывают, с какими параметрами следует обращаться к этой подпрограмме (количество параметров, их последовательность, типы). Они задаются в заголовке подпрограммы в виде списка формальных параметров, разбитого на группы, разделенные точками с запятыми. В группу формальных параметров включаются однотипные параметры одной категории. Для каждого формального параметра следует указать его имя, как правило, тип и его категорию. Имена параметров могут быть любыми, в том числе и совпадать с именами объектов программы. В случае совпадения параметр основной программы с таким именем становится недоступным для непосредственного использования подпрограммой. Тип формального параметра может быть практически любым, но в заголовке подпрограммы нельзя вводить новый тип.

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

Синтаксис описания функций и процедур:

function <имя функции> (<список параметров>):<тип возвращаемого значения>;

{ заголовок функции или объявление функции }

<объявление локальных переменных, типов, констант, описания вложенных функций и процедур>

begin

<операторы тела функции>;

end;

procedure <имя процедуры> (<список параметров>);

{ заголовок процедуры или объявление процедуры }

<объявление локальных переменных, типов, констант, описания вложенных функций и процедур>

begin

<операторы тела процедуры>;

end;

Список параметров и объявление локальных элементов и вложенных процедур и функций являются необязательными. Если список параметров отсутствует, то скобки после имени не ставятся.

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

Возвращаемое значение в теле функции присваивается имени функции или специальной предопределенной переменной Result. Имя функции – это не переменная. Оно может фигурировать только в левой части оператора присваивания и не может входить в какие-либо выражения, за исключением рекурсивных вызовов. Result – это обычная переменная.

Есть несколько способов передачи параметров в процедуры и функции. Каждому способу передачи параметров соответствует свое правило описания параметра

1.  передача по значению;
имя_параметра: тип

В момент вызова подпрограммы в памяти создаются временные переменные и в них копируются значения аргументов. На этом связь между переменными и аргументами разрывается. Аргументы при этом защищены от непреднамеренного изменения своих значений вызванной процедурой или функцией. Недостаток – затраты времени на копирование и затраты памяти для хранения копий.

2.  передача по ссылке;
Var имя_параметра: тип;

Процедура работает со ссылкой – указателем на место хранения аргумента в памяти. Любые изменения параметра относятся к тому аргументу, который передан при вызове подпрограммы.

3.  передача как константы;
Const имя_параметра: тип;

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

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

Реальный тип аргумента должен соответствовать типу, принятому в подпрограмме, но не обязательно точно. Например, если параметр – массив, то размер массива, определенный в подпрограмме, может превышать размер аргумента. Если получается несоответствие типов (аргумент – real, а в подпрограмме – integer), то никаких сообщений об ошибках и никаких исключений генерироваться не будет, но результаты вычислений будут неверными.

2.2  Параметры со значениями по умолчанию

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

<имя параметра>: <тип параметра> = <значение по умолчанию>;

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

<имя процедуры> ();

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

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

2.3  Область видимости и время жизни

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

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

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

Константы, переменные, подпрограммы могут использоваться только в области их видимости, которая зависит от того места, в котором определен элемент. При определении области видимости используется понятие блока. Блок состоит из разделов объявлений и следующего за ними составного оператора.

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

Если во вложенном блоке какой-то идентификатор внешнего блока переопределен (то есть объявлен заново), то во вложенном блоке виден только переопределенный идентификатор (имя, описанное в блоке, экранирует объекты из внешних блоков). Во внешнем блоке видна только внешняя переменная. Имена объектов, описанных в некотором блоке, считаются известными в пределах данного блока, включая и все вложенные блоки.

Имена объектов, описанных в блоке, должны быть уникальны в пределах данного блока.

Использование в другом модуле предложения Uses, включающего модуль, в интерфейсной части которого объявлен некоторый элемент, включает тем самым новую область его видимости уже в другом модуле. Когда в предложении Uses перечисляются несколько модулей, от области видимости определяются так же, как и в случае вложенных блоков. При этом первый из перечисленных модулей аналогичен самому внешнему блоку, а последний – самому внутреннему.

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

2.4  Перегрузка функций

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

2.5  Передача параметров – структурированных данных

Параметры подпрограммы могут иметь любой тип, однако в заголовке подпрограммы нельзя вводить новый тип. Структурированный тип надо заранее объявить в разделе Type. Затем использовать имя объявленного структурированного типа можно использовать в любом месте программы, в том числе и в заголовках подпрограмм. Если структурированный тип не объявлен заранее, то при попытке ввести этот тип в заголовке подпрограммы, за исключением открытых массивов и открытых строк, компилятор выдаст сообщение об ошибке. Кроме того, параметром подпрограммы может быть массив, объявленный как динамический. Для этого в списке формальных параметров массив должен фигурировать как открытый.

2.6  Передача параметров как открытых массивов

Если объявить функцию или процедуру, работающую с массивом следующим образом: procedure P(A: array[0..5] of integer);, то компилятор воспримет это как синтаксическую ошибку. Правильным объявлением будет:

Type

t = array[0..5] of integer;

procedure P(A: t);

Подпрограммы в Object Pascal и Delphi могут воспринимать в качестве параметров не только массивы фиксированного размера, но и так называемые открытые массивы. В этом случае в объявлении он описываются как массивы базовых типов без указания их размерности. Например:

procedure P(A: array of integer; var B: array of integer);

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

Массив, переданный как открытый, воспринимается в теле подпрограммы как массив с целыми индексами, начинающимися с 0. Размер массива может быть определен функциями Length (число элементов) и High (наибольшее значение индекса). Всегда High = Length – 1.

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

S:=Sum([1,2,3.5,5,7.8]);

Хотя в массиве, объявленном как открытый, индексация элементов начинается с 0, в качестве фактических аргументов можно передавать массивы с любой целочисленной индексацией. И в теле подпрограммы лучше использовать операторы вида:

for X:=Low(A) to High(A) do …;

В качестве открытых массивов можно передавать только одномерные массивы.

2.7  Параметры в виде открытых массивов констант

Открытые массивы этого вида разрешают передавать в процедуру или функцию массив различных по типу значений. При передаче такого массива от объявляется как array of const.

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

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

Если в подпрограмму передается массив констант, то в ее теле необходимо производить явное преобразование типов. Пример:

function MakeStr(S: array of const): string;

Var I:Integer;

begin

Result:=’’;

for I:=0 to High(S) do

With S[I] do

case VType of

vtChar: Result:=VChar;

vtBoolean: if VBoolean then Resul:=’T’ else Result:=’F’;

end;

end;

В Delphi 7 вместо array of const можно использовать array of variant. Эти типы являются взаимозаменяемыми.

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

2.8  Передача имен процедур и функций в качестве параметров

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

Var

P: Procedure;

Возможными значениями этой переменной могут быть любые процедуры без параметров.

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

Для процедурных переменных допустимы операторы присваивания, в правых частях которых находятся идентификаторы других процедурных переменных или идентификаторы подпрограмм.

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

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

Процедурные переменные можно использовать в структурированных типах (записях или массивах).

Правила использования подпрограмм в качестве значения процедурной переменной

1.  Они должны компилироваться с ключом компилятора {$F+} или иметь директиву far для получения полного адреса подпрограммы.

2.  Они не должны быть стандартными процедурами или функциями.

3.  Они не должны объявляться внутри других процедур или функций.

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

Описание процедурных и функциональных типов производится в разделе описания типов:

Type

FuncType = function(z: Real): Real;

ProcType = procedure(a, b:Real;var x, y:Real);

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

Type

Proc = procedure;

После объявления процедурного или функционального типа его можно использовать для описания формальных параметров – имен процедур и функций.

Кроме того, необходимо написать те реальные процедуры или функции, имена которых будут передаваться как фактические параметры. Эти процедуры и функции должны компилироваться в режиме дальней адресации с ключом {$F+}.

Пример. Составить программу для вычисления определенного интеграла по методу Симпсона.

Вычисление подынтегральной функции реализовать с помощью функции, имя которой передается как параметр. Значение определенного интеграла по формуле Симпсона вычисляется по формуле:

где a и b – нижняя и верхняя границы интервала интегрирования, , n – число разбиений интервала интегрирования, должно быть четным.

Type

Func= function(x: Real): Real;

Var

I, TN, TK:Real; N:Integer;

{$F+}

function Q(t: Real): Real;

begin

Q:=2*t/Sqrt(1–Sin(2*t));

end;

{$F–}

procedure Simps(F:Func; a, b:Real; N:Integer; var INT:Real);

Var

sum, h: Real; j:Integer;

begin

if Odd(N) then N:=N+1;

h:=(b–a)/N;

sum:=0.5*(F(a)+F(b));

for j:=1 to N–1 do

sum:=sum+(j mod 2+1)*F(a+j*h);

INT:=2*h*sum/3

end;

begin

Write(' Введите начало и конец отрезка и количество разбиений: ');

Read(TN, TK, N);

Simps(Q, TN, TK, N,I);

WriteLn('I=',I:8:3)

end.

2.9  Операторы выхода

Для завершения работы программ, процедур и функций без предварительного перехода по меткам к закрывающему end в языке есть процедуры Exit и Halt.

Вызов Exit завершает работу своего программного блока и передает управление вызывающей программе. Если Exit выполняется в подпрограмме, то выполнение этой подпрограммы прекратится, и далее будет выполняться следующий за вызовом этой подпрограммы оператор. Если Exit выполняется в основной программе, выход из нее будет эквивалентен ее нормальному завершению.

Вызов процедуры Halt, где бы она не находилась, завершает работу программы и передает управление операционной системе. Процедуру Halt можно вызвать следующим образом:

Halt(n);

где n – код возврата, который может быть проанализирован операционной системой с помощью команды IF ERRORLEVEL. Значение n=0 соответствует нормальному завершению работы программы. Вызов процедуры Halt без параметра эквивалентен вызову Halt(0).

2.10 Модули

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

Модуль – это отдельно хранимая и автономно компилируемая программная единица, включающая в себя различные компоненты интерфейсного раздела (типы, константы, переменные, процедуры и функции) и, возможно, некоторые операторы инициализирующего раздела. Объекты, помещенные в интерфейсной части, доступны для других модулей и основной программы. Тела процедур и функций располагаются в исполняемой части модуля, которая может быть скрыта от пользователя.

Итак, модуль (Unit) – это особым образом оформленная библиотека подпрограмм. Модуль, в отличие от программы, не может быть запущен на выполнение самостоятельно, он может только участвовать в построении программ и других модулей.

Все программные элементы модуля можно разбить на две части:

·  элементы, предназначенные для использования другими программами или модулями, такие элементы называют интерфейсными;

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

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

Unit

<имя модуля>; //Заголовок модуля

//описание видимых программных элементов модуля

Interface //Открытый интерфейс модуля

{

Сюда могут помещаться списки подключаемых модулей, объявления типов, констант, переменных, функций и процедур, к которым будет доступ из других модулей

}

// описание скрытых программных элементов модуля

Implementaton // Реализация модуля

{

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

}

Initialization // не обязательный

{

Операторы, выполняемые один раз при первом обращении к модулю (при старте программы)

}

Finalization // не обязательный

{

Операторы, выполняемые при любом завершении программы

}

end.

Раздел Interface представляет собой внешний интерфейс модуля. Поэтому подключаемые в нем модули, объявленные типы, классы, константы, переменные, функции и процедуры доступны внешним модулям, обращающимся к данному модулю.

Раздел Implementaton представляет собой реализацию модуля. Все подключаемые в нем объекты доступны только в пределах данного модуля. Основное тело модуля составляют коды, реализующие ранее объявленные функции и процедуры.

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

Раздел Finalization включает в себя операторы, которые выполняются только один раз при любом завершении программы: нормальном или аварийном. В нем могут помещаться операторы, производящие удаление временных файлов, освобождение ресурсов памяти и т. п. Введение раздела не разрешается, если в модуле нет раздела Initialization.

В частном случае модуль может не содержать части реализации и части инициализации, тогда структура модуля будет такой:

unit

<имя модуля>;

interface

{ описание видимых программных элементов модуля }

implementation

end.

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

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

Основное имя модуля берется из заголовка модуля. Для подключения модуля к программе необходимо указать его имя в разделе описания модулей, например:

uses

CRT, Graph;

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

unit

M;

interface

var

K: Integer;

implementation

.................

end.

Пусть программа, использующая этот модуль, также содержит переменную К:

Program P;

uses

M;

var

K: Char;

begin

.............

end.

Для того, чтобы в программе P иметь доступ к переменной K из модуля M, необходимо задать составное имя M. K.

Использование составных имен применяется не только к именам переменных, а ко всем именам, описанным в интерфейсной части модуля. Рекурсивное использование модулей запрещено.

Если в модуле имеется раздел инициализации, то операторы из этого раздела будут выполнены перед началом выполнения программы, в которой используется этот модуль.

2.11 Подключение модулей

Раздел подключения модулей начинается с uses, после которого следует список модулей, разделяемый запятыми. Например:

Uses Windows, SysUtils;

Предложение uses в головном файле программы может записываться следующим образом:

Uses Unit1 in 'c:\examples\unit1.pas';

В предложениях uses, включаемых в модули, использование in не допускается.

При взаимных ссылках модулей друг на друга не разрешаются циклические ссылки с помощью предложения uses, размещенных в разделах Interface. Такие циклы надо разрывать, перенося одно или все предложения uses из разделов Interface в разделы Implementaton модулей.

Например, недопустимыми циклическими ссылками являются следующие предложения в модулях:

Unit Unit1;
interface
uses Unit2;

…
Implementation

…

end.

Unit Unit2;
interface
uses Unit1;

… Implementation

…

end

Выходом из положения будут следующие варианты:

1.  Unit Unit1;
interface
…
Implementation
uses Unit2;
…
End.

Unit Unit2;
interface
uses Unit1;
…
Implementation
…
End.

2.  Unit Unit1;
interface
…
Implementation
uses Unit2;
…
end.
Unit Unit2;
interface
…
Implementation
uses Unit1;
…
end.

Нередко требуется ввести вручную ссылку на библиотечный модуль, в котором объявлены те или иные процедуры или функции, используемые в приложении. Если вызовы этих процедур содержатся только в разделе Implementation, целесообразно записывать оператор uses в этом же разделе. Но если имена объектов, объявленных в библиотечном модуле, используются в интерфейсе модуля, соответствующий оператор uses должен размещаться в интерфейсе.

3  Структуры данных и алгоритмы их обработки

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

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

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

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

3.2  Указатели

Оперативная память компьютера – это совокупность ячеек для хранения информации. Каждая ячейка памяти (байт) имеет свой адрес. Указатели – это переменные, множество допустимых значений которых содержит адреса ячеек памяти, а также специальное значение (нулевой или пустой адрес), обозначающее, что указатель в данный момент времени нельзя использовать для обращения к памяти.

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

Есть два вида указателей: типизированные и нетипизированные.

Типизированный указатель связывается с определенным типом данных (стандартным или определенным программистом), например:

Var

PPoint = ^TPoint;

Type

TPoint = record

X, Y: Real;

dO: Real;

end;

Такая последовательность объявлений не будет ошибкой, поскольку допускается объявить указатель на тип, который до этого не был описан.

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

Var

P: Pointer;

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

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

Var

PInt1, PInt2:^Integer;

PReal:^Real;

P: Pointer;

begin

// оба указателя связаны с целым типом

PInt2:=PInt1;

// Ошибка, так как указатели связаны с разными типами данных

PReal:=Pint2;

// Можно использовать нетипизированный указатель,

// чтобы указателю на вещественное значение присвоить

// значение указателя на целое значение

P:= Pint2;

PReal:=p;

end;

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

Пример использование этой операции:

Var

PInt:^Integer;

Rl:Real;

I: Integer;

begin

I:=5;

// Чтобы присвоить указателю ссылку

// на конкретную область памяти,

// можно применить операцию взятия адреса переменной

PInt:=@I;

// применение операции @ к переменной возвращает

// указатель на эту переменную.

// После выполнения этого оператора в переменной PInt

// хранится адрес переменной I – то есть Pint указывает

// на переменную I, значение которой равно 5

R:=2*I*Pint^; // 2*5*5 // //

Write(R:7:2);//__50.00

end;

Операция разыменования не применима к указателям типа pointer. Чтобы разыменовать указатель типа pointer, надо сначала привести его к другому типу указателя. Например:

Type

PInteger = ^Integer;

Var

P:Pointer;

Pint:PInteger;

I, J: Integer;

begin

I:=5;

// приведение указателя типа pointer к указателю на целое

// и присваивание указателю P адреса переменной I

PInteger(P):=@I;

// J:=5 + 5;

J:=PInteger(PP)^+I;

Write(J:7);

end;

Указатели широко используются в Object Pascal и Delphi, причем часто неявно для пользователя. Например, передача параметров по ссылке в подпрограммы осуществляется именно через указатели.

3.3  Указатели и динамическая память

Динамическая память рассматривается в Delphi как сплошной массив байтов, который называется кучей. Для работы с динамической памятью есть две группы подпрограмм:

1.  Аргументами процедур New и Dispose могут быть только типизированные указатели. Синтаксис этих процедур:
procedure New(var P: Pointer); procedure Dispose (var P: Pointer);.
Процедура New резервирует память и при успешном завершении помещает в переменную-указатель параметр адрес первого байта выделенной области памяти. Размер выделяемой области определяется размером памяти, необходимым для размещения того типа данных, который указан при объявлении указателя. Освобождение памяти, ранее выделенной процедурой New, осуществляется процедурой Dispose. В эту процедуру должен быть передан указатель, в котором хранится адрес области памяти, выделенной процедурой New. Процедура Dispose освобождает память, но не изменяет значение указателя, не делает его равным nil, хотя он теперь не указывает ни на что конкретное. Поэтому нужно явным образом присваивать указателям значение nil. Например:

Var

P:^real;
…

begin

New(P);

P^:=5.5;

…

Dispose(P);

P:=Nil;

end;

Type

TPoint = record

X, Y,Z:integer;

end;

var

P:^TPoint;

begin

New(P);

with P^ do begin

X:=0;

Y:=0;

Z:=0;

end;

…

Dispose(P);

P:=Nil;

end;

2.  Аргументами процедур GetMem и FreeMem могут быть как и типизированные, и нетипизированные указатели. Эти процедуры имеют следующий синтаксис:

GetMem(var P: Pointer; Size: Integer);

GetMem(var P: Pointer; Size: Integer);

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

Var

P:^real;

…

begin

GetMem(P, SizeOf(Real));

P^:=5.5;

…

FreeMem(P, SizeOf(Real));

P:=Nil;

end;

Type

TPoint = record

X, Y,Z:integer;

end;

Var

P:^TPoint;

begin

GetMem(P, SizeOf(TPoint));

with P^ do begin

X:=0;

Y:=0;

Z:=0;

end;

…

FreeMem(P, SizeOf(TPoint));

P:=Nil;

end;

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

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

Начиная с Delphi 4 можно использовать так называемые динамические массивы. При объявлении динамических массивов их размер не указывается:

Примеры объявлений динамических массивов:

Var

A: array of Real;

B: array of array of Integer;

C: array of array of array of Char;

Массив A имеет одно измерение, массив B – два измерения, массив C – три измерения.

Фактически идентификатор динамического массива ссылается на указатель, содержащий адрес первого байта памяти, выделенной для размещения массива. Распределение памяти и указание границ индексов по каждому измерению динамического массива производится во время выполнения программы. Для этого используется функция SetLength, которая имеет два аргумента – переменная, объявленная как динамический массив, и количество элементов массива. Нижняя граница индексов по любому измерению динамического массива всегда равна нулю. Поэтому верхняя граница индекса по какому-либо измерению будет на единицу меньше длины массива по данному измерению. Пример использования функции SetLength:

Var

a, b : array of Real;

begin

SetLength(a,5);

SetLength(b,15);

//какие-то действия с массивами

//Освобождение памяти, занимаемой динамическими массивами

a:=Nil;

Finalize(b);

end;

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

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

Var

X: array of array of Real;

begin

SetLength(X,4); //задаем количество столбцов – длину строки матрицы

//задаем длину каждого из столбцов

SetLength(X[0],4);

SetLength(X[1],4);

SetLength(X[2],4);

SetLength(X[3],4);

end;

или гораздо короче:

Var

X: array of array of Real;

begin

SetLength(X,4,4);

end;

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

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

Var

X: array of array of Real;

begin

//задаем количество столбцов – длину строки матрицы

SetLength(X,5);

//задаем длину каждого из столбцов

SetLength(X[0],5);

SetLength(X[1],4);

SetLength(X[2],3);

SetLength(X[3],2);

SetLength(X[4],1);

end;

В многомерных динамических массивах каждый элемент любого из измерений – это динамический массив, который нужно инициализировать. И хотя функция SetLength имеет максимум три параметра, можно создавать не только двумерные динамические массивы. Например, кубический массив 5× 5×5 инициализировать можно следующим образом:

var

Y: array of array of array of Real;

I, j:integer;

begin

SetLength(Y,5);

for i:=0 to 4 do begin

SetLength(Y[i],5);

for j:=0 to 4 do

SetLength(Y[I, j],5);

end;

end;

3.5  Списки: основные виды и способы реализации

Структура данных – это своего рода библиотека. Она поддерживает определенный порядок доступа к данным. При описании структуры данных определяется набор действий, которые возможны для нее и четко описывается результат каждого действия. В объектно-ориентированных языках структуре данных соответствует класс. Данные хранятся в свойствах, набор действий реализуется методами класса. Структуру данных легко реализовать и в императивных языках программирования, придерживаясь того же самого принципа – выделить набор функций, с помощью которых можно получить доступ к данным, а сами данные описываются как статические переменные. Следует четко различать описание структуры данных с логической точки зрения и описание ее реализации. Различных реализаций может быть много, но с точки зрения пользователя все они должны быть эквивалентны.

В структурах данных с прямым (произвольным) доступом возможен непосредственный доступ к любому элементу. Примеры структур с произвольным доступом – массивы и множества. В структурах данных с последовательным доступом непосредственный доступ возможен лишь к одному или нескольким элементам, для доступа к остальным элементам надо выполнить дополнительные действия. В свое время для хранения данных использовалась магнитная лента и доступ к данным, хранившимся на магнитной ленте, был только последовательным.

Такие структурированные типы данных, такие, как статические массивы, множества, записи, представляют собой статические структуры - их размеры неизменны в течение всего времени выполнения программы. Массивы позволяют с помощью стандартных приемов управлять большими группами объектов. Однако массивы не обладают достаточной гибкостью. Перераспределение элементов массива может быть сложным и зани­мать много времени. Например, чтобы переместить элемент из одного конца мас­сива в другой, нужно сдвинуть каждый эле­мент на одну позицию, чтобы заполнить оставшуюся от другого элемента ячейку и только потом поместить элемент в его новую позицию.

Динамические структуры данных позволяют быстро совершать такие перемещения, к тому могут легко изменять свой размер в ходе решения задачи. Стеки, очереди, списки, деревья и некоторые другие виды структур называются динамическими. Разные виды списков обладают разными свойствами. В разных списках разные способы связи отдельных элементов и разные наборы допустимых операций. Стеки и очереди, например, просты и функционально ограничены. Циклические и двусвязные списки с указателями поддерживают более развитые средства управления данными.

Список – это упорядоченная последовательность элементов – для каждого элемента можно указать предыдущий и следующий за ним элементы. Исключением могут быть первый и последний элементы списка (в нециклических списках). Принято выделять следующие виды списков:

·  Односвязные линейные списки;

·  Односвязные циклические списки;

·  Двусвязные линейные списки;

·  Двусвязные циклические списки;

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

В линейном списке последний указатель равен nil – он не указывает на какой-либо элемент. В циклическом списке пустого указателя нет - последний узел списка содержит указатель на первый его элемент, поэтому получается замкнутая структура данных. Один из элементов циклического списка условно считают корнем. Каждый элемент двусвязного списка содержит два указателя – один из них указывает на предыдущий элемент, а второй – на следующий элемент. Такие структуры используются реже, чем односвязные.

Рассмотрим пример работы со стеком – одним из частных случаев списка.

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

Наглядный пример стека – стопка книг на столе, из которой нужную книгу можно достать, предварительно сняв все книги, лежащие на ней.

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

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

Кроме локальных переменных, в аппаратном стеке сохраняются адреса возврата при вызовах подпрограмм. Адрес возврата – это адрес оператора, следующего за вызовом подпрограммы. В большинстве процессоров имеются специальные команды, поддерживающие вызов подпрограммы с предварительным помещением адреса возврата в стек и возврат из подпрограммы по адресу, извлекаемому из стека.

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