С++
Добавить к коду следующие:
ДВУСВЯЗНЫЙ список
1. Есть указатель на последнюю ячейку (tail).
2. Каждая ячейка знает где находится прошлая.
Код:
#include
#include
using namespace std;
// Одна ячейка односвязного списка
// В структуре всё по-умолчанию public
// T - шаблон. Позволяет создавать объекты, указывая тип данных T
template
struct Node {
T value; // значение ячейки
Node* pNext; // указатель на следующую ячейку
Node(T value = T()) {
this->value = value;
this->pNext = nullptr;
}
};
// Односвязный список
template
class ForwardList {
// Node будет заменяться на Node
typedef Node Node;
Node* head; // указатель на первую ячейку
unsigned int size; // кол-во ячеек (unsigned int - инты без минуса)
public:
ForwardList() {
head = nullptr; // head = 00000000
size = 0;
}
unsigned int GetSize() const {
return size;
}
void PushFront(const T value) {
size++;
// Если список пуст
if (head == nullptr) {
// Создаю новую ячейку и привязываю её к указателю на первую ячейку
head = new Node(value);
// окончить функцию (дальше не сработет)
return;
}
// Если список не был пуст
// Создаю новую ячейку, которая станет первой
Node* temp = new Node(value);
// Следующей от темп будет нынешняя первая ячейка
temp->pNext = head;
// Переключую указатель на первую ячейку на новосозданную
head = temp;
}
void PopFront() {
if (head == nullptr)
return;
// Сохраняем адрес второй ячейки
Node* temp = head->pNext;
// удаляем первую ячейку
delete head;
// переключаем голову на вторую (теперь первую) ячейку
head = temp;
size--;
}
// !!! НЕОПТИМИЗИРОВАННО ИЗ-ЗА СПЕЦИФИКИ ОДНОСВЯЗНОГО СПИСКА
void PushBack(const T value) {
size++;
if (head == nullptr) {
head = new Node(value);
return;
}
// Создаю указатель для перебора ячеек
Node* temp = head;
// Переключаю указатель на последнюю ячейку
while (temp->pNext != nullptr)
temp = temp->pNext;
// Создаю новую ячейку после последней
temp->pNext = new Node(value);
}
// Вывод односвязного списка на экран
void Print() const {
// Создаем указатель для перебора ячеек
// Сначала он будет указывать на первую ячейку
Node* temp = head;
// Перебираем ячейки до тех пор пока не вылезем за пределы
while (temp != nullptr) {
// Вывожу значение ячейки на экран
std::cout << temp->value << " ";
// Переключаю указатель на следующую ячейку
temp = temp->pNext;
}
std::cout << std::endl;
}
bool operator ==(const ForwardList & other) const {
if (this->size != other.size)
return false;
// Указатель для перебора this листа
Node* thisTemp = this->head;
// указатель для перебора other листа
Node* otherTemp = other.head;
// перебираем пока не переберём весь лист
while (thisTemp != nullptr) {
// Если пара ячеек не совпала по значению - списки не равны
if (thisTemp->value != otherTemp->value)
return false;
thisTemp = thisTemp->pNext;
otherTemp = otherTemp->pNext;
}
// Если до сюда ни разу не сработал return false - значит все ок и списки равны
return true;
}
};
int main() {
// DZ
// 1. PopBack (удаление с конца)
// 2. Insert (добавление по индексу)
// 3. RemoveAt (удаление по индексу)
// 4. operator +
// 5. Конструктор копирования
// 6. Сортировка
// 7. GetUnique, который возвращает новый лист ТОЛЬКО из уникальных элементов
ForwardList fl;
fl.PushBack(1);
fl.PushBack(2);
fl.PushBack(3);
ForwardList fl2;
fl2.PushBack(1);
fl2.PushBack(2);
fl2.PushBack(3);
if (fl == fl2)
std::cout << "LISTS ARE EQUAL" << std::endl;
}
Ответы
Ответ:
Для добавления функционала двусвязного списка в код, нужно внести следующие изменения:
1. Определить структуру для ячейки двусвязного списка (Node) с указателями на предыдущую и следующую ячейки.
2. Внести соответствующие изменения в класс ForwardList для поддержки двусвязного списка, такие как наличие указателя на последнию ячейку (tail) и изменение связей при добавлении и удалении элементов.
Вот пример изменений для реализации двусвязного списка:
```cpp
// Одна ячейка двусвязного списка
template <typename T>
struct Node {
T value; // значение ячейки
Node* pNext; // указатель на следующую ячейку
Node* pPrevious; // указатель на предыдущую ячейку
Node(T value = T()) {
this->value = value;
this->pNext = nullptr;
this->pPrevious = nullptr;
}
};
// Двусвязный список
template <typename T>
class DoublyLinkedList {
typedef Node<T> Node;
Node* head; // указатель на первую ячейку
Node* tail; // указатель на последнюю ячейку
unsigned int size; // кол-во ячеек
public:
DoublyLinkedList() {
head = nullptr;
tail = nullptr;
size = 0;
}
// ... (оставьте остальной код без изменений)
};
int main() {
// ... (оставьте остальной код без изменений)
}
```
Для реализации функционала двусвязного списка, нужно внести следующие изменения:
1. Добавить функцию для добавления элемента в начало списка (PushFront), учитывая обновление указателя на предыдущую ячейку.
2. Добавить функцию для добавления элемента в конец списка (PushBack), учитывая обновление указателя на следующую ячейку.
3. Добавить функцию для удаления элемента с начала списка (PopFront), учитывая обновление указателя на предыдущую ячейку.
4. Добавить функцию для вывода списка в обратном порядке (PrintReverse), используя указатель на последнюю ячейку (tail).
Вот пример реализации:
```cpp
// Одна ячейка двусвязного списка
template <typename T>
struct Node {
T value; // значение ячейки
Node* pNext; // указатель на следующую ячейку
Node* pPrevious; // указатель на предыдущую ячейку
Node(T value = T()) {
this->value = value;
this->pNext = nullptr;
this->pPrevious = nullptr;
}
};
// Двусвязный список
template <typename T>
class DoublyLinkedList {
typedef Node<T> Node;
Node* head; // указатель на первую ячейку
Node* tail; // указатель на последнюю ячейку
unsigned int size; // кол-во ячеек
public:
DoublyLinkedList() {
head = nullptr;
tail = nullptr;
size = 0;
}
void PushFront(const T value) {
size++;
Node* newNode = new Node(value);
newNode->pNext = head;
if (head != nullptr) {
head->pPrevious = newNode;
}
head = newNode;
if (size == 1) {
tail = head;
}
}
void PushBack(const T value) {
size++;
Node* newNode = new Node(value);
if (tail != nullptr) {
tail->pNext = newNode;
newNode->pPrevious = tail;
}
tail = newNode;
if (size == 1) {
head = tail;
}
}
void PopFront() {
if (head == nullptr) {
return;
}
size--;
Node* temp = head;
head = head->pNext;
if (head != nullptr) {
head->pPrevious = nullptr;
} else {
tail = nullptr;
}
delete temp;
}
void Print() const {
Node* temp = head;
while (temp != nullptr) {
std::cout << temp->value << " ";
temp = temp->pNext;
}
std::cout << std::endl;
}
void PrintReverse() const {
Node* temp = tail;
while (temp != nullptr) {
std::cout << temp->value << " ";
temp = temp->pPrevious;
}
std::cout << std::endl;
}
};
int main() {
DoublyLinkedList<int> dll;
dll.PushBack(1);
dll.PushBack(2);
dll.PushBack(3);
dll.PushFront(0);
dll.Print(); // Output: 0 1 2 3
dll.PrintReverse(); // Output: 3 2 1 0
dll.PopFront();
dll.Print(); // Output: 1 2 3
dll.PrintReverse(); // Output: 3 2 1
return 0;
}
```
Теперь вы можете использовать этот класс для работы с двусвязным списком, включая добавление, удаление и вывод элементов как в примере выше.