Динамічні структури даних: списки
Вступ
В
мовах програмування (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 << "Введіть
назва файлу: "; 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
(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 <
iostream.h>
# include
# include <
stdlib.h>
# 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);
)
Список літератури
Для
підготовки даної роботи були використані матеріали з сайту http://comp-science.narod.ru
