Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ЛІНІЙНІ ОДНОЗВ’ЯЗНІ ТА ДВОЗВ’ЯЗНІ СПИСКИ
Інформація про навчальний заклад
ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2023
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування складних алгоритмів
Частина тексту файла (без зображень, графіків і формул):
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ
імені ІГОРЯ СІКОРСЬКОГО”
ЗВІТ
з лабораторної роботи №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).
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора