Динамічні структури даних: списки
Вступ
В
мовах програмування (Pascal, C, ін) існує й інший спосіб виділення
пам'яті під дані, який називається динамічним. У цьому випадку пам'ять під
величини відводиться під час виконання програми. Такі величини будемо називати
динамічними. Розділ оперативної пам'яті, розподіляється статичний, називається
статичної пам'яттю; динамічно розподілена розділ пам'яті називається
динамічною пам'яттю (динамічно розподіленою пам'яттю).
Використання
динамічних величин надає програмісту ряд додаткових
можливостей. По-перше, підключення динамічної пам'яті дозволяє збільшити
обсяг оброблюваних даних. По-друге, якщо потреба в якихось даних
відпала до закінчення програми, то зайняту ними пам'ять можна звільнити для
іншої інформації. По-третє, використання динамічної пам'яті дозволяє
створювати структури даних змінного розміру.
Робота
з динамічними величинами пов'язана з використанням ще одного типу даних --
посилального типу. Величини, що мають контрольний тип, називають покажчиками.
Покажчик
містить адресу поля в динамічній пам'яті, що зберігає величину певного
типу. Сам покажчик розташовується в статичної пам'яті.
Адреса
величини - це номер першого байта поля пам'яті, в якому розташовується
величина. Розмір поля однозначно визначається типом.
Далі
будемо більш докладно обговорювати покажчики і дії з ними в мові Pascal,
приклади будемо приводити на Pascal та C.
Величина
посилального типу (покажчик) описується в розділі опису змінних наступним
так:
Var: ^;
Ось
приклади опису покажчиків:
Type Mas1 = Array [1 .. 100] Of
Integer;
Var
P1: ^ Integer;
P2: ^ String;
Pm: ^ Mas1;
Тут
P1 - покажчик на динамічну величину цілого типу; P2 - покажчик на
динамічну величину строкового типу; Pm - покажчик на динамічний масив,
тип якого задано у роздiлi 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
# include
# include
# include
# 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
(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
