Динамічні структури даних

Динамічні структури за визначенням характеризуються відсутністю фізичної суміжності елементів структури в пам’яті непостійністю і непередбачуваністю розміру (числа елементів) структури в процесі її обробки [1−2]. У цьому розділі розглянуті особливості динамічних структур, визначувані їх першою характерною властивістю. Особливості, пов’язані з другою властивістю розглядаються в останньому розділі даного розділу.

Оскільки елементи динамічної структури розташовуються по непередбачуваних адресах пам’яті, адреса елементу такої структури не може бути обчислений з адреси початкового або попереднього елементу. Для встановлення зв’язку між елементами динамічної структури використовуються покажчики, через які встановлюються явні зв’язки між елементами. Таке представлення даних в пам’яті називається зв’язним. Елемент динамічної структури складається з двох полів:

• · інформаційного поля або поля даних, в якому містяться ті дані, ради яких і створюється структура; у загальному випадку інформаційне поле само є інтегрованою структурою — вектором, масивом, записом і т.п.;
• · поле зв’язок, в якому містяться один або декілька покажчиків, що пов’язує даний елемент з іншими елементами структури;

Коли зв’язне представлення даних використовується для вирішення прикладного завдання, для кінцевого користувача «видимим» робиться тільки вміст інформаційного поля, а поле зв’язок використовується тільки програмістом-розробником.

Достоїнства зв’язного представлення даних — в можливості забезпечення значної мінливості структур;

• · розмір структури обмежується тільки доступним об'ємом машинної пам’яті;
• · при зміні логічній послідовності елементів структури потрібне не переміщення даних в пам’яті, а тільки корекція покажчиків.

Разом з тим зв’язне уявлення не позбавлене і недоліків, основні з яких:

робота з покажчиками вимагає, як правило, вищої кваліфікації від програміста;

• · на поля зв’язок витрачається додаткова пам’ять;
• · доступ до елементів зв’язної структури може бути менш ефективним за часом.

Останній недолік є найбільш серйозним і саме їм обмежується застосовність зв’язного представлення даних. Якщо в суміжному представленні даних для обчислення адреси будь-якого елементу нам у всіх випадках достатньо було номери елементу і інформації, що міститься в дескрипторі структури, то для зв’язного уявлення адреса елементу не може бути обчислений з початкових даних. Дескриптор зв’язної структури містить один або декілька покажчиків, що дозволяють увійти до структури, далі пошук необхідного елементу виконується проходженням по ланцюжку покажчиків від елементу до елементу. Тому зв’язне уявлення практично ніколи не застосовується в завданнях, де логічна структура даних має вид вектора або масиву — з доступом по номеру елементу, але часто застосовується в завданнях, де логічна структура вимагає іншої початкової інформації доступу (таблиці, списки, дерева і так далі).