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