Лінійні однозв’язні та двозв’язні списки
Інформація про навчальний заклад
ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2022
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування складних алгоритмів
Частина тексту файла
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ
імені ІГОРЯ СІКОРСЬКОГО”
ЗВІТ
з лабораторної роботи №5
з навчальної дисципліни “Програмування складних алгоритмів”
Тема: «Лінійні однозв’язні та двозв’язні списки»
Варіант № 16
Дата «19» травень 2022
Київ 2022
Мета роботи: Метою лабораторної роботи є ознайомитися з основами роботи з двозв’язним списком, однозв’язним.
Завдання до лабораторної роботи:
1. Створити лінійний однозв’язний список, вивести його. Якщо в списку є елемент із заданим ключем, вилучити його, а попередній та настуні поміняти місцями. Виконати завдання згідно варіанту.
2. Створити двозв’язний список, вивести його. Виконати завдання згідно варіанту з двозвязним списком.
Варіанти індивідуальних завдань
16. Створити стек символів. Якщо у стеці більше голосних літер – новий стек заповнити 10 одиницями, якщо ж більше голосних – новий стек заповнити двійками.
Теоретичні відомості:
Лінійний однозвв’язний список
Лінійний список – це динамічна структура даних, кожний елемент якої за допомогою вказівника зв’язується з наступним елементом.
З визначення випливає, що кожен елемент списку містить поле даних (Data) (воно може мати складну структуру) і поле посилання на наступний елемент (next). Поле посилання останнього елемента повинно містити порожній покажчик (NULL).
Так як посилання лише одне (тільки на наступний елемент), то такий список є однозв’язним.
Коли говорять про лінійний список, то, як правило, мають на увазі саме однозв’язний список.
Двобічно зв'язаний список — вид зв'язаного списку, у якому посилання в кожному вузлі вказують на попередній і на подальший вузол у списку.
Якщо в списку після останнього елемента йде перший, то такий список називається кільцевим двобічно зв'язаним списком. Тобто, поле prev голови списку вказує на хвіст списку, а поле next хвоста списку вказує на голову списку.
По двобічно зв'язаному списку можна пересуватися в будь-якому напрямку — як від початку до кінця, так і навпаки. Для нього простіше проводити видалення і перестановку елементів, оскільки завжди відомі адреси тих елементів списку, вказівник яких спрямований на змінюваний елемент.
Хід роботи:
Написано програмний код, який виконує 2 завдання. Перше – за допомогою однозв’язного списку, друге – двозв’язного.
Код програми для однозв’язного списка:
Посилання на код:
https://replit.com/join/hpvwlgzqic-tr-15khavkin
#include
#include "string"
#include
#include
#include
using namespace std;
template class Node {
public:
Node* pNext;
T Data;
Node(T Data = T(), Node* pNext = nullptr) {
this->Data = Data;
this->pNext = pNext;
}
};
template 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 Show();
void DelAndSwap(T Data);
private:
int Size;
Node* Head;
};
template List::List() {
Size = 0;
Head = nullptr;
}
template List::~List() { Clear(); }
template void List::PushBack(T Data) {
if (!Head) {
Head = new Node(Data);
}else {
Node* Current = this->Head;
while (Current->pNext) {
Current = Current->pNext;
}
Current->pNext = new Node(Data);
}
Size++;
}
template T& List::operator[](const int Index) {
int Counter = 0;
Node* Current = this->Head;
while (Current) {
if (Counter == Index) {
return Current->Data;
}
Current = Current->pNext;
Counter++;
}
}
template void List::PopFront() {
Node* Temp = Head;
Head = Head->pNext;
delete Temp;
Size--;
}
template void List::PushFront(T Data) {
...
Завантаження файлу
Стань активним учасником руху antibotan!
Поділись актуальною інформацією,
і отримай привілеї у користуванні архівом! Детальніше
Поділись актуальною інформацією,
і отримай привілеї у користуванні архівом! Детальніше