Попередня сторінка          Зміст           Наступна сторінка          Електронні посібники ВНТУ

 

ЛАБОРАТОРНА РОБОТА № 11

ВИКОРИСТАННЯ ДИНАМІЧНИХ СТРУКТУР

 

Мета роботи

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

 

 

        

       ТЕОРЕТИЧНІ ВІДОМОСТІ

 

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

Лінійні списки 

Лінійний список – це скінченна послідовність однотипних елементів (вузлів). Кількість елементів у цій послідовності називається довжиною списку. Наприклад, F=(1,2,3,4,5,6) – лінійний список, його довжина 6.

При роботі зі списками часто доводиться виконувати такі операції:

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

Основні методи зберігання лінійних списків поділяються на методи послідов­ного та зв'язаного зберігання.

Послідовне зберігання списків. Метод послідовного зберігання списків ґрун­ту­ється на використанні масиву елементів деякого типу та змінної, в якій збе­рі­гається поточна кількість елементів списку. При послідовному зберіганні спис­ків за допо­могою масивів елементи списку зберігаються в масиві. Така організація дозволяє легко переглядати вміст списку та дода­вати нові елементи в його кінець. Але такі операції, як вставляння нового елементу в середину списку чи вилучення еле­менту з середини списку по­тре­бують зсуву всіх наступних елементів. При збільшенні елементів ма­си­ву кількість операцій для впорядкування списку стрімко зростає. 

 Зв'язане зберігання лінійних списків. Найпростіший спосіб зв'язати мно­жи­ну елементів – зробити так, щоб кожен елемент містив посилання на наступ­ний. Це односпрямований (однозв'язаний) список. Якщо додати в такий список ще й посилання на попередній елемент, то отримаємо двозв'язаний список. А список, перший та останній елементи якого зв'язані, називається кільцевим.

Стеки

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

Стек реалізує принцип LIFO (last in – first out, останнім прийшов – першим пішов). Найбільш наглядним прикладом організації стеку може бути дитяча пірамідка, де додавання і знімання кілець здійснюється як раз відповідно до цього принципу.

Основні операції над стеками:

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

Стек створюється так само, як і лінійний список, оскільки стек є частковим випадком односпрямованого списку. 

Черги

Черга – це лінійний список, де елементи вилучаються з початку списку, а додаються в кінець (як звичайна черга в магазині). 

 Двостороння черга – це лінійний список, у якого операції додавання, вилучення і доступу до елементів можливі як спочатку так і в кінці списку. Таку чергу можна уявити як послідовність книг, що стоять на полиці так, що доступ до них можливий з обох кінців.

Черга є частковим випадком односпрямованого списку. Вона реалізує принцип FIFO (first in – first out, першим прийшов – першим пішов).

Черги створюються аналогічно до лінійних списків та стеків. 

Двійкові дерева

Бінарне дерево – це динамічна струк­тура даних, що складається з вузлів (елементів), кожен з яких містить, окрім даних, не більше двох посилань на інші бінарні дерева. На кожен вузол припадає рівно одне посилання. Початковий вузол називається коренем дерева.

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

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

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

Для бінарних дерев визначені наступні операції:

• включення вузла у дерево;
• пошук по дереву;
• обхід дерева;
• видалення вузла.

 

Порядок виконання роботи

 

1. Засвоїти теоретичний матеріал. Використовуючи лекційний матеріал і інші літературні джерела, дослідити функції роботи з різними динамічними структурами.
2. Розробити програму згідно індивідуального завдання. Для кожного режиму роботи програми повинні бути розроблені окремі функції. Вхідні і вихідні дані повинні зберігатись у файлах.
3. Підготувати звіт:
•  варіант і текст завдання;
•  схема взаємодії функцій програми (з вказанням даних, що передаються і повертаються функціями);
•  схема даних програми;
•  лістинг програми і результати виконання;
•  висновки.

 

Варіанти індивідуальних завдань

 

Створити динамічну структуру, елементами якої є дані, що створю­вались і оброблялись у лабораторних роботах №7 та №9.

Реалізувати різні функції:

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

 

Контрольні питання

 

1. Що таке динамічні структури?  З чого вони складаються?
2. Наведіть різни приклади опису динамічних структур.
3. Які види динамічних структур існують?
4. Які види зберігання лінійних списків ви знаєте?
5. Які операції над лінійними списками можна виконувати?
6. Поясніть, що таке стеки.
7. Назвіть основні операції над стеками і поясніть їх виконання схематично.
8. Як можна отримати доступ до будь-якого елементу стека, окрім вершини?
9. Наведіть фрагмент коду для додавання елементу у стек.
10. Поясніть, що таке черги і правила їх організації.
11. Назвіть основні операції над чергами і поясніть їх виконання схематично.
12. Наведіть фрагмент коду для ініціалізації  черги.
13. В чому сутність бінарного дерева? 
14. Які операції над елементами бінарного дерева можна здійснювати?
15. Покажіть на прикладі створення бінарного дерева, елементи якого цілі числа або символи абетки.