МІНІСТЕРСТВО НАУКИ І ОСВІТИ УКРАЇНИ
Одеський національний політехнічний університет
Інститут комп'ютерних систем
Кафедра "Комп'ютерні інтелектуальні системи та мережі"
Курсова робота
Динамічні структури даних
2004
Анотація
Метою даної роботи служить розробка ефективних алгоритмів на динамічних структурах даних.
Головною особливістю динамічних структур є можливість зміни їх структури і розміру в процесі роботи програми. Це істотно підвищує гнучкість програми, розмір структури обмежується тільки розміром пам'яті машини. Однак така гнучкість обходиться дещо більшими витратами пам'яті на зберігання самої структури і її обробку, оскільки додаткову пам'ять вимагають покажчики.
Алгоритми роботи з цими структурами дуже сильно залежать від виду самої структури.
У даній роботі представлені алгоритми роботи зі стеком. Також тут представлена ​​інструкція користувача по даній програмі.
Зміст
Анотація
1. Теоретичні відомості
1.1 Опис структури даних "Стек"
2. Розробка
2.1 Процедура додати елемент
2.2 Процедура видалення елемента
2.3 Процедура очищення пам'яті
2.4 Роздруківка вмісту
3. Інструкція користувача
4. Код програми
5. Контрольний приклад
Висновок
Перелік використаної літератури
Додатка
1. Теоретичні відомості
У цьому розділі ми ознайомимося з динамічними структурами даних і власне стеком.
Переваги динамічних структур даних
Динамічні структури даних по визначенням характеризуються відсутністю фізичної суміжності елементів структури пам'яті непостійністю і непередбачуваністю розміру (числа елементов4) структури в процесі її обробки. У цьому розділі розглянуті особливості динамічних структур, що визначаються їх першим характерною властивістю.
Оскільки елементи динамічної структури розташовуються по непередбачуваним адресами пам'яті, адреса елемента такої структури не може бути вирахуваний із адреса початкового чи попереднього елемента. Для встановлення зв'язку між елементами динамічної структури використовуються покажчики, через які встановлюються явні зв'язки між елементами. Таке подання даних у пам'яті називається зв'язковим.
Елемент динамічної структури складається з двох полів:
інформаційного поля або поля даних, в якому містяться ті дані, заради яких і створюється структура; загалом випадку інформаційне поле саме є інтегрованою структурою-вектором, масивом, записом і т.п.;
поле зв'язок, в якому містяться один або декілька покажчиків, що зв'язує даний елемент з іншими елементами структури.
Коли зв'язне уявлення даних використовується для розв'язання прикладної задачі, для кінцевого користувача видимим робиться тільки вміст інформаційного поля, а поле зв'язок використовується тільки програмістом-розробником.
Переваги зв'язного представлення даних:
в можливості забезпечення значною мінливості структур;
розмір структури обмежується тільки розміром пам'яті машини;
при зміні логічної послідовності елементів структури потрібно не переміщення даних в пам'яті, а тільки корекція покажчиків.
Однак існують і недоліки:
робота з покажчиками потребує, як правило, більш високої кваліфікації від програміста;
на поля зв'язок витрачається додаткова пам'ять;
доступ до елементів зв'язної структури може бути менш ефективним за часом.
Застосування динамічних структур
Останній недолік є найбільш серйозним і саме ним обмежується застосовність зв'язного представлення даних. Якщо в суміжному поданні даних для обчислення адреси будь-якого елементу нам у всіх випадках достатньо було номера елемента або інформації, що міститься в дескрипторі структури, то для зв'язкового представлення адресу елемента не може бути обчислений з вихідних даних.
Дескриптор зв'язної структури містить один або декілька покажчиків, що дозволяють увійти в структуру, далі пошук і необхідного елемента виконується проходженням по ланцюжку покажчиків від елемента до елемента. Тому зв'язне уявлення практично ніколи не застосовується в задачах, де логічна структура даних має вигляд вектора або масиву - з доступом за номером елемента, але часто застосовується в задачах, де логічна структура вимагає іншої початкової інформації доступу (таблиці, стеки, списки, дерева і т.д.).
Завдання курсового проекту
За списком номер 2, тоді маємо наступне завдання.
Реалізувати стек, що містить 4-ре поля:
Ім'я функції, що повертається значення, кількість параметром і самі параметри.
Реалізувати для даного стека роботу наступних операцій:
додавання елемента;
видалення елемента;
очищення пам'яті від стека;
вивід на екран всіх значень списку;
перевірка про переповнення стек;
виведення повідомлення на екран про переповненні стека.
1.1 Опис структури даних "Стек"
Стеком називається динамічна структура даних, додавання компоненти в яку і виключення компоненти з якої проводиться з одного кінця, званого вершиною стека. Стек працює за принципом LIFO (Last-In, First-Out) - Надійшов останнім, обслуговується першим.
Зазвичай над стеками виконується три операції:
початкове формування стека (запис першої компоненти);
додавання компоненти в стек;
вибірка компоненти (видалення).
Для формування стека і роботи з ним необхідно мати дві змінні типу вказівник, перша з яких визначає вершину стека, а друга - допоміжна.
2. Розробка
У цьому розділі будуть послідовно розглянуті процедури (методи), що працюють з даною структурою (Стеком). Вхідні значення процедур вводяться з клавіатури посредствам різних діалогових вікон за допомогою програмного продукту Builder C + +.
Нижче наведена сама структура:
struct tStack
{
char strFName [255];// ім'я функції
char strRValue [6];// повертане значення
int numPar;// кількість Введення параметрів
char ** pParams;// покажчик на парамаетри
bool bFilled;// заповнений чи елемент
tStack * pNext;// покажчик на наступний елемент
tStack ()
{
pNext = NULL;// задаємо початкові параметри стека, що він порожній
numPar = 0;
bFilled = false;
}
void Add (char * strFName_, char * strRValue_, int numPar_, char ** pParams_);
void Delete ();
void Print (TMemo * memo);
void Free ();
};
strFName - поле, що зберігає ім'я функції;
strRValue - поле, що зберігає повернене значення;
numParams - поле, що зберігає кількість параметрів;
pRarams - поле покажчика, що зберігає адресс значень параметрів;
Далі наведені опису процедур:
void Add (char * strFName_, char * strRValue_, int numPar_, char ** pParams_);
void Delete ();
void Print (TMemo * memo);
void Free ().
2.1 Процедура додавання елемента
Нижче приведений код процедури додавання елемента в стек:
tStack * temp;// створюємо покажчик temp типу tStack
int num = 0;// кількість елементів 0
int max_num = 1000;// максимальна кількість елементів дорівнює 1000
void tStack :: Add (Char * strFName_, char * strRValue_, int numPar_, char ** pParams_)
{
if (num == (max_num-1)) MessageBox ("Almost Overload", "Warning", MB_OK);// Якщо елементів на одиницю менше максимальної кількості елементів, програма попередить діалоговим вікном
if (num == max_num)// Якщо елементів максимальну кількість
{
MessageBox ("Overload"...
