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

– додавання елементів у список;

– пошук елементів по полю кількість;

– друк підсписків;

– коректировка значення поля «Кількість» деякого елемента.

1.4 Опис структури даних «двохзв’язний список»

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

Лінійні зв’язні списки є простими динамічними структурами даних. В даній роботі під двохзв’язним списком маємо на увазі два сумісних однозв’язних списку, тобто два підсписку. Тому у кожного елемента списку є два покажчики на слідуючий елемент першого підсписку та другого підсписку. У першому підсписку кінцевий елемент матиме покажчик дорівнюючий нулю, а у другому підсписку крім кінцевого ще й усі елементи, які не виконують умови «менш, ніж К» будуть також дорівнювати нулю.

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

2. Розробка

Структура даних «двохзв’язний список» буде реалізована у нашій програмі таким чином:

struct S_Spisok {

char SName[40];

int SDate[dd];

int SCount;

S_Spisok *Next;

S_Spisok *Next_K;

};

SName[40], SDate[dd], SCount – інформаційні поля структури, які зберігають назву виробу, дату та кількість відповідно. На зберігання назви виробу виділяється символьний масив на 40 символів. Для зберігання дати використвуємо масив цілих чисел. Кількість елементів масиву задана до початку опису структури константою, яка дорівнює три. Третє поле зберігає кількість віробів і має тип int цілого числа.

Next, Next_K – покажчики на наступний елемент першого та другого підсписків відповідно. Мають тип покажчика на дану структуру, що э логічним.

На початку програми ми створюємо статичний масив Name типу char на 40 символів для зберігання назви виробу. Також створюємо статичні змінні, а для зберігання вибраного пункту меню, k для зберігання кількості виробу. Статичний масив D буде зберігати дату, як три окремих числа.

З цього моменту в програмі починається цикл з післяумовою.

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

Програма вимагає вибору команди з меню шляхом уведення номеру команди. Перевірка вибраного меню реалізована функцією switch.

Якщо користувач увів «0» то припиняється обробка у функції switch і припиняється праця циклу, бо не виконується умова а!=0.

При виборі пункту «1» дія передається функції About(), яка виводить інформацію про завдання проекту.

З введенням двійки буде зроблена перевірка на існування хоча б одного елементу масиву: if(! First). Якщо першого елементу не існуватиме, користувачеві пропонується можливість введення значення К. К потрібне для подальшого формування другого підсписку. Далі, незалежно від умови існування хоча б одного елементу структури, друкується допит на введення інформаційних даних структури. Введені дані передаються параметрами у функцію Add.

Функція Add реалізує додавання нового елемента у список. Вона створює новий динамічний елемент структури і покажчик на нього. Парамерти функції копіруються у новий елемент. Покажчики нового елементу дорівнюють нулю.

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

Якщо у другому підсписку нема елементів і кількість виробів в новому елементові структури менш, ніж К, покажчики на перший та останній елементи другого підсписку будуть дорівнювати новому елементові.