Вступ
Незалежно від типу задач, які ми вирішуємо, кожна програма оперує якимись даними, а сама програма являє собою методи управління і обробки цих даних. Швидкість виконання програмою поставленої задачі залежить не тільки від алгоритмів, використаних в ній для обробки і управління даними, але також і від самої організації даних. Таким чином, ми приходимо до поняття про структуру даних.
На відміну від статистичних, динамічні структури даних мають велику гибкість у використанні, бо не мають обмежень в розмірі (безумовно, не враховуючи пам’яті машини). Слово динамічні нам говорить про можливість утворення елементів структур в ході виконання програми, що є дуже зручним засобом.
В даній роботі розробляється динамічний тип даних – список, яких потім пред’явлений у вигляді двохзв’язного списку, реалізованого за допомогою адресації, основаної на покажчиках.
Основними ознаками списку являється наявність двох покажчиків: на початок і кінець структури. Особливість реалізації: додавання нового елемента структури у кінець списку та читання усього списку з початку.
1. Теоретичні відомості
1.1 Переваги динамічних структур даних
Динамічні структури за визначенням характеризуються відсутністю фізично близької розташованості елементів структури в пам’яті, непостійністю і непередбаченістю розміру числа елементів структури в процесі її обробки.
Так як елементи динамічної структури розташовуються за непередбаченим адресом пам’яті, адрес елементу такої структури не може бути вирахуваний із адреса початкового чи попереднього елемента. Для установлення зв’язку між елементами динамічної структури використовуються покажчики, через які встановлюються наявні зв’язки між елементами. Такі зв’язки даних в пам’яті називаються пов’язаними зв’язками.
Елемент динамічної структури складається із двох полів інформаційного поля або поля даних, в якому є ті данні, із-за яких і створюється структура. В даному разі інформаційне поле саме являється інтегрованою структурою-вектором, масивом, записом і т.д. Поле зв’язку, в якому міститься один чи декілька покажчиків, які пов’язують даний елемент з іншими елементами структури.
Коли динамічні структури використовуються для рішення прикладної задачі, для кінцевого користувача «видимим» є тільки зміст інформаційного поля, а поле зв’язків використовується тільки програмістом-розробником.
Переваги роботи з даними такого типу:
- в можливості забезпечення значимої зміни структур;
- розмір структури обмежується тільки доступним об’ємом машинної пам’яті;
- при зміні логічної послідовності елементів структури треба не переміщати данні в пам’яті, а тільки корегувати покажчики.
Однак є і недоліки, основні із яких є:
- робота з покажчиками потребує більш високої кваліфікації від програміста;
- на поля зв’язку витрачається додаткова пам’ять:
- доступ до елементів зв’язної структури може бути менш ефективним в часі.
1.2 Використання динамічних структур.
Останній недолік є найбільш серйозним і саме ним обмежується використання структур. Якщо в статичних даних для виявлення адреса будь-якого елемента нам досить номера елемента і інформації, наявної в дескрипторі структури, то для динамічних даних адрес елемента не може бути вирахуваний із початкових даних.
Дескриптор зв’язної структури має один із декількох показників, який дозволяє увійти в структуру, далі пошук необхідного елемента виконується ланцюгом покажчиків від елемента до елемента. Тому динамічні данні практично ніколи не використовуються у задачах, де логічна структура даних має вид вектора або масиву з доступом за номером елемента, але часто використовується у задачах, де логічна структура вимагає іншої початкової інформації доступу (таблиці, списки, дерева и т.д.)
1.3 Завдання курсового проекту
Маємо варіант п’ятнадцять. Тип структури – двохзв’язний список з такими полями:
– назва виробу;
– дата виготовлення;
– кількість.
В перший однозв’язний підсписок входять усі записи, в другий – тільки ті, у яких поле кількість менш, ніж К.
Вимагається виконати такі операції:
– додавання елементів у список;
– пошук елементів по полю кількість;
– друк підсписків;
– коректировка значення поля «Кількість» деякого елемента.
1.4 Опис структури даних «двохзв’язний список»
Списком називається упорядкування більшості, яке складається із перемінного числа елементів, до яких примінені операції включення та виключення. Список, що показує відношення сусідства між елементами, називається лінійним. Якщо обмеження на довжину списку не допускається, то список знаходиться в пам’яті зв’язної структури.
Лінійні зв’язні списки є простими динамічними структурами даних. В даній роботі під двохзв’язним списком маємо на увазі два сумісних однозв’язних списку, тобто два підсписку. Тому у кожного елемента списку є два покажчики на слідуючий елемент першого підсписку та другого підсписку. У першому підсписку кінцевий елемент матиме покажчик дорівнюючий нулю, а у другому підсписку крім кінцевого ще й усі елементи, які не виконують умови «менш, ніж К» будуть також дорівнювати нулю.
Тип організації структури «список» вимагає виконувати читання з початку списку, а додавання нових елементів у кінець списку. Враховуючи два підсписку, нам необхідно мати чотири покажчика: на початок і кінець першого підсписку, на початок і кінець другого. Поки підсписки не матимуть жодного елемента, покажчики на кінець та початок будуть дорівнювати нулю. Варто передбачити випадок, коли другий підсписок не матиме елементів у той час, коли перший підсписок матиме їх.
0 комментариев