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

Введение

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

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

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

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

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

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

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

Величина ссылочного типа (указатель) описывается в разделе описания переменных следующим образом:

               Var : ^;

Вот примеры описания указателей:

   Type Mas1 = Array[1..100] Of Integer;

   Var      P1 : ^Integer;

               P2 : ^String;

               Pm : ^Mas1;

Здесь P1 — указатель на динамическую величину целого типа; P2 — указатель на динамическую величину строкового типа; Pm — указатель на динамический массив, тип которого задан в разделе Type.

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

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

               NEW();

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

               := ^

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

               NEW(P1); NEW(P2); NEW(Pm);

После их выполнения в динамической памяти оказывается выделенным место под три величины (две скалярные и один массив), которые имеют идентификаторы:

   P1^, P2^, Pm^

Например, обозначение P1^ можно расшифровать так: динамическая переменная, на которую ссылается указатель P1.

Рекомендуем скачать другие рефераты по теме: решебник по химии, реферат методы.





1  2  3  4  5  6  7  8 | Следующая страница реферата