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

В языках программирования (Pascal, C, др.) существует и другой способ выделения памяти под данные, который называется динамическим. В этом случае память под величины отводится во время выполнения программы. Такие величины будем называть динамическими. Раздел оперативной памяти, распределяемый статически, называется статической памятью; динамически распределяемый раздел памяти называется динамической памятью (динамически распределяемой памятью).

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

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

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

Адрес величины — это номер первого байта поля памяти, в котором располагается величина. Размер поля однозначно определяется типом.

Далее будем более подробно обсуждать указатели и действия с ними в языке Pascal, примеры будем приводить на Pascal и C.

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

Каким же образом происходит выделение памяти под динамическую величину? Память под динамическую величину, связанную с указателем, выделяется в результате выполнения стандартной процедуры NEW. Формат обращения к этой процедуре:

NEW(<указатель>);

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

<имя динамической величины>:= <указатель>^

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

Кроме процедуры NEW значение указателя может определяться оператором присваивания:

<указатель>:= <ссылочное выражение>;

В качестве ссылочного выражения можно использовать

указатель;

ссылочную функцию (т.е. функцию, значением которой является указатель);

константу Nil.

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

До присваивания значения ссылочной переменной (с помощью оператора присваивания или процедуры NEW) она является неопределенной.

Ввод и вывод указателей не допускается.

Рассмотрим пример. Пусть в программе описаны следующие указатели:

Var D, P: ^Integer;

K: ^Boolean;

Тогда допустимыми являются операторы присваивания

D:= P; K:= Nil;

поскольку соблюдается принцип соответствия типов. Оператор K:= D ошибочен, т.к. базовые типы у правой и левой части разные.

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

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

NEW(D); NEW(P);

{Выделено место в динамической памяти под две целые переменные. Указатели получили соответствующие значения}

D^:= 3; P^:= 5;

{Динамическим переменным присвоены значения}

P:= D;

{Указатели P и D стали ссылаться на одну и ту же величину, равную 3}

WriteLn(P^, D^); {Дважды напечатается число 3}

Таким образом, динамическая величина, равная 5, потеряла свой указатель и стала недоступной. Однако место в памяти она занимает. Это и есть пример возникновения "мусора". На схеме показано, что произошло в результате выполнения оператора P:= D.

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

DISPOSE(<указатель>);

Например, если динамическая переменная P^ больше не нужна, то оператор

DISPOSE(P)

удалит ее из памяти. После этого значение указателя P становится неопределенным. Особенно существенным становится эффект экономии памяти при удалении больших массивов.

В версиях Турбо-Паскаля, работающих под операционной системой MS DOS, под данные одной программы выделяется 64 килобайта памяти (или, если быть точнее, 65520 байт). Это и есть статическая область памяти. При необходимости работать с большими массивами информации этого может оказаться мало. Размер динамической памяти — много больше (сотни килобайт). Поэтому использование динамической памяти позволяет существенно увеличить объем обрабатываемой информации.

Следует отчетливо понимать, что работа с динамическими данными замедляет выполнение программы, поскольку доступ к величине происходит в два шага: сначала ищется указатель, затем по нему — величина. Как это часто бывает, действует "закон сохранения неприятностей": выигрыш в памяти компенсируется проигрышем во времени.

Не нашли, что искали? Воспользуйтесь поиском: