Курсова робота
"Динамічні структури даних. Рішення задач. Стек. Чергу. Дек "
Введення
Для вирішення багатьох практичних завдань використовуються структури даних - масив, запис, безліч і так далі. Мета опису типів даних і подальшого опису змінних, як відносяться до цього типом, полягає в тому, щоб зафіксувати на час виконання програми розмір значень, що присвоюються цим змінним і, відповідно, фіксувати розмір виділюваної області пам'яті для них. Такі змінні називаються статичними.
Внаслідок фіксування розміру виділеної пам'яті виникають певні труднощі: неефективне використання оперативної пам'яті. Нам, у багатьох випадках, заздалегідь не відомі значення тієї чи іншої змінної, і навіть факт існування цього значення. Для вирішення завдань ми можемо використовувати тільки статичні змінні, але ми не знаємо значення результату і його розміри, тому нам би довелося виділяти місце в пам'яті для максимально можливого підсумкового значення, що призводить до нераціонального використання пам'яті машини.
Створені і не описані заздалегідь, змінні розміщуються на вільні ділянки в динамічної області оперативної пам'яті. Такий спосіб розподілу пам'яті називається динамічним. Існують безліч типів динамічних структур даних, серед них, такі як стек, чергу, лінійні списки, деки, дерева і інші.
В деяких випадках рішення задачі ефективніше при використанні стеків, в інших дерев, по-третє, - наступних. У цій роботі неповний огляд стеків, черг і деков.
1. Стек
Типова ситуація, коли одна проблема вимагає вирішення іншої, яка нерозв'язна без рішення третьої і так далі. У цьому ряду проблема, не викликала нових проблем, вирішується нами першою, хоча оформилася останньої, а вихідна проблема вирішується в останню чергу. Така дисципліна обслуговування позначається LIFO і часто використовується в програмах. Їй відповідає абстрактна лінійна структура, звана стек.
Визначення для стека на мові лінійного списку:
стек - окремий випадок лінійного односвязного списку, для якого дозволено додавати або видаляти елементи тільки з одного кінця списку, який називається вершиною стека.
Приміщення нового елемента в стек, читання для обробки і його видалення відбувається в одному його кінці - верхівці. Інший кінець стека неактивний. Якщо ми видалимо елемент, в верхівці виявляється наступний, можна порівняти з дією магазину в стрілецьку зброю. Включення нового елемента як би проштовхує наявні елементи в сторону дна. Порядок їх проходження при зберіганні не порушується, як і в чергах, масивах та інших структурах. Оскільки в кожний момент потрібен доступ до одного, верхньому, елементу стека, індекси елементів не потрібні.
Нехай Т - деякий тип. Розглянемо тип В«стек елементів типу ТВ». Його значеннями є послідовності значень типу Т. Основні операції, які використовуються при застосуванні стека
В· Зробити порожнім;
В· Додати елемент;
В· Взяти елемент;
В· Стек порожній;
В· Вершина стека: Т;
Процедура В«Зробити порожнімВ» робить стек порожнім, тобто В«на дні стека нічого немаєВ», малюнок № 2. Процедура В«додати елементВ» додає елемент Х, типу Т, в кінець послідовності.
Процедура В«Взяти елементВ» застосовна, якщо послідовність S непорожній, вона забирає з неї останній елемент, який стає значенням змінної т.). Вираз В«стек порожнійВ» істинно, якщо послідовність S порожня. Вираз В«вершина стека В»визначено, якщо послідовність s непорожній, і одно останньому елементу послідовності s (.
Реалізація стека на основі масиву
Будемо вважати, що вершина нашого стека - це перший елемент масиву, тоді вершина буде знаходитись завжди у першій клітинці масиву, а дно буде просуватися по масиву. Для зручності домовимося порожнім членам масиву - вільному стеку привласнювати - 1000.
Помітно, що стек обмежений по розмірах: у нього можна записати обмежена кількість елементів
Розділ оголошення змінних і констант на мові програмування Паскаль виглядає наступним чином:
Const n = 10;
турі typeelem = Integer; { оголошення типу змінного }
Stack = Array Of typeelem;
Var s: stack;
Х: typeelem ;
I : Integer ;
Стек можна моделювати за допомогою двох змінних:
1. S - Стек.
2. Х - змінна для вмісту вершини.
Для того щоб не було непорозумінь і помилок потрібно роздруковувати вміст стека. Ця процедура виводить на екран вміст стека у вигляді стовпчика, на верху якої буде виводитися вершина. У самому нижньому положенні буде знаходитися перший занесений елемент.
Procedure list ; { процедура роздруківки змісту стека }
Var i: Integer;
Begin
Writeln;
I : = 1; { покажчик вершини ставиться на вершину стека }
While And Do Begin
Writeln;
Inc
End ;
End; {list}
Для додавання елемента в стек треба, щоб цей елемент був типу елемента стека. Процедуру додавання можна описати таким чином:
Procedure push ;
Var i : Integer ; {процедура вставки}
Begin
For i: = n Downto 2 Do s: = s;
S : = x
End ; { push }
Процедура додавання: спочатку ми повинні звільнити місце під новий елемент, для цього зрушуємо всі елементи стека по масиву вправо і тільки після додаємо новий в вільну комірку.
Функція В«взяти елемент В»в змінну криється у тому, щоб вважати елемент в змінну і видалити його з стека. Функції ми присвоюємо значення вершини стека, після чого зрушуємо весь стек на одну комірку вліво. У циклі присвоюємо I - тому I +1 значення. Останньому члену масиву - В«дноВ» стека присвоюємо -1000.
Function pop : typeelem ; { зчитування з видаленням}
Var i: Integer;
Begin
Pop: = S;
For i: = 1 To n-1 Do s: = s;
S : = -1000
End ; { pop }
Функція вершина стека: значенню функції присвоюємо значення вершини стека.
Function stacktop : typeelem ; { зчитування без видалення }
Begin
Stacktop: = S
End; {stacktop}
Функція стек порожній: якщо значення вершини стека не дорівнює -1000, то функції присвоюємо значення логічної змінної
FALSE .
Function empty: Boolean; { перевірка на порожнечу }
Begin
If s <> -1000 empty: = false;
End; {empty}
В основній програмі використовуються вище зазначені процедури, наприклад:
init; { процедура ініціалізації }
list; { роздруківка вмісту стека }
For i: = 1 To 3 Do
push; { вставка в стек
