Динамічні інформаційні структури
Після аналізу розділу опису типів даних та визначення змінних транслятор відводить кожній змінній відповідну кількість ділянок пам’яті та закріплює їх за кожною змінною на весь час роботи програмного блоку. Навіть якщо змінна більше не потрібна, пам’ять не може бути використана. Тому такі дані мають назву статичних.
Однак багато задач потребують більш складних інформаційних структур. Для таких задач характерно, що їх структури даних змінюються під час виконання програми. Такі структури даних мають назву динамічнихструктур.
До динамічних структур належать:
– стекові структури;
– однозв’язні та двозв’язні списки;
– бінарні дерева та ін.
Стек – це впорядкований набір елементів, в якому доповнення нових та видалення існуючих елементів проводиться тільки з одного боку, який називається вершиною стека.
Стек називають структурою типу LIFO (Last In - First Out) – останнім прийшов – першим пішов.
Черга – це впорядкований набір елементів, в якому доповнення нових елементів проводиться з одного боку (початок черги), а видалення елементів черги проводиться з іншого боку (кінець черги).
Чергу називають структурою типу FIFO (First In - First Out) – першим прийшов, першим пішов.
Дек (deque) – це впорядкований набір елементів, в якому доповнення нових та видалення існуючих елементів допускається з любого боку.
Дерево – це сукупність вузлів (вершин) та направлених ребер (дуг), які їх з’єднують, причому в кожен вузол (за винятком кореня) веде рівно одна дуга. Корінь – це початковий вузод дерева, в який не веде жодна дуга.
Впорядковане дерево – це дерево всі вершини якого впорядковані.
Двійковим деревом називається дерево, кожен вузол якого має не більше двох синів.
Лінійний список – це послідовність однотипних елементів, що розташовані лінійно один за одним та пов’язаних вказівниками.
Кожна змінна списку являє собою запис, оскільки складається мінімум з двох компонент: ідентифікуючого ключа (значення) та вказівника на попередній елемент.
Список може бути порожнім.
Список, кожен елемент якого посилається на попередній, називається однозв’язним.
Лінійний список, в якому кожний елемент має вказівник на наступний, називається односпрямованим або однозв’язним списком. По односпрямованому списку можна рухатися тільки в одному напрямку.
Двоспрямованим або двозв’язним списком називається динамічна структура, кожен з елементів якої має вказівник як на наступний, так і на попередній елемент. Двозв’язний список завдяки двом вказівникам надає можливість рухатися по списку у будь-якому напрямку.
Для програмної підтримки усіх цих структур можна використовувати масиви, але при цьому або необхідно описувати занадто великі масиви з відомою надлишковістю, або, у випадку визначення свідомо малих масивів, можливість застосування програми буде обмежена.
Альтернативою масивам є вказівники. Їх перевага полягає у тому, що:
– вони дозволяють створювати динамічні структури необхідної розмірності;
– програміст отримує можливості оперувати великими об’єктами за допомогою 4-байтних вказівників.
Перше ніж ми перейдемо до знайомства з динамічними структурами, розглянемо, що таке динамічні об’єкти.