Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Представлення в пам’яті комп’ютера статичних даних
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2011
Тип роботи:
Курсова робота
Предмет:
Структура даних
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
/
Кафедра ЕОМ
КУРСОВА РОБОТА
( Частина 2 )
НА ТЕМУ:
"Представлення в пам’яті комп’ютера
статичних даних"
Вибір варіанту:
Вибір АТД:
2 = [8 +12 + 83 ] % 3 + 1
Вибір номера завдання:
2 = [8 + 83 ] % 10 + 1
Зміст
2. Завдання 2: Динамічні структури даних………………………………………………………………3
2.1. Теоретична частина……………………………………………………………………...…………………3
2.2. Частина 1. Побудова АТД………………………………………………………………...……………...6
2.2.1. Постановка задачі………………………………………………………………....…………………6
2.2.2. Динаміка вмісту………………………………………………………………...……………………..6
2.2.3. Результати виконання програми …………………………………………………………...8
2.3. Частина 2. Застосування АТД………………………………………………………………...………9
2.3.1. Постановка задачі………………………………………………………………...…………………9
2.3.2. Алгоритм розв’язання задачі……………………………………………………………….....9
2.3.3. Результати виконання програми……………………………………………………………10
Висновки………………………………………………………………...………………………………………………….11
Список літератури………………………………………………………………...…………………………………..12
Додатки………………………………………………………………...……………………………………………………13
2. Завдання 2: Динамічні структури даних
2.1 Теоретична частина
Чергою 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()
Повертає кількість елементів у черзі
Розглянемо статичну реалізацію черги на основі масиву з фіксованим рзміром. В наведенному далі лістінгу показано заголовочний файл для шаблонного класу queue, аналогічний класу queue зі стандартної бібліотеки шаблонів STL.
// ФАЙЛ: queue1.h (частина простору імен main_savitch_8B)
#ifndef MAIN_SAVITCH_QUEUE1_H
#define MAIN_SAVITCH_QUEUE1_H
#include <cstdlib> // Provides size_t
namespace main_savitch_8B
{
template <class Item>
class queue
{
public:
// ОПЕРАТОРИ ПЕРЕІМЕНОВАННЯ ТИПІВ ТА КОНСТАНТНІ ЧЛЕНИ
typedef std::size_t size_type;
typedef Item value_type;
static const size_type CAPACITY = 30;
// КОНСТРУКТОР
queue( );
// МОДИФІКУЮЧІ ФУНКЦІЇ-ЧЛЕНИ
void pop( );
void push(const Item& entry);
// КОНСТАНТНІ ФУНКЦІЇ-ЧЛЕНИ
bool empty( ) const { return (count == 0); }
Item front( ) const;
size_type size( ) const { return count; }
private:
Item data[CAPACITY];
size_type first;
size_type last;
size_type count;
// ДОПОМІЖНІ ФУНКЦІЇ-ЧЛЕНИ
size_type next_index(size_type i) const { return (i+1) % CAPACITY; }
};
}
#include "queue1.template" // Директива включення реалізації.
#endif
Файл реалізації класу queue показаний в наступному лістінгу:
#include <cassert> // Надає макрос assert.
namespace main_savitch
{
template <class Item>
const typename queue<Item>::size_type queue<Item>::CAPACITY;
template <class Item>
queue<Item>::queue( )
{
count = 0;
first = 0;
last = CAPACITY - 1;
}
template <class Item>
Item queue<Item>::front( ) const
{
assert(!empty( ));
return data[first];
}
template <class Item>
void queue<Item>::pop( )
{
assert(!empty( ));
first = next_index(first);
--count;
}
template <class Item>
void queue<Item>::push(const Item& entry)
{
assert(size( ) < CAPACITY);
last = next_index(last);
data[last] = entry;
++count;
}
}
Дек - особливий вид черги. Дек (від англ. deq - double ended queue, тобто черга із двома кінцями) - це така послідовність, у якій як додавання, так і вилучення елементів може здійснюватися з кожного із двох кінців. Окремі випадки дека - дек з обмеженим входом і дек з обмеженим виходом. Логічна й фізична структури дека аналогічні логічній і фізичній структурі кільцевої FіFO-черги. Однак, стосовно до дека доцільно говорити не про початок і кінець, а про лівий і правий кінці. Динамічна реалізація дека є об'єднанням стека і черги.
Основні операції над деком:
додавання элемента справа;
додавання элемента слева;
вилучення элемента справа;
вилучення элемента слева;
Задачі, що вимагають використання структури дека, зустрічаються в обчислювальній техніці і програмуванні набагато рідше, ніж завдання, реалізовані на структурі стека або черги. Як правило, вся організація дека виконується програмістом без яких-небудь спеціальних засобів системної підтримки.
Прикладом дека може бути, наприклад, якийсь термінал, у який вводяться команди, кожна з яких виконується якийсь час. Якщо ввести наступну команду, не дочекавшись, поки закінчиться виконання попередньої, то вона встане в чергу й почне виконуватися, як тільки звільниться термінал. Це FІFO-черга. Якщо ж додатково ввести операцію скасування останньої введеної команди, то отримаємо дек.
2.2. Частина 1. Побудова АТД
2.2.1. Постановка задачі
Змоделювати чергу або дек на базі статичного масиву згідно з завданням. Написати основні операції для роботи з чергою (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).
Примітка: після реалізації черги або деку працювати з ними як з абстрактними типами даних, а не як з масивами.
Змоделювати дек (тобто додавати i вилучати елементи можна з обох кінців). Після обробки всієї заданої вхідної послідовності продублювати всі елементи дека (тобто замість кожного одного елемента має стати підряд два однакових).
2.2.2. Динаміка вмісту
Вхідна послідовність: -1, 2, 3, 4, 5, 6, 7, -8, 9, 10, 11, 12, 13, 14.
Функція
Динаміка деку
Операція
queue ( )
к п
first = 0;
last = -1;
pop_left ( )
к п
deq underflow
push_right (2)
п к
2
last++;
data [last] = x;
count ++;
push_left (3)
п к
3
2
for (int i=0; i<n; i++)
copy [i] = data [i];
data [first] = x;
for (int i=0; i<n-1; i++)
data [i+1] = copy [i];
count ++;
last ++;
push_right (4)
п к
3
2
4
last++;
data [last] = x;
count ++;
push_left (5)
п к
5
3
2
4
for (int i=0; i<n; i++)
copy [i] = data [i];
data [first] = x;
for (int i=0; i<n-1; i++)
data [i+1] = copy [i];
count ++;
last ++;
push_right (6)
п к
5
3
2
4
6
last++;
data [last] = x;
count ++;
push_left (7)
п к
7
5
3
2
4
6
for (int i=0; i<n; i++)
copy [i] = data [i];
data [first] = x;
for (int i=0; i<n-1; i++)
data [i+1] = copy [i];
count ++;
last ++;
pop_right ( )
п к
7
5
3
2
4
6
last--;
push_left (9)
п к
9
7
5
3
2
4
for (int i=0; i<n; i++)
copy [i] = data [i];
data [first] = x;
for (int i=0; i<n-1; i++)
data [i+1] = copy [i];
count ++;
last ++;
push_right (10)
п к
9
7
5
3
2
4
last++;
data [last] = x;
count ++;
push_left (11)
п к
11
9
7
5
3
2
4
10
for (int i=0; i<n; i++)
copy [i] = data [i];
data [first] = x;
for (int i=0; i<n-1; i++)
data [i+1] = copy [i];
count ++;
last ++;
push_right (12)
п к
11
9
7
5
3
2
4
10
12
last++;
data [last] = x;
count ++;
push_left (13)
п к
13
11
9
7
5
3
2
4
10
12
for (int i=0; i<n; i++)
copy [i] = data [i];
data [first] = x;
for (int i=0; i<n-1; i++)
data [i+1] = copy [i];
count ++;
last ++;
push_right (14)
п к
13
11
9
7
5
3
2
4
10
12
14
deq overflow
2.2.3. Результати виконання програми
/
2.3. Частина 2. Застосування АТД
2.3.1. Постановка задачі
Автостоянка має одну полосу, на якій може бути розмiщено до 10 автомобiлiв. Машини в'їжджають з пiвденного кiнця стоянки i від'їжджають з пiвнiчного. Якщо автомобiль власника, що прийшов на стоянку забрати його, не розташований пiвнiчнiше за всі решту, то всi автомобiлi, що стоять пiвнiчнiше його, виїжджають iз зупинки, потiм виїжджає його машина і всі машини повертаються в початковому порядку. Якщо машина залишає гараж, то всi машини розташованi пiвденнiше, перемiщаються вперед на стiльки позицій, скiльки є вiльних мiсць в пiвнiчнiй частинi. Написати програму зчитування групи рядків, кожний з яких мiстить літеру "A" для прибуття i літеру "D" для вiдправлення, а також номер машини. Машини прибувають i вiдправляються в порядку, що задає цей список рядків. Програма має видавати повiдомлення при кожному прибутті або вiдправленні машини. При прибутті машини в ньому повинно говоритись, чи є на стоянці вiльне мiсце. Якщо вiльне мiсце вiдсутнє, машина чекає до тих пiр, поки воно не звiльниться, або до моменту зчитування рядка, що повідомляє про вiдправлення цього автомобiля. Якщо з'являється вiльне мiсце, повинно видаватись iнше повiдомлення. При вiдправленнi автомобiля повiдомлення повинно мiстити в собi кiлькiсть перемiщень машини в серединi стоянки (включаючи її вiдправлення, але не прибуття; це число рiвне 0, якщо машина була вiдправлена під час очiкування вільного місця).
2.3.2. Алгоритм розв’язання задачі
Створимо клас avto, у якому будемо зберігати 2 рядки, розмір яких користувач вводить на початку виконання програми. Один рядок зберігатиме номер авто, а інший – дію. Після чого у циклі будемо обробляти цю послідовність.
Ініціалізуємо 2 черги – автостоянка parking та черга у автостоянку cherga.
Якщо введена дія А (додати у автостоянку), то спочатку за допомогою функції full аналізуємо, чи на автостоянці є вільні місця. Якщо місць немає – додаємо до черги (черга cherga ), якщо місця є – додаємо у автостоянку (черга parking).
Якщо введена дія D (вилучити авто ) – ми аналізуємо, чи є дане авто в черзі parking. Якщо є – вилучаємо його і у разі наявності автомобіля у черзі cherga (перевірка за допомогою функції empty ) переміщаємо його у кінець черги parking. А якщо немає авто у parking, перевіряємо чи є він у черзі cherga і , відповідно, якщо він є, то вилучаємо його із черги cherga. Якщо авто ніде немає – виводимо відповідне повідомлення.
Якщо введена інша літера, виводимо повідомлення про помилку.
2.3.3. Результати виконання програми
/
Висновки
У процесі виконання курсової роботи я дослідив внутрішнє представлення в пам’яті комп’ютера базових і похідних типів даних статичної структури та динамічних структур даних.
Оволодів необхідними для спеціалістів комп’ютерної інженерії знаннями та навиками для роботи з даними. Успішно виконав поставлені завдання та розробив програмні продукти з використанням АДТ, які розв’язують поставлені задачі.
Список літератури
Лисак Т. А. Основи представлення даних в пам'яті комп'ютера: Конспект лекцій (частина І ) з дисципліни “Програмування. Частина IIІ. Структури даних та алгоритми". – Львів: Видавництво НУ “Львівська політехніка”, 2010 – 37 с.
Ніколас Вірт. Алгоритми та структури даних – Видавництво «Мир» ,1989 р. 3 книги
Уильям Топп, Уильям Форд. Структуры данных в С++. – М.:Бином, 2000 - 700 с
Трамбле Ж., Соренсон П. Введение в структуры данных. – М.:Машиностроение, 1982
Додатки
Частина 1. Побудова АТД
Частина 2. Застосування АТД
avto.h
#pragma once
class avto
{
public:
avto(int i);
int *Numb;
char *action;
int Size;
~avto(void);
};
avto.cpp
#include "avto.h"
#include <iostream>
using namespace std;
avto::avto(int i)
{
Size=i;
Numb = new int [Size];
action = new char [Size];
for (int i=0; i<Size; i++)
{
cout<<"Введiть номер автомобiля: ";
cin>>Numb [i];
cout<<"Введiть дiю (A-прибуття, D-вiдправлення): ";
cin>>action [i];
cout<<endl;
}
}
avto::~avto(void)
{
}
queue.h
#pragma once
class queue
{
int count;
static const int first = 0 ;
int last;
int data [10];
public:
queue(void);
~queue(void);
void push_left (int х);
void push_right (int х);
void pop_left ();
void pop_right ();
int front_left ();
int front_right ();
bool Empty ();
bool full () ;
void Show ();
};
queue.cpp
#include "queue.h"
#include <iostream>
using namespace std;
queue::queue(void)
{
for (int i=0; i<10; i++)
data [i]=0;
count = 0;
last = -1;
}
queue::~queue(void)
{
}
void queue::push_left (int x)
{
if (last>=9)
cout <<endl<<"### deq overflow ###"<<endl<<endl;
else
{
int copy [9];
for (int i=0; i<9; i++)
copy [i] = data [i];
data [first] = x;
for (int i=0; i<9; i++)
data [i+1] = copy [i];
count ++;
last ++;
}
}
void queue::push_right (int x)
{
if (last>=9)
cout <<endl<<"### deq overflow ###"<<endl<<endl;
else
{
last++;
data [last] = x;
count ++;
}
}
void queue::pop_left ()
{
if (last==-1)
cout<<endl<<"### deq underflow ###"<<endl<<endl;
else
{
for (int i=0; i<9; i++)
data [i] = data [i+1];
last--;
count--;
}
}
void queue::pop_right ()
{
if (last==-1)
cout<<endl<<"### deq underflow ###"<<endl<<endl;
else
{
last--;
count--;
}
}
int queue::front_left ()
{
return data [first];
}
int queue::front_right ()
{
return data [last];
}
bool queue::Empty ()
{
if (last==-1)
return true;
else
return false;
}
bool queue::full ()
{
if (last==9)
return true;
else
return false;
}
void queue::Show ()
{
cout<<"Вмiст деку:"<<endl;
for (int i=0; i<count; i++)
cout<<" "<<data [i];
cout<<endl;
}
main.cpp
#include "queue.h"
#include <iostream>
#include "avto.h"
using namespace std;
int main ()
{
setlocale (LC_ALL,"Ukrainian");
cout<<"Введiть кiлькiсть автомобiлiв: ";
int tmp;
cin>>tmp;
cout<<endl;
avto mashines (tmp);
queue parking;
queue cherga;
for (int i=0; i<mashines.Size; i++)
{
if (mashines.action[i]=='A')
{
if (parking.full ()==true)
{
cherga.push_right(mashines.Numb[i]);
cout<<"Авто № "<<mashines.Numb[i]<<" добавлено в чергу"<<endl;
}
else
{
cout<<"Є вiльне мiсце на автостоянцi"<<endl;
parking.push_right(mashines.Numb[i]);
cout<<"Автомобiль № "<<mashines.Numb[i]<<" прибув на автостоянку"<<endl;
}
}
else
{
if (mashines.action[i]=='D')
{
if (parking.Empty()==true)
cout<<"Неможливе вилучення з порожньої автостоянки"<<endl;
else
{
queue copy;
int size=0;
while (parking.Empty()==false)
{
copy.push_right(parking.front_left());
parking.pop_left();
size++;
}
while (copy.Empty()==false)
{
parking.push_right(copy.front_left());
copy.pop_left();
}
int buffer [10];
for (int j=0; j<10; j++)
buffer [j]=-1;
int klk=0;
tmp=0;
for (int j=0; j<size; j++)
{
if (parking.front_left()==mashines.Numb[i])
{
parking.pop_left();
cout<<"Авто № "<<mashines.Numb[i]<<"
вiдправилось з автостоянки "<<endl;
cout<<"Кiлькiсть перемiщень при цьому: "<<klk<<endl;
cout<<endl;
}
else
{
buffer [tmp]=parking.front_left();
tmp++;
klk++;
parking.pop_left();
}
}
for (int q=0; q<tmp; q++)
parking.push_right(buffer[q]);
if (klk==size)
cout<<"Авто № "<<mashines.Numb[i]<<" немає на автостоянцi "<<endl;
else
{
if (cherga.Empty()==false)
{
parking.push_right(cherga.front_left());
cout<<"Авто № "<<cherga.front_left()<<" прибуло iз черги на автостоянку "<<endl;
cherga.pop_left();
}
}
if (cherga.Empty()==false)
{
tmp=0;
int klk_ch=0;
while (cherga.Empty()==false)
{
if (cherga.front_left()==mashines.Numb[i])
{
cherga.pop_left();
cout<<"Авто № "<<mashines.Numb[i]<<"
вiдправилось з черги "<<endl;
cout<<endl;
}
else
{
buffer [tmp]=cherga.front_left();
tmp++;
klk++;
cherga.pop_left();
}
}
for (int q=0; q<tmp; q++)
cherga.push_right(buffer[q]);
}
}
}
else
cerr<<"Помилкове введення даних у програму!"<<endl;
}
}
system ("pause");
return 0;
}
програмний продукт продемонстровано і захищено
_________________ ________________ _______________
Kузьо М.М дата оцінка
05.01.2013 17:01-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора