Тема 7. Загальна характеристика динамічних структур даних.

Питання теми та основні терміни.

Посилання, покажчик, динамічний об’єкт

Інформаційні матеріали теми

Поняття посилального типу.

Дії над посиланнями.

1. Поняття посилального типу.

Змінні, які використовувались нами до цих пір при написанні програм, є статичними. Вони оголошуються на етапі  створення програми. Об’єм пам’яті, потрібний для таких об’єктів, не змінюється під час виконання програми. Використання таких змінних в деяких випадках призводить до певних незручностей. Розглянемо такий приклад: нехай за результатами здачі екзамену студентами потрібно сформувати списки  успішності, тобто, список осіб, що здали на “5”, на “4”, тощо. Очевидно, що розв’язок цього завдання може бути одержаний за допомогою масиву рядкових величин. Однак, оскільки наперед кількість студентів в кожному списку невідома, кожен масив потрібно оголосити з максимально можливою для даного завдання кількістю елементів. В такому випадку ми вмисно будемо мати чотирикратне перебільшення використання пам’яті. Якщо врахувати, що сегмент даних для програми на мові Паскаль не може перевищувати 64 кілобайти, то для структур великих розмінностей може виникнути помилка Out of memory (вихід за межі пам’яті).  Було б непогано, якби об’єкти створювались по мірі  необхідності. Така можливість в мові Паскаль є, і вона реалізується за допомогою спеціального типу даних – посилального типу. Значенням такого типу є посилання на деякий програмний об’єкт. Фактично, змінна посилального типу містить адресу деякої комірки пам’яті, в якій розташований інший об’єкт програми.

Оголошення посилального типу здійснюється таким чином:

Type

massiv = array[1..100] of integer;

din1=^integer;

din2=^massiv

В даному випадку тип din1 являє собою посилання та об’єкти цілого типу, а din2 – посилання на масив. Значок ^ показує, що вказаний тип є посилальним.

При оголошенні посилального типу в правій частині опису  можна використовувати тільки ім’я базового типу, а не його опис. Тому наступний опис типу неприпустимий:

Type

din3=^array[1..100] of integer;

Змінні посилального типу називаються посиланнями або покажчиками. Якщо покажчик не пов’язаний з жодним об’єктом, то йому потрібно присвоїти значення порожнього посилання (nil).

При оголошенні посилання резервується лише місце під адресу цього об’єкта. Сам об’єкт ще не існує, і може бути створений при необхідності. Для створення нового об’єкту за покажчиком використовується стандартна процедура new. Вона має такий формат:

new(p)

де p – змінна посилального типу.

Тип створеного об’єкта буде співпадати з тим типом, який вказаний при оголошенні відповідного посилального типу. Звертання до створеного об’єкту здійснюється через вказівку імені покажчика з суфіксом ^. Таким чином, при оголошенні посилального типу знак ^ вказується  зліва від імені об’єкта, а при використанні динамічного об’єкту (змінної) – справа від імені покажчика. Сам динамічний об’єкт можна використовувати як і звичайний статичний об’єкт. Тобто, для нього можна застосовувати всі операції, функції  та оператори, які допустимі для відповідного базового типу.

Приклад.

type

massiv = array[1..100] of integer;

din1=^integer;

din2=^massiv

var

a:din1;

b:din2;

i:integer;

begin

new(a);

new(b);

for i:=1 to 100 do readln(a^[i]);

b^:=5;

...

end.