Контрольная работа: Реалізація двохзв’язного списка

Вступ

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

На відміну від статистичних, динамічні структури даних мають велику гибкість у використанні, бо не мають обмежень в розмірі (безумовно, не враховуючи пам’яті машини). Слово динамічні нам говорить про можливість утворення елементів структур в ході виконання програми, що є дуже зручним засобом.

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

Основними ознаками списку являється наявність двох покажчиків: на початок і кінець структури. Особливість реалізації: додавання нового елемента структури у кінець списку та читання усього списку з початку.

1. Теоретичні відомості

1.1 Переваги динамічних структур даних

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

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

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

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

Переваги роботи з даними такого типу:

- в можливості забезпечення значимої зміни структур;

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

- при зміні логічної послідовності елементів структури треба не переміщати данні в пам’яті, а тільки корегувати покажчики.

Однак є і недоліки, основні із яких є:

- робота з покажчиками потребує більш високої кваліфікації від програміста;

- на поля зв’язку витрачається додаткова пам’ять:

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

1.2 Використання динамічних структур.

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

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

1.3 Завдання курсового проекту

Маємо варіант п’ятнадцять. Тип структури – двохзв’язний список з такими полями:

– назва виробу;

– дата виготовлення;

– кількість.

В перший однозв’язний підсписок входять усі записи, в другий – тільки ті, у яких поле кількість менш, ніж К.

--> ЧИТАТЬ ПОЛНОСТЬЮ <--