Динамические структуры данных




1. Статическая и динамическая память.

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

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

Распределение памяти.

Размер динамической памяти можно варьировать в широких пределах. По умолчанию этот размер определяется всей доступной памятью ПК и, как правило, составляет не менее 200 – 300 Кбайт. Таким образом, динамическая память – это фактически единственная возможность обработки массивов данных большой размерности. Существуют и другие задачи, которые трудно или невозможно решить без использования динамической памяти. Например, динамическая память широко используется для временного запоминания данных при работе с графическими средствами ПК.

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

2. Статические и динамические переменные.

Статическая переменная:

а) описывается в основной программе, модуле или подпрограмме явно (в разделе Var) и обозначается своим именем;

б) существует в течение всего времени выполнения программы или подпрограммы, в которой она описана;

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

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

Динамическая переменная:

а) не указывается явно в описаниях переменных (в разделе Var) и не имеет имени;

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

в) хранится в динамической памяти.

3. Тип – указатель.

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

а) в разделе описания типов

Type

< имя_ссылочного_типа> = ^ < тип данных >;

Var

< имя_переменной >: < имя_ссылочного типа >;

Пример 1.

Type

T = ^ Integer; {объявление ссылочного типа}

Var

A: T; {указатель А ссылается на динамическую переменную целого типа}

б) явно в разделе описания переменных

Var

< имя_переменной >: ^ < тип данных >;

Пример 2.

Var

B: ^ Real; {указатель В ссылается на динамическую переменную вещественного типа}

< Тип данных > является базовым типом. В качестве базового типа может использоваться любой стандартный тип данных языка Pascal (включая структурированные типы данных и тип-указатель) либо тип данных, определенный пользователем в разделе Type. В примере 1 для ссылочного типа Т базовым является тип Integer. Для переменной-указателя А тип задан через идентификатор, описанный в разделе описания типов, в примере 2 для переменной-указателя В – в явном виде.

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

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

4. Доступ к переменной по указателю.

Доступ к переменной по указателю называется косвенным доступом к переменной.

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

Например, чтобы увеличить значение переменной, на которую указывает указатель Р, можно записать:

P^:= P^ + 2; {доступ к переменной по указателю Р}

Пример 3.

Type

T = ^ Integer; {объявление ссылочного типа}

Var

A: T; {указатель А ссылается на динамическую переменную целого типа}

Y: Integer; {переменная целого типа}

B: ^ Real; {указатель В ссылается на динамическую переменную вещественного типа }

Begin

Y:=5;

New(A);

A^:=5;

New(B);

B^:=6.78;

End.

В примере 3 переменная Y – это статическая переменная целого типа, которая явным образом объявлена в разделе Var, имеет собственное уникальное имя, память под эту переменную выделяется при запуске программы и освобождается по окончании выполнения программы. Запись Y:=5; означает, что в переменную Y записывается значение «5».

Указатель А ссылается на динамическую переменную целого типа. При этом в переменной-указателе А содержится адрес переменной целого типа. Чтобы создать эту переменную в динамической памяти используется процедура New(A), которая выделяет память под целочисленную переменную, а в А помещает адрес этой переменной в динамической памяти. Таким образом, значение «5» в примере записывается в память по адресу, который содержится в переменной А. Аналогично, переменная В является указателем на вещественную переменную. С помощью процедуры New(B) выделяется память под вещественную переменную, а в указатель В записывается адрес этой переменной в динамической памяти. Запись B^:=6.78; означает, что значение «6.78» записывается в динамическую память по адресу, хранящемуся в переменной В.

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

5. Управление динамической памятью (процедуры New и Dispose ).

Для выделения динамической памяти под динамическую переменную используется процедура New. После ее выполнения в куче выделяется память, равная размеру динамических переменных и указатели приобретают значения адресов динамических переменных. Например, после выполнения оператора New(A) (см. пример 3) в куче будет выделено 2 байта (под переменную типа Integer), а указатель А приобретет значение адреса выделенных в куче двух байтов. За одно обращение к куче процедурой New можно зарезервировать до 65521 байта динамической памяти.

Динамическую память можно не только занимать в куче, но и возвращать ее обратно. Для этого используется процедура Dispose. Например, операторы Dispose(A) и Dispose(B) вернут в кучу столько байт, сколько было выделено динамическим переменным A^ и B^, которые связаны с указателями А и В (см. пример 3).

Следует отметить, что оператор Dispose(<указатель>) не изменяет значение <указателя>, а лишь возвращает в кучу память, ранее связанную с этим указателем. Однако повторное применение процедуры к «свободному » (не связанному с определенным адресом динамической памяти) указателю приведет к возникновению ошибки периода выполнения. Чтобы пометить свободный указатель, программист может использовать зарезервированное слово Nil.

Nil означает специальный указатель, который «никуда не указывает». Можно представить такую ситуацию: в адресном пространстве оперативной памяти компьютера выделяется один адрес, по которому заведомо не может быть размещена ни одна переменная. На это место памяти и ссылается такой нулевой (пустой) указатель, который обозначается словом Nil. Указатель Nil считается константой, совместимой с любым ссылочным типом, поэтому его значение можно присваивать любому указателю. Обычно значение Nil присваивают указателю, когда указание надо отменить или в начале инициализации программы. Это позволяет проверять значение указателя, прежде чем присваивать ему какое-либо значение.

Примечание ( !!! ). Начальное значение указателя (при его объявлении в разделе описания переменных) может быть произвольным. Использование указателей, которым не присвоено значение процедурой New или каким-либо другим способом, никак не контролируется системой и может привести к непредсказуемым результатам.

К указателям можно применять операции отношения, в том числе и сравнение с Nil.

Пример.

Var

P: ^ Real; {объявление указателя на веществ. переменную}

Begin

P:=Nil; {присваивание Р значения «свободный указатель»}

If P = Nil {если Р – «свободный указатель»}

Then New(P); {то выделить из кучи память под веществ. переменную Р^}

Dispose(P); {вернуть в кучу память, выделенную под веществ. перем. Р^}

P:=Nil; {присваивание Р значения «свободный указатель»}

Задача

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



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-08-20 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: