Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Динамічні структури даних
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2012
Тип роботи:
Курсова робота
Предмет:
Програмування
Частина тексту файла (без зображень, графіків і формул):
Національний університет “Львівська політехніка”
Кафедра ЕОМ
Курсова робота ( частина ІІ )
На тему:
“ Динамічні структури даних ”
з дисципліни:
"Програмування"
Вибір варіантів індивідуального завдання:
Вибір АТД: № = [(16) + (1993) + (97) ] % 4 + 1 = 3 ( АТД Список)
Номер завдання: № = [(10) + (1993) + (71) ] % 10 + 1=5
ЗАВДАННЯ НА КУРСОВУ РОБОТУ
Завдання 1
Побудувати список згідно заданої вхідної послідовності чисел, показуючи динаміку його вмісту. Після обробки всієї послідовності перевірити, чи перший елемент списку містить значення 0. Якщо це так, то додати ще один елемент зі наченням 0 в кінець списку, якщо ні – то зі списку вилучити всі елементи зі наченням 0 .
Завдання 2
Поліном від трьох змінних ( X , Y , Z ) представити у вигляді циклічного списку, в якому кожний вузол має п’ять полів: одне – для коефіцієнта члена поліному , друге – для показника степеня змінної X , третє – для показника степеня змінної Y, четверте – для показника степеня змінної Z, п’яте – для вказівника на наступний вузол списку. Елементи списку мають бути впорядковані спочатку по зменшенню степеня Х, пізніше по зменшенню степеня Y, а після цього по зменшенню степеня Z. Структура збереження поліномів повинна забезпечувати ефективне виконання такої операції над ними:
Обчислення полінома по заданим значенням X , Y , Z .
ЗМІСТ
1. ТЕОРЕТИЧНА ЧАСТИНА
2. ЗАВДАННЯ 3. ПОБУДОВА АТД
2.1. Постановка задачі
2.2. Динаміка вмісту
2.3. Результати виконання програми
3. ЗАВДАННЯ 4. ЗАСТОСУВАННЯ АТД
3.1. Постановка задачі
3.2. Алгоритм розв’язання задачі
3.2.1. Словесний опис алгоритму
3.2.2. Граф-схема алгоритму
3.3. Результати виконання програми
ВИСНОВКИ
СПИСОК ЛІТЕРАТУРИ
ДОДАТОК А. ТЕКСТ ПРОГРАМИ ДО ЗАВДАННЯ 3
ДОДАТОК Б. ТЕКСТ ПРОГРАМИ ДО ЗАВДАННЯ 4
1.ТЕОРЕТИЧНА ЧАСТИНА
Лінійний список – це скінчена послідовність однотипних елементів (вузлів), можливо, з повтореннями. Список розташовується в пам'яті довільним чином. Кожний вузол однонаправленого лінійного зв'язаного списку містить вказівник на наступний вузол списку, що дозволяє переміщуватись вперед по списку. Кожний вузол двонаправленого лінійного зв'язаного списку містить вказівники на попередній і наступний вузли списку, що дозволяє переміщуватись по списку вперед та назад.
Вставка і вилучення вузлів у списку реалізовані ефективно: змінюються тільки вказівники. З іншого боку, довільний доступ до вузлів списку підтримується погано: щоб прийти до певного вузла списку, треба відвідати всі попередні вузли. Крім того, на відміну від стеків або черг, додатково витрачається пам'ять під один або два вказівники на кожний елемент списку.
Список росте дуже просто: додавання кожного нового елемента приводить до того, що вказівники на попередній і наступний вузли списку, між якими вставляється новий вузол, міняють свої значення. У новому елементі таким вказівникам присвоюється значення адрес сусідніх елементів.
Список використовує тільки такий об'єм пам'яті, який потрібний для наявної кількості елементів.
В бібліотеці стандартних шаблонів STL існує клас list, що підтримує двунаправлений лінійний список. В класі list визначений конструктор list, що створює порожній список. Нижче в таблиці наведені основні функції-члени класу list:
Функція-член
Опис
begin ()
Повертає двонаправлений ітератор для першого елемента
end ()
Повертає двонаправлений ітератор для позиції за останнім елементом
insert (pos , elem)
Вставляє копію elem в позицію ітератора pos і повертає позицію нового елемента
push_back (elem)
Додає копію elem в кінець списку
push_front (elem)
Вставляє копію elem в початок списку
pop_back (elem)
Вилучає останній елемент списку (не повертаючи його)
pop_front (elem)
Вилучає перший елемент списку (не повертаючи його)
remove (val)
Вилучає всі елементи списку зі значенням val
erase (pos)
Вилучає елемент в позиції ітератора pos і повертає позицію наступного елемента списку
clear ()
Вилучає всі елементи списку (контейнер залишається порожнім)
2. ЗАВДАННЯ 3. ПОБУДОВА АТД
2.1. Постановка задачі
Змоделювати лінійний зв'язаний одно- або двонаправлений список, реалізований за допомогою вказівників. Написати основні операції для роботи зі списком і продемонструвати правильність їх виконання. Для цього в програмі на вході задати послідовність з К (К>=10) різних цілих чисел (числа вводити з клавіатури). Всі додатні і нульові числа послідовно вставляти у відповідне місце списку так, щоб список весь час залишався відсортованим по зростанню значень його елементів. Кожне від'ємне число має вилучати зі списку всі елементи, значення яких дорівнюють модулю цього від'ємного числа. Якщо в списку таких елементів не буде знайдено, то видавати відповідне повідомлення про відсутність цього числа у списку і продовжувати роботу. Виводити на екран динаміку вмісту списку під час обробки заданої послідовності. Вхідну послідовність чисел задати такою, щоб вона демонструвала роботу всіх основних операцій.
2.2. Динаміка вмісту
Послідовність з 10 чисел: 1 2 0 -1 3 2 2 -3 4 0
Схематичне зображення списку після обробки всієї послідовності :
List *tmp = new List
tmp->push(1);
0
0
Space[14]
0
14
Space[13]
0
13
Space[12]
0
12
Space[11]
0
11
Space[10]
0
10
Space[9]
0
9
Space[8]
0
8
Space[7]
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
0
0
Space[14]
0
14
Space[13]
0
13
Space[12]
0
12
Space[11]
0
11
Space[10]
0
10
Space[9]
0
9
Space[8]
0
8
Space[7]
0
7
Space[6]
0
6
Space[5]
0
5
Space[4]
0
4
Space[3]
0
3
Space[2]
1
0
Space[1]
0
0
Space[0]
data next
tmp->push(2);
tmp->push(0);
0
0
Space[14]
0
14
Space[13]
0
13
Space[12]
0
12
Space[11]
0
11
Space[10]
0
10
Space[9]
0
9
Space[8]
0
8
Space[7]
0
7
Space[6]
0
6
Space[5]
0
5
Space[4]
0
4
Space[3]
2
0
Space[2]
1
2
Space[1]
0
0
Space[0]
data next
0
0
Space[14]
0
14
Space[13]
0
13
Space[12]
0
12
Space[11]
0
11
Space[10]
0
10
Space[9]
0
9
Space[8]
0
8
Space[7]
0
7
Space[6]
0
6
Space[5]
0
5
Space[4]
0
0
Space[3]
2
3
Space[2]
1
2
Space[1]
0
0
Space[0]
data next
tmp->pop(-1);
tmp->push(3);
0
1
Space[14]
0
14
Space[13]
0
13
Space[12]
0
12
Space[11]
0
11
Space[10]
0
10
Space[9]
0
9
Space[8]
0
8
Space[7]
0
7
Space[6]
0
6
Space[5]
0
5
Space[4]
0
0
Space[3]
2
3
Space[2]
1
0
Space[1]
0
0
Space[0]
data next
0
1
Space[14]
0
14
Space[13]
0
13
Space[12]
0
12
Space[11]
0
11
Space[10]
0
10
Space[9]
0
9
Space[8]
0
8
Space[7]
0
7
Space[6]
0
6
Space[5]
0
0
Space[4]
0
4
Space[3]
2
3
Space[2]
1
0
Space[1]
0
0
Space[0]
data next
tmp->push(2);
tmp->push(2);
0
1
Space[14]
0
14
Space[13]
0
13
Space[12]
0
12
Space[11]
0
11
Space[10]
0
10
Space[9]
0
9
Space[8]
0
8
Space[7]
0
7
Space[6]
3
0
Space[5]
3
0
Space[4]
0
4
Space[3]
2
3
Space[2]
1
0
Space[1]
0
0
Space[0]
data next
0
1
Space[14]
0
14
Space[13]
0
13
Space[12]
0
12
Space[11]
0
11
Space[10]
0
10
Space[9]
0
9
Space[8]
0
8
Space[7]
2
0
Space[6]
3
6
Space[5]
3
0
Space[4]
0
4
Space[3]
2
3
Space[2]
1
0
Space[1]
0
0
Space[0]
data next
tmp->pop(-3);
tmp->push(4);
0
1
Space[14]
0
14
Space[13]
0
13
Space[12]
0
12
Space[11]
0
11
Space[10]
0
10
Space[9]
0
9
Space[8]
0
8
Space[7]
2
0
Space[6]
3
0
Space[5]
3
5
Space[4]
0
6
Space[3]
2
3
Space[2]
1
4
Space[1]
0
0
Space[0]
data next
0
1
Space[14]
0
14
Space[13]
0
13
Space[12]
0
12
Space[11]
0
11
Space[10]
0
0
Space[9]
0
8
Space[8]
4
0
Space[7]
2
7
Space[6]
3
5
Space[5]
3
0
Space[4]
0
6
Space[3]
2
3
Space[2]
1
4
Space[1]
0
0
Space[0]
data next
tmp->push(0);
0
1
Space[14]
0
14
Space[13]
0
13
Space[12]
0
12
Space[11]
0
11
Space[10]
0
10
Space[9]
0
0
Space[8]
4
8
Space[7]
2
0
Space[6]
3
7
Space[5]
3
5
Space[4]
0
6
Space[3]
2
3
Space[2]
1
4
Space[1]
0
0
Space[0]
data next
2.3. Результати виконання програми
/
ЗАВДАННЯ 4. ЗАСТОСУВАННЯ АТД
3.1. Постановка задачі
Поліном від трьох змінних ( X , Y , Z ) представити у вигляді циклічного списку, в якому кожний вузол має п’ять полів: одне – для коефіцієнта члена поліному , друге – для показника степеня змінної X , третє – для показника степеня змінної Y, четверте – для показника степеня змінної Z, п’яте – для вказівника на наступний вузол списку. Елементи списку мають бути впорядковані спочатку по зменшенню степеня Х, пізніше по зменшенню степеня Y, а після цього по зменшенню степеня Z. Структура збереження поліномів повинна забезпечувати ефективне виконання такої операції над ними:
Обчислення полінома по заданим значенням X , Y , Z .
Алгоритм розв’язання задачі
Словесний опис алгоритму
Для розв’язання даного завдання потрібно створити зв’язний список, кожна комірка якого буде містити чотири значення, а саме : степінь змінної X (nx), степінь змінної Y (ny), степінь змінної Z (nz), а також значення для коефіцієнту члена поліному. Значення цих змінних вводимо з клавіатури.
Після двох циклів введення значень змінних відбувається порівняння, спочатку по степеню nx,якщо степені nx рівні – то порівняння відбувається по степенях ny ітд. Для того, щоб завершити введеня коефіцієнтів і степенів слід при проханні комп’ютера ввести значення С, задати його рівним -100 – це і стане знаком для завершення введення даних. Для виконня обчислення поліному( многочлена) потрібно додати функцію обчислення, де слід внести формулу для обчислення, а потім передати в цю формулу значення змінних X, Y, Z, які будуть введені з клавіатури. Результат обчислення буде виведено на екран.
Граф-схема алгоритму
Так
Ні
Ні Ні
Так Так
Так Ні Ні
Так
Так Ні Ні
Так
3.3. Результати виконання програми
/
ВИСНОВКИ
Виконуючи цю частину курсової роботи я повторив, як оперувати абстрактними типами даних такими, як списки, а саме закріпив в пам’яті способи їхнього використання у прикладних задачах. Вдосконалив своє вміння програмувати використовуючи даний АТД.
СПИСОК ЛІТЕРАТУРИ
Конспект лекцій з дисципліни “Програмування. Частина IIІ. Структури даних та алгоритми".
Стивен Прата. Язик программирования С. Лекции и упражнения. - М.:Издательский дом ”Вильямс”, 2006. – 950 с.
Стивен Прата. Язик программирования С. Лекции и упражнения. - М.:Издательский дом ”Вильямс”, 2012. – 1240 с
Кнут Д. Искусство програмирования, том 1. Основные алгоритмы. – М.:Изд.дом ”Вильямс”, 2001. – 720 с.
ДОДАТОК А. ТЕКСТ ПРОГРАМИ ДО ЗАВДАННЯ 3
list.h
#include <cmath>
template <class T>
class List
{
private:
struct Node { T data; Node * next; }; // вложена структура
Node * head; // вказівник на початок списку
bool push_first(T el); // додавання перед першим елементом
bool push_back(T el); // додавання після останнього елемента
public:
List(); // констуктор
~List() { // деструктор
Node * temp;
while (head) {
temp = head;
head = head->next;
delete temp;
}
};
bool push(T el); // додавання елемента і сортування
bool pop(T el); // вилучення елемента
void show() { // вивід списку на екран
Node * res;
res = head;
while (res != NULL) {
std::cout << res->data << " ";
res = res->next;
}
cout << std::endl;
}
bool checking(); // перевірка кінцевої умови
};
template <class T>
List<T>::List() // ств. пустого списку
{
head = NULL;
}
template <class T>
bool List<T>::push_first(T el)
{
Node * add = new (Node); // ств. вузла
add->next = head; // зв"язуєм зі списком
add->data = el; // заносим дані
head = add; // зміжуєм початок
return true;
}
template <class T>
bool List<T>::push_back(T el)
{
Node * add = new Node; // ств. вузла
Node * res; // для збереження початку
res = head;
while (res->next != NULL)
res = res->next; // проходим до кінця
res->next = add; //додаєм елемент після останнього
add->next = NULL;
add->data = el; // заносим дані
return true;
}
template <class T>
bool List<T>::push(T el)
{
int count = 0;
Node * res;
res = head;
while (2) {
// переходим до елемента більшого за даний, або до кінця списку
if (res == NULL)
break;
if (res->data > el)
break;
res = res->next;
count++;
}
if (head == res) { // якщо це початок
List::push_first(el); // додаєм в початок
}
else if (res == NULL && res != head) { // якщо це кінець
List::push_back(el); // додаєм в кінець
}
else // в інших випадках
{
//додаєм в середину
Node * add = new Node; // ств. вузол
res = head; // переходим на початок
for (int i = 1; i < count; ++i) // переходим до останнього меншого елемента
res = res->next;
add->data = el; // заносим дані
add->next = res->next; // вставляєм в список
res->next = add; //зв"язуєм список
}
return true;
}
template <class T>
bool List<T>::pop(T el)
{
el = abs(el);
bool is = false;
Node * temp;
Node * tmp;
temp = head; // зберігаєм початок
while (temp->next) { // проходим до кінця
if (temp->next->data == el) // якщо елементи рівні
{
// видаляєм їх
tmp = temp->next;
temp->next = tmp->next;
delete tmp;
is = true;
continue;
}
temp = temp->next;
}
// окремо обробляєм 1й елемент
if (head->data == el) // якщо елементи рівні
{
head = head->next; // зміщуєм початок
is = true;
}
return is;
}
template <class T>
bool List<T>::checking()
{
if (head->data == 0) // якщо 1й ел. == 0
push_back(0); // то додаєм 0 в кінець
else
pop(0); // в іншому випадку видаляєм всі 0
return true;
}
main.cpp
#include <iostream>
#include <vector>
#include "list.h"
using namespace std;
typedef int Type;
void show_sequence(const std::vector<Type> & v);
int main(void)
{
setlocale(0, "Ukr");
Type k;
vector<Type> item;
cout << "Введiть послiдовнiсть (для закiнчення вводу введiть будь який символ): \n";
while (cin >> k)
item.push_back(k); // Зчитування послідовності
system("cls");
cin.clear();
while (cin.get() != '\n')
continue;
List<Type> l; // ств. об"єкту списка
show_sequence(item); // вивід послідовності
cout << endl;
for (unsigned int i = 0; i < item.size(); ++i) { // обробка всієї посл.
if (item[i] >= 0) { // якщо ел. >= 0
l.push(item[i]); // додаєм його в список
cout << endl;
l.show(); // виводим список
cout << "Елемент " << item[i] << " додано в список!\n";
}
else // в іншому випадку
{
cout << endl;
if (l.pop(item[i])) { // якщо є елемент в списку, видаляєм його
l.show();
cout << "Елемент(и) " << abs(item[i]) << " видалений(i) зi списку!\n";
}
else { // якщо немає
l.show();
cout << "Неможливо здiйснити операцiю видалення! В списку немає даного елемента: " << abs(item[i]) << "!\a" << endl; // виводим повідомлення
}
}
}
cout << endl;
cout << "Перевiрка!\n";
l.checking(); // перевірка кінцевої умови
l.show();
system("Pause");
return 0;
}
void show_sequence(const vector<Type> & v)
{
for (unsigned int i = 0; i < v.size(); ++i) // вивід послідовності
cout << v[i] << " ";
cout << endl;
}
ДОДАТОК Б. ТЕКСТ ПРОГРАМИ ДО ЗАВДАННЯ 4
#include<iostream>
#include<assert.h>
#include<math.h>
using namespace std;
struct spysok // структура для списку
{ double c;
int nx,ny,nz; // ініціалізація степенів
struct spysok *next; // вказівник на наступні елементи
};
typedef struct spysok *catalog; // заміна ключового слова
class annotation{ // клас для побудови списку
catalog FIRST_ELEMENT; // змінна голови списку
int k; // змінна кінця списку
public:
annotation(){FIRST_ELEMENT=NULL;k=0;} // конструктор
catalog find(catalog FIRST_ELEMENT, double CELL,int CELL1, int CELL2, int CELL3);// перевірка на наявність елементів
catalog find_before(catalog FIRST_ELEMENT, catalog node);// перевіка елементів для вставки перед
catalog find_after(catalog node);//перевірка елементів для вставки після
catalog find_last(catalog FIRST_ELEMENT); // пошук останнього елемента
catalog get_head(){return FIRST_ELEMENT;} // повернення голови
catalog find_great(catalog FIRST_ELEMENT,double CELL,int CELL1, int CELL2, int CELL3);// пошук найбільших елементів
void push(catalog *head_ptr, double CELL,int CELL1, int CELL2, int CELL3);// прототип для додавання елементів
void push_before(catalog *head_ptr, double CELL,int CELL1, int CELL2, int CELL3);// прототип для додавання перед обраним елементом
void put_after(catalog *node_prt, double CELL,int CELL1, int CELL2, int CELL3); //прототип для додавання після обраного елемента
void delete1(catalog *head_ptr, catalog *node_ptr);
int print_list(catalog head);// для друку
double calculate(catalog head,double X, double Y, double Z);};// обчислення поліному
void annotation::push(catalog *head_ptr, double CELL,int CELL1, int CELL2, int CELL3)
{
spysok *new_ptr;
new_ptr = new spysok;
new_ptr->c = CELL;
new_ptr->nx = CELL1;
new_ptr->ny = CELL2;
new_ptr->nz = CELL3;
new_ptr->next = FIRST_ELEMENT;
if (*head_ptr==NULL)
{*head_ptr = new_ptr;
FIRST_ELEMENT=*head_ptr;
}
else
find_last(*head_ptr)->next = new_ptr;
k++;
return ;
}
void annotation::push_before(catalog *head_ptr, double CELL,int CELL1, int CELL2, int CELL3)
{
spysok *new_ptr;
new_ptr = new spysok;
new_ptr->c = CELL;
new_ptr->nx = CELL1;
new_ptr->ny = CELL2;
new_ptr->nz = CELL3;
new_ptr->next = *head_ptr;
*head_ptr = new_ptr;
k++;
return ;
}
void annotation::put_after(catalog *node_prt, double CELL,int CELL1, int CELL2, int CELL3)
{
catalog new_ptr = NULL;
new_ptr = new spysok;
new_ptr->c = CELL;
new_ptr->nx = CELL1;
new_ptr->ny = CELL2;
new_ptr->
18.03.2015 01:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора