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

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), а указатель А приобретет значение адреса выделенных в куче 2-ух байтов. За одно воззвание к куче процедурой 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; {присваивание Р значения «свободный указатель»}

Задачка

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


diffuznij-toksicheskij-zob-b-n-grejvsa-bazedova-b-n-etiologiya-patogenez-klinika-laboratornie-i-instrumentalnie-issledovaniya-lechenie.html
diffuznoe-aksonalnoe-povrezhdenie-klinika-diagnostika-lechenie.html
difrakcionnaya-reshyotka-prohodyashego-sveta.html