ЛІНІЙНІ ОДНОЗВ’ЯЗНІ ТА ДВОЗВ’ЯЗНІ СПИСКИ

Інформація про навчальний заклад

ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано

Інформація про роботу

Рік:
2022
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування складних алгоритмів

Частина тексту файла (без зображень, графіків і формул):

НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №5 з навчальної дисципліни “Програмування складних алгоритмів” Тема: ЛІНІЙНІ ОДНОЗВ’ЯЗНІ ТА ДВОЗВ’ЯЗНІ СПИСКИ Варіант №12 Київ 2022 Мета: Метою лабораторної роботи є ознайомитися з основами роботи з двозв’язним списком, однозв’язним. Теоретична частина Зв'язаний список — це лінійна структура даних, в якій елементи не зберігаються в суміжних місцях пам'яті. Елементи зв'язаного списку зв'язуються за допомогою вказівників. Простіше кажучи, зв'язаний список складається з вузлів, де кожен вузол містить поле даних і посилання (посилання) на наступний вузол у списку. Типи зв'язаних списків Однозв'язаний список - це найпростіший тип зв'язаного списку, в якому кожен вузол містить деякі дані і покажчик на наступний вузол того ж типу даних. Вузол, який містить покажчик на наступний вузол, означає, що вузол зберігає адресу наступного вузла в послідовності. Один зв'язаний список дозволяє передавати дані лише одним способом. Двозв'язаний список - двосторонній зв'язаний список або двосторонній зв'язаний список - це більш складний тип зв'язаного списку, який містить покажчик на наступний, а також на попередній вузол у послідовності. Таким чином, він містить три частини: дані, покажчик на наступний вузол, і покажчик на попередній вузол. Це дозволило б нам переміщатися по списку і в протилежному напрямку. Завдання: 1. Створити лінійний однозв’язний список, вивести його. Якщо в списку є елемент із заданим ключем, вилучити його, а попередній та настуні поміняти місцями. Виконати завдання згідно варіанту. 2. Створити двозв’язний список, вивести його. Якщо в списку є елемент із заданим ключем, вилучити його. Виконати завдання згідно варіанту з двозвязним списком. Завдання до Варіанту_12 Задано натуральне число n, дійсні числа х(1)…х(n), (n>=2). Одержати послідовність х(1)-х(n) , x(2)-x(n),…,x(n-1)-x(n). Результати виконання лабораторної роботи:  Код: Main.cpp //Лабораторна робота №5_ПСА //ТР-15_Ткаченко_Майя, Варіант_12 #include <iostream> #include "single-list.h" #include "double-list.h" using namespace std; int main() { cout<<"\n====================>\n1. Створити лінійний однозв’язний список, вивести його. Якщо в списку є елемент із заданим ключем, вилучити його, а попередній та настуні поміняти місцями. Виконати завдання згідно варіанту.\n====================>\n"; cout<<"2. Створити двозв’язний вивести його. Якщо в списку елемент із заданим ключем, вилучити його. Виконати завдання згідно варіанту з двозвязним списком.\n====================>\n"; cout<<"Завдання до Варіанту_12\n====================>\nЗадано натуральне число n, дійсні числа х(1)…х(n), (n>=2). Одержати послідовність х(1)-х(n) , x(2)-x(n),…,x(n-1)-x(n).\n====================>\n"; int n; cout << "\t<<---Виконання завдання №1--->>>\t" << endl; cout << "========<<<Введіть значення для n (більше або дорівнює 2): "; cin >> n; List<int> Lst; cout << "========>>>Початковий список:"; for (int i = 1; i < n; ++i) { Lst.PushBack(i - n); } Lst.ListOutput(); cout << "========<<<Введіть номер для видалення (попередній і наступний номер буде поміняно місцями): "; int RemoveNumber; cin >> RemoveNumber; Lst.RemoveDataAndSwapPrevAndNextData(RemoveNumber); cout << "========>>>Список після редагування:\n"; Lst.ListOutput(); cout << "\t<<---Виконання завдання №2--->>>\t" << endl; DoubleList<int> DoubleLst; cout << "========<<<Введіть значення для n (більше або дорівнює 2): "; cin >> n; cout << "========>>>Початковий список:"; for (int i = 1; i < n; ++i) { DoubleLst.PushBack(i - n); } DoubleLst.ListOutput(); return 0; } Single-list.h #ifndef PCA_LR_5_SINGLE_LIST_H #define PCA_LR_5_SINGLE_LIST_H #include "string" #include <fstream> #include <iostream> #include <vector> using namespace std; template <typename T> class SingleNode { public: SingleNode *pNext; T Data; SingleNode(T Data = T(), SingleNode *pNext = nullptr) { this->Data = Data; this->pNext = pNext; } }; template <typename T> class List { public: List(); ~List(); void Insert(T Value, int Index); void RemoveAt(int Index); void PopFront(); void PopBack(); void PushBack(T Data); void PushFront(T Data); void Clear(); int GetSize() const { return Size; } T &operator[](const int Index); int Search(T Data); void ListOutput(); void RemoveDataAndSwapPrevAndNextData(T Data); private: int Size; SingleNode<T> *Head; }; template <typename T> List<T>::List() { Size = 0; Head = nullptr; } template <typename T> List<T>::~List() { Clear(); } template <typename T> void List<T>::PushBack(T Data) { if (!Head) { Head = new SingleNode<T>(Data); } else { SingleNode<T> *Current = this->Head; while (Current->pNext) { Current = Current->pNext; } Current->pNext = new SingleNode<T>(Data); } Size++; } template <typename T> T &List<T>::operator[](const int Index) { int Counter = 0; SingleNode<T> *Current = this->Head; while (Current) { if (Counter == Index) { return Current->Data; } Current = Current->pNext; Counter++; } } template <typename T> void List<T>::PopFront() { SingleNode<T> *Temp = Head; Head = Head->pNext; delete Temp; Size--; } template <typename T> void List<T>::PushFront(T Data) { Head = new SingleNode<T>(Data, Head); Size++; } template <typename T> void List<T>::RemoveAt(int Index) { if(Index < 0 || Index > Size) return; if (Index == 0) { PopFront(); } else { SingleNode<T> *Previous = this->Head; for (int i = 0; i < Index - 1; ++i) { Previous = Previous->pNext; } SingleNode<T> *ToDelete = Previous->pNext; Previous->pNext = ToDelete->pNext; delete ToDelete; Size--; } } template <typename T> void List<T>::PopBack() { RemoveAt(Size - 1); } template <typename T> int List<T>::Search(T Data) { SingleNode<T> *Temp = Head; for (int i = 0; i < Size; i++) { if (Temp->Data == Data) { return i; } Temp = Temp->pNext; } return -1; } template <typename T> void List<T>::Clear() { while (Size) { PopFront(); } } template<typename T> void List<T>::ListOutput() { SingleNode<T> *Temp = Head; for (int i = 0; i < Size; i++) { cout << Temp->Data << " "; Temp = Temp->pNext; } cout << endl; } template<typename T> void List<T>::RemoveDataAndSwapPrevAndNextData(T Data) { SingleNode<T> *Prev = nullptr; SingleNode<T> *Temp = Head; for (int i = 0; i < Size; i++) { if (Temp->Data == Data) { //i = 0, because start list "1 0 2" will be "0 2", namely numbers won`t swap //i = Size - 1(last element) -> "1 0 2" will be "1 0" if(i == 0) { PopFront(); return; } else if (i == Size - 1) { PopBack(); return; } int TempData = Temp->pNext->Data; Temp->pNext->Data = Prev->Data; Prev->Data = TempData; Prev->pNext = Temp->pNext; delete Temp; Size--; return; } Prev = Temp; Temp = Temp->pNext; } //if number not found //cout << "Номер не знайдено:" << endl; } #endif //PCA_LR_5_SINGLE_LIST_H Double-list.h #ifndef PCA_LR_5_DOUBLE_LIST_H #define PCA_LR_5_DOUBLE_LIST_H #include "string" #include <fstream> #include <iostream> #include <vector> using namespace std; template <typename T> class DoubleNode { public: DoubleNode *pNext; DoubleNode *pPrev; T Data; DoubleNode(T Data = T(), DoubleNode *pNext = nullptr, DoubleNode *pPrev = nullptr) { this->Data = Data; this->pNext = pNext; this->pPrev = pPrev; } }; template<typename T> class DoubleList { public: DoubleList(); ~DoubleList(); void ListOutput(); void PushBack(T Data); T& operator[](const int index); void PopFront(); void Clear(); void DMinMaxExchange(); int GetSize() { return Size;} private: int Size; DoubleNode<T> *Head; DoubleNode<T> *Tail; }; template<typename T> DoubleList<T>::DoubleList() { Head = nullptr; Tail = nullptr; Size = 0; } template<typename T> DoubleList<T>::~DoubleList() { Clear(); } template<typename T> void DoubleList<T>::ListOutput() { DoubleNode<T> *Temp = Head; for (int i = 0; i < Size; i++) { cout << Temp->Data << " "; Temp = Temp->pNext; } cout << endl; } template<typename T> void DoubleList<T>::PushBack(T Data) { if(Head == nullptr) { Head = new DoubleNode<T>(Data); Tail = Head; } else { DoubleNode<T> *current = this->Head; while(current->pNext != nullptr) { current = current->pNext; } current->pNext = new DoubleNode<T>(Data, nullptr, current); Tail = current->pNext; } Size++; } template<typename T> T & DoubleList<T>::operator[](const int index) { int counter = 0; DoubleNode<T> *current = this->Head; while (current != nullptr) { if (counter == index) { return current->Data; } current = current->pNext; counter++; } } template<typename T> void DoubleList<T>::PopFront() { DoubleNode<T> *temp = Head; Head = Head->pNext; delete temp; Size--; } template<typename T> void DoubleList<T>::Clear() { while (Size) { PopFront(); } } template<typename T> void DoubleList<T>::DMinMaxExchange() { DoubleNode<T> *Curr = this->Head; while (Curr->pNext) { Curr = Curr -> pNext; } T Temp = Curr->Data; Curr->Data = Head->Data; this->Head->Data = Temp; } #endif //PCA_LR_5_DOUBLE_LIST_H Посилання на Repl.it : https://replit.com/join/jeptmygswo-tr-15tkachienko Висновки Під час виконання лабораторної роботи було розгянуто основи роботи з однозв’язним та двозв’язними списками. Розроблено програму, яка дозволяє одержати послідовність х(1)-х(n) , x(2)-x(n),…,x(n-1)-x(n), за допомогою заданого числа n(n>=2) і дійсних чисел х(1)…х(n).
Антиботан аватар за замовчуванням

13.07.2023 18:07-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, увійдіть або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!
Нічого не вибрано
0%

Оголошення від адміністратора

Антиботан аватар за замовчуванням

Подякувати Студентському архіву довільною сумою

Admin

26.02.2023 12:38

Дякуємо, що користуєтесь нашим архівом!