Динамические структуры данных: списки
Динамические структуры данных: списки
Введение
В
языках программирования (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 > 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 Next=First;
First=Vsp;
return First;
}
Zveno
*Iz_Nachala(Zveno *First)
{ Zveno *Vsp;
Vsp=First->Next;
free(First);
return Vsp;
}
Zveno *V_Spisok(Zveno
*Pred, BT X)
{ Zveno *Vsp;
Vsp = (Zveno *) malloc(sizeof(Zveno));
Vsp->Inf=X;
Vsp->Next=Pred->Next;
Pred->Next=Vsp;
return Vsp;
}
BT Iz_Spiska(Zveno
*Pred)
{ BT X;
Zveno *Vsp;
Vsp=Pred->Next;
Pred->Next=Pred->Next->Next;
X=Vsp->Inf;
free(Vsp);
return X;
}
void Print(Zveno
*First)
{ Zveno *Vsp;
Vsp=First;
while (Vsp)
{cout Inf Next;}
cout 0
Then If S2 = Nil
Then Begin V_Nachalo(S2, V1^.Inf);
V2 := S2 End
Else Begin V_Spisok(V2, V1^.Inf);
V2 := V2^.Next End;
If V1^.Inf < 0
Then If S3 = Nil
Then Begin V_Nachalo(s3, V1^.Inf);
V3 := S3 End
Else Begin V_Spisok(V3, V1^.Inf);
V3 := V3^.Next End;
V1:= V1^.Next
End;
WriteLn('Результирующий список из
положительных элементов: '); Print(S2);
WriteLn('Результирующий список из
отрицательных элементов: '); Print(S3);
Ochistka(S1); Ochistka(S2); Ochistka(S3);
End.
// Программа на C++
#include "SPIS.CPP"
void main()
{Zveno *S1, *S2, *S3, *V1, *V2, *V3;
BT a; int i, n;
clrscr();
randomize();
S1=NULL;
//
создаём первый элемент
a=-100+random(201);
S1=V_Nachalo(S1, a);
n=1+random(20);
//
формируем список произвольной длины и выводим на печать
V1=S1;
for (i=2; iInf > 0)
if (!S2)
{S2=V_Nachalo(S2, V1->Inf); V2 = S2;}
else {V_Spisok(V2, V1->Inf); V2 = V2->Next;};
if (V1->Inf < 0)
if (!S3)
{S3=V_Nachalo(S3, V1->Inf); V3 = S3;}
else {V_Spisok(V3, V1->Inf); V3 = V3->Next;};
V1= V1->Next;}
cout
|
