Динамічні
структури даних: списки
Вступ
У попередніх
оглядах ми розглядали програмування, пов'язане з обробкою тільки статичних даних. Статичними
величинами називаються такі, пам'ять під які виділяється під
час компіляції і зберігається протягом всієї роботи програми.
У мовах
програмування (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
<< "Введіть ім'я файлу:"; 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среднее ціле одно" <
cout << "середнє речовий
одно: "<
fclose (t);
)
Списки
Давай обговоримо це питання
про те, як у динамічній пам'яті можна створити структуру даних змінного
розміру.
Розберемо
Наведемо приклад. У процесі фізичного експерименту часто знімаються
показання приладу (припустимо, термометра) і записуються в комп'ютерну пам'ять
для подальшої обробки. Наперед невідомо, скільки буде вироблено
вимірювань.
Якщо для
обробки таких даних не використовувати зовнішню пам'ять (файли), то розумно
розташувати їх у динамічній пам'яті. По-перше, динамічна пам'ять дозволяє
зберігати більший обсяг інформації, ніж статична. А по-друге, у динамічній
пам'яті ці числа можна організувати в зв'язаний список, який не вимагає
попереднього зазначення кількості чисел, подібно до масиву. Що ж таке
"зв'язаний список"? Схематично він виглядає так:
Тут Inf --
інформаційна частина ланки списку (величина будь-якого простого або
структурованого типу, крім файлового), Next - покажчик на наступну ланку
списку; First - покажчик на головній ланка списку.
Згідно
визначенням, список розташовується в динамічно пам'яті, в
статичної пам'яті зберігається лише вказівник на головній ланка. Структура, в
відміну від масиву, є дійсно динамічної: ланки створюються і
видаляються в міру необхідності, в процесі виконання програми.
Для оголошення
списку зроблено виняток: вказівник на ланка списку оголошується раніше, ніж
саме ланка. У загальному вигляді оголошення виглядає так.
Type U = ^ Zveno;
Zveno
= Record Inf: BT; Next: U End;
Тут BT --
деякий базовий тип елементів списку.
Якщо покажчик
посилається лише на наступну ланку списку (як показано на малюнку і в
оголошеної вище структурі), то такий список називають односпрямованим, якщо
на наступне та попереднє ланки - двонаправленим списком. Якщо вказівник в останньому
ланці встановлений не в Nil, а посилається на головній ланка списку, то такий
список називається кільцевих.
Кільцевими можуть бути і односпрямовані, і двонаправлені списки.
Більш докладно
розглянемо роботу зі зв'язаними списками на прикладі однонаправленої
некольцевого списку.
Виділимо типові
операції над списками:
додавання
ланки в початок списку;
видалення ланки
з початку списку;
додавання
ланки в довільне місце списку, відмінне від початку (наприклад, після ланки,
вказівник на яке задано);
видалення ланки
з довільного місця списку, відмінного від початку (наприклад, після ланки,
вказівник на яке задано);
перевірка, порожній
Чи список;
очищення списку;
друк списку.
Реалізуємо
виділений набір операцій у вигляді модуля. Підключивши цей модуль, можна вирішити
більшість типових завдань на обробку списку. Нехай список оголошений так, як
було описано вище. Перші чотири дії спочатку реалізуємо окремо, додавши до них
ілюстраціями.
1. Додавання
ланки в початок списку
(Процедура долучення ланки в початок
списку; в x міститься додається інформація)
Procedure
V_Nachalo (Var First: U; X: BT);
Var Vsp: U;
Begin
New (Vsp);
Vsp ^. Inf: = X;
Vsp ^. Next
: = First; (Те ланка, що було заголовним, стає другим за рахунком)
First: = Vsp; (Нове ланка
стає заголовним)
End;
2. Видалення
ланки з початку списку
(Процедура видалення ланки з початку
списку;
в x міститься інформація з
віддаленого ланки)
Procedure
Iz_Nachala (Var First: U; Var X: BT);
Var Vsp: U;
Begin
Vsp: = First; (Забираємо
посилання на поточне заголовної ланка)
First: = First ^. Next; (Те
ланка, що було другим за рахунком, стає заголовним)
X: = Vsp ^. Inf; (Забираємо інформацію з видаляємого
ланки)
Dispose (Vsp); (Знищуємо
ланка)
End;
3. Додавання
ланки в довільне місце списку, відмінне від початку (після ланки, покажчик
на яке задано)
(Процедура долучення ланки до списку
після ланки,
на яке посилається вказівник Pred;
в x міститься інформація для
додати)
Procedure
V_Spisok (Pred: U; X: BT);
Var Vsp: U;
Begin
New (Vsp); (Створюємо пусте ланка)
Vsp ^. Inf
: = X; (заносить інформацію)
Vsp ^. Next: = Pred ^. Next; (Тепер
ця ланка посилається на те,
що
було слідом за ланкою Pred)
Pred ^. Next: = Vsp; (Тепер нове
ланка встало слідом за ланкою Pred)
End;
4. Видалення
ланки з довільного місця списку, відмінного від початку (після ланки,
вказівник на яке задано)
(Процедура видалення ланки зі списку
після ланки,
на яке посилається вказівник Pred;
в x міститься інформація з
віддаленого ланки)
Procedure
Iz_Spiska (Pred: U; Var X: BT);
Var Vsp: U;
Begin
Vsp: = Pred ^. Next; (Забираємо посилання на видалити ланка)
(Видаляємо
ланка зі списку, перенаправивши посилання на наступне
за ним ланка)
Pred ^. Next: =
Pred ^. Next ^. Next;
X
: = Vsp ^. Inf; (Забираємо інформацію з видаляємого ланки)
Dispose (Vsp); (Знищуємо ланка)
End;
Наведемо повний
текст модуля.
(Мова Pascal)
Unit Spisok;
Interface
Type BT = LongInt;
U = ^ Zveno;
Zveno = Record Inf: BT; Next: U End;
Procedure V_Nachalo (Var First: U; X: BT);
Procedure Iz_Nachala (Var First: U; Var X: BT);
Procedure V_Spisok (Pred: U; X: BT);
Procedure Iz_Spiska (Pred: U; Var X: BT);
Procedure Ochistka (Var First: U);
Function Pust (First: U):
Boolean;
Procedure Print (First: U);
Implementation
Procedure V_Nachalo;
Var Vsp: U;
Begin
New (Vsp);
Vsp ^. Inf: = X;
Vsp ^. Next: = First;
First: = Vsp;
End;
Procedure Iz_Nachala;
Var Vsp: U;
Begin
Vsp: = First;
First: = First ^. Next;
X: = Vsp ^. Inf;
Dispose (Vsp);
End;
Procedure V_Spisok;
Var Vsp: U;
Begin
New (Vsp);
Vsp ^. Inf: = X;
Vsp ^. Next: = Pred ^. Next;
Pred ^. Next: = Vsp;
End;
Procedure Iz_Spiska;
Var Vsp: U;
Begin
Vsp: = Pred ^. Next;
Pred ^. Next: = Pred ^. Next ^. Next;
X: = Vsp ^. Inf;
Dispose (Vsp);
End;
Procedure Ochistka;
Var Vsp: BT;
Begin
While Not Pust (First) Do Iz_Nachala (First, Vsp)
End;
Function Pust;
Begin
Pust: = First = Nil
End;
Procedure Print;
Var Vsp: U;
Begin
Vsp: = First;
While Vsp <> Nil Do
Begin
Write (Vsp ^. Inf: 6);
Vsp: = Vsp ^. Next
End; WriteLn
End;
Begin
End.
// Мова С + +
# include
# include
# include
# include
typedef
long BT;
struct Zveno (
BT Inf;
Zveno * Next;);
Zveno * V_Nachalo (Zveno * First, BT X)
(Zveno
* Vsp;
Vsp = (Zveno *) malloc (sizeof (Zveno ));
Vsp-> Inf = X; Vsp-> 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 << '';
Vsp = Vsp-> Next;)
cout
<< "n";
)
int Pust (Zveno * First)
(
return
! First;
)
Zveno * Ochistka (Zveno * First)
(
while (! Pust (First)) First = Iz_Nachala (First);
return First;
)
Приклад.
Скласти програму, яка на основі визначеного списку формує два інших,
розміщуючи в першому з них позитивні, а в другій - негативні елементи
вихідного списку.
При реалізації
алгоритму будемо використовувати підпрограми розробленого модуля. Це
істотно полегшує вирішення завдання.
(Програма на
Turbo Pascal)
Program Ex_sp_1;
Uses Spisok;
Var S1, S2, S3, V1, V2, V3: U; A: BT; I, N: Byte;
Begin
Randomize;
N: = 1 +
Random (20);
S1: = Nil;
A: = -100 + Random (201);
V_Nachalo (S1, A); V1: = S1;
For I: = 2
To N Do
Begin A: =
-100 + Random (201); V_Spisok (V1, A); V1: = V1 ^. Next End;
WriteLn ( 'Простий список:'); Print (S1);
V1: =
s1; S2: = Nil; S3: = Nil;
While V1
<> Nil Do
Begin
If
V1 ^. Inf> 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;
i <= n; i ++)
(
a =- 100 + random (201);
V1 = V_Spisok (V1, a);
)
Print (S1);
V1 = S1; S2 = NULL; S3 = NULL;
while (V1)
(if
(V1-> Inf> 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 << "результуючий список
з позитивних елементів: n ";
Print (S2);
cout << "результуючий список з
негативних елементів: n ";
Print (S3);
S1 = Ochistka (S1); S2 = Ochistka (S2); S3 = Ochistka (S3);
)
Контрольні
питання і завдання
Чим відрізняються
статичні і динамічні величини?
Яка пам'ять
називається динамічно розподіляє?
Що таке
покажчик?
Які види
покажчиків вам відомі?
Як
визначається адреса змінної?
Наведіть
приклади оголошення покажчиків.
Як виділити
пам'ять під динамічну змінну? Як звільнити пам'ять від динамічної
змінної?
Що таке
"разименованіе"?
Що в мові
Pascal позначає константа Nil (в мові C константа NULL)?
У якому випадку
можливо присвоювання покажчиків?
Які ситуації
призводять до виникнення у динамічно розподіляє пам'яті
"сміття"?
Що розуміють
під "пов'язаним списком"?
Як
класифікують зв'язані списки?
Які основні
дії над списками і компонентами списків зазвичай реалізують?
Як описується
список?
Двонаправлений
список оголошений таким чином:
Type BT = Byte;
U = ^ Zveno;
Zveno = Record Inf: BT; Pred, Next: U End;
Тут Pred,
Next - відповідно покажчики на попереднє і наступне ланки списку.
Розробити основні підпрограми для обслуговування такого списку.
Список
літератури
Для підготовки
даної роботи були використані матеріали з сайту http://www.comp-science.narod.ru/
