Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Структура даних СТЕК
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерної техніки, автоматики та метрології
Факультет:
Не вказано
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2011
Тип роботи:
Звіт
Предмет:
Структури даних та алгоритми
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
ІНСТИТУТ КОМП’ЮТЕРНОЇ ТЕХНІКИ АВТОМАТИКИ ТА МЕТРОЛОГІЇ
Кафедра ЕОМ
ЗВІТ ЛАБОРАТОРНОЇ РОБОТИ №3
З ПРЕДМЕТУ: «Програмування. Частина III.
Структури даних та алгоритми»
ТЕМА: «Структура даних СТЕК»
ВИБІР ВАРІАНТУ:
№ варіанта = (17+80)%21+1=14
Львів – 2011
Мета роботи.
Вивчення фундаментальної абстрактної структури даних стек. Набуття практичних навичок побудови стека, дослідження динаміки його вмісту та використання стеків для розв'язання прикладних задач.
Постановка задачі.
Змоделювати стек на базі статичного масиву згідно з завданням. Написати основні операції для роботи зі стеком (push, pop, top, empty, full) і продемонструвати правильність їх виконання. Для цього (якщо в завданні не вказано інший спосіб) в програмі на вході задати послідовність з К (К>10) цілих чисел (числа вводити з клавіатури). Всі додатні числа послідовно заносити в стек, а кожне від'ємне число має вилучати зі стеку один елемент. Виводити на екран динаміку вмісту стеку під час обробки заданої послідовності. Вхідну послідовність чисел задати такою, щоб вона демонструвала роботу основних операцій та генерувала виникнення ситуацій "втрати значимості стеку"(stack underflow) і "переповнення стеку" (stack overflow).
Примітка: після реалізації стеку працювати з ним як з абстрактним типом даних, а не як з масивом.
14. Реалізувати за допомогою одного масиву з N елементiв два стеки, що містять слова. Стеки повинні рости з кінців масиву назустріч один одному. На вході задається послідовність слів. Якщо слово починається з великої літери, то воно додається в стек, якщо з малої, то зі стеку вилучається один елемент. Якщо слово починається з голосної літери, то воно працює з першим стеком, а якщо з приголосної – то з другим. Після обробки всієї заданої вхідної послідовності визначити в якому стеку менша кількість слів.
Алгоритм розв’язання задачі.
За індивідуальним завданням я розробила алгоритм розв’язання задачі.
Цей алгоритм був реалізований у програмі, в якій спочатку підключаються потрібні для виконання програми бібліотеки. Потім створила клас stack і наповнюю його інтерфейс, описую методи класу та його конструктори. Створюю функцію func, в якій реалізовую поставлене завдання.
Пишу функцію-драйвер main, яка демонструє роботу мого абстрактного стеку створюючи об’єкти типу stack та використовуючи функцію func.
Динаміка вмісту стеку
Стек1:
Порожній стек
Елементи вхідної послідовності
-1
Hello
my
Name
Christian
Happy
s_ptr[4]
s_ptr[3]
s_ptr[2]
s_ptr[1]
Used(
s_ptr[0]
s_ptr[4]
S_ptr[3]
s_ptr[2]
(
s_ptr[1]
Hello
s_ptr[0]
s_ptr[4]
s_ptr[3]
s_ptr[2]
s_ptr[1]
(
s_ptr[0]
s_ptr[4]
s_ptr[3]
s_ptr[2]
(
s_ptr[1]
Name
s_ptr[0]
s_ptr[4]
s_ptr[3]
(
s_ptr[2]
Chris
s_ptr[1]
Name
s_ptr[0]
s_ptr[4]
(
s_ptr[3]
Happy
s_ptr[2]
Chris
s_ptr[1]
NAme
s_ptr[0]
Функції:
push(“Hello”)
pop()
push(“Name”)
push(“Chris)
push(“Happy”)
Стек2:
Порожній стек
Елементи вхідної послідовності
-1
is
And
I’m
a[4]
a[3]
a[2]
a[1]
Used(
a[0]
a[4]
a[3]
a[2]
a[1]
(
a[0]
a[4]
a[3]
a[2]
(
a[1]
And
a[0]
a[4]
a[3]
(
a[2]
I’m
a[1]
And
a[0]
Функції:
pop()
push(“And”)
push(“I’m”)
Результати виконання програми.
/
Висновки.
Виконавши дану лабораторну роботу, я вивчила фундаментальну абстрактну структуру даних стек, набула практичних навичок побудови стека, дослідила динаміку його вмісту та використання стеків для розв'язання прикладних задач.
Додатки.
//include.h
#pragma once
#include <iostream>
#include <new>
#include <string.h>
#include <clocale>
#define N 100
using std::cout;
using std::endl;
using std::cin;
//stack.h
#include "include.h"
template <class Type>
class stack{
private:
Type *s_ptr;
Type used;
public:
stack();//конструктор класу
stack(Type *b, int size);//перевантажений варіант конструктора
void push(Type);
void pop();
void show(int num);
bool empty() const { return (s_ptr[0] == 0); }
int size();
Type top() const{
if (empty()){
return s_ptr[0];}
else return 0;
};
};
template <class Type>
stack <Type> :: stack()
{
s_ptr = new Type[N];
used = 0;
for(int i=0; i < N; i++){
s_ptr[i] = 0;
}
}
template <class Type>
stack <Type> :: stack(Type *b, int size)
{
s_ptr = new Type[size];
used = 0;
for(int i=0; i < size; i++){
s_ptr[i] = b[i];
}
}
template <class Type>
void stack <Type> :: push(Type r)
{
if (s_ptr[N]!=0 && s_ptr[N-1]!=0)
cout << "Неможлива операція, стек переповнений" << '\n';
for(int i = N - 1; 0 <= i; i--)
s_ptr[i+1] = s_ptr[i];
s_ptr[0] = r;
}
template <class Type>
void stack <Type> :: pop()
{
for(int i = 0; i < size(); i++)
s_ptr[i] = s_ptr[i+1];
return;
}
template <class Type>
int stack <Type>::size(){
int index = 0;
for(int i = 0; s_ptr[index]!=0; i++)
index++;
return index;
}
template <class Type>
void stack <Type> ::show(int number){//функція яка відображая вміст створеного користувачем стеку з індексом number
if(!empty()){
cout << "Стек№" << number <<": ";
for(int i=0; i < size(); i++)
cout << s_ptr[i] <<",";
}
else
cout << "Стек№" << number << " порожнiй";
cout << endl;
}
//main.cpp
#include "stack.h"
void func(stack<char*>&, stack<char*>&, char*);//прототип функції, яка заповнює стеки відповідно до завдання
int main(){
char str[N][50];
stack<char*> stN1, stN2;
setlocale(LC_ALL, "");
int index = 0;
cout << "Введiть текст(латинськими лiтерами) для занесення його до стеку,\nдля завершення роботи та висновку натиснiть 1:";
do{
cin >> str[index];
func(stN1, stN2, str[index]);
index++;
} while (str[index-1][0] != '1');
cout<< "Розмiр стеку№1:" << stN1.size() << endl << "Розмiр стеку№2:" << stN2.size() << endl << "Отже,";
if (stN1.size()==stN2.size()){
cout << "розмiри стекiв рiвнi" << endl;
};
if (stN1.size()<stN2.size()){
cout << "стек№2 бiльший вiд стеку№1" << endl;
};
if (stN1.size()>stN2.size()){
cout << "стек№1 бiльший вiд стеку№2" << endl;
};
return 0;
}
//func.cpp
#include "stack.h"
void func(stack<char*>& st1, stack<char*>& st2, char* e_word){
if(e_word[0]>=65 && e_word[0]<=90){
if (e_word[0]=='A' || e_word[0]=='O' || e_word[0]=='E'
|| e_word[0]=='U' || e_word[0]=='Y' || e_word[0]=='I'){
st1.push(e_word);
st1.show(1);
}
else{
st2.push(e_word);
st2.show(2);
}
}
if (e_word[0]>=97 && e_word[0]<=122){
if (e_word[0]=='a' || e_word[0]=='o' || e_word[0]=='e'
|| e_word[0]=='u' || e_word[0]=='y' || e_word[0]=='i'){
st1.pop();
st1.show(1);
}
else{
st2.pop();
st2.show(2);
}
}
return;
}
21.10.2013 21:10-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора