Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Структура даних СТЕК
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2010
Тип роботи:
Лабораторна робота
Предмет:
Інші
Група:
КІ
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
/
Лабораторна робота № 3
Структура даних СТЕК
Львів – 2010
1 Мета роботи:
Вивчення фундаментальної абстрактної структури даних стек. Набуття практичних навичок побудови стека, дослідження динаміки його вмісту та використання стеків для розв'язання прикладних задач.
2 Постановка задачі:
Реалізувати за допомогою одного масиву з N елементiв два стеки. Стеки повинні рости з кінців масиву назустріч один одному. На вході задається послідовність пар цiлих чисел (X,Y), де X - додатнє ціле число, Y - число 1 або 2. Якщо число X є парним, то воно додається в стек, якщо X є непарним числом, то зі стеку вилучається один елемент. Друге число Y кожної пари (X,Y) вказує на номер стеку, з яким виконується робота. Після обробки всієї заданої вхідної послідовності визначити в якому стеку добуток всіх парних чисел буде найменьшим.
3 Алгоритм роз’вязку задачі:
Стек організовуємо у вигляді шаблонного класу. Це дає можливість працювати з усіма стандартними типами даних. Спочатку вводим кількість елементів а потім по черзі задаєм пари Х(число) та Y(номер стеку). Дані вносяться в перший чи другий стек якщо чило додатнє або видаляються якщо відємне. Після обробки всієї заданої вхідної послідовності визначаєм у якому стеку добуток парних чисел найменший.
4 Динаміка вмісту стеку:
Задана послідовність: (2,1); (6,2); (12,2); (4,1); (4,2); (2,2); (6,1); (6,2); (3,1); (8,1)
n дія – почерговність занесення в стек.
Стек 1:
Порожній стек
Елементи вхідної послідовності
2
4
6
3
8
Data[4]
Data[3]
Data[2]
Data[1]
Used(
Data[0]
Data[4]
Data[3]
Data[2]
Used(
Data[1]
2
Data[0]
Data[4]
Data[3]
Used(
Data[2]
4
Data[1]
2
Data[0]
Data[4]
Used(
Data[3]
6
Data[2]
4
Data[1]
2
Data[0]
Data[4]
Data[3]
Used(
Data[2]
4
Data[1]
2
Data[0]
Data[4]
Data[3]
Used(
Data[2]
4
Data[1]
2
Data[0]
Функції :
push(2);1 дія
push(4);4 дія
push(9); 7 дія
pop();9 дія
push(8); 10 дія
Стек 2:
Порожній стек
Елементи вхідної послідовності
6
12
4
2
6
Data[4]
Data[3]
Data[2]
Data[1]
Used(
Data[0]
Data[4]
Data[3]
Data[2]
Used(
Data[1]
6
Data[0]
Data[4]
Data[3]
Used(
Data[2]
12
Data[1]
6
Data[0]
Data[4]
Used(
Data[3]
4
Data[2]
12
Data[1]
6
Data[0]
Data[4]
2
Data[3]
Used(
4
Data[2]
12
Data[1]
6
Data[0]
6
Data[4]
2
Data[3]
Used(
4
Data[2]
12
Data[1]
6
Data[0]
Функції :
push(6);2 дія
push(12); 3 дія
push(4); 5 дія
push(2);6 дія
push(6); 8 дія
5 Результати виконання програми:
/
Висновки:
На цій лабораторній роботі я ознайомилась з cтруктурою даних стек. Дослідила принципи і методи роботи зі стеком.
Додатки:
#include <iostream>
#include <conio.h>
using namespace std;
class Stack{
public:
Stack(int N){
right=N;
n=N;
left=0;
}
void Push_left(int a){
k[left]=a;
left++;
}
void Push_right(int a){
k[right]=a;
right--;
}
int Top_left(){
return k[left-1];
}
int Top_right(){
return k[right+1];
}
void Pop_left(){
if(this->empty_left()==false)
left--;
}
void Pop_right(){
if(this->empty_right()==false)
right++;
}
bool empty_left(){
if(left==0)
return true;
else
return false;
}
bool empty_right(){
if(right==n)
return true;
else
return false;
}
bool full(){
if(left==0 && right==n)
return true;
else
return false;
}
void Print_left(){
cout<<"Stack #1:\n";
if (this->empty_left()!=1){
for(int i=0;i<left;i++)
cout<<k[i]<<" ";
cout<<endl;
}
else
cout<<"Stack #1 is empty!\n";
}
void Print_right(){
cout<<"Stack #2:\n";
if (this->empty_right()!=1){
for(int i=n;i> right;i--)
cout<<k[i]<<" ";
cout<<endl;
}
else
cout<<"Stack #2 is empty!\n";
}
void Print(){
this->Print_left();
cout<<"\n";
this->Print_right();
}
void Func(){
int a=1,b=1;
for(;this->empty_left()!=true;){
if(this->Top_left()%2==0)
a=a*this->Top_left();
this->Pop_left();
}
for(;this->empty_right()!=true;){
if(this->Top_right()%2==0)
b=b*this->Top_right();
this->Pop_right();
}
if(a>b)
cout<<"Answer: 1st Stack!";
if(a<b)
cout<<"Answer: 2st Stack!";
if(a==b)
cout<<"Steky rivni";
}
private:
int n;
int k[30];
int left;
int right;
};
int main(){
int a=1,b,c;
Stack k(40);
cout<<"Vvedit' kilkist' chusel: ";
cin>>c;
for(int i=0;i<c;i++){
cout<<endl<<i+1<<".X= ";
cin>>a;
cout<<endl<<i+1<<".Y= ";
cin>>b;
if(a%2==0){
if(b==1)
k.Push_left(a);
else
k.Push_right(a);
}
if(a%2==1){
if(b==1)
k.Pop_left();
else
k.Pop_right();
}
system("cls");
//cout<<"\n--------------------------"<<endl;
k.Print();
}
k.Func();
getchar();
getchar();
return 0;
}
18.11.2012 16:11-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора