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

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

Введение

В языках программирования (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 килобайта памяти (или, если быть точнее, 65 520 байт). Это и есть статическая область памяти. При необходимости работать с большими массивами информации этого может оказаться мало. Размер динамической памяти — много больше (сотни килобайт). Поэтому использование динамической памяти позволяет существенно увеличить объем обрабатываемой информации.

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

Пример. Дан текстовый файл размером не более 64 Кб, содержащий действительные числа, по одному в каждой строке. Переписать содержимое файла в массив, разместив его в динамически распределяемой памяти. Вычислить среднее значение элементов массива. Очистить динамическую память. Создать целый массив размером 10 000, заполнить его случайными целыми числами в диапазоне от -100 до 100 и вычислить его среднее значение.

{Язык Turbo Pascal}.

Program Srednee;

Const NMax = 10 000;

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 10 000.

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.