МЕТОДИЧКА_С++_Ч2
.pdfПрактична робота №13
Тема: Програмування з використанням динамічних
структур даних в мові С++
Мета роботи: Оволодіння навиками алгоритмізації і програмування з
використанням динамічних структур даних, навиками
створення та використання стеку та черги.
Теоретичні відомості
Загальні відомості про стек. Способи формування стеку.
Стек — це окремий випадок однонаправленого списку, додавання елементів в який і вибірка з якого виконуються з одного кінця, званого вершиною стеку. Інші операції із стеком не визначені. При вибірці елемент виключається із стека.
Говорять, що стек реалізує принцип обслуговування LIFO (last in — first out,
останнім прийшов, — першим пішов). Стек найпростіше уявити собі як закриту з одного кінця вузьку трубу, в яку кидають м'ячі. Дістати перший кинутий м'яч можна тільки після того, як вийняті всі останні. До речі, сегмент стека названий так саме тому, що пам'ять під локальні змінні виділяється за принципом LIFO. Стеки широко застосовуються в системному програмному забезпеченні, компіляторах, в різних рекурсивних алгоритмах.
Приклад 13.1 Програма, яка формує стек з п'яти цілих чисел (1,2, 3, 4, 5) і
виводить його на екран. Функція приміщення в стек за традицією називається push,
а вибірки — pop. Покажчик для роботи із стеком (top) завжди посилається на його вершину.
#include <iostream.h> #include <conio.h> struct Node{
int d; Node *p;
71
};
Node * first(int d);
void push(Node **top, int d); int pop(Node **top); //--------------------
int main(){
Node *top= first(1);
for (int i = 2; i<6; i++)push(&top, i); while (top)
cout << pop(&top) << ' '; getch();
return 0;
}
//Pochatkove formuvannya steku Node * first(int d){
Node *pv = new Node; pv->d = d;
pv->p = 0; return pv;
}
//Zanesennya v stek
void push(Node **top, int d){ Node *pv = new Node;
pv->d = d; pv->p = *top; *top = pv;
}
72
// Viborka iz steku int pop(Node **top){ int temp = (*top)->d; Node *pv = *top; *top = (*top)->p; delete pv;
return temp;
}
Результат роботи програми: 5 4 3 2 1
Загальні відомості про черги. Способи реалізації черги.
Черга — це окремий випадок однонаправленого списку, додавання елементів в який виконується в один кінець, а вибірка — з іншого кінця. Інші операції з чергою не визначені. При вибірці елемент виключається з черги. Говорять, що чергу реалізує принцип обслуговування FIFO (first in — first out, першим прийшов, —
першим пішов). Чергу найпростіше уявити собі, постоявши в ній годину-дві. У
програмуванні черзі застосовуються, наприклад при моделюванні, диспетчеризації завдань операційною системою, буферизованому введенні/виведенні.
Приклад 13.2 Програма, яка формує чергу з п'яти цілих чисел і виводить її на екран.
Функція розміщення в кінець черги називається add, а видалення — del. Покажчик на початок черги називається pbeg, покажчик на кінець — pend.
#include <iostream.h> #include <conio.h> struct Node{
int d; Node *p; };
Node * first(int d);
void add(Node **pend, int d); int del(Node **pbeg);
73
//основна програма
int main(){
Node *pbeg = first(1);
Node *pend = pbeg;
for (int i = 2; i<6; i++)add(&pend, i); while (pbeg)
cout << del(&pbeg) << ' '; getch();
return 0;
}
//Pochatkove formuvannya chergi Node * first(int d){
Node *pv = new Node; pv->d = d;
pv->p = 0; return pv;
}
//Dodavannya v kinec
void add(Node **pend, int d){ Node *pv = new Node;
pv->d = d; pv->p =0; (*pend)->p = pv; *pend = pv;
}
// Viborkavidalennya int del(Node **pbeg){ int temp = (*pbeg)->d; Node *pv = *pbeg; *pbeg = (*pbeg)->p; delete pv;
return temp;
}
74
Результат роботи програми:
1 2 3 4 5
Послідовність виконання роботи
1.Уважно ознайомитися з теоретичним матеріалом щодо виконання практичної роботи.
2.Вивчити :
формат опису простого елементу (компоненти, вузла) ;
різновиди лінійних списків;
операції над лінійними списками.
7.Набрати програми з прикладів 13.1 та 13.2.
8.Відкомпілювати їх та зробити висновки, щодо алгоритмів створення стеку та черги.
9.Оформити звіт до практичної роботи. Звіт повинен містити: тему, мету,
постановку задачі, тексти програм , результати роботи програм та відповіді на контрольні питання.
Контрольні питання
1.Що таке стек?
2.Який принцип покладений у роботу стеку?
3.Де застосовуються стеки?
4.Яким чиною будується стек?
5.Що таке черга?
6.Якою абревіатурою позначається черга?
7.За яким принципом працює черга?
8.Які є способи формування черги?
75
76