МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
Структура даних СТЕК
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи № 3
з дисципліни
" Програмування. Частина III.
Структури даних та алгоритми "
для студентів напрямку
6.0915 “Комп’ютерна інженерія”
Львів – 2008
Методичні вказівки до лабораторної роботи "Структура даних СТЕК" з дисципліни “Програмування. Частина IIІ. Структури даних та алгоритми" для підготовки студентів напрямку 6.0915 “Комп’ютерна інженерія” / Укл. Т.А.Лисак – Львів: Видавництво НУ “Львівська політехніка”, 2008 – 27 с.
Укладач: Лисак Т.А., ст. викладач каф.ЕОМ
Відповідальний
за випуск: Мельник А.О., д-р техн. наук, проф.
Рецензенти: Опир Ю.М., ст. викладач каф.ЕОМ
Юрчак І.Ю., доцент кафедри САПР, к.т.н.
1. МЕТА РОБОТИ
Вивчення фундаментальної абстрактної структури даних - стека. Набуття практичних навичок побудови стека, дослідження динаміки його вмісту та використання стеків для розв'язання прикладних задач.
2. ТЕОРЕТИЧНІ ВІДОМОСТІ
Стек - динамічна структура даних, що представляє собою впорядкований набір елементів, у якій додавання нових елементів і видалення існуючих відбувається з одного кінця, який називається вершиною стека. Згідно визначення, елементи вилучаються зі стека в порядку, зворотному їхньому додаванню в цю структуру, тобто діє принцип LIFO (Last In, Fist Out – останнім прийшов, першим вийшов). Уявимо собі стопку тарілок. Нижня тарелка із цієї стопки буде використана останньою, а верхня тарілка, яка була покладена в стопку останньою, буде використана першою.
Стеки широко використовуються в системному програмному забезпеченні, включаючи компілятори і інтерпретатори.
Найбільш наочним прикладом організації стека служить дитяча пірамідка, де додавання й зняття кілець здійснюється саме відповідно до визначення стека.
Історично склалося так, що дві основні операції для стека - помістити в стек і вилучити зі стека - одержали назву відповідно "заштовхнути" і "виштовхнути". Тому для реализации стека необхідно створити дві функції: "push" (заштовхнути), що поміщає елемент у вершину стека, і "pop" (виштовхнути), що вилучає з вершини стека значення. Необхідно також передбачити певну область у пам'яті, де фактично буде зберігатися стек. Для цього можна використати масив або можна виділити область пам'яті, використовуючи засіб динамічного розпреділення пам'яті.
Приклад 1:
Нехай задана послідовність: 7 , 5 , 9 , 2 . Непарні числа цієї послідовності додаються у стек, а кожне парне число вилучає зі стеку один елемент.
Нижче показана динаміка вмісту стека під час обробки заданої послідовності:
Порожній стек
Елементи вхідної послідовності
7
5
9
2
Data[4]
Data[3]
Data[2]
Data[1]
Used(
Data[0]
Data[4]
Data[3]
Data[2]
Used(
Data[1]
7
Data[0]
Data[4]
Data[3]
Used(
Data[2]
5
Data[1]
7
Data[0]
Data[4]
Used(
Data[3]
9
Data[2]
5
Data[1]
7
Data[0]
Data[4]
Data[3]
Used(
Data[2]
5
Data[1]
7
Data[0]
Функції :
push(7);
push(5);
push(9);
top(); pop();
Оскільки стек - це важлива абстракція даних, у стандартній бібліотеці С++ передбачений клас stack, для використання якого потрібно включити заголовочний файл:
#include <stack>
Повний набір стандартних операцій роботи зі стеком показаний у таблиці:
Операція
Дія
empty()
Повертає true, якщо стек порожній, і false у противному випадку
sіze()
Повертає кількість елементів у стеку
pop()
Видаляє елемент із вершини стека, але не повертає його значення
top()
Повертає значення елемента з вершини стека, але не видаляє його
push(іtem)
Поміщає новий елемент у стек
У наведеній програмі показані приклади використання цих операцій:
#include <stack>
#include <iostream>
int main()
{
const int ia_size = 10;
int ia[ia_size]={0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
// заповнення стеку
int ix = 0;
stack< int > intStack;
for ( ; ix < ia_size; ++ix )
intStack.push( ia[ ix ] );
int error_cnt = 0;
if ( intStack.size() != ia_size ) {
cerr << "Помилка! Неправильний розмір IntStack: " // cerr - вихідний потік
<< intStack.size() // повідомлень про помилки
<< "\t очікується: " << ia_size << endl,
++error_cnt;
}
int value;
while ( intStack.empty() == false )
{
// зчитування елемента з вершини стека
value = intStack.top();
if ( value != --ix ) {
cerr << " Помилка! очікується " << ix
<< " отримано " << value << endl;
++error_cnt;
}
// вилучення елемента
intStack.pop();
}
cout << "В результаті запуска програми отримано "
<< error_cnt << " помилок" << endl;
}
До двох стек одного типу можна застосовувати операції порівняння: рівність, нерівність, менше, більше, менше або дорівнює, більше або дорівнює, якщо вони визначені над елементами стека. Елементи порівнюються попарно. Перша пара неспівпадаючих елементів визначає результат операції порівняння вцілому.
Розглянемо статичну реалізацію стека на основі масиву з фіксованим рзміром. В наведенному далі лістінгу показано заголовочний файл для шаблонного класу stack, аналогічний класу stack зі стандартної бібліотеки шаблонів STL.
// ФАЙЛ: stack1.h
// ЗАБЕЗПЕЧУВАНИЙ ШАБЛОННИЙ КЛАС: stack<Item>
//
// ШАБЛОННИЙ ПАРАМЕТР, ОПЕРАТОРИ ПЕРЕІМЕНОВАННЯ ТИПІВ
// ТА КОНСТАНТНІ ЧЛЕНИ класу stack<Item>
// Шаблонний параметр Item уявляє собою тип елементів,
// що зберігаються у стеку. Він визначається також як
// stack<Item>::value_type
// і може бути довільним вбудованим типомв мові С++ (int, char і т.д.),
// а також класом, в якому визначений конструктор по замовчуванню,
// конструктор копіювання і оператор присвоєння. Визначення типу
// stack<Item>::size_type відноситься до довільної змінної, в якій зберігається
// кількість елементів стека. В цій реалізації константа
// stack<Item>:: CAPACITY означає максимальну кількість елементів довільного
// стека (як тільки ця кількість буде досягнута, заштовхування
// елементів у стек припиняється).
//
// КОНСТРУКТОР ШАБЛОННОГО КЛАСУ stack<Item>:
// stack()
// Післяумова: стек ініціалізується порожнім.
//
// МОДИФІКУЮЧІ ФУНКЦІЇ-ЧЛЕНИ шаблонного класу stack<Item>:
// void push(const Item& entry)
// Передумова: size( ) < CAPACITY.
// Післяумова: в стек занесена нова копія елемента.
//
// void pop( )
// Передумова: size( ) > 0.
// Післяумова: вилучена вершина стека.
//
// КОНСТАНТНІ ФУНКЦІЇ-ЧЛЕНИ шаблонного класу stack<Item>:
// Item top( ) const
// Передумова: size( ) > 0.
// Післяумова: повертається вершина стека, однак стек при цьому
// не змінюється. Цим цей клас дещо відрізняється від стека,
// що описаний в стандартній бібліотеці шаблонів STL ( в якому
// функція top повертає посилання на елемент, що знаходиться у
// вершині стека).
//
// size_type size( ) const
// Післяумова: повертає загальну кількість елементів у стеку.
//
// bool empty( ) const
// Післяумова: повертає значення true, якщо стек порожній,
// и значення false, якщо це не так.
//
// СЕМАНТИКА ЗНАЧЕНЬ для шаблонного класу stack<Item>.
// До об'єктів класу stack<Item> можна застосувати операцію
// присвоєння і конструктор копіювання.
#ifndef MAIN_SAVITCH_STACK1_H
#define MAIN_SAVITCH_STACK1_H
#include <cstdlib> // Надає тип size_t.
namespace main_savitch_7A
{
template <class Item>
class stack
{
public:
// ОПЕРАТОРИ ПЕРЕТВОРЕННЯ ТИПІВ ТА КОНСТАНТНІ ЧЛЕНИ
typedef std::size_t size_type;
typedef Item value_type;
static const size_type CAPACITY = 30;
// КОНСТРУКТОР
stack( ) { used = 0; }
// МОДИФІКУЮЧІ ФУНКЦІЇ-ЧЛЕНИ
void push(const Item& entry);
void pop( );
// КОНСТАНТНІ ФУНКЦІЇ-ЧЛЕНИ
bool empty( ) const { return (used == 0); }
size_type size( ) const { return used; }
Item top( ) const;
private:
Item data[CAPACITY]; // Частково заповнений масив.
size_type used;
};
}
#include "stack1.template" // Директива включення реалізації.
#endif
Файл реалізації класу stack показаний в наступному лістінгє:
// ФАЙЛ: stack1.template
// РЕАЛІЗОВАНИЙ ШАБЛОННИЙ КЛАС stack<Item>:
// Цей файл входить до складу заголовочного і окремо не компілюється.
// Інваріант класу stack:
// 1. Кількість елементів у стеку зберігається у змінній-члені used.
// 2. Елементи стека знаходяться у частково заповненому масиві data. На дні стеку // знаходиться елемент data[0], далі - data[0] і так далі аж до вершини стека, // у якій розташований елемент data[used-1].
#include <cassert> // Надає макрос assert.
namespace main_savitch_7A
{
template <class Item>
const typename stack<Item>::size_type stack<Item>::CAPACITY;
template <class Item>
void stack<Item>::push(const Item& entry)
// ВИКОРИСТОВУВАНА БІБЛІОТЕКА: cassert
{
assert(size( ) < CAPACITY);
data[used] = entry;
++used;
}
template <class Item>
void stack<Item>::pop( )
// ВИКОРИСТОВУВАНА БІБЛІОТЕКА: cassert
{
assert(!empty( ));
--used;
}
template <class Item>
Item stack<Item>::top( ) const
// ВИКОРИСТОВУВАНА БІБЛІОТЕКА: cassert
{
assert(!empty( ));
return data[used-1];
}
}
3. ПОРЯДОК ВИКОНАННЯ РОБОТИ
1. При підготовці до лабораторної роботи, необхідно засвоїти теоретичний матеріал по темі і підготуватись до контрольного опитування по розумінню питань даної тематики.
2. Згідно з індивідуальним завданням розробити алгоритм розв’язання задачі.
3. Підготувати програмну реалізацію розробленого алгоритму. Засобами вбудованого тексто-вого редактора інтегрованого середовища набрати текст підготовленої програми. Відкомпілювати, налагодити та виконати програму.
4. Протестувати програму згідно зі складеною системою тестів і, при потребі, підкоректувати текст програми. Проаналізувати отримані результати.
5. Написати контрольне опитування по темі.
6. Оформити звіт по роботі.
Без підготовкі до роботи (програмної реалізації розробленого алгоритму) студент до роботи не допускається.
4. ЗМІСТ ЗВІТУ
I. Оформити титульну сторінку звіту стандартного зразка, на якій вказати назву лабораторної роботи, її номер та номер варіанту.
II. В звіті мають бути відображені наступні пункти:
Титульна сторінка стандартного зразка з назвою лабораторної роботи, її номером та номером варіанту.
1. Мета роботи.
2. Завдання 1.
2.1. Постановка задачі.
2.2. Алгоритми розв’язання задачі.
2.3. Результати виконання програми.
3. Завдання 2.
3.1. Постановка задачі.
3.2. Динаміка вмісту стеку.
3.3. Результати виконання програми.
Висновки.
Додаток: тексти програм (обов’язково відображати на екрані всі зміни,
що будуть відбуватись у стеку).
5. ЗАВДАННЯ НА ЛАБОРАТОРНУ РОБОТУ
І. Завдання 1: Використати для розв’язання задач клас stack зі стандартної бібліотеки шаблонів STL .
1. Перетворити вираз з інфіксної форми запису в префіксну форму.
2. Перетворити вираз з інфіксної форми запису без дужок в постфіксну форму.
3. Перетворити вираз з інфіксної форми запису з необхідними дужками в постфіксну форму.
4. Обчислити вираз, представлений в інфіксній формі запису.
5. Обчислити вираз, представлений в постфіксній формі запису.
6. Перевірити баланс дужок в арифметичному виразі, який містить тільки один тип дужок – круглі.
7. Написати програму синтаксичного аналізу відповідностей відкриваючих і закриваючих дужок в арифметичному виразі, що має три набори дужок "(" i ")", "<" i ">", "[" i "]". Роздрукувати таблицю відповідностей дужок, причому в таблиці повинно бути зазначено, для яких дужок відсутні парні їм дужки. Для ідентифікації дужок використати їх порядкові номери у виразі.
Приклад: Для арифметичного виразу:
1 2 3 4 5 6
(a+b1)/2+6.5]*{4.8+sin(x)
має бути виведена таблиця виду:
Дужки
відкриваюча закриваюча
1 2
- 3
5 6
4 -
Прочерки в таблиці означають відсутність відповідної дужки.
8. Написати програму, що визначає, чи має символьний рядок, що вводиться, правильну форму виду a D b D c D ... D z , де кожний рядок a, b, c, ..., z має форму рядка виду x C y, де x - рядок, що складається з літер A і B, а y - рядок, обернений до рядка x (наприклад, якщо x = ABABBA, то y повинен дорiвнювати ABBABA). Отже, рядок має правильну форму, якщо він складається з будь-якої кiлькостi подiбних рядків, що роздiленi символом "D". Визначити чи введений рядок правильний.
9. Мажоруючим елементом в послідовності A[1..N] називається елемент, що зустрічається в послідовності більш N/2 разів. В послідовності може бути не більше одного мажоруючого елемента. Визначити, чи є в послідовності мажоруючий елемент, і якщо є, то який.
Приклад: Послідовність 3, 3, 4, 2, 4, 4, 2, 4, 4 має мажоруючий елемент 4, тоді як в послідовності 3, 3, 4, 2, 4, 4, 2, 4 мажоруючого елемента немає.
Вказівки до розв’язання задачі: Створіть стек і додавайте або вилучайте зі стеку елементи за таким правилом:
на першому кроці покладіть в стек A[1];
на i-ом кроці (i=2, ..., N) повторіть такі дії:
якщо стек порожній, то покладіть в нього A[і]; інакше, якщо елемент A[і] співпадає з елементом, що знаходиться у вершині стеку, то додайте A[і] у стек; інакше вилучіть елемент з вершини стеку.
Якщо стек не порожній, то в ньому залишаться лише співпадаючі елементи. Якщо в послідовності є мажоруючий елемент, те він і залишиться в стеку після N-го кроку. Для перевірки (у випадку не порожнього стеку після виконання N-го кроку) чи є елемент у стеку мажоруючим (якщо в стеку більше одного елемента, то вони всі однакові), перегляньте послідовність ще раз і підрахуйте, скільки раз зустрічається в ній елемент, що залишився в стеку. Якщо це число більше N/2, то цей елемент є мажоруючим, інакше - мажоруючого елемента в послідовності немає.
10. Задано n однакових на вигляд каменів, деякі з яких насправді різні по вазі. Є прилад, що дозволяє по двох каменях визначити, однакові вони чи різні (але не показує, який тяжчий). Відомо, що серед цих каменів більшість (більше n/2) однакових. Зробивши не більше n зважувань, знайти хоча б один камінь з цієї більшості.
Вказівки до розв’язання задачі: Дивіться вказівки до попередньої задачі.
ІІ. Завдання 2: Побудувати динамічну структуру даних стек на базі статичного масиву.
1. Реалізуйте за допомогою одного масиву з N елементiв два послідовних стеки. Стеки повинні рости з кінців масиву назустріч один одному. На вході задаються пари цiлих чисел (i,j), де i=(1;2), j – любе. Перше число (і) вказує на номер стеку (1 або 2), з яким буде виконуватись робота. Якщо друге число j>0, то воно додається в і – тий стек, якщо j<0, то з і - го стеку вилучається один елемент, j=0 – ігнорується. Перепишіть основні операції роботи зі стеками і продемонструйте динаміку стеків.
2. Реалізуйте стек, у якому замість двох функцій top i pop використовується тільки одна функція pop, яка робить ці дві дії одночасно, тобто і вилучає елемент зі стеку, і повертає його значення
3. Задайте послідовність, що складається з цифр 0 і 1 . Кожна цифра 1 додається в класичний стек, а кожна цифра 0 вилучає зі стека один елемент.
4. Напишіть програму, яка будує класичний стек (числа вводяться з клавіатури) і після цього перевіряє, чи елементи стека будуть відсортовані по спаданню або по зростанню.
5. Напишіть програму для реалізації стека, який мiстить цiлi числа, за допомогою масиву data, в якому data[0] (а не окрема змiнна) використовуєтся для зберiгання вершини стека, а решта елементів масиву можуть містити елементи самого стека.
6. Напишіть програму, яка будує класичний стек (числа вводяться з клавіатури) і після цього перевіряє, чи цей стек буде “дзеркальним”.
7. Напишіть програму для послiдовного зберiгання двох стекiв в масивi з N елементiв (стеки розміщуються один за одним: перша половина масиву – перший стек, друга половина масиву – другий стек). На вході задаються пари цiлих чисел (i,j), 1 ( i ( 2. Число j пари (i,j) з j>0 додається в i -ий стек; число j пари (i,j), з j<=0, не використовується, але зі стека вилучається один елемент.
8. Реалізуйте стек із “проштовхуванням”: вершина стека завжди знаходиться в першій комірці масиву; при “заштовхуванні” в стек наступного елемента, він поміщається у вершину стеку, а всі решта елементів просуваються на одну позицію далі; при вилученні зі стека одного елемента всі решта елементів пересуваються назад.
9. Реалізуйте стек, у якому до опису стека додано ще дві змінні EMPTY i FULL, замість функції empty. За допомогою цих змінних в функціях push i pop виконати перевірку можливості додавання нового елемента до стека або вилучення елемента з вершини стека.
10. Реалізуйте стек, у якому вершина стека вказує на останній елемент стека, а не на перший вільний елемент масиву.
6. ВИБІР ІНДИВІДУАЛЬНОГО ЗАВДАННЯ
Перша літера прізвища
Номер студента в списку групи
А, І, С
Б, Ї, Т
В, Й, У
Г, К, Ф
Д, Л, Х
Е, М, Ц
Є, Н, Ч
Ж,О,Ш,Щ
З, П, Ю
И, Р, Я
1, 11, 21
І 1
ІІ 1
І 1
ІІ 2
І 1
ІІ 3
І 1
ІІ 4
І 1
ІІ 5
І 1
ІІ 6
І 1
ІІ 7
І 1
ІІ 8
І 1
ІІ 9
І 1
ІІ 10
2, 12, 22
І 2
ІІ 1
І 2
ІІ 2
І 2
ІІ 3
І 2
ІІ 4
І 2
ІІ 5
І 2
ІІ 6
І 2
ІІ 7
І 2
ІІ 8
І 2
ІІ 9
І 2
ІІ 10
3, 13, 23
І 3
ІІ 1
І 3
ІІ 2
І 3
ІІ 3
І 3
ІІ 4
І 3
ІІ 5
І 3
ІІ 6
І 3
ІІ 7
І 3
ІІ 8
І 3
ІІ 9
І 3
ІІ 10
4, 14, 24
І 4
ІІ 1
І 4
ІІ 2
І 4
ІІ 3
І 4
ІІ 4
І 4
ІІ 5
І 4
ІІ 6
І 4
ІІ 7
І 4
ІІ 8
І 4
ІІ 9
І 4
ІІ 10
5, 15, 25
І 5
ІІ 1
І 5
ІІ 2
І 5
ІІ 3
І 5
ІІ 4
І 5
ІІ 5
І 5
ІІ 6
І 5
ІІ 7
І 5
ІІ 8
І 5
ІІ 9
І 5
ІІ 10
6, 16, 26
І 6
ІІ 1
І 6
ІІ 2
І 6
ІІ 3
І 6
ІІ 4
І 6
ІІ 5
І 6
ІІ 6
І 6
ІІ 7
І 6
ІІ 8
І 6
ІІ 9
І 6
ІІ 10
7, 17, 27
І 7
ІІ 1
І 7
ІІ 2
І 7
ІІ 3
І 7
ІІ 4
І 7
ІІ 5
І 7
ІІ 6
І 7
ІІ 7
І 7
ІІ 8
І 7
ІІ 9
І 7
ІІ 10
8, 18, 28
І 8
ІІ 1
І 8
ІІ 2
І 8
ІІ 3
І 8
ІІ 4
І 8
ІІ 5
І 8
ІІ 6
І 8
ІІ 7
І 8
ІІ 8
І 8
ІІ 9
І 8
ІІ 10
9, 19, 29
І 9
ІІ 1
І 9
ІІ 2
І 9
ІІ 3
І 9
ІІ 4
І 9
ІІ 5
І 9
ІІ 6
І 9
ІІ 7
І 9
ІІ 8
І 9
ІІ 9
І 9
ІІ 10
10, 20, 30
І 10
ІІ 1
І 10
ІІ 2
І 10
ІІ 3
І 10
ІІ 4
І 10
ІІ 5
І 10
ІІ 6
І 10
ІІ 7
І 10
ІІ 8
І 10
ІІ 9
І 10
ІІ 10
7. НАВЧАЛЬНО-МЕТОДИЧНІ МАТЕРІАЛИ
Грегори К. Использование Visual С++. Специальное издание. - М.: «Диалектика», 1999.
Мешков А.В., Тихомиров Ю.В. Visual С++ и MFC. Пер. с англ. – 2-е изд. перераб. и доп. – СПб.: БХВ - Петербург, 2002. – 1040 с.
Страуструп Б. Язык программирования С++. Третье издание. - М.: «Издательство Бином», 1999.
Трамбле Ж., Соренсон П. Введение в структуры данных. – М.:Машиностроение, 1982
Уильям Топп, Уильям Форд. Структуры данных в С++. – М.:Бином, 2000 - 700 с
8. КОНТРОЛЬНІ ЗАПИТАННЯ
5
3
9
7
1
8
Mas[0] Mas[1] Mas[2] Mas[3] Mas[4] Mas[5]
Verh
4
Мал.1. Реалізація стеку S1 на базі масиву Mas
1. На малюнку 1 зображений масив Mas і вершина стека Verh, за допомогою яких заданий стек S1. Намалюйте схематичне зображення цього стека.
2. Перемалюйте малюнок 1 після виконання такої операції:
Pop ();
3. Для заданого на малюнку 1 стека S1, напишіть функцію додавання в стек елемента Х (дотримуйтесь назв згідно з малюнком 1).
4. Напишіть умовний оператор, який вилучить зі стека S1 один елемент і виведе повідомлення ”ТАК”, якщо він є парним числом і повідомлення ”НІ” - якщо це не так.
5. В послідовності 4 2 7 3 8 2 1 6 кожна парна цифра визначає операцію рush , а кожна непарна цифра визначає операцію рop. Намалюйте динаміку вмісту стека під час виконання цих операцій над порожнім спочатку стеком.
ЗМІСТ
Мета роботи............................................................................................................................. 3
Теоретичні відомості……………………………… …….…………………………………..3
Порядок виконання роботи….………………………………………………………….…....6
Зміст звіту....................................………...…………………………………………………....7
Завдання на лабораторну роботу……...………………………………………………...…....7
Вибір індивідуального завдвння.……………………….......………………..……..………...9
Навчально-методичні матеріали…………………….......………………........……..……… 10
Контрольні запитання.................………...…………………………………………….……. 10
НАВЧАЛЬНЕ ВИДАННЯ
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи
"Структура даних СТЕК"
з дисципліни
“Програмування. Частина IIІ. Структури даних та алгоритми"
для підготовки студентів напрямку
6.0915 “Комп’ютерна інженерія
Укладач Т.А.Лисак, ст. викладач каф.ЕОМ
Редактор
Комп’ютерне складання
Підписано до друку 2006 р.
Формат 70 х 100 1/16. Папір офсетний.
Друк на різографі. Умовн. друк. арк. ...... Обл.-вид. арк. ......
Наклад ..... прим. Зам.
Поліграфічний центр
Видавництва Національного університету “Львівська політехніка”
вул. Колесси, 2, 79000, Львів