Динамические структуры данных: списки (стр. 1 из 2)
Введение
В предыдущих обзорах мы рассматривали программирование, связанное с обработкой только статических данных. Статическими величинами называются такие, память под которые выделяется во время компиляции и сохраняется в течение всей работы программы.
В языках программирования (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.
Дальнейшая работа с динамическими переменными происходит точно так же, как со статическими переменными соответствующих типов. Им можно присваивать значения, их можно использовать в качестве операндов в выражениях, параметров подпрограмм и пр. Например, если переменной P1^ нужно присвоить число 25, переменной P2^ присвоить значение символа "Write", а массив Pm^ заполнить по порядку целыми числами от 1 до 100, то это делается так:
P1^ := 25;
P2^ := 'Write';
For I := 1 To 100 Do Pm^[I] := I;
Кроме процедуры 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 байт). Это и есть статическая область памяти. При необходимости работать с большими массивами информации этого может оказаться мало. Размер динамической памяти — много больше (сотни килобайт). Поэтому использование динамической памяти позволяет существенно увеличить объем обрабатываемой информации.
Следует отчетливо понимать, что работа с динамическими данными замедляет выполнение программы, поскольку доступ к величине происходит в два шага: сначала ищется указатель, затем по нему — величина. Как это часто бывает, действует "закон сохранения неприятностей": выигрыш в памяти компенсируется проигрышем во времени.
Пример. Дан текстовый файл размером не более 64 Кб, содержащий действительные числа, по одному в каждой строке. Переписать содержимое файла в массив, разместив его в динамически распределяемой памяти. Вычислить среднее значение элементов массива. Очистить динамическую память. Создать целый массив размером 10000, заполнить его случайными целыми числами в диапазоне от –100 до 100 и вычислить его среднее значение.
{Язык Turbo Pascal}
Program Srednee;
Const NMax = 10000;
Type Diapazon = 1..NMax;
MasInt = Array[Diapazon] Of Integer;
MasReal = Array[Diapazon] Of Real;
Var PIint : ^MasInt; PReal : ^MasReal;
I, Midint : longInt; MidReal : Real; T : Text; S : string;
Begin
Write('Введитеимяфайла: '); ReadLn(S);
Assign(T, S); Reset(T); MidReal := 0; MidInt := 0;
Randomize;
NEW(PReal); {Выделение памяти под вещественный массив}
{Ввод и суммирование вещественного массива}
While Not Eof (T) Do
Begin ReadLn(T, PReal^[I]); MidReal := MidReal + PReal^[I] End;
DISPOSE(PReal); {Удаление вещественного массива}
NEW(PInt); {Выделение памяти под целый массив}
{Вычисление и суммирование целого массива}
For I := 1 To NMax Do
Begin PInt^[I] := -100 + Random(201); MidInt := MidInt + PInt^[I] End;
{Вывод средних значений}
WriteLn('среднее целое равно: ', MidInt Div NMax);
WriteLn('среднее вещественное равно: ', (MidReal / NMax) : 10 : 6)
End.
// Язык C++
#include < stdio.h >
#include < time.h >
#include < stdlib.h >
#include < iostream.h >
#define NMax 10000
typedef int MasInt;
typedef float MasReal;
MasInt *PInt; MasReal *PReal;
int I, n, MidInt; float MidReal; char S[255];
FILE *t; char *endptr;
void main()
{ cout << "Введитеимяфайла: "; cin >> S;
t=fopen(S, "r");
MidReal = 0; MidInt = 0;
randomize(); I=0;
/*Выделение памяти под вещественный массив*/
PReal = (MasReal*) malloc (sizeof(MasReal));
/*Ввод и суммирование вещественного массива*/
while (!feof(t))
{fgets(S, 255, t); // вводим из файла строку
PReal[I] = strtod(S, &endptr); // преобразуем введенную строку в вещественное число
MidReal += PReal[I]; I++;}
n=I+1;
free (PReal); /*Удаление вещественного массива*/
PInt = (MasInt*) malloc(sizeof(MasInt)); /*Выделение памяти под целый массив*/
/* Вычисление и суммирование целого массива */
for (I=0; I < NMax; I++)
{ PInt[I] = -100 + random(201);
MidInt += PInt[I];}
/*Вывод средних значений*/
cout << "\nсреднеецелоеравно " << MidInt / double(NMax) << "\n";
cout << "среднее вещественное равно: " << MidReal / n << "\n";
fclose(t);
}
Списки
Обсудим вопрос о том, как в динамической памяти можно создать структуру данных переменного размера.
Разберем следующий пример. В процессе физического эксперимента многократно снимаются показания прибора (допустим, термометра) и записываются в компьютерную память для дальнейшей обработки. Заранее неизвестно, сколько будет произведено измерений.
Если для обработки таких данных не использовать внешнюю память (файлы), то разумно расположить их в динамической памяти. Во-первых, динамическая память позволяет хранить больший объем информации, чем статическая. А во-вторых, в динамической памяти эти числа можно организовать в связанный список, который не требует предварительного указания количества чисел, подобно массиву. Что же такое "связанный список"? Схематически он выглядит так:
