Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2011
Тип роботи:
Курсова робота
Предмет:
Структури даних та алгоритми
Група:
КІ-25
Частина тексту файла (без зображень, графіків і формул):
0Мiнiстерство освiти і науки, молоді та спорту України
Національний університет «Львівська політехніка»
Кафедра ЕОМ
Курсова робота(Частина 2) з дисципліни «Програмування. Частина ІІІ. Структури даних та алгоритми»
Вибір варіанту:
Вибір АТД: (6+5+77)%3+1=2
Вибір номера завдання: (6+77)%10+1=4
Зміст
Завдання 2: Динамічні структури даних----------------------------------------------------------3
2.1. Теоретична частина----------------------------------------------------------------------------4
2.2. Частина 1. Побудова АТД-------------------------------------------------------------------9
2.2.1. Постановка задачі------------------------------------------------------------------------9
2.2.2. Динаміка вмісту--------------------------------------------------------------------------9
2.2.3. Результати виконання програми-----------------------------------------------------11
2.3. Частина 2. Застосування АТД-------------------------------------------------------------12
2.3.1. Постановка задачі-----------------------------------------------------------------------12
2.3.2. Алгоритм розв’язання задачі---------------------------------------------------------12
2.3.3. Результати виконання програми-----------------------------------------------------13
Висновки-------------------------------------------------------------------------------------------------14
Список літератури-------------------------------------------------------------------------------------15
Додатки---------------------------------------------------------------------------------------------------16
Завдання 2. Частина 1: Побудова АТД
Змоделювати абстрактний тип даних (АТД) на базі статичного масиву, який використати в другій частині цього завдання. Переписати основні операції роботи з АТД і продемонструвати їх застосування при додаванні та вилученні елементів в АТД. Для реалізації цього задати послідовність з К > 10 цілих чисел (числа вводити з клавіатури). Всі парні числа додавати в АТД, а кожне непарне число має вилучати з АТД один елемент. Виводити на екран динаміку вмісту АТД під час обробки заданої послідовності.
Завдання 2. Частина 2: Застосування АТД
Розв’язати задачу використовуючи АТД "ЧЕРГА"
Змоделювати чергу або дек на базі статичного масиву згідно з завданням. Переписати основні операції для роботи з чергою (push, pop, front, empty, full) або деком (push_left, push_right, pop_left, pop_right, front_left, front_right, empty, full) і продемонструвати правильність їх виконання. Для цього (якщо в завданні не вказано інший спосіб) в програмі на вході задати послідовність з К (К>10) цілих чисел (числа вводити з клавіатури). Всі додатні числа послідовно заносити в чергу (дек), кожне від’ємне число має вилучати з черги (деку) один елемент (при роботі з деком, парні числа працюють з правим кінцем деку, а непарні – з лівим). Виводити на екран динаміку вмісту черги (деку) під час обробки заданої послідовності. Вхідну послідовність чисел задати такою, щоб вона демонструвала роботу основних операцій та генерувала виникнення ситуацій "втрати значимості черги"(queue underflow) і "переповнення черги" (queue overflow) або "втрати значимості деку"(deq underflow) і "переповнення деку" (deq overflow).
Примітка: після реалізації черги або деку працювати з ними як з абстрактними типами даних, а не як з масивами.
Змоделювати чергу, в якій до опису черги додано функцію wipe_out, яка вилучає всі елементи з черги. Кожний раз, коли у вхідній послідовності зустрічається число 0, то всі елементи мають бути вилучені з черги. Після обробки всієї заданої вхідної послідовності перевірити, чи є в черзі одинакові числа.
2.1. Теоретична частина
Стек - динамічна структура даних, що представляє собою впорядкований набір елементів, у якій додавання нових елементів і видалення існуючих відбувається з одного кінця, який називається вершиною стека. Згідно визначення, елементи вилучаються зі стека в порядку, зворотному їхньому додаванню в цю структуру, тобто діє принцип LIFO (Last In, Fist Out – останнім прийшов, першим вийшов).
Найбільш наочним прикладом організації стека служить дитяча пірамідка, в якій додавання й зняття кілець здійснюється саме відповідно до визначення стека. Можна уявити також стопку тарілок. Нижня тарілка із цієї стопки буде використана останньою, а верхня тарілка, яка була покладена в стопку останньою, буде використана першою. Подібне відбувається й в стеку.
Стеки широко використовуються як для розв’язання прикладних задач, так і в системному програмному забезпеченні, включаючи компілятори і інтерпретатори.
Історично склалося так, що дві основні операції для стека - помістити в стек і вилучити зі стека - одержали назву відповідно "заштовхнути" і "виштовхнути". Тому для реалізації стека необхідно створити дві функції: "push" (заштовхнути), що поміщає елемент у вершину стека, і "pop" (виштовхнути), що вилучає з вершини стека один елемент. Необхідно також передбачити певну область у пам'яті, де фактично буде зберігатися стек. Для цього можна використати масив або можна виділити область пам'яті, використовуючи засоби динамічного розподілу пам'яті.
Приклад :
Нехай задана послідовність: 7 , 5 , 9 , 2 . Непарні числа цієї послідовності додаються у стек, а кожне парне число вилучає зі стеку один елемент.
Нижче показана динаміка вмісту стека під час обробки заданої послідовності:
Порожній стек
Елементи вхідної послідовності
7
5
9
2
Data[4]
Data[3]
Data[2]
Data[1]
Used(
Data[0]
Data[4]
Data[3]
Data[2]
Used(
Data[1]
7
Data[0]
Data[4]
Data[3]
Used(
Data[2]
5
Data[1]
7
Data[0]
Data[4]
Used(
Data[3]
9
Data[2]
5
Data[1]
7
Data[0]
Data[4]
Data[3]
Used(
Data[2]
5
Data[1]
7
Data[0]
Функції :
push(7);
push(5);
push(9);
top(); pop();
Оскільки стек - це важлива абстракція даних, у стандартній бібліотеці С++ передбачений клас stack, для використання якого потрібно включити заголовочний файл:
#include <stack>
Повний набір стандартних операцій роботи зі стеком показаний у таблиці:
Операція
Дія
empty()
Повертає true, якщо стек порожній, і false у противному випадку
sіze()
Повертає кількість елементів у стеку
pop()
Видаляє елемент із вершини стека, але не повертає його значення
top()
Повертає значення елемента з вершини стека, але не видаляє його
push(іtem)
Додає новий елемент у стек
Чергою FІFO (Fіrst - Іn - Fіrst- Out - "першим прийшов - першим вийшов") називається така послідовність зі змінною довжиною, у якій додавання елементів виконується тільки з однієї сторони (цю сторону часто називають кінцем або хвостом черги), а вилучення - з іншої сторони (називають початком або головою черги). Ті самі черги до прилавків і до кас, які ми так не любимо, є типовим побутовим прикладом черги FІFO.
Основні операції над чергою - ті ж, що й над стеком - додавання, вилучення, визначення розміру, читання, що не руйнує чергу.
Приклад :
В послідовності 8 2 6 3 1 4 9 кожна парна цифра визначає операцію push (додавання цієї цифри в чергу), а кожна непарна цифра визначає операцію pop (вилученя з черги одного елемента).
Введемо такі позначення: P – покажчик початку черги, К – покажчик кінця черги
Наведемо динаміку вмісту черги під час обробки заданої послідовності:
K P
0)
- порожня черга
P K
P K
P K
1)
8
2)
8
2
3)
8
2
6
P K
P K
P K
4)
2
6
5)
6
6)
6
4
P K
7)
4
Оскільки черга - це важлива абстракція даних, у стандартній бібліотеці С++ передбачений клас queue, для використання якого потрібно включити заголовочний файл:
# include <queue>
Набір стандартних операцій роботи з чергою показаний у таблиці:
Операція
Дія
push(іtem)
Поміщає новий елемент у кінець черги
pop()
Вилучає елемент з черги, але не повертає його значення
front()
Повертає значення елемента з початку черги, але не вилучає його
empty()
Повертає true, якщо черга порожня, і false у противному випадку
sіze()
Повертає кількість елементів у черзі
Лінійний список – це скінчена послідовність однотипних елементів (вузлів), можливо, з повтореннями. Список розташовується в пам'яті довільним чином. Кожний вузол однонаправленого лінійного зв'язаного списку містить вказівник на наступний вузол списку, що дозволяє переміщуватись вперед по списку. Кожний вузол двонаправленого лінійного зв'язаного списку містить вказівники на попередній і наступний вузли списку, що дозволяє переміщуватись по списку вперед та назад.
Вставка і вилучення вузлів у списку реалізовані ефективно: змінюються тільки вказівники. З іншого боку, довільний доступ до вузлів списку підтримується погано: щоб прийти до певного вузла списку, треба відвідати всі попередні вузли. Крім того, на відміну від стеків або черг, додатково витрачається пам'ять під один або два вказівники на кожний елемент списку.
Список росте дуже просто: додавання кожного нового елемента приводить до того, що вказівники на попередній і наступний вузли списку, між якими вставляється новий вузол, міняють свої значення. У новому елементі таким вказівникам присвоюється значення адрес сусідніх елементів.
Список використовує тільки такий об'єм пам'яті, який потрібний для наявної кількості елементів.
Приклад 1: Динаміка вмісту списку
Порожній список
Реалізація списку на базі масиву
Схематичне зображення списків
0
0
Space[7]
List
0
Free
1
0
7
Space[6]
0
6
Space[5]
0
5
Space[4]
0
4
Space[3]
0
3
Space[2]
0
2
Space[1]
0
0
Space[0]
. data next
List
.
NULL
Free
0
(
0
(
0
(
0
(
0
(
0
(
0
NULL
data next
Виконаємо наступні операціїї над списком:
// push(elem) – додає elem в кінець списку
// pop(pos)- вилучає елемент, що знаходиться в позиції pos
push(106);
push (245);
push (317);
push (472);
pop (4);
push (808);
pop (3);
Результат виконання операцій
Реалізація списку на базі масиву
Схематичне зображення списків
List
1
Free
6
0
4
Space[7]
0
7
Space[6]
808
0
Space[5]
472
3
Space[4]
317
0
Space[3]
245
5
Space[2]
106
2
Space[1]
0
0
Space[0]
. data next
List
106
(
245
(
808
NULL
data next
Free
0
(
0
(
472
(
317
NULL
data next
Виконаємо операцію insert (pos , elem), яка вставляє elem в позицію pos:
insert (5 , 613 )
Було
Стало
List
1
Free
6
0
4
Space[7]
0
7
Space[6]
808
0
Space[5]
472
3
Space[4]
317
0
Space[3]
245
5
Space[2]
106
2
Space[1]
0
0
Space[0]
. data next
List
1
Free
7
0
4
Space[7]
613
5
Space[6]
808
0
Space[5]
472
3
Space[4]
317
0
Space[3]
245
6
Space[2]
106
2
Space[1]
0
0
Space[0]
. data next
List
106
(
245
(
808
NULL
data next
Free
0
(
0
(
472
(
317
NULL
data next
List
106
(
245
(
613
(
808
NULL
data next
Free
0
(
472
(
317
NULL
data next
Виконаємо операцію pop (pos), яка вилучає елемент, що знаходиться в позиції pos
pop (List )
Було
Стало
List
1
Free
7
0
4
Space[7]
613
5
Space[6]
808
0
Space[5]
472
3
Space[4]
317
0
Space[3]
245
6
Space[2]
106
2
Space[1]
0
0
Space[0]
. data next
List
2
Free
7
0
4
Space[7]
613
5
Space[6]
808
0
Space[5]
472
3
Space[4]
317
1
Space[3]
245
6
Space[2]
106
0
Space[1]
0
0
Space[0]
. data next
List
106
(
245
(
613
(
808
NULL
data next
Free
0
(
472
(
317
NULL
data next
List
245
(
613
(
808
NULL
data next
Free
0
(
472
(
317
(
106
NULL
data next
2.2. Частина 1. Побудова АТД
2.2.1.Постановка задачі
Змоделювати абстрактний тип даних (АТД) на базі статичного масиву, який використати в другій частині цього завдання. Переписати основні операції роботи з АТД і продемонструвати їх застосування при додаванні та вилученні елементів в АТД. Для реалізації цього задати послідовність з К > 10 цілих чисел (числа вводити з клавіатури). Всі парні числа додавати в АТД, а кожне непарне число має вилучати з АТД один елемент. Виводити на екран динаміку вмісту АТД під час обробки заданої послідовності.
2.2.2. Динаміка вмісту
Позначимо: P – початок черги; К – кінець черги.
В послідовності 5 4 3 0 1 2 -5 2 3, якщо зустрічається елемент зі значенням 0 застосовується функція wipe_out() – видалення всіх елементів черги, якщо зустрічається додатне число – виконується ф-ція push(), та ф-ція pop(), якщо число від’ємне.
1) K P
порожня
черга
2) P K
5
push(5)
3) P K
5
4
push(4)
4) P K
5
4
3
push(3)
5) K P
wipe_out()
6) P K
1
push(1)
7) P K
1
2
push(2)
8) P K
2
pop()
9) P K
2
2
push(2)
10) P K
2
2
3
push(3)
2.2.3. Результати виконання програми
/
2.3. Частина 2. Застосування АТД
2.3.1. Постановка задачі
Фiрма KRESS по зберiганню i збуту побутової техніки отримує вантажi з товарами по рiзним цiнам. Пізніше фiрма продає ці товари з 20-% надбавкою, причому товари, що отриманi раніше, продаються у першу чергу (стратегiя "перший отриманий - продається першим"). Товари з першої партії грузів продаються по ціні, на 20% вищій ніж закупочна. Після того як вся перша партія повністю розпродана, приступають до продажі другої партії, також по збільшеній на 20% цені, і т.д.
Написати програму, яка зчитує з текстового файлу записи про торговi операцiї двох типiв: операцiї по закупцi i операцiї по продажу. Запис про продажу мiстить префiкс "Р", після якого йде кiлькiсть товару, що продається. Запис про закупку мiстить префiкс "Z" , кiлькiсть товару і вартiсть всієї партiї. Пiсля зчитування запису про закупку товару виводити повідомлення про кiлькiсть товару, вартiсть одиниці товару i загальну вартiсть всiєї партiї. Пiсля зчитування запису про операцiю продажу товару виводити повідомлення про кiлькiсть товару, продану з кожної партії, цiну, по якiй був проданий кожний товар, суму, на яку були продані товари з кожної партії, а також загальну суму проданого товару, середню ціну одиниці товару і суму отриманого прибутку. Якщо кiлькiсть товару що є на складi недостатня для виконання замовлення на продаж товару, то продати всi товари зі складу і вивести повідомлення: "ХХХ одиниць товару немає на складi".
2.3.2. Алгоритм розв’язання задачі
В даному алгоритмі операція по закупці і продажу реалізована за допомогою черги.
Програма зчитує з текстового файлу записи про торговi операцiї двох типiв: операцiї по закупцi i операцiї по продажу.
З читується вхідний рядок (рядок складається з символу який означає запис про продажу , після якого йде кiлькiсть товару, що продається.).
Якщо символ Р (кiлькiсть товару, що продається).
Перевіряється кількість товару в черзі.
(Товар в черзі) виводити повідомлення про кiлькiсть товару, продану з кожної партії, цiну, по якiй був проданий кожний товар, суму, на яку були продані товари з кожної партії, а також загальну суму проданого товару, середню ціну одиниці товару і суму отриманого прибутку.
(Якщо кiлькiсть товару що є на складi недостатня для виконання замовлення на продаж товару) то продати всi товари зі складу і вивести повідомлення: "ХХХ одиниць товару немає на складi"
.Якщо символ Z (запис про закупку)
Перевіряється кількість товару в черзі.
(Товар в черзі) виводити повідомлення про кiлькiсть товару, вартiсть одиниці товару i загальну вартiсть всiєї партiї..
(Якщо кiлькiсть товару що є на складi недостатня для виконання замовлення на продаж товару) то продати всi товари зі складу і вивести повідомлення: "ХХХ одиниць товару немає на складi"
2.3.3. Результати виконання програми
/
Висновок.
В даній частині курсової роботи я дослідив внутрішнє представлення в пам’яті комп’ютера базових і похідних типів даних статичної структури та динамічних структур даних.
Індивідуальне завдання на курсову роботу вибрав згідно з своїми анкетними даними.
Розробив, відлагодив та протестував програму на мові С++і оформив звіт.
СПИСОК ЛІТЕРАТУРИ
Грегори К. Использование Visual С++. Специальное издание. - М.: «Диалектика», 1999.
Мешков А.В., Тихомиров Ю.В. Visual С++ и MFC. Пер. с англ. – 2-е изд. перераб. и доп. – СПб.: БХВ - Петербург, 2002. – 1040 с.
Страуструп Б. Язык программирования С++. Третье издание. - М.: «Издательство Бином», 1999.
Трамбле Ж., Соренсон П. Введение в структуры данных. – М.:Машиностроение, 1982
Уильям Топп, Уильям Форд. Структуры данных в С++. – М.:Бином, 2000 - 700 с
Додатки
Завдання 1:
// stdafx.h : include file for standard system include files,
// or project specific include files that are used frequently, but
// are changed infrequently
//
const int M = 100;
#pragma once
#include <cassert>
#include "q.h"
#include <stdio.h>
#include <tchar.h>
#include <iostream>
// q.h
template <class Item>
class queue
{
private:
Item INFO[M];
int count;
public:
queue( );
void pop( );
void push(const Item& entry);
bool empty( ) const { return (count == 0); }
Item front( ) const;
int size( ) const { return count; }
void show();
void muve();
bool full(){return (INFO[M-1] == M-1);};
void wipe_out();
bool same();
};
template <class Item>
queue<Item>::queue( )
{
count = 0;
INFO[0] = 1;
INFO[M-1] = 0;
}
template <class Item>
Item queue<Item>::front( ) const
{
assert(!empty( ));
return INFO[1];
}
template <class Item>
void queue<Item>::pop( )
{
muve();
count--;
}
template <class Item>
void queue<Item>::push(const Item& entry)
{
assert(!(count > M - 1));
++count;
INFO[++INFO[M-1]] = entry;
}
template <class Item>
void queue<Item>::show()
{
std::cout << "QUENE: ";
for(int i = INFO[0]; i < INFO[M-1]+1; i++){
std::cout << INFO[i] << " " ;
}
std::cout << std::endl;
}
template <class Item>
void queue<Item>::muve()
{
for(int i = INFO[0]; i < INFO[M-1]; i++){
INFO[i] = INFO[i+1];
}
--INFO[M-1];
}
template <class Item>
void queue<Item>::wipe_out()
{
for (int i=0; i<count; i++)
{
muve();
}
count = 0;
}
template <class Item>
bool queue<Item>::same()
{
bool b = false;
for (int i=0; i<count-1; i++)
if (INFO[i]==INFO[i+1]) { b = true; }
return b;
}
//main.cpp
#include "stdafx.h"
using namespace std;
int main()
{
queue<int> q;
int v[M], m;
int k = 0;
cout << "ENTER VALUE OF QUEUE TO CONTINUE OR TEXT TO EXIT..." << std::endl;
while(cin >> v[k++]) { m = k; }
q.show();
for(k = 0; k < m; k++)
{
if (v[k]==0) { q.wipe_out(); q.show(); }
if (v[k]>0) { q.push(v[k]); q.show(); }
if (v[k]<0) { q.pop(); q.show(); }
}
cout << "\nSIZE: " << q.size() << endl;
cout << "EMPTY: " << boolalpha << q.empty() << endl;
cout << "FULL: " << boolalpha << q.full() << endl;
cout << "FRONT: " << q.front() << endl;
cout << "THE SAME ELEMENTS IN QUEUE: " << q.same() << endl;
cin.get();
return 0;
}
Завдання 2:
//--------------------------------queue.cpp----------------------------------
// quere_4.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <string.h>
#include <conio.h>
using namespace std;
class quere{
double data[20]; // реалізяція черги
int left; // ліва сторона черги
int right; // права сторона черги
public:
quere();
void push(double); // метод додавання елемента
void pop(); // метод вилучення елемента
bool empty(); // метод перевірки на пустоту черги
bool full(); // метод перевірки на заповнення черги
double font(); // метод для переглядання елемента
void show (); // метод для показу вмісту черги на екран
void replaceElement(double);
};
quere::quere(){
left = 0;
right = 0;
}
void quere::push(double a){
if (right == 19)
throw "quere overflow exeption\n";
cout << "push: " << a << endl;
data[right] = a;
right++;
}
void quere::pop(){
if (empty())
throw "quere underflow exeption\n";
cout << "pop: " << font() << endl;
left++;
}
bool quere::empty(){
return left == right;
}
bool quere::full(){
return right==19;
}
double quere::font(){
return data[left];
}
void quere::show(){
int i = left;
int j = right;
cout << "quere: ";
while (i != j){
if (i != right+1)
cout << data[i] << " ";
i++;
}
cout << endl;
}
void quere::replaceElement(double element){
data[left] = element;
}
int _tmain(int argc, _TCHAR* argv[])
{
quere price;
quere realPrice;
quere count;
FILE* fi;
int numOfPart = 1;
char action;
int cnt;
int prc;
int good, num;
double profit = 0, fullSum = 0, fullCount = 0;
ifstream file("shop.txt");
for(int i=0; !file.eof(); i++){
file >> action;
if (action == 'Z'){
cout << "\nZ\n";
file >> cnt;
cout << "number of goods: " << cnt << endl;
count.push(cnt);
file >> prc;
cout << "price of goods: " << prc << endl;
cout << "price of one good: " << (double)prc/cnt << endl;
realPrice.push((double)prc/cnt);
price.push(((double)prc/cnt) + (((double)prc/cnt)*20)/100);
cout << endl;
}
if (action == 'P'){
cout << "\nP\n";
file >> num;
good = count.font
25.11.2012 22:11-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора