Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ЛІНІЙНІ ОДНОЗВ’ЯЗНІ ТА ДВОЗВ’ЯЗНІ СПИСКИ
Інформація про навчальний заклад
ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
ЗІ
Кафедра:
Не вказано
Інформація про роботу
Рік:
2022
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування складних алгоритмів
Частина тексту файла (без зображень, графіків і формул):
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ
імені ІГОРЯ СІКОРСЬКОГО”
ЗВІТ
з лабораторної роботи №5
з навчальної дисципліни “Програмування складних алгоритмів”
Тема:
«ЛІНІЙНІ ОДНОЗВ’ЯЗНІ ТА ДВОЗВ’ЯЗНІ СПИСКИ»
Варіант 18
Мета: Метою лабораторної роботи є ознайомитися з основами роботи з двозв’язним списком, однозв’язним списком, стеком та чергою.
Теоретична частина
Лінійнийоднозвв’язний список
Лінійний список – цединамічна структура даних, кожнийелементякої за допомогоювказівниказв’язується з наступнимелементом.
З визначеннявипливає, щокоженелемент списку містить поле даних (Data) (вономожематискладну структуру) і поле посилання на наступнийелемент (next). Поле посиланняостанньогоелемента повинно міститипорожнійпокажчик (NULL).
Так як посиланнялишеодне (тільки на наступнийелемент), то такий список є однозв’язним.
Коли говорять про лінійний список, то, як правило, мають на увазісамеоднозв’язний список.
Двобічнозв'язаний список — вид зв'язаного списку, у якому посилання в кожному вузлівказують на попередній і на подальший вузол у списку.
Якщов спискупісляостанньогоелементайде перший, то такий список називається кільцевимдвобічнозв'язаним списком. Тобто, поле prev голови списку вказує на хвіст списку, а поле next хвоста списку вказує на голову списку.
По двобічнозв'язаному списку можнапересуватисяв будь-якомунапрямку — як від початку до кінця, так і навпаки. Для ньогопростішепроводити видалення і перестановку елементів, оскількизавждивідоміадреси тих елементів списку, вказівник якихспрямований на змінюваний елемент.
Завдання до лабораторної роботи:
1. Створити лінійний однозв’язний список, вивести його. Якщо в списку є елемент із заданим ключем, вилучити його, а попередній та настуні поміняти місцями. Виконати завдання згідно варіанту.
2. Створити двозв’язний список, вивести його. Якщо в списку є елемент із заданим ключем, вилучити його. Виконати завдання згідно варіанту з двозвязним списком.
18. Створити стек цілих чисел. Визначити чого більше – парних чи непарних чисел.
Результат роботи
/
Висновок: Було написано програму, яка перевіряє два списки на наявність ключа, вказаного користувачем, і видаляє при знаходженні. Потім програма рахує кількість парних і непарних чисел в обох списках і порівнює їх.
Програмний код
https://replit.com/join/grgnrhpoac-okseniait
#include <iostream>
#include <time.h>
#include <random>
#include <chrono>
#include "List2.h"
#include "List1.h"
using namespace std;
int iteration = 0;
#define SIZE 10
int main() {
srand(time(NULL));
//Однозв'язний список
cout << "Однозв'язний список\n";
List1<int> lst1;
for(int i = 0;i < SIZE;i++){
lst1.pushback(rand()%50);
}
for(int i = 0;i < lst1.GetSize();i++){
cout << lst1[i] << " ";
}
int key;
cout << "\nВведіть ключ: ";
cin >> key;
for(int i = 0;i < lst1.GetSize();i++){
if(lst1[i] == key){
lst1.remove(i);
int storage, start[i], scount = 0, end[lst1.GetSize() - i], ecount = 0;
for(int j = 0;j < lst1.GetSize();j++){
if(j < i){
start[scount] = lst1[j];
scount++;
}
else{
end[ecount] = lst1[j];
ecount++;
}
}
scount = 0;
ecount = 0;
for(int j = 0;j < lst1.GetSize();j++){
if(j < lst1.GetSize() - i){
lst1[j] = end[ecount];
ecount++;
}
else{
lst1[j] = start[scount];
scount++;
}
}
break;
}
}
for(int i = 0;i < lst1.GetSize();i++){
cout << lst1[i] << " ";
}
cout << endl;
/////
int even[SIZE], odd[SIZE], ecount = 0, ocount = 0;
auto start1 = chrono::high_resolution_clock::now();
for(int i = 0;i < lst1.GetSize();i++){
if(lst1[i] % 2 == 0){
// even[ecount] = lst1[i];
ecount++;
iteration++;
}
else if(lst1[i] % 2 != 0){
odd[ocount] = lst1[i];
ocount++;
iteration++;
}
}
auto finish1 = chrono::high_resolution_clock::now();
/*cout << "\neven: ";
for(int i = 0;i < ecount;i++){
cout << even[i] << " ";
}
cout << "\nodd: ";
for(int i = 0;i < ocount;i++){
cout << odd[i] << " ";
}*/
if(ecount>ocount){
cout << "\nБільше парних " << ecount << " > " << ocount;
}
else if(ecount<ocount){
cout << "\nБільше непарних " << ecount << " < " << ocount;
}
else{
cout << "\nОднакова кількість " << ecount << " = " << ocount;
}
cout << "\nЧас: " << (finish1 - start1).count() << "ns" << endl;
cout << "Кількість ітерацій: " << iteration << endl;
//Двозв'язний список
iteration = 0;
cout << "\n\nДвозв'язний список\n";
List2<int> lst2;
for(int i = 0;i < SIZE;i++){
lst2.pushback(rand()%50);
}
for(int i = 0;i < lst2.GetSize();i++){
cout << lst2[i] << " ";
}
cout << "\nВведіть ключ: ";
cin >> key;
for(int i = 0;i < lst2.GetSize();i++){
if(lst2[i] == key){
lst2.remove(i);
}
}
cout << endl;
for(int i = 0;i < lst2.GetSize();i++){
cout << lst2[i] << " ";
}
ecount = 0;
ocount = 0;
auto start2 = chrono::high_resolution_clock::now();
for(int i = 0;i < lst2.GetSize();i++){
if(lst2[i] % 2 == 0){
//even[ecount] = lst2[i];
ecount++;
iteration++;
}
else if(lst2[i] % 2 != 0){
//odd[ocount] = lst2[i];
ocount++;
iteration++;
}
}
auto finish2 = chrono::high_resolution_clock::now();
/*cout << "\neven: ";
for(int i = 0;i < ecount;i++){
cout << even[i] << " ";
}
cout << "\nodd: ";
for(int i = 0;i < ocount;i++){
cout << odd[i] << " ";
}*/
if(ecount>ocount){
cout << "\nБільше парних " << ecount << " > " << ocount;
}
else if(ecount<ocount){
cout << "\nБільше непарних " << ecount << " < " << ocount;
}
else{
cout << "\nОднакова кількість " << ecount << " = " << ocount;
}
cout << "\nЧас: " << (finish2 - start2).count() << "ns" << endl;
cout << "Кількість ітерацій: " << iteration << endl;
}
List1.h
template<typename T>
class Node1{
public:
Node1 *pNext;
T data;
Node1(T data = T(), Node1 *pNext = nullptr){
this->data = data;
this->pNext = pNext;
}
};
template<typename T>
class List1{
public:
~List1();
List1();
int GetSize(){
return SIZE;
}
void pushback(T data);
T& operator[](const int index);
int Search(T Data);
void remove(int index);
void WriteIn(std::string filename);
void ReadFrom(std::string filename);
private:
int SIZE;
Node1<T> *pHead;
};
template<typename T>
List1<T>::List1(){
SIZE = 0;
pHead = nullptr;
}
template<typename T>
void List1<T>::pushback(T data){
if(pHead == nullptr){
pHead = new Node1<T>(data);
}
else{
Node1<T> *current = this->pHead;
while(current->pNext != nullptr){
current = current->pNext;
}
current->pNext = new Node1<T>(data);
}
SIZE ++;
}
template<typename T>
T & List1<T>::operator[](const int index){
int count = 0;
Node1<T> *current = this->pHead;
while(current != nullptr){
if(count == index){
return current->data;
}
current = current->pNext;
count++;
}
}
template<typename T>
void List1<T>::remove(int index){
if(index == 0){
Node1<T> *first = this->pHead;
pHead = first->pNext;
delete first;
SIZE --;
}
else{
Node1<T> *prev = this->pHead;
for(int i = 0;i < index - 1;i++){
prev = prev->pNext;
}
Node1<T> *next = prev->pNext;
prev->pNext = next->pNext;
delete next;
SIZE--;
}
}
template<typename T>
List1<T>::~List1(){
for(int i = 0;i < SIZE;i++){
remove(i);
}
}
List2.h
template<typename T>
class Node{
public:
T DATA;
Node *pNext, *pPrev;
Node(T DATA = T(), Node *pNext = nullptr, Node *pPrev = nullptr){
this->DATA = DATA;
this->pNext = pNext;
this->pPrev = pPrev;
}
};
template<typename T>
class List2{
public:
List2();
//~List2();
int GetSize(){
return SIZE;
}
T & operator[](const int index);
void pushback(T DATA);
void remove(int index);
private:
int SIZE;
Node<T> *pHead, *pTail;
};
template<typename T>
void List2<T>::pushback(T DATA){
if(SIZE == 0){
pHead = new Node<T>(DATA);
SIZE++;
}
else if(SIZE == 1){
pTail = new Node<T>(DATA);
pHead->pNext = pTail;
pTail->pPrev = pHead;
SIZE++;
}
else{
Node<T> *pNew = new Node<T>(DATA);
pNew->pPrev = pTail;
pTail->pNext = pNew;
pTail = pNew;
SIZE++;
}
}
template<typename T>
List2<T>::List2(){
SIZE = 0;
pHead = nullptr;
pTail = nullptr;
}
template<typename T>
T & List2<T>::operator[](const int index){
int count;
if(index <= SIZE/2){
count = 0;
Node<T> *current = this->pHead;
while(current != nullptr){
if(count == index){
return current->DATA;
}
current = current->pNext;
count++;
}
}
else{
Node<T> *current = this->pTail;
count = SIZE - 1;
while(current != nullptr){
if(count == index){
return current->DATA;
}
current = current->pPrev;
count--;
}
}
}
template<typename T>
void List2<T>::remove(int index){
if(index == 0){
Node<T> *first = this->pHead;
pHead = first->pNext;
delete first;
}
else if(index <= SIZE/2){
Node<T> *prev = this->pHead;
for(int i = 0;i < index - 1;i++){
prev = prev->pNext;
}
Node<T> *theone = prev->pNext;
Node<T> *next = theone->pNext;
prev->pNext = next;
next->pPrev = prev;
delete theone;
}
else if(index == SIZE - 1){
Node<T> *last = this->pTail;
pTail = last->pPrev;
delete last;
}
else{
Node<T> *next = this->pTail;
for(int i = 0;i < SIZE - index - 2;i++){
next = next->pPrev;
}
Node<T> *theone = next->pPrev;
Node<T> *prev = theone->pPrev;
prev->pNext = next;
next->pPrev = prev;
delete theone;
}
SIZE--;
}
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора