Динамічні
структури даних: списки
Вступ
У попередніх
оглядах ми розглядали програмування, пов'язане з обробкою тільки статичних даних. Статичними
величинами називаються такі, пам'ять під які виділяється під
час компіляції і зберігається протягом всієї роботи програми.
У мовах
програмування (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
# 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 <
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
