在双链表中添加函数会导致无限循环

Question

我在编写双链表时遇到了麻烦。问题是当我检查链接是否为nullptr时，我的Add函数会导致无限循环。当我不这样做时，它会给我一个错误。我一直在努力解决这个问题，但我怎么也想不出来。下面是add方法:

    void Add(string n, int w) //Method to add a node to the Linked List and maintain the order.
{
    node * nd = new node(n, w, nullptr, nullptr);
    if (nHead == nullptr && wHead == nullptr) //If there is nothing in the Linked List
    {
        nHead = nd; //Add a node
        wHead = nd;
    }
    else //If there is something in the linked List
    {
        node * ntraverse = nHead; //variable to traverse down the name links
        while (nd->name > ntraverse->name && ntraverse->wLink != nullptr)
        {
            ntraverse = ntraverse->nLink; // Traverses down the name links until nd's name is smaller than a links
        }
        nd->nLink = ntraverse; // Here, the namelink for nd is set to ntraverse, since ntraverse is less than or equal to nlink
        ntraverse->nLink = nd; // So here, since nd is the new value appended to the rest of the list, we set ntraverse = nlink.
                               // note at this point, we have not handled weight
        node * wtraverse = wHead; //variable to traverse down the weight links
        while (nd->weight > wtraverse->weight && wtraverse->wLink != nullptr)
        {
            wtraverse = wtraverse->wLink; // Traverses down the weight links until nd's weight is smaller than a links
        }
        nd->wLink = wtraverse; // Here, the namelink for nd is set to ntraverse, since ntraverse is less than or equal to nlink
        wtraverse->wLink = nd; // So here, since nd is the new value appended to the rest of the list, we set ntraverse = nlink.
        //at this point, nd holds both the correct nlink and wlink
    }
    cout << "Added: " << nd->name << " " << nd->weight << "n";
    cout << "Current nlist:n";
    nPrint();
    cout << "Current wlist:n";
    wPrint();
    size++; //increment size
}

任何帮助都将非常感激。如果你需要我回答什么，请告诉我。Node工作得很好，它存储了4个值:name, weight, nLink和wLink，其中nLink按名称排序，wLink按权重排序。对于LinkedList, nHead是名称头，wHead是权重头。

再次感谢您的帮助。

Answer 1

你把wLink和nLink混在一起了

node * ntraverse = nHead; //variable to traverse down the name links
while (nd->name > ntraverse->name && ntraverse->wLink != nullptr)

在上面的示例中，您遍历名称链接并测试是否位于权重列表的末尾。

这不是一个双链表，它是两个单链表，您应该分别处理每个列表。

换句话说，你的代码应该看起来像这样:

    void Add(string n, int w) //Method to add a node to the Linked List and maintain the order.
{
    node * nd = new node(n, w, nullptr, nullptr);
    if (nHead == nullptr ) //If there is nothing in the Linked List
    {
        nHead = nd; //Add a node
    }

    else //If there is something in the linked List
    {
       /* Code to handle nLink with no mention of wLink */
    }
    if (wHead == nullptr ) //If there is nothing in the Linked List
    {
        wHead = nd; //Add a node
    }

    else //If there is something in the linked List
    {
       /* Code to handle wLink with no mention of nLink */
    }
}

当然，理想的解决方案是编写一个链表类....

Answer 2

所以我知道问题是什么了。在每个循环的末尾，我有

    nd->wLink = wtraverse; // Here, the namelink for nd is set to ntraverse, since ntraverse is less than or equal to nlink
    wtraverse->wLink = nd; // So here, since nd is the new value appended to the rest of the list, we set ntraverse = nlink.

这会造成一个循环。Nd的链接存储wtraverse，而wtraverse的链接存储Nd，这意味着其中一个链接将指向列表的另一部分。

关于双链表术语的语义争论，我的数据结构教授将节点有两个链接的数据结构称为双链表。无论正确与否，争论语义并没有什么帮助，也没有做任何事情来解决问题。