Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Програмування. Частина III. Структури даних та алгоритми
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2011
Тип роботи:
Курсова робота
Предмет:
Структури даних та алгоритми
Група:
КІ
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет „Львівська політехніка”
Кафедра ЕОМ
Звіт
з курсової роботи (частина 2)
з дисципліни:
" Програмування. Частина III. Структури даних та алгоритми "
Вибір АТД:
№ = [(день народження) + (місяць народження) + (ASCII–код першої літери прізвища – велика латинська літера) ] % 3 + 1 =
= (19+11+83)%3 +1 = (113)%3+1 = 2+1 = 3 (список)
Примітка: 1 – стек, 2 – черга, 3- список.
Вибір номера завдання:
№ = [(день народження) + (ASCII–код першої літери прізвища – велика латинська літера) ] % 10 + 1 =
= (24+83)%10+1 = 102%10+1 = 2+1 = 3.
Завдання:
Частина 1
Змоделювати лінійний зв'язаний одно- або двонаправлений список, реалізований за допомогою вказівників (вибір здійснити виходячи з умови задачі). Написати основні операції для роботи зі списком і продемонструвати правильність їх виконання. Для цього (якщо в завданні не вказано інший спосіб) в програмі на вході задати послідовність з К (К>=10) цілих чисел (числа вводити з клавіатури). Всі додатні і нульові числа послідовно вставляти у відповідне місце списку так, щоб список весь час залишався відсортованим по зростанню (точніше по неспаданню) значень його елементів. Кожне від'ємне число має вилучати зі списку всі елементи, значення яких дорівнюють модулю цього від'ємного числа. Якщо в списку таких елементів не буде знайдено, то видавати відповідне повідомлення про відсутність цього числа у списку. Виводити на екран динаміку вмісту списку під час обробки заданої послідовності. Вхідну послідовність чисел задати такою, щоб вона демонструвала роботу всіх основних операцій.
Побудувати список згідно заданої вхідної послідовності чисел, показуючи динаміку його вмісту. Після обробки всієї послідовності розбити побудований список на два рівних (якщо кількість елементів списку парна) або майже рівних (якщо кількість елементів списку непарна) по довжині списка.
Частина 2
Розв’язати задачу використовуючи АТД "СПИСОК"
3. Написати програму, що моделює обчислювальну систему з кiлькома користувачами. Кожен користувач має свiй унiкальний iдетифiкацiйний номер ID i бажає виконати на ЕОМ ряд операцiй. У будь-який момент часу ЕОМ може виконувати одночасно тiльки одну операцiю. Кожний вхiдний рядок вiдповiдає одному користувачу i мiстить його ID, за яким йде початок роботи, а за ним - набiр цiлих чисел, кожне з яких представляє тривалість кожної з виконуваних користувачем операцiй. Вхiднi данi впорядкованi по зростанню часу початку роботи. Весь час задається в секундах. Вважається, що користувач не видає запрос на проведення наступної операцiї до тих пiр, поки не закiнчилось виконання попередньої, а ЕОМ виконує операцiї за принципом "перший, що поступив, обслуговується першим". Програма повинна iмiтувати роботу системи i виводити повiдомлення, що мiстять ID користувача i час початку i закiнчення проведення операцiї. В кiнцi процесу моделювання вивести середній час очiкування для кожної операцiї. Час очiкування - це рiзниця мiж тим часом, коли був виданий запрос на виконання операцiї, i початком її виконання
Зміст
Завдання на роботу 2
2 Завдання 2: Динамічні структури даних 4
2.1 Теоретична частина 4
2.2 Частина 1. Побудова АТД 5
2.2.1 Постановка задачі 5
2.2.2 Динаміка вмісту 5
2.2.3 Результати виконання програми 6
2.3Частина 2. Застосування АТД 7
2.3.1 Постановка задачі 7
2.3.2 Алгоритм розв’язання задачі 8
2.3.3 Результати виконання програми 8
Висновки 9
Список літератури 9
Додатки 10
2. Завдання 2: Динамічні структури даних
Теоретична частина
В програмуванні та комп'ютерних науках структу́ри да́них — це способи організації даних в комп'ютерах. Часто разом зі структурою даних пов'язується і специфічний перелік операцій, що можуть бути виконаними над даними, організованими в таку структуру.
Правильний підбір структур даних є надзвичайно важливим для ефективного функціонування відповідних алгоритмів їх обробки. Добре побудовані структури даних дозволяють оптимізувати використання машинного часу та пам'яті комп'ютера для виконання найбільш критичних операцій.
Відома формула «Програма = Алгоритми + Структури даних» дуже точно виражає необхідність відповідального ставлення до такого підбору. Тому іноді навіть не обраний алгоритм для обробки масиву даних визначає вибір тої чи іншої структури даних для їх збереження, а навпаки.
Підтримка базових структури даних, які використовуються в програмуванні, включена в комплекти стандартних бібліотек найбільш розповсюджених мов програмування, таких як Standart Template Library для C++, Java API, Microsoft.NET, тощо.
Лінійний список – це скінчена послідовність однотипних елементів (вузлів), можливо, з повтореннями. Список розташовується в пам'яті довільним чином. Кожний вузол однонаправленого лінійного зв'язаного списку містить вказівник на наступний вузол списку, що дозволяє переміщуватись вперед по списку. Кожний вузол двонаправленого лінійного зв'язаного списку містить вказівники на попередній і наступний вузли списку, що дозволяє переміщуватись по списку вперед та назад.
Вставка і вилучення вузлів у списку реалізовані ефективно: змінюються тільки вказівники. З іншого боку, довільний доступ до вузлів списку підтримується погано: щоб прийти до певного вузла списку, треба відвідати всі попередні вузли. Крім того, на відміну від стеків або черг, додатково витрачається пам'ять під один або два вказівники на кожний елемент списку.
Список росте дуже просто: додавання кожного нового елемента приводить до того, що вказівники на попередній і наступний вузли списку, між якими вставляється новий вузол, міняють свої значення. У новому елементі таким вказівникам присвоюється значення адрес сусідніх елементів.
Список використовує тільки такий об'єм пам'яті, який потрібний для наявної кількості елементів.
2.2Частина 1: Побудова АТД
1.Постановка задачі
Змоделювати лінійний зв'язаний одно- або двонаправлений список, реалізований за допомогою вказівників (вибір здійснити виходячи з умови задачі). Написати основні операції для роботи зі списком і продемонструвати правильність їх виконання. Для цього (якщо в завданні не вказано інший спосіб) в програмі на вході задати послідовність з К (К>=10) цілих чисел (числа вводити з клавіатури). Всі додатні і нульові числа послідовно вставляти у відповідне місце списку так, щоб список весь час залишався відсортованим по зростанню (точніше по неспаданню) значень його елементів. Кожне від'ємне число має вилучати зі списку всі елементи, значення яких дорівнюють модулю цього від'ємного числа. Якщо в списку таких елементів не буде знайдено, то видавати відповідне повідомлення про відсутність цього числа у списку. Виводити на екран динаміку вмісту списку під час обробки заданої послідовності. Вхідну послідовність чисел задати такою, щоб вона демонструвала роботу всіх основних операцій.
Побудувати список згідно заданої вхідної послідовності чисел, показуючи динаміку його вмісту. Після обробки всієї послідовності розбити побудований список на два рівних (якщо кількість елементів списку парна) або майже рівних (якщо кількість елементів списку непарна) по довжині списка.
2.Динаміка вмісту
Виберу якусь вхідну послідовність для виконання програми
1,2,3,-8,4,5,6,-7,8,9, 10
Намалюю динаміку вмісту списку після введення таких даних:
Стан списку після виконання умови (розбиття на два списки(майже рівні)).
список 1
список 2
3.Результати виконання програми
Програма виводить динаміку списку в текстовому вигляді і по завершенню дублює вміст списку, як було задано в умові.
2.3.Частина 2. Застосування АТД
1.Постановка задачі
Розв’язати задачу використовуючи АТД "СПИСОК"
3. Написати програму, що моделює обчислювальну систему з кiлькома користувачами. Кожен користувач має свiй унiкальний iдетифiкацiйний номер ID i бажає виконати на ЕОМ ряд операцiй. У будь-який момент часу ЕОМ може виконувати одночасно тiльки одну операцiю. Кожний вхiдний рядок вiдповiдає одному користувачу i мiстить його ID, за яким йде початок роботи, а за ним - набiр цiлих чисел, кожне з яких представляє тривалість кожної з виконуваних користувачем операцiй. Вхiднi данi впорядкованi по зростанню часу початку роботи. Весь час задається в секундах. Вважається, що користувач не видає запрос на проведення наступної операцiї до тих пiр, поки не закiнчилось виконання попередньої, а ЕОМ виконує операцiї за принципом "перший, що поступив, обслуговується першим". Програма повинна iмiтувати роботу системи i виводити повiдомлення, що мiстять ID користувача i час початку i закiнчення проведення операцiї. В кiнцi процесу моделювання вивести середній час очiкування для кожної операцiї. Час очiкування - це рiзниця мiж тим часом, коли був виданий запрос на виконання операцiї, i початком її виконання
2.Алгоритм розв’язання задачі
Для розв’язання цієї задачі використовую список, створений у частині 1. Додаю до нього функції Add(Node* list, int c, int n); void DeleteAll(Node* list); void Differ(Node* list) та void Print(Node* list);
для добавлення елементу (Add). для виводу на екран (Print),та для розрізняння чисел (Differ). В файлі main.cpp запрограмував введення з клавіатури вхідних даних.
3.Результати виконання програми
Висновки
Виконуючи цю частину курсової роботи я навчився дослідження внутрішнє представлення в пам’яті комп’ютера базових і похідних типів даних статичної структури та динамічних структур даних, а саме детально познайомився з структурою даних списку і навчився використовувати її на прикладі конкретної задачі.
Список літератури
Матвейчук Т. А. Основи представлення данних в пам'яті комп'ютера: Конспект лекцій (частина І ) з дисципліни “Програмування. Частина IIІ. Структури даних та алгоритми". – Львів: Видавництво НУ “Львівська політехніка”, 2010 – 37 с.
Конспект лекцій.
Додатки
До завдання 1
#include <iostream>
using namespace std;
struct Node
{
int data;
Node* next;
};
// Розруковати весь список
void Print(Node* list);
// Добавити новий елемент
void Add(Node** list, int data);
// Видалити елемент
void Delete(Node* list, int data);
// Видалаити весь список
void DeleteAll(Node* list);
// Розділити список
Node* SplitList(Node* list);
// Отримати довжину списку
int GetLength(Node* list);
int main()
{
int k = 10;
int data;
cin>>data;
Node* list = new Node;
list->data = data;
list->next = NULL;
Print(list);
for(int i = 1; i < k; i++)
{
int data;
cin>>data;
if (data >= 0)
{
Add(&list, data);
}
else
{
Delete(list, -data);
}
}
Node* list2 = SplitList(list);
cout<<endl<<"Two lists:"<<endl;
Print(list);
Print(list2);
DeleteAll(list);
DeleteAll(list2);
return 0;
}
void Print(Node* list)
{
cout<<"List: ";
Node* current = list;
while(current != NULL)
{
cout << current->data << " ";
current = current->next;
}
cout<<endl;
}
void Add(Node** list, int data)
{
cout<<"Added: "<<data<<endl;
Node* item = new Node;
item->data = data;
item->next = NULL;
Node* current = *list;
if (current->data > data)
{
item->next = current;
*list = item;
Print(*list);
return;
}
while(current->next != NULL && current->next->data < data)
{
current = current->next;
}
item->next = current->next;
current->next = item;
Print(*list);
}
void Delete(Node* list, int data)
{
cout<<"Deleting "<<data<<endl;
int num = 0;
while(list != NULL && list->data == data)
{
Node* item = list;
list = list->next;
delete item;
num++;
}
if (list == NULL)
{
cout<<"Deleted "<<num<<" item(s)"<<endl;
return;
}
Node* current = list;
while(current->next != NULL)
{
if (current->next->data == data)
{
Node* item = current->next;
current->next = item->next;
delete item;
num++;
}
else
{
current = current->next;
}
}
cout<<"Deleted "<<num<<" item(s)"<<endl;
Print(list);
}
void DeleteAll(Node* list)
{
while(list != NULL)
{
Node* item = list;
list = list->next;
delete item;
}
}
Node* SplitList(Node* list)
{
int len = GetLength(list) / 2;
Node *list2;
for(int i = 1; i<len;i++)
{
list = list->next;
}
list2 = list->next;
list->next = NULL;
return list2;
}
int GetLength(Node* list)
{
int len = 0;
while(list != NULL)
{
len++;
list = list->next;
}
return len;
}
До завдання 2
#include <iostream>
using namespace std;
struct Node
{
int c;
int n;
Node* next;
};
Node* Add(Node* list, int c, int n)
{
Node* item = new Node;
item->c = c;
item->n = n;
item->next = NULL;
list->next = item;
return item;
}
void DeleteAll(Node* list);
void Differ(Node* list)
{
list->c *= list->n;
list->n--;
if (list->n == 0)
{
delete list->next;
list->next = NULL;
}
while(list->next != NULL)
{
list->next->n--;
if (list->next->n < 0)
{
delete list->next;
list->next = NULL;
}
else
{
list->next->c *= list->next->n + 1;
list = list->next;
}
}
}
void Print(Node* list)
{
while(list != NULL)
{
if (list->c > 1 || list->n == 0)
{
cout<<list->c;
}
if (list->n > 0)
{
cout<<"X";
}
if (list->n > 1)
{
cout<<"^"<<list->n;
}
if (list->next != NULL)
{
cout<<"+";
}
list = list->next;
}
cout<<endl;
}
int main()
{
int n;
cout<<"Enter n: ";
cin>>n;
Node* list = new Node;
cout<<"C1=";
cin>>list->c;
cout<<"n1=";
cin>>list->n;
list->next = NULL;
Node* current = list;
for(int i = 2;i<=n;i++)
{
int n,c;
cout<<"C"<<i<<"=";
cin>>c;
cout<<"n"<<i<<"=";
cin>>n;
current = Add(current, c, n);
}
Print(list);
Differ(list);
Print(list);
DeleteAll(list);
return 0;
}
void DeleteAll(Node* list)
{
while(list != NULL)
{
Node* item = list;
list = list->next;
delete item;
}
}
Програмний продукт перевірив Кузьо М.
дата підпис
10.12.2012 17:12-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора