c++ - 链表插入错误

Question

我正在尝试像这样在 C++ 中实现一个带有公开节点的简单双向链表 (省略了一些方法，应该很清楚它们的作用):

template<typename T>
class Node
{
public:
    Node(T _value)
    {
        m_Data = _value;
        m_HasParent = false;
        m_HasNext = false;
        m_Parent = NULL;
        m_Next = NULL;
    }
    void insertAfter(Node<T>* _item)
    {
        m_Next = _item;
        m_HasNext = true;
        _item->insertBefore(this);
    }
    void insertBefore(Node<T>* _item)
    {
        if(m_HasParent)
        {
            m_Parent->insertAfter(_item);
            _item->insertAfter(this);
        }
        else
        {
            m_Parent = _item;
            m_HasParent = true;
        }
    }
private:
    T m_Data;
    Node<T>* m_Parent;
    Node<T>* m_Next;
    bool m_HasParent;
    bool m_HasNext;
};

template<typename T>
class LinkedList
{
public:
    LinkedList()
    {
        m_Root = NULL;
        m_HasRoot = false;
    }
    ~LinkedList()
    {
        if(m_HasRoot)
        {
            delete m_Root;
        }
    }
    void pushFront(T _value)
    {
        if(m_HasRoot)
        {
            Node<T>* node = new Node<T>(_value);
            m_Root->insertBefore(node);
            node->insertAfter(m_Root);
            m_Root = node;
        }
        else
        {
            m_Root = new Node<T>(_value);
            m_HasRoot = true;
        }
    }
    void pushBack(T _value)
    {
        if(m_HasRoot)
        {
            Node<T>* last = m_Root;
            while(true)
            {
                if(last->getHasNext())
                {
                    last = last->getNext();
                }
                else
                {
                    break;
                }
            }
            Node<T>* node = new Node<T>(_value);
            last->insertAfter(node);
            return;
        }
        else
        {
            m_Root = new Node<T>(_value);
            m_HasRoot = true;
        }
    }

    T operator[](int _i)
    {
        Node<T>* last = m_Root;
        for(int i = 0; i <= _i; i++)
        {
            if(last->getHasNext())
            {
                last = last->getNext();
            }
            else
            {
                break;
            }
        }
        return last->getData();
    }
private:
    Node<T>* m_Root;
    bool m_HasRoot;
};

但是，当执行下面的小测试时:

int main(int argc, char** argv)
{
    LinkedList<int> l;
    l.pushBack(0);
    l.pushBack(1);
    l.pushBack(2);
    l.pushBack(3);
    int count = l.getCount();
    std::cout << "count: " << count << std::endl;
    for(int i = 0; i < count; i++)
    {
        std::cout << "Value at [" << i << "]: " << l[i] << std::endl;
    }
    std::string s;
    std::cin >> s;
    return 0;
}

我希望看到数字 0, 1, 2, 3 按此顺序打印出来，但这是我得到的:

出于某种原因，向后插入不太有效。我发现我的代码没有根本性的错误，任何人都可以发现问题吗？这是在 MinGW 5.1、64 位、Windows 10 64 位上。然而，在runnable.com上执行这个问题时，似乎一切正常？？参见 this draft .这是 MinGW 中的错误还是我的错误？

编辑1

现在这很奇怪，有时它似乎在 runnable 中工作，有时它产生的结果与我本地机器上的结果相同......我完全糊涂了。

Answer 1

尝试改变 ListWidget::operator[] 中的循环条件来自 i <= _i至 i < _i . _i 不应有迭代等于 0 .

标志是您从第二个元素开始打印，即 1并打印最后一个元素两次。您忘记了根节点。

---

请注意，您正在检查节点是否有后继节点，但您并未检查列表是否不为空 (m_root != nullptr)。使其保持一致 - 要么删除所有可能的 UB 情况，要么不检查任何内容。