Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2011
Тип роботи:
Звіт
Предмет:
Структури даних та алгоритми
Група:
КІ
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет „Львівська політехніка”
Кафедра ЕОМ
Звіт
до курсової роботи (Частина 2)
з дисципліни: “ Програмування. Частина III. Структури даних та алгоритми ”
Процес знаходження номеру варіанта індивідуального завдання
Вибір АТД:
№ = [(день народження) + (місяць народження) + (ASCII–код першої літери прізвища – велика латинська літера) ] % 3 + 1 = [(26) + (11) + (75) ] % 3 + 1 = 2
Примітка: 1 – стек, 2 – черга, 3- список.
Вибір номера завдання:
№ = [(день народження) + (ASCII–код першої літери прізвища – велика латинська літера) ] % 10 + 1 =
= [(26) + (75) ] % 10 + 1 =2
Зміст
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) – покажчик кінця черги
Наведемо динаміку вмісту черги під час обробки заданої послідовності:
Вхідна послідовність: { 4, 8, 4, 9, 7, 3, 1, 2, 6, 8, 3 }
1)
-порожня черга
2)
4
-push(4)
3)
4
8
-push(8)
4)
4
8
4
-push(4)
5)
8
4
-pop();
6)
4
-pop();
7)
-pop(); Порожня черга
8)
-pop(); queue underflow
9)
2
-push(2);
10)
2
6
-push(6);
11)
2
6
8
-push(8);
12)
6
8
-pop();
2. 3. Результат виконання програми
/
3. Частина 2. Застосування АТД
3.1. Постановка задачі
2. Автостоянка має одну полосу, на якій може бути розм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кування вільного місця).
3.2. Алгоритм розв’язання задачі
Для розв’язку цієї задачі потрібно:
1.Написати клас який реалізує всі функції потрібні для реалізації цього завдання.
2.Написана функція pop реалізує вилучення з черги.
3. Написана функція push реалізує додавання в чергу нового елемента .
3.3. Результати виконання програми
/
Висновки
Дослідження внутрішнього представлення в пам’яті комп’ютера базових і похідних типів даних статичної структури та динамічних структур даних.
Список літератури
Матвейчук Т. А. Основи представлення данних в пам'яті комп'ютера: Конспект лекцій (частина І ) з дисципліни “Програмування. Частина IIІ. Структури даних та алгоритми". – Львів: Видавництво НУ “Львівська політехніка”, 2010 – 37 с.
Грегори К. Использование Visual С++. Специальное издание. - М.: «Диалектика», 1999.
Мешков А.В., Тихомиров Ю.В. Visual С++ и MFC. Пер. с англ. – 2-е изд. перераб. и доп. – СПб.: БХВ - Петербург, 2002. – 1040 с.
Страуструп Б. Язык программирования С++. Третье издание. - М.: «Издательство Бином», 1999.
Трамбле Ж., Соренсон П. Введение в структуры данных. – М.:Машиностроение, 1982
Уильям Топп, Уильям Форд. Структуры данных в С++. – М.:Бином, 2000 - 700 с
Додатки
Частина 1. Побудова АТД
// queue1.h
#define queue 5
class Tqueue
{
private:
int data[queue]; // масив елементів черги
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==queue)
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. Застосування АТД
// queue.h
#include <iostream>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
class cherga {
int i, st[10]; int south;
public:
void set () { south=9;
for (int i=0;i<10;i++)
st[i]=0;
}
void push(int j) {
st[south]=j;
south--;
}
void pop() {
south++;
}
void show_ch() {
for (int i=0;i<=9;i++)
cout<< st[i]<<" ";
cout<<endl;
}
void set_after(int j) { south=j;}
void janje(int i,int j) {
for (;j<i;i--){
st[i]=st[i-1];
if (i==j) st[i-1]=0;
}
st[j]=0;st[j+1]=0;
}
int empty() { if (south<=-1) return 1; else return 0;}
int front() { return st[south]; }
int size() { return (9-south); }
int show_south() { return south;}
int ret_firts() { return st[0];}
} ;
// main.cpp
#include "queue.h"
int main()
{
cherga ob;
ob.set();
char a='a',carch; int car, tmp_name,tmp_index,tmp_indexST,tmp,k, buffer[10],bufL=0,lich;
FILE *fp;
if ((fp = fopen("data.txt","r"))==NULL) {
cout<<"can't open file"<<endl;
exit(1);
} else cout<<"file opened"<<endl;
while (a!=EOF) {
a = getc(fp);
if (a=='A')
{
lich=0;
carch = getc(fp);
car=carch-0x30;
if (ob.empty()==1){
cout<<endl<<"ztojanka zapovnena, zachekajte koly zvilnetsa mistse "<<endl;
cout<<"mashyna "<<car<<" staje v chergu"<<endl;
ob.push(car);
goto next;
}
ob.push(car);
ob.show_ch();
cout<<"mashyna z nomerom "<<car<<"prybula na zupynku"<<endl;
}
else if(a=='B') {
carch = getc(fp);
car=carch-0x30;
k=ob.show_south();
int temp;
tmp_index=tmp_indexST=ob.show_south();
while (k!=10) {
temp=ob.front();
if (car==temp) { tmp_index=k; tmp_name=ob.front(); break; }
ob.pop();
k++;}
ob.set_after(tmp_index+1);
if (tmp_index==9) goto jamp;
cout<<endl<<"Mashyny ";
for (int i=tmp_index+1;i<10;i++)
{
cout<<ob.front()<<" ";
ob.pop();
}
cout<<"vyjihaly shob dady dorogy"<<endl;
jamp: cout<<"mashyna z nomerom "<<car<<"pokynula zupynku"<<endl;
ob.janje(tmp_index,tmp_indexST);
ob.set_after(tmp_indexST+1);
ob.show_ch();cout<<endl<<"----------------------"<<endl;
if (bufL!=0)
while (bufL<0)
{
ob.push(buffer[bufL]);
ob.show_ch();
bufL--;
}
}
next:;
}
getch();
return 0;
}
18.11.2012 16:11-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора