НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ
імені ІГОРЯ СІКОРСЬКОГО”
ЗВІТ
з лабораторної роботи №5
з навчальної дисципліни “Програмування складних алгоритмів”
Тема: «Лінійні однозв’язні та двозв’язні списки»
Варіант № 16
Дата «19» травень 2022
Київ 2022
Мета роботи: Метою лабораторної роботи є ознайомитися з основами роботи з двозв’язним списком, однозв’язним.
Завдання до лабораторної роботи:
1. Створити лінійний однозв’язний список, вивести його. Якщо в списку є елемент із заданим ключем, вилучити його, а попередній та настуні поміняти місцями. Виконати завдання згідно варіанту.
2. Створити двозв’язний список, вивести його. Виконати завдання згідно варіанту з двозвязним списком.
Варіанти індивідуальних завдань
16. Створити стек символів. Якщо у стеці більше голосних літер – новий стек заповнити 10 одиницями, якщо ж більше голосних – новий стек заповнити двійками.
Теоретичні відомості:
Лінійний однозвв’язний список
Лінійний список – це динамічна структура даних, кожний елемент якої за допомогою вказівника зв’язується з наступним елементом.
З визначення випливає, що кожен елемент списку містить поле даних (Data) (воно може мати складну структуру) і поле посилання на наступний елемент (next). Поле посилання останнього елемента повинно містити порожній покажчик (NULL).
Так як посилання лише одне (тільки на наступний елемент), то такий список є однозв’язним.
Коли говорять про лінійний список, то, як правило, мають на увазі саме однозв’язний список.
Двобічно зв'язаний список — вид зв'язаного списку, у якому посилання в кожному вузлі вказують на попередній і на подальший вузол у списку.
Якщо в списку після останнього елемента йде перший, то такий список називається кільцевим двобічно зв'язаним списком. Тобто, поле prev голови списку вказує на хвіст списку, а поле next хвоста списку вказує на голову списку.
По двобічно зв'язаному списку можна пересуватися в будь-якому напрямку — як від початку до кінця, так і навпаки. Для нього простіше проводити видалення і перестановку елементів, оскільки завжди відомі адреси тих елементів списку, вказівник яких спрямований на змінюваний елемент.
Хід роботи:
Написано програмний код, який виконує 2 завдання. Перше – за допомогою однозв’язного списку, друге – двозв’язного.
Код програми для однозв’язного списка:
Посилання на код:
https://replit.com/join/hpvwlgzqic-tr-15khavkin
#include <iostream>
#include "string"
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
template <typename T> class Node {
public:
Node* pNext;
T Data;
Node(T Data = T(), Node* 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 Show();
void DelAndSwap(T Data);
private:
int Size;
Node<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 Node<T>(Data);
}else {
Node<T>* Current = this->Head;
while (Current->pNext) {
Current = Current->pNext;
}
Current->pNext = new Node<T>(Data);
}
Size++;
}
template <typename T> T& List<T>::operator[](const int Index) {
int Counter = 0;
Node<T>* Current = this->Head;
while (Current) {
if (Counter == Index) {
return Current->Data;
}
Current = Current->pNext;
Counter++;
}
}
template <typename T> void List<T>::PopFront() {
Node<T>* Temp = Head;
Head = Head->pNext;
delete Temp;
Size--;
}
template <typename T> void List<T>::PushFront(T Data) {
Head = new Node<T>(Data, Head);
Size++;
}
template <typename T> void List<T>::Insert(T Value, int Index) {
if (Index == 0) {
PushFront(Value);
}else {
Node<T>* Previous = this->Head;
for (int i = 0; i < Index - 1; ++i) {
Previous = Previous->pNext;
}
Node<T>* NewNode = new Node<T>(Value, Previous->pNext);
Previous->pNext = NewNode;
Size++;
}
}
template <typename T> void List<T>::RemoveAt(int Index){
if (Index < 0 || Index > Size) return;
if (Index == 0) {
PopFront();
}else {
Node<T>* Previous = this->Head;
for (int i = 0; i < Index - 1; ++i) {
Previous = Previous->pNext;
}
Node<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){
Node<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>::Show(){
Node<T>* Temp = Head;
for (int i = 0; i < Size; i++){
cout << Temp->Data << " ";
Temp = Temp->pNext;
}
cout << endl;
}
template<typename T>
void List<T>::DelAndSwap(T Data){
Node<T>* Prev = nullptr;
Node<T>* Temp = Head;
for (int i = 0; i < Size; i++){
if (Temp->Data == Data){
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;
}
cout << "Число не знайдено" << endl;
}
int main(){
srand(time(nullptr));
cout << "Завдання 1" << endl;
int N;
cout << "Введіть розмір списку :" << endl;
cin >> N;
List<int> Lst;
cout << "Початковий список"<< endl;
for (int i = 0; i < N; ++i){
Lst.PushBack(rand() % 100 - 50);
}
Lst.Show();
cout << "Введіть число для видалленя(поперднє і наступне будуть замінені на один одне): ";
int numberdel;
cin >> numberdel;
Lst.DelAndSwap(numberdel);
cout << "Список після: " << endl;
Lst.Show();
return 0;
}
Результат програми для однозв’язного списку:
/
Код програми для двозв’язного списка:
Посилання на код:
https://replit.com/join/dakeheevuo-tr-15khavkin
#include "string"
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
template <typename T> class Node2 {
public:
Node2 *pNext;
Node2 *pPrev;
T Data;
Node2(T Data = T(), Node2 *pNext = nullptr, Node2 *pPrev = nullptr) {
this->Data = Data;
this->pNext = pNext;
this->pPrev = pPrev;
}
};
template<typename T>
class List2{
public:
List2();
~List2();
void Show();
void PushBack(T Data);
T& operator[](const int index);
void PopFront();
void Clear();
void VoweOrConso();
int GetSize() { return Size;}
private:
int Size;
Node2<T> *Head;
Node2<T> *Tail;
};
template<typename T>
List2<T>::List2(){
Head = nullptr;
Tail = nullptr;
Size = 0;
}
template<typename T>
List2<T>::~List2(){
Clear();
}
template<typename T>
void List2<T>::Show(){
Node2<T> *Temp = Head;
for (int i = 0; i < Size; i++){
cout << Temp->Data << " ";
Temp = Temp->pNext;
}
cout << endl;
}
template<typename T>
void List2<T>::PushBack(T Data){
if(Head == nullptr){
Head = new Node2<T>(Data);
Tail = Head;
} else{
Node2<T> *current = this->Head;
while(current->pNext != nullptr){
current = current->pNext;
}
current->pNext = new Node2<T>(Data, nullptr, current);
Tail = current->pNext;
}
Size++;
}
template<typename T>
T & List2<T>::operator[](const int index){
int counter = 0;
Node2<T> *current = this->Head;
while (current != nullptr){
if (counter == index){
return current->Data;
}
current = current->pNext;
counter++;
}
}
template<typename T>
void List2<T>::PopFront(){
Node2<T> *temp = Head;
Head = Head->pNext;
delete temp;
Size--;
}
template<typename T>
void List2<T>::Clear(){
while (Size){
PopFront();
}
}
template<typename T>
void List2<T>::VoweOrConso(){
char Vovels[6] = { 'A','O','U','I','E','Y' };
char Consonats[19] = { 'B','C','D','F','G', 'H','K','L','M','N','P','Q','R','S','T','V','W','X','Z'};
int k=0;
int k2=0;
List2<int> Lst3;
Node2<T> *Temp = Head;
for (int i = 0; i < Size; i++){
for (int v = 0; v < 6; v++){
if(Temp->Data == Vovels[v]){
k=k+1;
}
}
for (int c = 0; c < 19; c++){
if(Temp->Data == Consonats[c]){
k2=k2+1;
}
}
Temp=Temp->pNext;
}
cout << k << " " << k2 << endl;
if(k>k2){
cout << "Більше голосних" << endl;
for (int i = 0; i < 10; ++i) {
Lst3.PushBack(1);
}
}else if(k2>k){
cout << "Більше приголосних" << endl;
for (int i = 0; i < 10; ++i) {
Lst3.PushBack(2);
}
} else {
cout << "Однакова кількість звуків" << endl;
for (int i = 0; i < 10; ++i) {
Lst3.PushBack(3);
}
}
Lst3.Show();
}
int main(){
srand(time(nullptr));
cout << "Завдання 2" << endl;
int N;
cout << "Введіть розмір списку :" << endl;
cin >> N;
List2<char> Lst2;
cout << "Початковий список: " << endl;
char c;
for (int i = 0; i < N; ++i) {
c = (rand() % 25) + 65;
Lst2.PushBack(c);
}
Lst2.Show();
Lst2.VoweOrConso();
return 0;
}
Результат другої програми для двоозв’язного списку:
/ / /
Висновок: У цій лабораторної роботі ознайомилися з роботою одно та двозв’язних списків, стеком та чергою Створили одно та двозв’язний список та виконали завдання згідно до індивідуального варіанту. Зроблено звіт до лабораторної роботи та надіслано викладачу.