МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Одеський національний політехнічний університет
Інститут комп'ютерних систем
Кафедра "Комп'ютерні інтелектуальні системи та мережі"
Динамічні структури даних
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", "", "Error", MB _ OK); / / діалогове вікно з помилкою
return; / / процедура додавання елемента зупиняється
}
num + +; / / лічильник кількості введених елементів
if (pNext) / / якщо є посилання на наступний елемент
pNext -> Add (strFName _, strRValue _, numPar _, pParams _); / / додаємо елемент з адресою pNext
else
{
if (! bFilled) / / якщо елемент заповнений
{
strcpy (strFName, strFName _); / / копіюємо значення рядків зі змінною в іншу
strcpy (strRValue, strRValue_);
numPar = numPar_;
pParams = new char * [numPar];
for (int i = 0; i <numPar; i + +) / / повторюємо цикл numPar раз
{
pParams [i] = new char [6]; / / виділяємо пам'ять для зберігання одного параметра 6 байт з масиву
strncpy (pParams [i], pParams_ [i],
6); / / копіюємо значення з введених, відсікаючи все більше 6-ти байт
}
bFilled = true; / / поле вважається заповненим
}
else
{
pNext = new tStack; / / виділяємо пам'ять під нові елемент tStack
pNext-> Add (strFName_, strRValue_, numPar_, pParams_); / / додаємо елемент
}
}
}
У цій функції реалізована і перевірка на переповнення стека. Перевірка переповнення виконується за кількістю введених елементів int max _ num = 1000; і лічильнику поточного елемента num:
if (num == (max _ num -1)) MessageBox ("Almost Overload", "Warning", MB _ OK); / / якщо елементів на одиницю менше максимальної кількості елементів, програма попередить діалоговим вікном
if (num == max _ num) / / якщо елементів максимальну кількість
{
MessageBox ("Overload", "", "Error", MB _ OK); / / діалогове вікно з помилкою
return; / / процедура додавання елемента зупиняється
}
num + +; / / лічильник кількості введених елементів
Реалізація введення параметрів (за певним введеному кількості) виконана через масив покажчиків.
Вхідні параметри надходять з методів С + + Builder через поля і кнопки виконання. Вихідного значення немає.
2.2 Процедура видалення елемента
Нижче приведений код видалення елементу:
void tStack:: Delete ()
{
if (pNext) / / якщо є наступний елемент
if (pNext -> pNext) / / якщо є більш 1-го елемента
pNext -> Delete (); / / запускаємо рекурсивно метод Delete () для наступного елемента
else
{
delete pNext; / / видаляємо в пам'яті адресу зазначену pNext
pNext = NULL; / / прісваєваєм значення покажчика pNext рівне нулю
}
}
За визначенням стека - видаляти можна тільки останній елемент, не руйнуючи стека.
Вхідні параметри відсутні. Вихідного значення немає.
2.3 Процедура очищення пам'яті
Процедура очищення пам'яті від всього стека, код:
void tStack:: Free ()
{
if (temp) delete temp; / / якщо є тимчасова мінлива temp, то очистити від неї пам'ять
if (pNext) / / якщо є хоча б один елемент
{
temp = this; / / temp присвоюється поточне значення
pNext-> Free (); / / запускаємо метод Free () для наступного елемента
}
}
Досить видалити перший елемент стека для руйнування стека, тут видаляється весь стек з кінця, тобто спочатку процедура доходить до кінця стека, далі в зворотному порядку видаляє в пам'яті значення елементів.
Вхідні параметри відсутні. Вихідного значення немає.
2.4 Роздруківка вмісту
Нижче приведений код друкування вмісту всього стека:
void tStack:: Print (TMemo * memo)
{
memo -> Lines -> Add ("* - -------------- - *"); / / вивід на екран значень
memo-> Lines-> Add (strFName);
memo-> Lines-> Add (strRValue);
memo-> Lines-> Add (IntToStr (numPar));
for (int i = 0; i <numPar; i + +) / / повторюємо в циклі роздруківку параметрів з кожною новою рядки
{
memo-> Lines-> Add (pParam [i]); / / додавання покажчика pParam [i]
}
if (pNext) / / якщо є наступний елемент
pNext -> Print (memo); / / рекурсивно запустити роздруківку наступного елемента
}
Вхідні параметри надходять з методів С + + Builder через поля і кнопки виконання. Вихідного значення немає.
3. Інструкція користувача
У цьому розділі буде описано як користуватися розробленою програмою.
Якщо потрібно додати елемента, то дотримуйтесь наступних пунктів:
введіть у полі "Ім'я функції" ім'я вашої функції;
введіть у полі "Значення, що повертається" повертається значення вашої функції;
введіть у полі "Параметри" ваші параметри (максимум по6 символів, за умовою) через знак ";" (крапка з комою);
натисніть кнопку додати.
Якщо потрібно видалити елемент, то натисніть кнопку "Видалити" і останній елемент стека очиститися з пам'яті.
Якщо потрібно очистити пам'ять від всього стека відразу, то натисніть кнопку "Очистити".
Якщо потрібно отримати дані, введені в стек, то натисніть кнопку "Роздрукувати" і програма в поле Edit виведе всі елементи стека в порядку "знизу-вверх", тобто спочатку до кінця.
4. Код програми
/ / ------------------------------------------------ ---------------------------
# Include <vcl. h>
# Pragma hdrstop
# Include "Unit1. H"
# Include <stdio. h>
# Include <stdlib. h>
/ / ------------------------------------------------ ---------------------------
# Pragma package (smart_init)
# Pragma resource "*. dfm"
TForm1 * Form1;
/ / ------------------------------------------------ ---------------------------
__fastcall TForm1:: TForm1 (TComponent * Owner)
: TForm (Owner)
{
}
/ / ------------------------------------------------ ---------------------------
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 ();
};
tStack * temp;
int num = 0;
int max_num = 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", "", "Error", MB_OK);
}
num + +;
if (pNext)
pNext-> Add (strFName_, strRValue_, numPar_, pParams_);
else
{
if (! bFilled)
{
strcpy (strFName, strFName_);
strcpy (strRValue, strRValue_);
numPar = numPar_;
pParams = new char * [numPar];
for (int i = 0; i <numPar; i + +)
{
pParams [i] = new char [6];
strncpy (pParams [i], pParams_ [i],
6);
}
bFilled = true;
}
else
{
pNext = new tStack;
pNext-> Add (strFName_, strRValue_, numPar_, pParams_);
}
}
}
void tStack:: Delete ()
{
if (pNext)
if (pNext-> pNext)
pNext-> Delete ();
else
{
delete [] pNext;
pNext = NULL;
}
}
void tStack:: Print (TMemo * memo)
{
memo-> Lines-> Add ("* - -------------- - *");
memo-> Lines-> Add ("Ім'я функції: "+ (AnsiString) strFName);
memo-> Lines-> Add ("Повертане значення: "+ (AnsiString) strRValue);
memo-> Lines-> Add ("Кількість параметрів: "+ (AnsiString) IntToStr (numPar));
memo-> Lines-> Add ("Параметри функції: ");
for (int i = 0; i <numPar; i + +)
{
memo-> Lines-> Add (pParams [i]);
}
if (pNext)
pNext-> Print (memo);
}
void tStack:: Free ()
{
if (temp) delete [] temp;
if (pNext)
{
temp = this;
pNext-> Free ();
}
}
tStack * stack;
void __fastcall TForm1:: Button1Click (TObject * Sender)
{
if (! stack) stack = new tStack;
char * str = new char [Edit1-> Text. Length () + 1];
strcpy (str, Edit1-> Text. c_str ());
char * str2 = new char [Edit2-> Text. Length () + 1];
strncpy (str2, Edit2-> Text. c_str (),
6);
char * str3 = Edit3-> Text. c_str ();
char * ptr = strtok (str3, ";");
char ** p = new char * [255];
int n = 0;
while (ptr)
{
p [n] = new char [6];
strncpy (p [n], ptr,
6);
ptr = strtok (NULL, ";");
n + +;
}
stack-> Add (str, str2, n, p);
}
/ / ------------------------------------------------ ---------------------------
void __fastcall TForm1:: Button4Click (TObject * Sender)
{
Memo1-> Lines-> Clear ();
if (! stack) return;
stack-> Print (Memo1);
}
/ / ------------------------------------------------ ---------------------------
void __fastcall TForm1:: Button2Click (TObject * Sender)
{
if (! stack) return;
if (! stack-> pNext)
{
delete [] stack;
stack = NULL;
return;
}
stack-> Delete ();
}
/ / ------------------------------------------------ ---------------------------
void __fastcall TForm1:: Button3Click (TObject * Sender)
{
if (! stack) return;
stack-> Free ();
delete [] stack;
stack = NULL;
}
/ / ------------------------------------------------ ---------------------------
void __fastcall TForm1:: FormCreate (TObject * Sender)
{
temp = NULL;
}
/ / ------------------------------------------------ ---------------------------
5. Контрольний приклад
Введемо в програму наступні значення:
ім'я функції 'summ'
значення, що повертається '2 a +3 b ';
параметри '2 a, 3 b; 0; 1 ';
і натиснемо кнопку додати.
Далі введемо аналогічні дані відповідно:
'Test _ summ', 'abajaba', 'qwerty asd; asd fg; asdgf 1; 123 d 456 "і натиснемо кнопку додати.
Тепер натиснемо кнопку роздрукувати і отримаємо наступне, враховуючи особливості умови:
* - -------------- - *
Ім'я функції: summ
Значення, що повертається: 2 a +3 b
Кількість параметрів: 4
Параметри:
2 a
3 b
0
1
* - -------------- - *
Ім'я функції: text _ summ
Значення, що повертається: abajab
Кількість параметрів: 4
Параметри:
qwerty
asd fg
asdfg 1
123 d 4
Тепер натиснемо кнопку видалити, а потім кнопку роздрукувати:
Ім'я функції: summ
Значення, що повертається: 2 a +3 b
Кількість параметрів: 4
Параметри:
2 a
3 b
0
1
Далі натиснемо кнопку очистити і при натисканні кнопки роздрукувати на екран програма нічого виводити не буде.
Висновок
Дана курсова робота є прикладом обробки інформації, представленої у вигляді стека, які наочно дозволяє побачити можливості реалізації запитів, передбачених алгоритмом, тобто здійснення ряду операцій над даними такої структури.
Опис алгоритму програмним способом реалізовано за допомогою мови С + +.
Область застосування алгоритму досить велика, так як сам алгоритм являє собою один із способів обробки інформації.
Робота з різного роду даними є дуже актуальною. Вирішення таких завдань дозволяється скоротити витрачається час на обробку даних і підвищити ефективність самої роботи.
Перелік використаної літератури
1. М. Уейт, С. Прата "Мова Сі", М: СВІТ, 1988
2. У. Мюррей, К. Паллас "Visual C + +", М: BHV, 1996
Програми