на вершину
Рис. 13.8. Граф – динамічна структура загального вигляду.
Граф утворюють декілька записів, покажчики яких виставлені довільним чином. У програмуванні використовуються і інші типи динамічних інформаційних структур (двозв’язні списки, кільця, і т.д.).
Ще раз відмітимо, що використання посилань частіше всього – чисто технічний прийом. Пам’ять для розміщення змінної може виділятись автоматично при виклику процедури і звільнятись при виході з неї. Однак явне використання посилань дозволяє використовувати при програмуванні більш різноманітні структури. Тому у сучасних мовах програмування (зокрема, в Паскалі) введені засоби, що маніпулюють як даними, так і посиланнями на них.
13.2. Посилальний тип даних. Посилання
Значеннями посилального типу даних є посилання (покажчики) на інші дані. Посилальні типи описуються у розділі типів наступним чином:
Type <ім’я посилального типу > = ^ <ім’я базового типу >
Ім’я змінної може бути зв’язано з описанням її типу безпосередньо в розділі змінних, або з іменем типу, вже описаного в розділі типів. Стиль мови віддає перевагу явному використанню імен типів.
Приклади описань:
1. Type
Vector = Array[1..100] of Integer;
Place = ^ Vector;
Var
a, b: Place;
або
Var
a, b: ^ Array[1..100] of Integer;
2. Type
Item = Record
Name: String[20];
Age: Integer
end;
Point = ^ Item;
Var
x, y: Point;
Якщо p – покажчик на змінну типу Т, то p^ – позначення самої цієї змінної. Ця система позначень може бути продемонстрована так:
змінна типу ^T змінна типу T
Рис. 13.9. Покажчики на змінні та змінні.
Ще раз укажемо на те, що при описанні посилальної змінної p пам’ять резервується тільки для неї. Значенням p по суті є початкова адреса розміщення p^ у пам’яті.
Для резервування пам’яті під дане типу Т^у мові використовується процедура New.
New (< змінна посилального типу >)
Виконання процедури New(p) полягає у заповненні комірки пам’яті, відведеної під змінну p початковою адресою ділянки пам’яті, в якій буде розміщено значення p^. Розмір цієї ділянки визначається типом змінної p.
Для звільнення пам’яті, відведеної раніш під T^, використовується процедура Dispose.
Dispose(<змінна посилального типу>)
Приклад 13.3.
Program ExamNewDis;
Type
Vector = Array[1..100] of Integer;
Place = ^Vector;
Item = Record
Name: String[20];
Age: Integer
end;
Point = ^Item;
Var
a, b: Place;
x, y: Point;
i: Integer;
Begin
New(x);
New(y);
Read(x^.Name);
Read(x^.Age);
y^ := x^;
Dispose(x);
New(a);
For I:= 1 to 100 do a^[i] := Sqr(i)+1;
b := a;
Dispose(a);
End.
Тут при зверненні до процедури New(x) буде відведено 22 байта під x^, при виконанні New(y) - 22 байта під y^, а при виконанні New(a) - 200 байт під a^. (Ми вважаємо, що під ціле число відводиться 2 байта). Оператор y^ := x^ пересилає дані з запису x^ у запис y^. Пам’ять, яку займає x^, звільняється оператором Dispose(x). Для переводу покажчика з одного даного на інше використовується оператор присвоювання. Нехай, наприклад, p і q - змінні одного посилального типу і має місце ситуація
P
Q
Тоді після виконання оператора p := q схема зміниться:
P
Q
Рис. 13.10. Виконання оператора присвоювання з покажчиками.
Зверніть увагу на те, що дані, на які до присвоювання посилалась p, стають недоступними! У прикладі, що розглядається, посилання b встановлено оператором b := a на масив a^. Тому оператор Dispose(a), звільняючи пам’ять, позбавить захисту не тільки масив a^, але й масив b^! Тому наступний оператор New може розмістити дані на місці масиву b.
На прикладах з інформаційними динамічними структурами ми бачили, що деякі поля посилальних типів можуть бути не заповнені посиланнями на інші записи, причому програміст повинен явним чином це вказувати. Для цього використовується стандартне ім’я Nil. (Після виконання операторів p := Nil; q := Nil покажчики p і q вказують на одне й те ж дане – у нікуди!)
13.3. Програмування динамічних структур даних
Найпростіші характерні прийоми обробки динамічних структур даних розглянемо на наступному прикладі:
Приклад 13.4.
а) Побудувати динамічну структуру даних, що зображена на рисунку 13.11:
First
Рис. 13.11.
(Дано хі - цілі числа.)
б) Прочитати дані в наступній послідовності x1 x4 x3 x1, x1 x2 x3.
Розв’язок.
Тип елемента структури визначимо наступним чином:
Type
Point = ^ Item;
Item = record
Data: Integer;
Right, Left: Point
End;
Для побудови структури використовуємо дві змінні типу Point - p і First.
Program Structure;
Type
Point = ^ Item;
Item = Record
Data: Integer;
Right, Left: Point
End;
Var
First: Point;
Procedure Build( Var First: Point);
Var p: Point;
Begin
New(p);
First := p;
Read(p^.Data); {побудований перший елемент структури}
New(p^.Left);
Read(p^.Left^.Data); {побудований другий елемент структури}
New(p^.Right);
Read(p^.Right^.Data); {побудований четвертий елемент структури}
p := p^.Left;
New(p^.Left);
p := p^.Left; Read(p^.Data);
p^.Right := Nil;
p^.left := First; {побудований третій елемент структури}
p := First^.Right; {p установлений на 4-ий елемент }
p^.Left := First^.Left;
p^.Right := First^.Left^.Left; {покажчики виставлені. Побудова закінчена}
End;
Procedure ReadGraph(First: Point);
Var p: Point;
Begin
{початок блока читання}
Writeln('x1,x4,x3,x1:');
p := First;
Write(p^.Data,'');
p := p^.Right;
Write(p^.Data,'');
p := p^.Right;
Write(p^.Data,'');
p := p^.Left;
Write(p^.Data,'');
p := First;
Writeln; Writeln('x1,x2,x3:');
Write(p^.Data,'');
p := p^.Left;
Write(p^.Data,'');
p := p^.Left;
Write(p^.Data,'');
Writeln('Кінець роботи')
End;
Begin
Build(First);
ReadGraph(First);
end.
Посилання p використовувалось для обходів структури, а First – як покажчик на початковий елемент структури.
13.4. Стеки, списки, черги
У цьому розділі розглядаються процедури, що реалізують стандартні засоби роботи зі списками: пошук елемента, вилучення елемента, вставка елемента. Аналогічними засобами користуються і при обробці інших інформаційних структур. Елемент списку описується наступним чином:
Type
Point = ^ Item;
Item = Record
Data: Integer;
Next: Point
End;
Відмітимо характерну деталь: описання елемента динамічної структури рекурсивне! Таким чином, описання динамічних структур неможливе без явного описання типів елементів цих структур.
