Пользовательская реализация двусвязного списка не работает (образовательный) - PullRequest
Новая
       37

Пользовательская реализация двусвязного списка не работает (образовательный)

2 голосов
/ 12 января 2020

Я реализовал свою собственную простую версию двусвязного списка. К сожалению, с этим, похоже, произошла ошибка. Кажется, что заголовок списка перемещается на новый Node, каждый раз, когда я добавляю один с push_back. Из-за этого print будет печатать последнее значение бесконечно.

Связанный список: 

struct doubly_linked_list
{
    Node *head = nullptr;
    Node *tail = nullptr;
    void push_back(Node n)
    {
        if (this->head == nullptr)
        {
            this->head = &n;
            this->tail = nullptr;
        }
        n.prev = this->tail;
        if (this->tail)
        {
            n.prev->next = &n;
        }
        this->tail = &n;
    }
    void print()
    {
        Node *tmp = this->head;
        while (tmp != nullptr)
        {
            std::cout << tmp->data << ", ";
            tmp = tmp->next;
        }
    }
};

Где Узел реализован как 

struct Node
{
    int data;
    Node *next = nullptr;
    Node *prev = nullptr;
    Node(int data)
    {
        this->data = data;
    }
    Node()
    {
        this->data = -1;
    }
};

main 

int main()
{
    doubly_linked_list dl;
    dl.push_back(Node{3});
    dl.push_back(Node{2});
    dl.push_back(Node{1});
    dl.push_back(Node{0});
    dl.push_back(Node{5});
    dl.print(); // print 5 forever
}

Отказ от ответственности: Просим учесть, что topi c этого поста носит образовательный характер. Я знаю о списках в стандарте c ++.

1 Ответ

2 голосов
/ 12 января 2020

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

#include <iostream>

struct Node
{
    int data;
    Node *next = nullptr;
    Node *prev = nullptr;
    Node(int data)
    {
        this->data = data;
    }
    Node()
    {
        this->data = -1;
    }
};

struct doubly_linked_list
{
    Node *head = nullptr;
    Node *tail = nullptr;
    void push_back(Node* n)
    {
        if (this->head == nullptr)
        {
            this->head = n;
            this->tail = nullptr;
        }
        n->prev = this->tail;
        if (this->tail)
        {
            n->prev->next = n;
        }
        this->tail = n;
    }
    void print()
    {
        Node *tmp = this->head;
        while (tmp != nullptr)
        {
            std::cout << tmp->data << ", ";
            tmp = tmp->next;
        }
     }
};

int main()
{
    doubly_linked_list dl;
    dl.push_back(new Node{3});
    dl.push_back(new Node{2});
    dl.push_back(new Node{1});
    dl.push_back(new Node{0});
    dl.push_back(new Node{5});
    dl.print(); // print 5 forever
}
...