С++
Добавить к коду следующие:
1. PopBack (удаление с конца)
2. Insert (добавление по индексу)
3. RemoveAt (удаление по индексу)
4. operator +
5. Конструктор копирования
6. Сортировка
7. GetUnique, который возвращает новый лист ТОЛЬКО из уникальных элементов
Сам код:
#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;
}
Ответы
Объяснение:
Для добавления описанных функций к классу `ForwardList`, вам необходимо выполнить следующие шаги. Ниже представлен код с комментариями, которые поясняют каждый шаг:
```cpp
#include <iostream>
#include <set> // Для сортировки и поиска уникальных элементов
using namespace std;
template <typename T>
struct Node {
T value;
Node* pNext;
Node(T value = T()) {
this->value = value;
this->pNext = nullptr;
}
};
template <typename T>
class ForwardList {
typedef Node<T> Node;
Node* head;
unsigned int size;
public:
// Остальной код без изменений
// 1. PopBack (удаление с конца)
void PopBack() {
if (size == 0)
return;
if (size == 1) {
delete head;
head = nullptr;
size = 0;
return;
}
Node* temp = head;
while (temp->pNext->pNext != nullptr) {
temp = temp->pNext;
}
delete temp->pNext;
temp->pNext = nullptr;
size--;
}
// 2. Insert (добавление по индексу)
void Insert(unsigned int index, const T value) {
if (index == 0) {
PushFront(value);
return;
}
if (index >= size) {
PushBack(value);
return;
}
Node* temp = head;
for (unsigned int i = 0; i < index - 1; i++) {
temp = temp->pNext;
}
Node* newNode = new Node(value);
newNode->pNext = temp->pNext;
temp->pNext = newNode;
size++;
}
// 3. RemoveAt (удаление по индексу)
void RemoveAt(unsigned int index) {
if (index >= size)
return;
if (index == 0) {
PopFront();
return;
}
if (index == size - 1) {
PopBack();
return;
}
Node* temp = head;
for (unsigned int i = 0; i < index - 1; i++) {
temp = temp->pNext;
}
Node* toDelete = temp->pNext;
temp->pNext = toDelete->pNext;
delete toDelete;
size--;
}
// 4. operator +
ForwardList operator+(const ForwardList& other) {
ForwardList result(*this);
Node* temp = other.head;
while (temp != nullptr) {
result.PushBack(temp->value);
temp = temp->pNext;
}
return result;
}
// 5. Конструктор копирования
ForwardList(const ForwardList& other) {
head = nullptr;
size = 0;
Node* temp = other.head;
while (temp != nullptr) {
PushBack(temp->value);
temp = temp->pNext;
}
}
// 6. Сортировка
void Sort() {
if (size <= 1)
return;
for (unsigned int i = 0; i < size - 1; i++) {
Node* temp = head;
for (unsigned int j = 0; j < size - i - 1; j++) {
if (temp->value > temp->pNext->value) {
T tmpValue = temp->value;
temp->value = temp->pNext->value;
temp->pNext->value = tmpValue;
}
temp = temp->pNext;
}
}
}
// 7. GetUnique, который возвращает новый лист ТОЛЬКО из уникальных элементов
ForwardList GetUnique() {
ForwardList result;
set<T> uniqueSet;
Node* temp = head;
while (temp != nullptr) {
uniqueSet.insert(temp->value);
temp = temp->pNext;
}
for (const T& value : uniqueSet) {
result.PushBack(value);
}
return result;
}
};
int main() {
// Остальной код без изменений
return 0;
}
```
Теперь у вас есть реализация методов `PopBack`, `Insert`, `RemoveAt`, перегрузки оператора `+`, конструктора копирования, сортировки и `GetUnique`. Вы можете использовать их в своей программе для работы с односвязным списком `ForwardList`.
Проверь!