Вступ
Незалежновід типу задач, які ми вирішуємо, кожна програма оперує якимись даними, а самапрограма являє собою методи управління і обробки цих даних. Швидкість виконанняпрограмою поставленої задачі залежить не тільки від алгоритмів, використаних вній для обробки і управління даними, але також і від самої організації даних.Таким чином, ми приходимо до поняття про структуру даних.
Навідміну від статистичних, динамічні структури даних мають велику гибкість увикористанні, бо не мають обмежень в розмірі (безумовно, не враховуючи пам’ятімашини). Слово динамічні нам говорить про можливість утворення елементівструктур в ході виконання програми, що є дуже зручним засобом.
Вданій роботі розробляється динамічний тип даних – список, яких потім пред’явленийу вигляді двохзв’язного списку, реалізованого за допомогою адресації, основаноїна покажчиках.
Основнимиознаками списку являється наявність двох покажчиків: на початок і кінецьструктури. Особливість реалізації: додавання нового елемента структури у кінецьсписку та читання усього списку з початку.
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.Інструкція користувача
При запуску програми Користувачу пропонується вибрати дію зменю, в якому зазначені пронумеровані можливості:
0Exit – вихід із програми;
1About – інформація про завдання;
2 Add– додавання нового елемента в список;
3Count – друк кількості елементів першого підсписку;
4Count K – друк кількості лементів другого підсписку;
5Print – друк першого підсписку;
6Print K – друк другого підсписку;
7Search – пошук елемента за полем «Кількість».
Длявибору дії потрібно ввести її номер. В залежності від обраного пункту, програмаможливо запросить увести додаткові дані.
Узв’язку з тим, що метою даної роботи являється робота з динамічними структурамиданих, то в програму не були введені засоби перевірки коректності уведених даних.
Назвавиробу не повинна мати пробілів. Дата виготовлення вводиться як три окремихцілих числа через пробіл. Кількість повинна буди цілим числом.
Програмаможе працювати вірно лише за умовою вірного вводу даних. За умови невірноговводу даних неможливо передбачити роботу програми. Треба перезавантажитипрограму для її вірної роботи. Обережно, усі раніше введені дані будутьзнищені.
Післявиконання якоїсь дії, програма знову надрукує меню і буде чекати Вашого вибору.
4.Контрольний приклад
//Обираємо дію 1 About:
0Exit 1 About 2 Add 1
KURSOVAYARABOTA PO DISCIPLINE PROGRAMMIPOVANIE
Variant#15
Realizovat'dvusvyazniy snisok dlya hraneniya i operaciy s dannimi vida
–
| Naimenovanieizdeliya | Data izgotovleniya | Koli4estvo |
–
Vperviy odnosvyazniy podspisok vhodyat vse zapisi. Vo vtoroy – tol'ko te, gde
pole «Koli4estvo»
Obespe4it'vipolnenie operaciy:
– Dobavlenienovogo elementa v spiskok;
– Poiskelementa po polyu «Koli4estvo»;
– Raspe4atkapodspiskov;
– Korrektirovkazna4eniya polya «Koli4estvo» nekotorogo elementa.
// Обираємо дію 2Add:
0Exit 1 About 2 Add 2
K =10
VvediteNaimenovanie izdeliya: Keyboard
Vveditedatu izgotovleniya: 26 12 2003
Vveditekoli4estvo izdeliy: 6
// Обираємо дію 4Count K:
0Exit 1 About 2 Add 3 Count
4Count K 5 Print 6 Print K 7 Search K :4
Spisoksostoit iz 1 strok
// Обираємо дію 2Add:
0Exit 1 About 2 Add 3 Count
4Count K 5 Print 6 Print K 7 Search K :2
VvediteNaimenovanie izdeliya: Mouse
Vveditedatu izgotovleniya: 01 01 2001
Vveditekoli4estvo izdeliy: 3
// Обираємо дію 4Count K:
0Exit 1 About 2 Add 3 Count
4Count K 5 Print 6 Print K 7 Search K :4
Spisoksostoit iz 2 strok
// Обираємо дію 6Print K:
0Exit 1 About 2 Add 3 Count
4Count K 5 Print 6 Print K 7 Search K :6
–
| | Naimenovanieizdeliya | Data izgotovleniya | Koli4estvo |
–
| 1| Keyboard|26.12.2003 | 6|
–
| 2| Mouse|1. 1.2001 | 3|
–
// Обираємо дію 5Print:
0Exit 1 About 2 Add 3 Count
4Count K 5 Print 6 Print K 7 Search K :5
–
| | Naimenovanieizdeliya | Data izgotovleniya | Koli4estvo |
–
| 1| Keyboard|26.12.2003 | 6|
–
| 2| Mouse|1. 1.2001 | 3|
–
// Обираємо дію 2Add:
0Exit 1 About 2 Add 3 Count
4Count K 5 Print 6 Print K 7 Search K :2
VvediteNaimenovanie izdeliya: Lamp
Vveditedatu izgotovleniya: 31 12 2006
Vveditekoli4estvo izdeliy: 33
// Обираємо дію 5Print:
0Exit 1 About 2 Add 3 Count
4Count K 5 Print 6 Print K 7 Search K :5
–
| | Naimenovanieizdeliya | Data izgotovleniya | Koli4estvo |
–
| 1| Keyboard|26.12.2003 | 6|
–
| 2| Mouse|1. 1.2001 | 3|
–
| 3| Lamp|31.12.2006 | 33|
–
// Обираємо дію 6Print K:
0Exit 1 About 2 Add 3 Count
4Count K 5 Print 6 Print K 7 Search K :6
–
| | Naimenovanieizdeliya | Data izgotovleniya | Koli4estvo |
–
| 1| Keyboard|26.12.2003 | 6|
–
| 2| Mouse|1. 1.2001 | 3|
–
// Обираємо дію 7Search K:
0Exit 1 About 2 Add 3 Count
4Count K 5 Print 6 Print K 7 Search K :7
VvediteK: 33
–
| | Naimenovanieizdeliya | Data izgotovleniya | Koli4estvo |
–
| 3| Lamp|31.12.2006 | 33|
–
// Обираємо дію 3Count:
0Exit 1 About 2 Add 3 Count
4Count K 5 Print 6 Print K 7 Search K :3
Spisoksostoit iz 3 strok
// Обираємо дію 4Count K:
0Exit 1 About 2 Add 3 Count
4Count K 5 Print 6 Print K 7 Search K :4
Spisoksostoit iz 2 strok
// Обираємо дію 0Exit:
0Exit 1 About 2 Add 3 Count
4Count K 5 Print 6 Print K 7 Search K :0
//Виконується вихід з програми.
ВИСНОВКИ
Отже,можна сказати, що покажчики дають нам можливість працювати з динамічнимиданими. Укупі з структурами досягається найбільш зручний метод організаціїзберігання, обробки даних, що знаходяться у динамічній пам’яті.
Вданій курсовій роботі був реалізований один із видів абстрактних типів даних –двохзв’язний список.
Впроцесі реалізації було використано розподіл необхідних дій на функції, щозначно спростило модифікацію в налагодженні програми. Також розробленіалгоритми для обробки двохзв’язного списку, виконуючи такі операції: додаванняелементів до підсписків, друк підсписків та кількість елементів в них,корегування поля елемента, пошук елементів по полю.
Розглянутоголовні властивості динамічних структур даних, область їх використання, а такожприведені приклади їх вживання.
Література
1. Шилдт Г.«Справочник программиста по С/С++»: Пер. с англ.: Видавництво «Вильямс», 2001.
2. А. Хортон«Visual C++ 2005. Базовый курс» Москва, Санкт-Петербург 2007.
3. А.П. Сергеев,А.Н. Терен «Программирование в Microsoft Visual C++ 2005» Москва,Санкт-Петербург 2006.
Додаток
Кодпрограми
#include
#include
#include
#include
#include
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
};
////////////////////////////////////////////////////////////////////////////////
// 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; cSDate[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
{
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
cout
for (int c=0; c
};
// –
// –
void Line (S_Spisok *Temp, int &k)
{
coutSName
coutSDate[0]
SDate[1]
SDate[2]
coutSCount
for (int c=0; c
};
// –
void Print(void)
{
S_Spisok *Temp = First;
int k=0;
if(Temp) Line0 ();
while(Temp)
{
k++;
Line (Temp, k);
Temp = Temp->Next;
};
cout
};
// –
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
};
////////////////////////////////////////////////////////////////////////////////
// 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
};
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
// основное тело проги
int main (void) {
char Name[40]; // масив для хранения наименования продукта
int a, // храним тут выбранную команду меню
D[dd], // масив для хранени даты
k, // храним вводимое количество продукта
K=0; // инициализация числа К
do {
cout
if(First) cout
cin>>a;
switch(a) {
case 0: break;
case 1: About();
break;
case 2: if(! First)
{
cout
cin>>K;
};
cout
cin>>Name;
cout
for (int c=0; c>D[c];
cout
cin>>k;
Add (Name, D, k, K);
break;
case 3: cout
break;
case 4: cout
break;
case 5: Print();
break;
case 6: Print_K();
break;
case 7: cout
cin>>k;
Search_K(k);
break;
default: cout
break;
};
} while (a!=0);
return 0;};