С++
Добавить к коду следующие:
ДВУСВЯЗНЫЙ список
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;

}

0 0 Пожаловаться