c++ - 为什么我的列表插入函数不会生成新节点？

Question

你好，我的这段代码的问题是在我的第二个 else 循环中；我从不输入它，因此我从不为我的列表创建新节点。谁能帮我看看我错过了什么？

    bool List::Insert(int data)
{
    Node* P = new Node;
    if(P==NULL)
    {
        return false;
    }
    else
    {
        P ->info = data;
        P ->next = NULL;
            if(Head == NULL)
            {
                Head = P;
            }
            else
            {
                Node* lastNode;
                for(lastNode = Head; lastNode ->next != NULL; lastNode = lastNode ->next)
                {
                    lastNode ->next = P;
                }
            }
        return true;
    }
}

Answer 1

这个:

Node* lastNode;
for(lastNode = Head; lastNode ->next != NULL; lastNode = lastNode ->next)
{
    lastNode ->next = P;
}

完全错了。它将为列表中当前的每个节点更改next 指针，以指向您的新节点。您只需更改最后 节点中的指针:

Node* lastNode = Head;
while (lastNode->next != NULL)
    lastNode = lastNode->next;
lastNode->next = P;

为了提高效率，您可能还想维护一个单独的 Tail 指针(除了您的 Head 之外)，这样您就可以简单地将整个操作替换为:

Tail->next = P;
Tail = P;

这样，您就不必在每次要追加新节点时都遍历整个列表。然后你的代码会变成这样(没有遍历，也更新了尾指针):

// Prepare new node.

Node *P = new Node;
P->info = data;
P->next = NULL;

// If list empty, set head and tail to new node, otherwise
//   append it.

if (Head == NULL) {
    Head = P;
    Tail = P;
} else {
    Tail->next = P;
    Tail = P;
}

我不会批评您的Insert 方法实际上不是插入而是追加这一事实。我近乎肛门的挑剔天性不太可能让你喜欢我:-)