Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Звіт
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2011
Тип роботи:
Завдання
Предмет:
Структури даних та алгоритми
Група:
КІ-22
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет „Львівська політехніка”
Кафедра ЕОМ
Звіт
до курсової роботи (Частина 2)
з дисципліни: “ Програмування. Частина III. Структури даних та алгоритми ”
на тему: “ ”
Процес знаходження номеру варіанта індивідуального завдання
Вибір АТД:
№ = [(день народження) + (місяць народження) + (ASCII–код першої літери прізвища – велика латинська літера) ] % 3 + 1 = [(21) + (7) + (66) ] % 3 + 1 = 2
Примітка: 1 – стек, 2 – черга, 3- список.
Вибір номера завдання:
№ = [(день народження) + (ASCII–код першої літери прізвища – велика латинська літера) ] % 10 + 1 =
= [(21) + (66) ] % 10 + 1 = 8
Зміст
1. Теоретична частина. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3ст.
2. Частина 1. Побудова АТД . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5ст.
2. 1. Постановка задачі . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5ст.
2. 2. Динаміка вмісту. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5ст.
2. 3. Результати виконання програми. . . . . . . . . . . . . . . . . . . . . . 6ст.
3. Частина 2. Застосування АТД. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7ст.
3.1. Постановка задачі. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7ст.
3.2. Алгоритм розв’язання задачі. . . . . . . . . . . . . . . . . . . . . . . . . 7ст.
3.3. Результати виконання програми. . . . . . . . . . . . . . . . . . . . . . . 8ст.
Висновки. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9ст.
Список літератури. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10ст.
Додатки. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11ст.
1.Теоретична частина
СТЕК
Стек - динамічна структура даних, що представляє собою впорядкований набір елементів, у якій додавання нових елементів і видалення існуючих відбувається з одного кінця, який називається вершиною стека. Згідно визначення, елементи вилучаються зі стека в порядку, зворотному їхньому додаванню в цю структуру, тобто діє принцип LIFO (Last In, Fist Out – останнім прийшов, першим вийшов).
Найбільш наочним прикладом організації стека служить дитяча пірамідка, в якій додавання й зняття кілець здійснюється саме відповідно до визначення стека. Можна уявити також стопку тарілок. Нижня тарілка із цієї стопки буде використана останньою, а верхня тарілка, яка була покладена в стопку останньою, буде використана першою. Подібне відбувається й в стеку.
Стеки широко використовуються як для розв’язання прикладних задач, так і в системному програмному забезпеченні, включаючи компілятори і інтерпретатори.
Історично склалося так, що дві основні операції для стека - помістити в стек і вилучити зі стека - одержали назву відповідно "заштовхнути" і "виштовхнути". Тому для реалізації стека необхідно створити дві функції: "push" (заштовхнути), що поміщає елемент у вершину стека, і "pop" (виштовхнути), що вилучає з вершини стека один елемент. Необхідно також передбачити певну область у пам'яті, де фактично буде зберігатися стек. Для цього можна використати масив або можна виділити область пам'яті, використовуючи засоби динамічного розподілу пам'яті.
ЧЕРГА
Чергою FІFO (Fіrst - Іn - Fіrst- Out - "першим прийшов - першим вийшов") називається така послідовність зі змінною довжиною, у якій додавання елементів виконується тільки з однієї сторони (цю сторону часто називають кінцем або хвостом черги), а вилучення - з іншої сторони (називають початком або головою черги). Ті самі черги до прилавків і до кас, які ми так не любимо, є типовим побутовим прикладом черги FІFO.
Основні операції над чергою - ті ж, що й над стеком - додавання, вилучення, визначення розміру, читання, що не руйнує чергу.
Дек - особливий вид черги. Дек (від англ. deq - double ended queue, тобто черга із двома кінцями) - це така послідовність, у якій як додавання, так і вилучення елементів може здійснюватися з кожного із двох кінців. Окремі випадки дека - дек з обмеженим входом і дек з обмеженим виходом. Логічна й фізична структури дека аналогічні логічній і фізичній структурі кільцевої FіFO-черги. Однак, стосовно до дека доцільно говорити не про початок і кінець, а про лівий і правий кінці. Динамічна реалізація дека є об'єднанням стека і черги.
Основні операції над деком:
додавання элемента справа;
додавання элемента слева;
вилучення элемента справа;
вилучення элемента слева;
Задачі, що вимагають використання структури дека, зустрічаються в обчислювальній техніці і програмуванні набагато рідше, ніж завдання, реалізовані на структурі стека або черги. Як правило, вся організація дека виконується програмістом без яких-небудь спеціальних засобів системної підтримки.
Прикладом дека може бути, наприклад, якийсь термінал, у який вводяться команди, кожна з яких виконується якийсь час. Якщо ввести наступну команду, не дочекавшись, поки закінчиться виконання попередньої, то вона встане в чергу й почне виконуватися, як тільки звільниться термінал. Це FІFO-черга. Якщо ж додатково ввести операцію скасування останньої введеної команди, то отримаємо дек.
СПИСОК
Лінійний список – це скінчена послідовність однотипних елементів (вузлів), можливо, з повтореннями. Список розташовується в пам'яті довільним чином. Кожний вузол однонаправленого лінійного зв'язаного списку містить вказівник на наступний вузол списку, що дозволяє переміщуватись вперед по списку. Кожний вузол двонаправленого лінійного зв'язаного списку містить вказівники на попередній і наступний вузли списку, що дозволяє переміщуватись по списку вперед та назад.
Вставка і вилучення вузлів у списку реалізовані ефективно: змінюються тільки вказівники. З іншого боку, довільний доступ до вузлів списку підтримується погано: щоб прийти до певного вузла списку, треба відвідати всі попередні вузли. Крім того, на відміну від стеків або черг, додатково витрачається пам'ять під один або два вказівники на кожний елемент списку.
Список росте дуже просто: додавання кожного нового елемента приводить до того, що вказівники на попередній і наступний вузли списку, між якими вставляється новий вузол, міняють свої значення. У новому елементі таким вказівникам присвоюється значення адрес сусідніх елементів.
Список використовує тільки такий об'єм пам'яті, який потрібний для наявної кількості елементів.
2. Частина 1. Побудова АТД
2. 1. Постановка задачі
Змоделювати абстрактний тип даних (АТД) на базі статичного масиву, який використати в другій частині цього завдання. Переписати основні операції роботи з АТД і продемонструвати їх застосування при додаванні та вилученні елементів в АТД. Для реалізації цього задати послідовність з К > 10 цілих чисел (числа вводити з клавіатури). Всі парні числа додавати в АТД, а кожне непарне число має вилучати з АТД один елемент. Виводити на екран динаміку вмісту АТД під час обробки заданої послідовності.
2. 2. Динаміка вмісту
Введемо такі позначення: F(first) – покажчик початку черги, L(last) – покажчик кінця черги
Наведемо динаміку вмісту черги під час обробки заданої послідовності:
Вхідна послідовність: { 2, 6, 4, 9, 7, 3, 1, 2, 8, 6, 3 }
1)
-порожня черга
2)
2
-push(2)
3)
2
6
-push(6)
4)
2
6
4
-push(4)
5)
6
4
-pop();
6)
4
-pop();
7)
-pop(); Порожня черга
8)
-pop(); queue underflow
9)
2
-push(2);
10)
2
8
-push(8);
11)
2
8
6
-push(6);
12)
8
6
-pop();
2. 3. Результат виконання програми
3. Частина 2. Застосування АТД
3.1. Постановка задачі
8. У магазині стоїть черга з m покупців. Час обслуговування покупця з черги – це випадкове ціле число в діапазоні від 1 до t1. Час додавання нового покупця до черги - це випадкове ціле число в діапазоні від 1 до t2. Промоделювати стан черги. Вивести повідомлення про час виникнення подій ( обслуго-вування та додавання покупця ) за період часу T (T >> t1, T >> t2).
3.2. Алгоритм розв’язання задачі
Для розв’язку цієї задачі потрібно:
1.Написати клас який реалізує всі функції потрібні для реалізації цього завдання.
2.Написана функція pop реалізує вилучення з черги.
3. Написана функція push реалізує додавання в чергу нового елемента .
3.3. Результати виконання програми
Висновки
Дослідження внутрішнього представлення в пам’яті комп’ютера базових і похідних типів даних статичної структури та динамічних структур даних.
Список літератури
Грегори К. Использование Visual С++. Специальное издание. - М.: «Диалектика», 1999.
Мешков А.В., Тихомиров Ю.В. Visual С++ и MFC. Пер. с англ. – 2-е изд. перераб. и доп. – СПб.: БХВ - Петербург, 2002. – 1040 с.
Страуструп Б. Язык программирования С++. Третье издание. - М.: «Издательство Бином», 1999.
Трамбле Ж., Соренсон П. Введение в структуры данных. – М.:Машиностроение, 1982
Уильям Топп, Уильям Форд. Структуры данных в С++. – М.:Бином, 2000 - 700 с
Додатки
Частина 1. Побудова АТД
// queue1.h
#define maxqueue 5
class Tqueue
{
private:
int data[maxqueue]; // масив елементів черги
int first,last,count; // змінні початок, кінець, і лічильник
public:
bool EMPTY, FULL; // Булеві змінні для визначення чи черга пуста, чи повна
// EMPTY повертає значення true якщо черга пуста, в іншому випадку false
// FULL повертає значення true якщо черга повна, в іншому випадку false
Tqueue();
void push(int); // додає новий елемент до черги
void pop(); // вилучає елемент із черги
int front(); // повертає значення елемента з початку черги, але не вилучає //його
};
// queue1.cpp
#include "queue1.h"
#include <iostream>
using namespace std;
Tqueue::Tqueue()
{
first=0,last=-1,count=0;
EMPTY=true, FULL=false;
}
void Tqueue::push(int item)
{
if(FULL==false)
{
data[++last]=item;
++count;
EMPTY=false;
if(count==maxqueue)
FULL=true;
};
}
void Tqueue::pop()
{
if(EMPTY==false)
{
for(int i=0;i<(count-1);i++)
data[i]=data[i+1];
count--;last--;
if(count==0)EMPTY=true;
}
}
int Tqueue::front()
{
return (data[first]);
}
// main.cpp
#include <conio.h>
#include <iostream>
#include "queue1.h"
using namespace std;
void print(Tqueue q)
{
Tqueue tmp;
tmp=q;
cout<<"Dunamika:";
if(q.EMPTY==true)
cout<<"Queue is EMPTY\n";
else
{
cout<<"{ ";
while(tmp.EMPTY==false)
{
cout<<tmp.front()<<" ";
tmp.pop();
}cout<<"}\n";
}
}
int main()
{
Tqueue a;
int i,b,c,mm,k=0,m=1;
cout<<"Killist elementiv cherhy: ";
cin>>b;
for(i=0;i<b;i++)
{
cout<<"Vvedit ["<<i+1<<"] element: ";
cin>>c;
if(c%2==0)
{
if(a.FULL==true)
{
cout<<"queue overflow\n";
}
else a.push(c);
}
if(c%2==1)
{
if(a.EMPTY==true)
{
cout<<"queue underflow\n";
}
else a.pop();}
print(a);
}
getch();
return 0;
}
Частина 2. Застосування АТД
// queue1.h
#define maxqueue 25
class Tqueue
{
private:
int data[maxqueue];
int mas[maxqueue];
int first,last,count;
public:
bool EMPTY, FULL;
Tqueue();
void push(int);
void pop();
int front();
};
// queue1.cpp
#include "queue1.h"
#include <iostream>
using namespace std;
Tqueue::Tqueue()
{
first=0,last=-1,count=0;
EMPTY=true, FULL=false;
}
void Tqueue::push(int item)
{
if(FULL==false)
{
data[++last]=item;
++count;
EMPTY=false;
if(count==maxqueue)FULL=true;
};
}
void Tqueue::pop()
{
if(EMPTY==false)
{
for(int i=0;i<(count-1);i++)
data[i]=data[i+1];
count--;last--;
if(count==0)EMPTY=true;
}
}
int Tqueue::front()
{
return (data[first]);
}
// main.cpp
#include <conio.h>
#include <iostream>
#include "queue1.h"
using namespace std;
void print(Tqueue q)
{
Tqueue tmp;
tmp=q;
cout<<"Dunamika: ";
if(q.EMPTY==true)
cout<<"queue is EMPTY\n";
else
{
cout<<"{ ";
while(tmp.EMPTY==false)
{
cout<<tmp.front()<<" ";
tmp.pop();
}cout<<"}";
}
}
int main()
{
Tqueue a;
int i,elInQueue,t,t1,t2,T;
cout<<"Kilkist ludej v cherzi: ";
cin>>elInQueue;
cout<<"Chas obsluhovuvannja pokupcja: ";
cin>>t1;
cout<<"Chas dodavannja pokupcja: ";
cin>>t2;
cout<<"Chas vidobrazhennja cherhy: ";
cin>>T;
for(i=1;i<=elInQueue;i++)
{
if(a.FULL==true)
{
cout<<"queue overfl\n";
break;
}
else a.push(i);
}
print(a);
cout<<"\n";
for(t=1;t<=T;t++)
{
if(t%t1==0)
{
i++;
if(a.EMPTY==true)
{
cout<<"queue underflow\n";
break;
}
else a.pop();
cout<<"Chas vykonannja podiji: "<<t<<endl;
cout<<"pislja obsluhovuvannja pokupcja: \n";
print(a);
cout<<"\n";
}
if(t%t2==0)
{
i++;
if(a.FULL==true)
{
cout<<"queue overfl \n";
break;
}
else a.push(i);
cout<<"Chas vykonannja podiji: "<<t<<endl;
cout<<"pisla dodavanna pokypca \n";
print(a);
cout<<"\n";
}
}
getch();
return 0;
}
25.01.2012 17:01-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора