c++ - 从链表中删除节点

Question

从最后一个功能中删除不能正常工作。它显示该节点已被删除，但是当我显示它时，它会进入无限循环并显示垃圾。想不出有什么问题！

这是代码：

using namespace std;
class List
{
    struct NODE
    {
        int item;
        NODE *next;
    };
    NODE *Head,*Tail;
    public:
    List()
    {
        Head=NULL;
        Tail=NULL;
    }
    ~List()
    {
        while(Head->next!=NULL)
        {
            Delete_At_Head();
        }
        Delete_At_Head();
    }
    void Add_At_First(int);
    void Add_At_Last(int);
    void Delete_At_Head();
    void Delete_At_Tail();
    int Is_Empty();
    void display();
};
void List::Add_At_First(int data)
{
    NODE *temp;
    temp=new NODE;
    if(Head==NULL)
    {
        temp->item=data;
        temp->next=NULL;
        Head=temp;
        Tail=Head;
    }
    else
    {
        temp->item=data;
        temp->next=Head;
        Head=temp;
    }
    cout<<"Node added at first!\n";
}
void List::Add_At_Last(int data)
{
    NODE *temp;
    temp=new NODE;
    temp->item=data;
    temp->next=NULL;
    if(Head==NULL)
    {
        Head=temp;
        Tail=temp;
    }
    else
    {
        Tail->next=temp;
        Tail=temp;
    }
    cout<<"Node added at last!\n";
}
void List::Delete_At_Head()
{
    NODE *temp;
    temp=new NODE;
    temp->item=Head->item;
    temp->next=Head->next;
    delete Head;
    Head=temp->next;
    delete temp;
    cout<<"Node deleted from head!\n";
}
void List::Delete_At_Tail()//Problematic part
{
    NODE *temp,*prev;
    temp=new NODE;
    prev=new NODE;
    temp=Head;
    while(temp->next!=NULL)
    {
        prev=temp;
        temp=temp->next;
    }
    prev->next=NULL;
    delete temp;
    delete Tail;
    Tail=prev;
    delete prev;
    cout<<"Node deleted from tail!\n";
}
int List::Is_Empty()
{
    if(Head==NULL)
        return 1;
    else
    return 0;
}
void List::display()//does not display after delete from tail
{
    NODE *temp;
    temp=new NODE;
    temp->item=Head->item;
    temp->next=Head->next;
    do
    {
        cout<<temp->item<<"-->";
        temp=temp->next;
    }while(temp->next!=NULL);
    cout<<temp->item;
}
int main()
{
    List obj;
    int ch,data;
    do
    {
        cout<<"\n1.Display\n2.Add at first\n3.Add at last\n4.Delete at 
head\n5.Delete at tail\n6.Exit\nEnter your choice: ";
        cin>>ch;
        switch(ch)
        {
            case 1:
            {
                if(obj.Is_Empty())
                    cout<<"List is Empty!\n";
                else
                    obj.display();
                break;
            }
            case 2:
            {
                cout<<"Enter data: ";
                cin>>data;
                obj.Add_At_First(data);
                break;
            }
            case 3:
            {
                cout<<"Enter data: ";
                cin>>data;
                obj.Add_At_Last(data);
                break;
            }
            case 4:
            {
                if(obj.Is_Empty())
                    cout<<"List is Empty!\n";
                else
                    obj.Delete_At_Head();
                break;
            }
            case 5:
            {
                if(obj.Is_Empty())
                    cout<<"List is Empty!\n";
                else
                    obj.Delete_At_Tail();
                break;
            }
            case 6:
            {
                break;
            }
        }
    }while(ch!=6);
    return 0;
}

Answer 1

以下应正确删除列表中的最后一项：

void List::Delete_At_Tail()
{
    if(Head == NULL) return;

    // If only one item in the list, delete it and empty the list...
    if(Head->next == NULL) {
        delete Head;
        Head = NULL;
        Tail = NULL;
        return;
    }

    // Find the last item in the list
    NODE *temp = Head;
    while(temp->next!=Tail)
    {
        temp=temp->next;
    }

    delete Tail;
    temp->next=NULL;
    Tail=temp;
    cout<<"Node deleted from tail!\n";
}

Answer 2

您肯定删除了太多对象Delete_At_Tail()（我假设这是您在编写delete_from_tail()或“从最后一个删除”时的意思；当编程精度就是一切！）功能：您想摆脱一个对象，但您正在删除delete三个对象，包括已删除对象的前身。您应该只delete删除要删除的对象，而不要删除其他对象。除此之外，该功能看起来还可以。

顺便说一句，由于您要维护指向 的指针，因此Tail您可以改进查找前任的方法：您可以next找到Tail. 这避免了在寻找前任的循环中保持两个变量最新的尴尬需要。