Динамічні структури даних (С++)

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

 Динамічні структури за визначенням характеризуються відсутністю фізичної суміжності елементів структури в пам'яті непостійністю і непередбачуваністю розміру (числа елементів) структури в процесі її обробки.

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

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

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

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

Переваги зв'язкового представлення даних - в можливості забезпечення значною мінливості структур;

• розмір структури обмежується тільки доступним об'ємом машинної пам'яті;

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

• велика гнучкість структури.

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

• на поля зв'язок споживання пам'ять;

• доступ до елементів зв'язковий структури може бути менш ефективним за часом.

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

).

 

Списки

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

Графічно зв'язку в списках зручно зображувати за допомогою стрілок.  Якщо компонента не пов'язана ні з якою іншою, то в поле покажчика записують значення, не вказує ні на який елемент.  Таке посилання позначається спеціальним ім'ям - nil.

На рис.  1 наведена структура односвязного списку.  На ньому поле INF - інформаційне поле, дані, NEXT - покажчик на наступний елемент списку. Кожен список повинен мати особливий елемент, званий покажчиком початку списку або головою списку, який зазвичай за форматом відмінний від інших елементів.  В поле покажчика останнього елемента списку знаходиться спеціальний ознака nil, що свідчить про кінець списку.

 

Рис.  1: Представлення однозв’язного списку

1 2 3

Схожі роботи