Алгоритми на структурах даних
Автор: FHGBK • Ноябрь 29, 2022 • Лабораторная работа • 5,849 Слов (24 Страниц) • 122 Просмотры
Міністерство освіти і науки України
Харківський національний університет радіоелектроніки
Кафедра системотехніки
Дисципліна: «Теорія алгоритмів»
ЛАБОРАТОРНА РОБОТА № 5
« Алгоритми на структурах даних »
Виконав: ст. гр. ІТУ-21-1 Литвиненко Михайло Юрійович |
| Прийняла: Прийняла: к.т.н., доц. каф. СТ Білова Тетяна Георгіївна з оцінкою «____________» «____»_______________2021р. | |
Харків 2021
Мета роботи :
Засвоїти базові алгоритми на лінійних структурах даних: список, черга, стек, дек. Розробити алгоритми основних операцій обробки заданої структури даних оцінити їх складність.
Завдання
Варіант 14. Реалізувати список, кожен елемент якого містить координати точки на площині. Операції вставки та видалення елементів виконувати в задану позицію. Додатково реалізувати алгоритм (та функцію) перевірки двох списків на рівність. Умова рівності двох елементів списку - однакова відстань від точки до початку координат.
Особливості статичної реалізації: список на масиві зі зрушенням.
Особливості динамічної реалізації: список двонаправлений.
Алгоритм визначення кількості елементів в структурі :
[pic 1]
Складність O(n)
Алгоритм виведення структури
[pic 2]
Код до блок-схеми
void show(list* head)
{
if (head == NULL) cout << "Список пуст!" << endl;
else
{
list* current = head;
cout << "Ваш список: ";
while (current != NULL)
{
cout << "(" << current->x << "," << current->y << ")" << " ";
current = current->next;
}
cout << endl;
}
}
Складність O(n)
Показ в обратном порядке
[pic 3]
Код:
void reversshow(list* tail)
{
if (tail == NULL) cout << "Список пуст!" << endl;
else
{
list* current = tail;
cout << "Ваш список в обратном порядке: ";
while (current != NULL)
{
cout << "(" << current->x << "," << current->y << ")" << " ";
current = current->prev;
}
cout << endl;
}
}
Алгоритм видалення елементів зі структури:
[pic 4][pic 5]
Код до блок-схеми
void del(int pos, list*& head, list*& tail)
{
if (head == NULL)
{
cout << "Невозможно удалить элемент - список пуст!" << endl;
return;
}
int k = 0;
list* current = head;
while (current != NULL)
{
k++;
current = current->next;
...