Question

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

Answer 1

Ответ:

Для добавления функционала двусвязного списка в код, нужно внести следующие изменения:

1. Определить структуру для ячейки двусвязного списка (Node) с указателями на предыдущую и следующую ячейки.

2. Внести соответствующие изменения в класс ForwardList для поддержки двусвязного списка, такие как наличие указателя на последнию ячейку (tail) и изменение связей при добавлении и удалении элементов.

Вот пример изменений для реализации двусвязного списка:

// Одна ячейка двусвязного списка

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).

Вот пример реализации:

// Одна ячейка двусвязного списка

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;

}

Теперь вы можете использовать этот класс для работы с двусвязным списком, включая добавление, удаление и вывод элементов как в примере выше.

Answer 2

Для добавления двусвязного списка, вам нужно создать новый класс DoubleNode, который будет иметь два указателя: один на следующий элемент (pNext) и один на предыдущий элемент (pPrev). Затем вы можете изменить класс ForwardList для поддержки двусвязного списка, добавив указатель tail на последний элемент и обновляя указатели pNext и pPrev при добавлении и удалении элементов.

Вот как может выглядеть обновленный код:

cppCopy code
#include <iostream>

template <typename T>
struct DoubleNode {
    T value;
    DoubleNode* pNext;
    DoubleNode* pPrev;
    
    DoubleNode(T value = T()) : value(value), pNext(nullptr), pPrev(nullptr) {}
};

template <typename T>
class DoubleLinkedList {
private:
    DoubleNode<T>* head;
    DoubleNode<T>* tail;
    unsigned int size;

public:
    DoubleLinkedList() : head(nullptr), tail(nullptr), size(0) {}

    unsigned int GetSize() const {
        return size;
    }

    void PushFront(const T& value) {
        size++;
        if (head == nullptr) {
            head = tail = new DoubleNode<T>(value);
            return;
        }

        DoubleNode<T>* newNode = new DoubleNode<T>(value);
        newNode->pNext = head;
        head->pPrev = newNode;
        head = newNode;
    }

    void PopFront() {
        if (head == nullptr) {
            return;
        }

        size--;
        if (head == tail) {
            delete head;
            head = tail = nullptr;
        } else {
            DoubleNode<T>* temp = head->pNext;
            temp->pPrev = nullptr;
            delete head;
            head = temp;
        }
    }

    void PushBack(const T& value) {
        size++;
        if (tail == nullptr) {
            head = tail = new DoubleNode<T>(value);
            return;
        }

        DoubleNode<T>* newNode = new DoubleNode<T>(value);
        newNode->pPrev = tail;
        tail->pNext = newNode;
        tail = newNode;
    }

    void Print() const {
        DoubleNode<T>* temp = head;
        while (temp != nullptr) {
            std::cout << temp->value << " ";
            temp = temp->pNext;
        }
        std::cout << std::endl;
    }

    bool operator ==(const DoubleLinkedList<T>& other) const {
        if (size != other.size) {
            return false;
        }

        DoubleNode<T>* thisTemp = head;
        DoubleNode<T>* otherTemp = other.head;

        while (thisTemp != nullptr) {
            if (thisTemp->value != otherTemp->value) {
                return false;
            }

            thisTemp = thisTemp->pNext;
            otherTemp = otherTemp->pNext;
        }

        return true;
    }
};

int main() {
    // Теперь вы можете использовать DoubleLinkedList
    DoubleLinkedList<int> list1;
    list1.PushBack(1);
    list1.PushBack(2);
    list1.PushBack(3);

    DoubleLinkedList<int> list2;
    list2.PushBack(1);
    list2.PushBack(2);
    list2.PushBack(3);

    if (list1 == list2) {
        std::cout << "Lists are equal." << std::endl;
    } else {
        std::cout << "Lists are not equal." << std::endl;
    }

    return 0;
}

В этом коде добавлены операции для работы с двусвязным списком, включая PushBack, Print, и operator==. Кроме того, я добавил проверку на равенство двух списков в функции main.