Лінійні однозв’язні та двозв’язні списки

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

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

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

Рік:
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) { ...
Антиботан аватар за замовчуванням

17.07.2023 07:07

Коментарі

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

Завантаження файлу

Якщо Ви маєте на своєму комп'ютері файли, пов'язані з навчанням( розрахункові, лабораторні, практичні, контрольні роботи та інше...), і Вам не шкода ними поділитись - то скористайтесь формою для завантаження файлу, попередньо заархівувавши все в архів .rar або .zip розміром до 100мб, і до нього невдовзі отримають доступ студенти всієї України! Ви отримаєте грошову винагороду в кінці місяця, якщо станете одним з трьох переможців!
Стань активним учасником руху antibotan!
Поділись актуальною інформацією,
і отримай привілеї у користуванні архівом! Детальніше