Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2011
Тип роботи:
Курсова робота
Предмет:
Структури даних та алгоритми
Група:
КІ
Частина тексту файла (без зображень, графіків і формул):
Мiнiстерство освiти і науки, молоді та спорту України
Національний університет «Львівська політехніка»
Кафедра ЕОМ
Курсова робота з дисципліни «Програмування. Частина ІІІ. Структури даних та алгоритми»
Завдання 2: Динамічні структури даних
№ = (8+4+75)%3+1= 1
№ = (8+75)%10+1= 4
Львів – 2011
Зміст
2. Завдання 2: Динамічні структури даних………………………………………….... 3
2.1. Теоретична частина………………………………………………………… 3
2.2. Частина 1. Побудова АТД………………………………………………….6
2.2.1. Постановка задачі……………………………………………………6
2.2.2. Динаміка вмісту……………………………………………………...6
2.2.3. Результати виконання програми……………………………………7
2.3. Частина 2. Застосування АТД…………………………………………….8
2.3.1. Постановка задачі……………………………………………………8
2.3.2. Алгоритм розв’язання задачі………………………………………..8
2.3.3. Результати виконання програми……………………………………11
Висновки………………………………………………………………………… 12
Список літератури………………………………………………………………13
Додатки………………………………………………………………………… 14
Завдання №2. Динамічні структури даних
2.1 Теоретична частина
Стек - динамічна структура даних, що являє собою впорядкований набір елементів, в якій додавання нових елементів і видалення існуючих виробляється з одного кінця, званого вершиною стека.
За визначення, елементи витягуються з стека в порядку, зворотному їх додаванню в цю структуру, тобто діє принцип "останній прийшов - перший пішов "(LIFO – Last In, First Out).
Найбільш наочним прикладом організації стека служить дитяча пірамідка, де додавання і зняття кілець здійснюється саме згідно з визначенням стека.
Стек можна організувати на базі будь-якої структури даних, де можна зберігати кількох однотипних елементів і де можна реалізувати визначення стека: лінійний масив, типізований файл, односпрямований або двонаправлений список. У нашому випадку найбільш відповідним для реалізації стека є односпрямований список, причому як вершини стека виберемо початок цього списку.
Виділимо типові операції над стеком і його елементами:
додавання елемента в стек;
видалення елемента з стека;
перевірка, чи порожній стек;
перегляд елемента в вершині стека без видалення;
очищення стека.
Для формування стека і роботи з ним необхідно мати дві змінні типу покажчик, перша з яких визначає вершину стека, а друга - допоміжна.
Операції зі стеком
Виконання операції push
push ("заштовхнути елемент"): елемент додається в стек та розміщується в його верхівці. Розмір стеку збільшується на одиницю. При перевищенні розміру стека граничної величини, відбувається переповнення стека (англ. stack overflow)
pop ("виштовхнути елемент"): отримує елемент з верхівки стеку. При цьому він видаляється зі стеку і його місце в верхівці стеку займає наступний за ним відповідно до правила LIFO, а розмір стеку зменшується на одиницю. При намаганні "виштовхнути" елемент з вже пустого стеку, відбувається ситуація "незаповнення" стеку (англ. stack underflow)
Кожна з цих операцій зі стеком виконується за фіксований час O(1) і не залежить від розміру стеку.
Додаткові операції (присутні не у всіх реалізаціях стеку):
isEmpty: перевірка наявності елементів в стеку; результат: істина (true), коли стек порожній.
isFull: перевірка заповненості стека. Результат: істина, коли додавання нового елементу неможливе.
clear: звільнити стек (видалити усі елементи).
top: отримати верхній елемент (без виштовхування).
size: отримати розмір (кількість елементів) стека.
swap: поміняти два верхніх елементи місцями.
Організація в пам'яті комп'ютера
Стек може бути організований як масив або множина комірок в певній області комп'ютера з додатковим зберіганням ще й вказівника на верхівку стека. Заштовхування першого елемента в стек збільшує адресу вказівника, виштовхування елементу зменшує її. Таким чином, адреса вказівника завжди відповідає комірці масиву, в якій зараз знаходиться верхівка стеку.
Багато процесорів ЕОМ мають спеціалізовані регістри, які використовуються як вказівники на верхівку стеку, або використовують деякі з регістрів загального вжитку для цієї спеціальної функції в певних режимах адресації пам'яті.
Реалізація базових алгоритмів
На мовах програмування високого рівня, стек може бути реалізований за допомогою масиву та додаткової змінної:
Для зберігання елементів стеку резервується масив S[1..n] певного розміру та додаткова змінна top[S], яка буде зберігати індекс верхівки стеку.
Операції push та pop тоді можуть бути записані так (без перевірки на переповнення та "незаповнення").
Приклади застосування
Калькулятори, які використовують зворотню польську нотацію, використовують стек для збереження даних обчислень.
Існують «стеко-орієнтовані» мови програмування (Forth, PostScript), які використовують стек як базову структуру даних при виконанні багатьох операцій (арифметичних, логічних, вводу-виводу тощо).
Стеко-орієнтованими є деякі з віртуальних машин, наприклад віртуальна машина Java.
Компілятори мов програмування використовують стек для передавання параметрів в процесі виклику підпрограм, процедур та функцій. Спеціалізований стек використовується також для збереження адрес повернення з підпрограм.
2.2. Частина 1. Побудова АТД
2.2.1. Постановка задачі
Змоделювати стек на базі статичного масиву згідно з завданням. Написати основні операції для роботи зі стеком (push, pop, top, empty, full) і продемонструвати правильність їх виконання. Для цього (якщо в завданні не вказано інший спосіб) в програмі на вході задати послідовність з К (К>10) цілих чисел (числа вводити з клавіатури). Всі додатні числа послідовно заносити в стек, а кожне від'ємне число має вилучати зі стеку один елемент. Виводити на екран динаміку вмісту стеку під час обробки заданої послідовності. Вхідну послідовність чисел задати такою, щоб вона демонструвала роботу основних операцій та генерувала виникнення ситуацій "втрати значимості стеку"(stack underflow) і "переповнення стеку" (stack overflow).
Примітка: після реалізації стеку працювати з ним як з абстрактним типом даних, а не як з масивом.
2.2.2 Динаміка вмісту стеку.
Покажемо, як наш стек відповідає на додавання деяких елементів.
Елементи вхідної послідовності
-1
2
8
5
0
Data[4]
Data[3]
Data[2]
Data[1]
Used(
-1
Data[0]
Data[4]
Data[3]
Data[2]
Used(
-1
Data[1]
2
Data[0]
Data[4]
Data[3]
Used(
-1
Data[2]
2
Data[1]
8
Data[0]
Data[4]
Used(
-1
Data[3]
2
Data[2]
8
Data[1]
5
Data[0]
Data[4]
Used(
0
Data[3]
0
Data[2]
0
Data[1]
0
Data[0]
push(-1);
push(2);
push(8);
push(5);
push(0);
Елементи вхідної послідовності
4
4
4
7
3
Data[4]
Data[3]
Data[2]
Data[1]
Used(
4
Data[0]
Data[4]
Data[3]
Data[2]
Used(
4
Data[1]
4
Data[0]
Data[4]
Used(
Data[3]
4
Data[2]
4
Data[1]
4
Data[0]
Data[4]
4
Data[3]
Used(
4
Data[2]
4
Data[1]
7
Data[0]
Data[4]
Data[3]
Used(
Data[2]
1
Data[1]
2
Data[0]
4
Data[4]
4
Data[3]
4
Data[2]
7
Data[1]
3
Data[0]
push(4);
push(4);
push(4);
push(7);
push(3);
2.2.3. Результати виконання програми
Таке повідомлення нам видасть програма, якщо умова не справджується(рис. 1).
/
Рис. 1
2.3. Частина 2. Застосування АТД
2.3.1. Постановка задачі
1.4. Обчислити вираз, представлений в інфіксній формі запису. Вказівки до розв’язання задачі: При обчисленні виразу, представленого в інфіксній формі застусовуйте два стеки – один для операндів, другий для операторів.
2.3.2. Алгоритм розв’язання задачі
Оскільки згідно поставленої задачі, нам потрібно обрахувати математичний вираз в інфіксній формі, використовуючи стек. В примітці підказується, що потрібно використати два стеки: перший – для змінних, другий – для операторів. Але при розв’язанні даної задачі ми натикаємося на проблему різнотипності даних, тобто в стек ми заштовхуємо масиви чисел і символів, що призводить до помилки. І для того, щоб цього не сталося ми вирішуємо дану проблему іншим шляхом, використовуючи не два, як йдеться в примітці, а одразу п’ять стеків.
Перші два стеки ми використовуємо, як йдеться в примітці, тобто перший для змінних, де ми будемо заштовхувати дані виду “ABC…Z”, тобто не що інше як змінні, потім яким ми будемо присвоювати значення. В другий стек ми будемо заштовхувати оператори(+,-,/,*).
В третій стек ми будемо заштовхувати присвоєні значення для змінних уже власне для обрахунку математичного виразу.
Четвертий стек буде порівняльним. Суть даного рішення така: в четвертому стеку буде оператор, який порівнюється, а порівнювати будемо із значенням другого стеку, тобто із наступним оператором. Ми вимушені робити таке порівняння у зв’язку із приорітетністю операції. Тобто, якщо у четвертому стеку «+», а у другому «*» або «/», то операція додавання поки що не виконається, а виконається множення або ділення, а лише потім додавання. А якщо в другому стеку «+» або «-», то в цьому випадку операція додавання виконається, оскільки приорітети даних операцій рівні.
В п’ятому стеку буде знаходитися значення, над яким потрібно виконати дію. Тобто op1 – в п’ятому стеку, а op2 – в третьому стеку. А яку операцію над ними потрібно виконати у четвертому стеку. Блок-схема алгоритму наведена на рис. 2 і його продовженню.
Рис.2 Блок-схема алгоритму
Продовження рис.2
2.3.3. Результати виконання програми
Результат виконання виразу a*b-c/d+e*f для значень a=4, b=3, c=81, d=9, e=4, f=2(рис. 3)
/
Рис.3. Результат = 11.
Результат виконання виразу a+b-c/d+e+f/g для значень a=1, b=2, c=3, d=4, e=5, f=6, e=3
/
Рис.4 Результат = -2
Висновки
Отже, виконуючи цю курсову роботу, я освоїв деякі навики роботи у середовищі Microsoft Visual Studio і засоби мови програмування Visual C++. Також я повторив і закріпив свої знання в області динамічних типів даних, а саме такого типу як стек.
Список літератури
Берзтисс А.Т. Структуры данных . – М.:Статистика, 1974 - 408 с.
Вирт Н. Алгоритмы + структуры данных = програмы. –М.:Мир,1985 - 406с.
Глибовець М.М Основи комп’ютерних алгоритмів - К.: НУ “Києво-Могилянська академія”, 2001 - 440 с.
Кнут Д. Искусство програмирования, том 1. Основные алгоритмы. – М.:Изд.дом ”Вильямс”, 2001. – 720 с.
Кнут Д. Искусство програмирования, том 3. Сортировка и поиск. – М.: Изд.дом ”Вильямс”, 2001. – 832 с.
Додатки
Завдання 1
#include<stdio.h>
#include<conio.h>
#define n 10
int stack[n]={0};
int k=0;
void push(int a) //створюємо цикл для вводу ел-ів у стек
{
if (k<n-1) {
stack[k]=a;
k++; } else
printf("\nStack 1 overload\n");
}
void pop()
{
if (k>0)
k--; else
printf("\nStack 1 underflow\n");
}
int top()
{
return stack[k-1];
}
bool empty()
{
return (!(bool)k);
}
bool full()
{
return ((bool)k);
}
void print()
{
for(int i=0;i<n;i++)
printf("%d ",stack[i]);
printf("\np=%d\n",k);
}
void wipe_out() //у цьому циклі організовано, що при вводі ел-та 0 всі ел-ти стеку вилучаються
{
k=0;
for(int i=0;i<n;i++)
stack[i]=0;
}
void main()
{
int g[]={-1,2,8,5,0,4,4,4,7,3};
for (int i=0;i<(sizeof(g)/sizeof(int));i++){
if (g[i]>0)
push(g[i]); else
if (g[i]<0)
pop(); else
wipe_out();
print();}
int tmp=0;
while (!(empty())){
if (!(top()%2!=0))
tmp=1;
pop();}
if (tmp==0) printf(" Stack: true "); else
printf(" Stack: false ");
getch();
}
Завдання 2
#include <iostream>
using namespace std;
#include <conio.h>
#include <stdio.h>
#include <deque>
#include <stack>
int main()
{
int i=0,j=0,g=0;
float op1,op2;
float tmp=0, res=0;
stack<char,deque<char>> s1,s2,s4;// оголошення стеку типу char
stack<int,deque<int>> s3,s5;// оголошення стеку типу int
setlocale(0,"rus");
char x[80];
int y[80];
cout<<"Введiть вираз, який потрiбно обчислити"<<endl;
gets_s(x);
for(i=(int)strlen(x)-1;i>=0;i--)// заштовхування рядка у стек
{
if (x[i]<=47)//якщо оператор то заштовхуємо у s2
{
s2.push(x[i]);
}
else // якщо змінна, то заштовхуємо у s1
{
s1.push(x[i]);
j++;// лічильник кількості символів
}
}
while(s1.empty()==false)// поки перший стек не пустий, то присвоюємо значення змінним
{
for(i=0;i<j;i++)
{
cout<<"Введiть "<<s1.top()<<endl;
s1.pop();
cin>>y[i];
}
}
for(i=j-1;i>=0;i--)// заштовхуємо значення змінних у s3
{
s3.push(y[i]);
}
while(s2.empty()==false && s3.empty()==false)
{
start: ;// мітка початку
g=0;
s5.push(s3.top());
s3.pop();
s4.push(s2.top());
s2.pop();
if (s2.empty()== true || s2.top()==0)// тіки в тому випадку, коли s2 пустий, щоб програма не завершила аварійно свою роботу
{
s2.push(0);
g++;
}
if (s4.top()==43 && s2.top()!=42 && s2.top()!=47)// операція додавання, числа в умові - ASCII-коди символів операторів
{
op1=s5.top();
op2=s3.top();
tmp=op1+op2;
s3.pop();
s5.pop();
s4.pop();
s3.push(tmp);
goto start;// коли виконання операції завершене, то переходимо на початок
}
if (s4.top()==47 && s2.top()!=42) // операція ділення
{
op1=s5.top();
op2=s3.top();
tmp=op1/op2;
s3.pop();
s4.pop();
s5.pop();
while(s4.empty()==false)
{
s2.push(s4.top());
s4.pop();
}
while(s5.empty()==false)
{
s3.push(s5.top());
s5.pop();
if (s5.empty()==true)
{
s5.push(s3.top());
s3.pop();
s3.push(tmp);
s3.push(s5.top());
s5.pop();
g++;
}
}
if (s5.empty()==true && g==0)
{
s3.push(tmp);
}
goto start; // переходимо на мітку початку
}
if (s4.top()==42) // операція множення, не задаємо більше ніяких перевірок наступних символів, оскільки
{
op1=s5.top();//операція множення має найвищий приорітет
op2=s3.top();
tmp=op1*op2;
s3.pop();
s4.pop();
s5.pop();
while(s4.empty()==false)
{
s2.push(s4.top());
s4.pop();
}
while(s5.empty()==false)
{
s3.push(s5.top());
s5.pop();
if (s5.empty()==true)
{
s5.push(s3.top());
s3.pop();
s3.push(tmp);
s3.push(s5.top());
s5.pop();
g++;
}
}
if (s5.empty()==true && g==0)
{
s3.push(tmp);
}
goto start;
}
if (s4.top()==45 && s2.top()!=42 && s2.top()!=47)// операція віднімання, перевірка аналогічно додаванню
{
op1=s5.top();
op2=s3.top();
tmp=op1-op2;
s3.pop();
s5.pop();
s4.pop();
s3.push(tmp);
goto start;
}
}
end: ;
cout<<"Результат виконання програми: "<<s5.top()<<endl;
_getch();
}
19.11.2012 14:11-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора