Файл: Отчет по выполнению практического задания 14 Тема Оценка вычислительной сложности алгоритма Дисциплина Структуры и алгоритмы обработки данных.pdf

МИНОБРНАУКИ РОССИИ
Федеральное государственное бюджетное образовательное учреждение
высшего образования
«МИРЭА – Российский технологический университет»
РТУ МИРЭА
Отчет по выполнению практического задания № 5.14
Тема:
Оценка вычислительной сложности алгоритма
Дисциплина: «Структуры и алгоритмы обработки данных»
Выполнил студент:
Белоглинцев И.А
Фамилия И.О.
Группа:
ИКБО-34-22
Номер группы
Москва – 2023

Цель работы: приобретение практических навыков:
Дан линейный однонаправленный список L

Разработать функцию, которая создает из значений узлов списка L два новых списка: L1 – из положительных элементов массива L; L2 – из остальных элементов списка L.

Разработать функцию, которая удаляет из списка L2 все отрицательные элементы.

Разработать функцию, которая в списке L1 узел с максимальным значением размещает перед первым узлом.
Функция описание данных. struct
Node
{ int val;
//информационное (полезная строка данных)
Node
* next;
//связь
Node(
int
_val
) : val(
_val
), next(
nullptr
) {};
//конструктор экземпляра узла списка
};
Здесь поле int – информационное (полезная строка данных), next – связь, Node – конструктор экземпляра узла списка.
Функция реализации односвязного списка.
1) указатель на первый узел;
2) указатель на последний узел;
3) конструктор списка; struct
NodeList
{
Node
* first;
//указатель на первый узел
Node
* last;
//указатель на последний узел
NodeList() : first(
nullptr
), last(
nullptr
) {}
//конструктор списка
Функция проверки наличия узлов в списке. bool is_empty() {
//Проверка наличия узлов в односвязном списке return first == nullptr
;
}
Функция удаления отрицательных чисел.
Если значение узла <0,то мы его удаляем, иначе оставляем.
Функция Последний (Максимальный элемент перенести в начало).
Пройдите по списку до последнего узла. Используйте два указателя: один для хранения адреса последнего узла, а другой для хранения адреса предпоследнего узла. После окончания цикла сделайте предпоследний узел последним узлом, а последний узел сделать головным узлом.

Сам код написанный на C++ представен ниже с результами.
#include

#include

#include

#include

struct
Node
{ int val;
//информационное (полезная строка данных)
Node
* next;
//связь
Node(
int
_val
) : val(
_val
), next(
nullptr
) {};
//конструктор экземпляра узла списка
};
/* See https://www.geeksforgeeks.org/move-last-element-to-front-of-a-given-linked-list/ for details of this function */
void
MaxInFisrtPos(
Node
** head_ref
) {
/* Если связанный список пуст, или он содержит только один узел,
тогда ничего не нужно делать,
просто верните*/
if
(*
head_ref
==
NULL
|| (*
head_ref
)->next ==
NULL
) return
;
/* Инициализировать второй последний и последний указатели*/
Node
* secLast =
NULL
;
Node
* last = *
head_ref
;
/*После этого цикла secLast содержит адрес второго последнего узла, а last содержит адрес последнего узла в Связанном списке */
while
(last->next !=
NULL
) { secLast = last; last = last->next;
}
/* Установить следующий за вторым последним как NULL */
secLast->next =
NULL
;
/* Установить следующий за последним в качестве головного узла*/
last->next = *
head_ref
;
/* Измените указатель головы чтобы он указывал на последний узел */
*
head_ref
= last;
} struct
NodeList
{
Node
* first;
//указатель на первый узел
Node
* last;
//указатель на последний узел
NodeList() : first(
nullptr
), last(
nullptr
) {}
//конструктор списка bool is_empty() {
//Проверка наличия узлов в односвязном списке return first == nullptr
;
} void push_back(
int
_val
) {
//добавление элемента в список
Node
* p = new
Node
(
_val
); if
(is_empty())
{ first = p; last = p; return
;

} last->next = p; last = p;
} void print() {
//вывод на экран список if
(is_empty()) return
;
Node
* p = first; while
(p)
{ std::cout
<<
p->val
<<
" "
; p = p->next;
} std::cout
<<
"\n"
;
} void remove_first(){
//функция удаления первого элемента в списке
Node
* old = first; first = first->next; delete old;
} void remove_element(
Node
* elm
, bool delete_elm
= true
) {
//функция удаленний элементов из списка
Node
* prev = first; if
(prev == elm
)
{ remove_first(); return
;
} while
(prev)
{ if
(prev->next == elm
)
{ prev->next = elm
->next; if
(
delete_elm
) delete elm
;
}
}
} void sort_list()
{
MaxInFisrtPos(&first);
}
}; void delete_negative(
NodeList
& list_to_remove
) {
Node
* mover = list_to_remove
.first; while
(mover != nullptr
)
{
Node
* elm = mover; mover = mover->next; if
(elm->val < 0)
{ list_to_remove
.remove_element(elm);
}
}
} void main() { using namespace std; setlocale(0,
""
);
NodeList lst1, lst2, lst3; for
(
int i = -10; i < 10; i++)
{ lst1.push_back(i);
//заполняем главный список
} cout
<<
"Главный лист\n"
; lst1.print();
Node
* mover = lst1.first; while
(mover != nullptr
)
{

Node
* elm = mover; mover = mover->next; if
(elm->val <= 0)
{ lst2.push_back(elm->val);
} else
{ lst3.push_back(elm->val);
}
} cout
<<
"Первый лист\n"
; lst3.print(); cout
<<
"Второй лист\n"
; lst2.print(); cout
<<
"удаляем все элементы из второго списка\n"
; delete_negative(lst2); cout
<<
"Ниже выведен пустой список из бывших отрицательных чисел\n"
; lst2.print(); cout
<<
"Выведем масимальный элемент на первое место\n"
; cout
<<
"До\n"
; lst3.print(); lst3.sort_list(); cout
<<
"После\n"
; lst3.print();
}