Реалізація двохзв’язного списка

Вступ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

– кількість.

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

Вимагається виконати такі операції:

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

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

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

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

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 реалізує додавання нового елемента у список. Вона створює новий динамічний елемент структури і покажчик на нього. Парамерти функції копіруються у новий елемент. Покажчики нового елементу дорівнюють нулю.

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

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

При віборі пункту «3» друкується кількість елементів в першому підсписку. Реалізується ця дія функцією Count: створюється новий покажчик Temp на елемент структури і йому привласнюється спочатку значення покажчика на перший елемент першого підсписку; у циклі з передумовою «поки існує Temp» підраховується кожний елемент та покажчикові Temp привласнюється адреса слідуючого елемента.

Пункт меню «4» виконує друк кількості елементів у другому підсписку. Функція Count_K має такий саме алгоритм, що і Count, тільки відносно другого підсписку.

При введенні п’ятірки виконується друк елементів першого підсписку. Реалізується ця дія за допомогою циклу з передумовою. Покажчику Temp до циклу привласнюється значення покажчика на перший елемент першого підсписку. У циклі друкується порядковий номер елемента й поточний елемент. Покажчику Temp привласнюється значення наступного елемента.

З уведенням «6» відбувається друк елементів другого підсписку. Алгоритм такий же, як і у функції Count. Різниця тільки у тому, що відбувається вже обробка елементів другого підсписку.

Якщо користувач увів «7», то відбудеться запит на введення цілого числа. Це число буде передане параметром у функцію Search. Ця функція реалізує пошук і друк елементів, у яких кількість виробів дорівнюватиме числу, наданому функції як її парамерт. З початку створиться покажчик Temp на елемент структури, який буде дорівнювати покажчику на перший елемент першого підсписку. Пошук буде виконаний за допомогою циклу з передумовою: поки існує Temp. Тобто проглядаються підряд усі елементи першого підсписку і вихід буде зумовлений привласненню покажчику Temp значення покажчика на наступний елемент останнього елемента першого підсписку. У циклі будуть друкуватися елементи, які відповідатимуть умові: кількість виробів дорівнює значенню параметру функції. Разом с цим у циклі є лічильник. Це дозволить друкувати дійсний порядковий номер елемента. Якщо не буде знайдено жодного елемента, що відповідатиме умові, то буде надруковане повідомлення про неіснування жодного потрібного елемента.

Після закінчення обробки switch здійснюється перевірка на вихід з циклу. Умовою є а!=0. Якщо умова виконується, то надрукується меню і программа буде чекати введення. Не здійснення цикцу приведе до закінчення роботи циклу, а потім і програми.

3. Інструкція користувача

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

0 Exit – вихід із програми;

1 About – інформація про завдання;

2 Add – додавання нового елемента в список;

3 Count – друк кількості елементів першого підсписку;

4 Count K – друк кількості лементів другого підсписку;

5 Print – друк першого підсписку;

6 Print K – друк другого підсписку;

7 Search – пошук елемента за полем «Кількість».

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

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

Назва виробу не повинна мати пробілів. Дата виготовлення вводиться як три окремих цілих числа через пробіл. Кількість повинна буди цілим числом.

Програма може працювати вірно лише за умовою вірного вводу даних. За умови невірного вводу даних неможливо передбачити роботу програми. Треба перезавантажити програму для її вірної роботи. Обережно, усі раніше введені дані будуть знищені.

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

4. Контрольний приклад

// Обираємо дію 1 About:

0 Exit 1 About 2 Add 1

KURSOVAYA RABOTA PO DISCIPLINE PROGRAMMIPOVANIE

Variant #15

Realizovat' dvusvyazniy snisok dlya hraneniya i operaciy s dannimi vida

–

| Naimenovanie izdeliya | Data izgotovleniya | Koli4estvo |

–

V perviy odnosvyazniy podspisok vhodyat vse zapisi. Vo vtoroy – tol'ko te, gde

pole «Koli4estvo» < K

Obespe4it' vipolnenie operaciy:

– Dobavlenie novogo elementa v spiskok;

– Poisk elementa po polyu «Koli4estvo»;

– Raspe4atka podspiskov;

– Korrektirovka zna4eniya polya «Koli4estvo» nekotorogo elementa.

// Обираємо дію 2 Add:

0 Exit 1 About 2 Add 2

K = 10

Vvedite Naimenovanie izdeliya: Keyboard

Vvedite datu izgotovleniya: 26 12 2003

Vvedite koli4estvo izdeliy: 6

// Обираємо дію 4 Count K:

0 Exit 1 About 2 Add 3 Count

4 Count K 5 Print 6 Print K 7 Search K :4

Spisok sostoit iz 1 strok

// Обираємо дію 2 Add:

0 Exit 1 About 2 Add 3 Count

4 Count K 5 Print 6 Print K 7 Search K :2

Vvedite Naimenovanie izdeliya: Mouse

Vvedite datu izgotovleniya: 01 01 2001

Vvedite koli4estvo izdeliy: 3

// Обираємо дію 4 Count K:

0 Exit 1 About 2 Add 3 Count

4 Count K 5 Print 6 Print K 7 Search K :4

Spisok sostoit iz 2 strok

// Обираємо дію 6 Print K:

0 Exit 1 About 2 Add 3 Count

4 Count K 5 Print 6 Print K 7 Search K :6

–

| | Naimenovanie izdeliya | Data izgotovleniya | Koli4estvo |

–

| 1| Keyboard| 26.12.2003 | 6|

–

| 2| Mouse| 1. 1.2001 | 3|

–

// Обираємо дію 5 Print:

0 Exit 1 About 2 Add 3 Count

4 Count K 5 Print 6 Print K 7 Search K :5

–

| | Naimenovanie izdeliya | Data izgotovleniya | Koli4estvo |

–

| 1| Keyboard| 26.12.2003 | 6|

–

| 2| Mouse| 1. 1.2001 | 3|

–

// Обираємо дію 2 Add:

0 Exit 1 About 2 Add 3 Count

4 Count K 5 Print 6 Print K 7 Search K :2

Vvedite Naimenovanie izdeliya: Lamp

Vvedite datu izgotovleniya: 31 12 2006

Vvedite koli4estvo izdeliy: 33

// Обираємо дію 5 Print:

0 Exit 1 About 2 Add 3 Count

4 Count K 5 Print 6 Print K 7 Search K :5

–

| | Naimenovanie izdeliya | Data izgotovleniya | Koli4estvo |

–

| 1| Keyboard| 26.12.2003 | 6|

–

| 2| Mouse| 1. 1.2001 | 3|

–

| 3| Lamp| 31.12.2006 | 33|

–

// Обираємо дію 6 Print K:

0 Exit 1 About 2 Add 3 Count

4 Count K 5 Print 6 Print K 7 Search K :6

–

| | Naimenovanie izdeliya | Data izgotovleniya | Koli4estvo |

–

| 1| Keyboard| 26.12.2003 | 6|

–

| 2| Mouse| 1. 1.2001 | 3|

–

// Обираємо дію 7 Search K:

0 Exit 1 About 2 Add 3 Count

4 Count K 5 Print 6 Print K 7 Search K :7

Vvedite K: 33

–

| | Naimenovanie izdeliya | Data izgotovleniya | Koli4estvo |

–

| 3| Lamp| 31.12.2006 | 33|

–

// Обираємо дію 3 Count:

0 Exit 1 About 2 Add 3 Count

4 Count K 5 Print 6 Print K 7 Search K :3

Spisok sostoit iz 3 strok

// Обираємо дію 4 Count K:

0 Exit 1 About 2 Add 3 Count

4 Count K 5 Print 6 Print K 7 Search K :4

Spisok sostoit iz 2 strok

// Обираємо дію 0 Exit:

0 Exit 1 About 2 Add 3 Count

4 Count K 5 Print 6 Print K 7 Search K :0

// Виконується вихід з програми.

ВИСНОВКИ

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

В даній курсовій роботі був реалізований один із видів абстрактних типів даних – двохзв’язний список.

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

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

Література

1. Шилдт Г. «Справочник программиста по С/С++»: Пер. с англ.: Видавництво «Вильямс», 2001.

2. А. Хортон «Visual C++ 2005. Базовый курс» Москва, Санкт-Петербург 2007.

3. А.П. Сергеев, А.Н. Терен «Программирование в Microsoft Visual C++ 2005» Москва, Санкт-Петербург 2006.

Додаток

Код програми

#include <iostream>

#include <conio.h>

#include <stdio.h>

#include <string.h>

#include <iomanip>

using namespace std;

////////////////////////////////////////////////////////////////////////////////

// глобальные переменные

const char dd=3; // отвечает за 3 числа даты

const char width=79; // ширина экрана

////////////////////////////////////////////////////////////////////////////////

// описание структуры

struct S_Spisok {

char SName[40];

int SDate[dd];

int SCount;

S_Spisok *Next;

S_Spisok *Next_K;

};

////////////////////////////////////////////////////////////////////////////////

// глобальные переменные

S_Spisok *First = NULL;

S_Spisok *Lost = NULL;

S_Spisok *First_K = NULL;

S_Spisok *Lost_K = NULL;

////////////////////////////////////////////////////////////////////////////////

// 1 About

void About(void) {

cout<<»n KURSOVAYA RABOTA PO DISCIPLINE PROGRAMMIPOVANIEn Variant #15»

<<»n Realizovat' dvusvyazniy snisok dlya hraneniya i operaciy s dannimi vida»

<<»n –»

<< "| Naimenovanie izdeliya | Data izgotovleniya | Koli4estvo |»

<<» –»

<<» V perviy odnosvyazniy podspisok vhodyat vse zapisi.»

<<» Vo vtoroy – tol'ko te, gde pole «Koli4estvo» < Kn»

<<» Obespe4it' vipolnenie operaciy:»

<<»n – Dobavlenie novogo elementa v spiskok;»

<<»n – Poisk elementa po polyu «Koli4estvo»;»

<<»n – Raspe4atka podspiskov;»

<<»n – Korrektirovka zna4eniya polya «Koli4estvo» nekotorogo elementa.nn»;

};

////////////////////////////////////////////////////////////////////////////////

// 2 Add (функция добавления нового элемента)

bool Add (char *Name, int *D, int &Count, int &K)

{

S_Spisok *Temp = new S_Spisok;

strcpy_s (Temp->SName, Name);

for (int c=0; c<dd; c++) Temp->SDate[c] = D[c];

Temp->SCount = Count;

Temp->Next = NULL;

Temp->Next_K = NULL;

if(Lost)

{

Lost->Next = Temp;

Lost = Temp;

}

else

{

First = Temp;

Lost = Temp;

};

if (Count < K)

{

if (Lost_K)

{

Lost_K->Next_K = Temp;

Lost_K = Temp;

}

else

{

First_K = Temp;

Lost_K = Temp;

};

};

return 1;

};

////////////////////////////////////////////////////////////////////////////////

// 3 Count (определение размера списка)

int Count (S_Spisok *Temp)

{

int k=0;

while(Temp)

{

k++;

Temp = Temp->Next;

};

return k;

};

////////////////////////////////////////////////////////////////////////////////

// 4 Count_K (определение размера списка К)

int Count_K (S_Spisok *Temp)

{

int k=0;

while(Temp)

{

k++;

Temp = Temp->Next_K;

};

return k;

};

////////////////////////////////////////////////////////////////////////////////

// 5 Print (вывод на экран данных)

// –

void Line0 (void) {

for (int c=0; c<width; c++) cout<<» –»;

cout<<»n| | Naimenovanie izdeliya | Data izgotovleniya | Koli4estvo |n»;

for (int c=0; c<width; c++) cout<<» –»;

};

// –

// –

void Line (S_Spisok *Temp, int &k)

{

cout<<»n| "<<setw(2)<<k<<"| "<<setw(40)<<Temp->SName<<"|»;

cout<<» «<<setw(2)<<Temp->SDate[0]<<».»

<<setw(2)<<Temp->SDate[1]<<».»

<<setw(4)<<Temp->SDate[2]<<» |»;

cout<<setw(12)<<Temp->SCount<< "|n»;

for (int c=0; c<width; c++) cout<<» –»;

};

// –

void Print(void)

{

S_Spisok *Temp = First;

int k=0;

if(Temp) Line0 ();

while(Temp)

{

k++;

Line (Temp, k);

Temp = Temp->Next;

};

cout<<»n»;

};

// –

void Print_K(void)

{

S_Spisok *Temp = First_K;

int k=0;

if(Temp) Line0 ();

while(Temp)

{

k++;

Line (Temp, k);

Temp = Temp->Next_K;

};

cout<<»n»;

};

////////////////////////////////////////////////////////////////////////////////

// 7 Search (поиск элемента с полем, равным К)

void Search_K (int k)

{

S_Spisok *Temp = First;

bool b=0;

int c=1;

while(Temp)

{

if (Temp->SCount == k)

{

if (b==0)

{

Line0 ();

b=1;

};

Line (Temp, c);

};

Temp = Temp->Next;

c++;

};

if (b==0) cout<<»n Zna4eniy, udovletvoryayuwih usloviyu, ne suwestvuet.»;

};

////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////

// основное тело проги

int main (void) {

char Name[40]; // масив для хранения наименования продукта

int a, // храним тут выбранную команду меню

D[dd], // масив для хранени даты

k, // храним вводимое количество продукта

K=0; // инициализация числа К

do {

cout<<»n 0 Exit «<<«1 About «<< «2 Add»;

if(First) cout<< «3 Count n»<<» 4 Count K»

<<«5 Print «<<«6 Print K «<< «7 Search K :»;

cin>>a;

switch(a) {

case 0: break;

case 1: About();

break;

case 2: if(! First)

{

cout<<»n K =»;

cin>>K;

};

cout<<»n Vvedite Naimenovanie izdeliya:»;

cin>>Name;

cout<<» Vvedite datu izgotovleniya:»;

for (int c=0; c<dd; c++) cin>>D[c];

cout<<» Vvedite koli4estvo izdeliy:»;

cin>>k;

Add (Name, D, k, K);

break;

case 3: cout<<»n Spisok sostoit iz «<<Count(First)<<» strokn»;

break;

case 4: cout<<»n Spisok sostoit iz «<<Count_K (First_K)<<» strokn»;

break;

case 5: Print();

break;

case 6: Print_K();

break;

case 7: cout<<»n Vvedite K:»;

cin>>k;

Search_K(k);

break;

default: cout<<» Neponyatnen'ko, povtorite vvod.»;

break;

};

} while (a!=0);

return 0;};