c++ - 链表中的头部未正确链接

Question

当 i 从链表中删除元素后显示时，显示 0 代替已删除的元素。我在更新节点时遇到问题。谁能解释发生了什么？为什么显示0？

#include<iostream>
#include<stdlib.h>
using namespace std;

    class node {

    public:
      int data;
      node *link;

    };

    class linkedlist {

        node *head;

    public:

        linkedlist() {
            head=NULL;
        }

        int add(int data1) {

            node *insertnode=new node;
            insertnode->data=data1;
            insertnode->link=NULL;

            node *temp=head;

            if(temp!=NULL)
            {
                while(temp->link!=NULL)
                {
                    temp=temp->link;
                }
                temp->link=insertnode;

            }
            else{head=insertnode;}

        }

        void disp()
        {
            node *temp1=head;
            cout<<endl;
            if(temp1==NULL)
            {
                cout<<"Empty"<<endl;
            }

            if(temp1->link==NULL)
            {
                cout<<temp1->data<<endl;

            }
            else {

                do {
                    cout<<temp1->data<<endl;
                    temp1=temp1->link;
                } while(temp1!=NULL);

            }

        }

        int remove(int removedata)
        {
            node *previous;
            node *temp2=head;
            if(temp2==NULL)
                {exit(0);}

            if(temp2->link==NULL)
            {
                delete temp2;
                head=NULL;
            }

            else
            {

                while(temp2!=NULL)
                {

                    if(temp2->data==removedata)
                    {
                        previous=temp2;
                        delete temp2;
                    }

                    temp2=temp2->link;

                }

            }

        }

    };

    int main()
    {

        linkedlist list;
        list.add(10);
        list.add(100);
        list.add(200);
        list.remove(10);
        list.disp();

    }

显示的输出是：

0
100
200

score 1 · Accepted Answer

您已删除头节点，但如果发生这种情况，您的代码中不会重新分配头节点。

因此，您在这里拥有的是未定义的行为。

你也这样做：

if(temp2->data==removedata)
{
    previous=temp2;
    delete temp2;
}
temp2=temp2->link;

换句话说，你删除了一些东西，然后取消引用它。我不确定previous这里应该做什么，但它现在还包含一个指向已删除内容的指针。幸运的是，它似乎是它唯一引用的地方（这里的意图是什么？）

而且您的函数似乎没有返回任何内容，但它被声明为返回一个 int。

所以我认为这里的逻辑都是错误的。

你需要做的是：

如果您的节点是头节点，则将头节点指向您要删除的节点的下一个节点。
否则，找到前一个节点（下一个要删除的节点所在的节点），并更新该节点以指向您要删除的节点的下一个节点。
删除节点，现在没有任何引用它。

像这样的东西（未经测试）：

if(head == NULL) return; // List is empty.

node *prev = head;
if(prev->data == removedata)
{
    head = prev->link;
    delete prev;
    return; // removed the head node
}
while(prev->link)
{
    if(prev->link->data == removedata)
    {
        node *t = prev->link;
        prev->link = t->link;
        delete t;
        return; // removed a non-head node
    }
    prev = prev->link;
}
// data is not in the list

或者，如果您想尝试变得聪明并消除特殊情况：

node **prevptr = &head;
node *cur = head;
while(cur)
{
    if(cur->data == removedata)
    {
        *prevptr = cur->link;
        delete cur;
        break;
    }
    prevptr = &cur->link;
    cur = cur->link;
}

score 1 · Accepted Answer

我可以建议我的代码吗？

int removeData(int target)
{
  //Let's return -1 if we can't find the target element.
  node *p,*q;
  for(q=head;q!=NULL && q->data!=target;p=q,q=q->link)
     ;
  if(q==NULL)
  {
    //Either the list was empty or the target element was not on the list
    return -1;
  }
  else
  {
    //We found the element, let's delete it.
    int ret=q->data;
    if(q==head)//If target node is the first node in list
      head=q->link;
    else
      p->link=q->link;
    delete q;//We delete the node pointed to by q here, which is our target node
    return ret;  
  }  
}

让我解释一下上面的代码。首先我们有两个临时指针，它们将指向前一个节点（p）和当前节点（q），同时我们正在遍历链表。我们将遍历列表只要列表没有结束或者只要当前节点不是我们的目标节点。当我们退出 for 循环时，我们可能有两个原因退出。要么q变成 NULL，这可能有两种含义，要么我们的列表为空，要么我们的列表没有目标节点。所以我们返回 -1，报告问题。或者q->data等于target，表示我们找到了目标节点，让我们删除它。我们存储当前值并删除节点。习惯上返回已删除节点的数据。希望对您有所帮助。

score 1 · Accepted Answer

这与您对上一个问题的回答密切相关。

让我们格式化这个函数并仔细看看。

int remove(int removedata)
{
    node* previous;     // Why is this unintialised?
    node* temp2 = head; // Can you think of a more meaningful name for this
                        // variable? Perhaps "current"?
    if (temp2 == NULL)
    {
        exit(0); // Do you really want to exit the program if you try to
                 // remove an item from an empty list? Is there a better way
                 // to handle this?
    }

    if(temp2->link == NULL) // What is so special about a linked list with one element?
    {
        delete temp2; // You've not checked to see if this element is
                      // `removedata`
        head = NULL;  // So calling this function for any list with one element
                      // results in an empty list. This is probably
                      // undesirable
    }
    else
    {
        while (temp2 != NULL) // Consider using a for-loop for iteration. It
                              // couples the increment(s) with the
                              // terminating condition.
        {
            if (temp2->data == removedata) // At this point we have found
                                           // our candidate for removal
            {
                previous = temp2; // This is not the "previous" node, but
                                  // the "current" one. And this variable is
                                  // never used. You do need to know where
                                  // the previous node is and whether it is
                                  // 'head' to update either the 'link' or
                                  // 'head'

                delete temp2;     // This does remove the correct node but
                                  // leaves the previous 'link' pointer
                                  // dangling and any subsequent nodes are
                                  // orphaned.
            }
            temp2 = temp2->link; // See comment above about for-loops.
        }
    }
} // This function is declared `int` but has no return statement.

另一种实现可能看起来像这样（未经测试）：

void remove(int removedata)
{
    for (node* current = head, * previous = NULL;
        current;
        previous = current, current = current->link)
    {
        if (current->data == removedata)
        {
            if (previous)
            {
                previous->link = current->link;
            }
            else
            {
                head = current->link;
            }
            delete current;
            break;
        }
    }
}

c++ - 链表中的头部未正确链接

3 回答 3

Related

Reference