单链表无限循环

Question

我开始学习链表已经一个星期了，我只学习了单链表。所以今天我实现了我在 C++ 中学到的链表，当我尝试运行它时，代码进入了一些随机数的无限循环。我尝试调试代码，但我找不到代码有什么问题。代码如下。帮助是appreciated.Thanks

#include <iostream>
using namespace std;

struct node{
int data;
node * next;
};

class singly{
private:
node * head,*tail;
public:
singly(){
    head=NULL;
    tail=NULL;
}

void createNode(int value){
    node * temp = new node;
    temp->data=value;
    temp->next=NULL;
    if(head==NULL){
        head=temp;
        tail=temp;
        temp=NULL;
    }

    else{
        tail->next=temp;
        tail=temp;
    }
}

void display(){
    node * temp = new node;
    head=temp;

    while(temp!=NULL){
        cout << temp->data << "\t" << endl;
        temp->next=temp;
    }
}

void insert_end(int value){
    node*newnode = new node;
    node*temp = new node;
    newnode->data=value;
    newnode->next=NULL;
    temp=head;

    while(temp->next!=NULL){
        temp = temp->next;
    }
    temp->next=newnode;
}

void delete_node(){
    node*current = new node;
    node*previous = new node;
    current = head;
    while(current->next!=NULL){
        previous=current;
        current=current->next;
    }

    tail=previous;
    previous->next=NULL;
    delete current;
}
};

int main(){

singly lists;
lists.createNode(32);
lists.createNode(654);
lists.createNode(34);
lists.createNode(234);

cout<<"\n--------------------------------------------------\n";
cout<<"---------------Displaying All nodes---------------";
cout<<"\n--------------------------------------------------\n";
lists.display();
cout<<"\n--------------------------------------------------\n";
cout<<"-----------------Inserting At End-----------------";
cout<<"\n--------------------------------------------------\n";
lists.createNode(55);
lists.display();
cout<<"\n--------------------------------------------------\n";
cout<<"-----------------Deleing At End-------------------";
cout<<"\n--------------------------------------------------\n";
lists.delete_node();
lists.display();
}

Answer 1

首先，display()是错误的。您希望更新为 temp = temp->next; 并且它也可以初始化为 node * temp = head 因此不需要第二行。

你的delete_node()可以重写为：

if (head->next == NULL) // handles the case that it consists of 1 element
{
    delete head;
    head = NULL;
}
else
{
    node *nextToEnd = head;
    node *end = head->next;
    while (end->next != NULL)
    {
        nextToEnd = end;
        end = end->next;
    }
    delete end;
    nextToEnd->next = NULL;
}

如评论中所述，查看 new keyword

Answer 2

成员函数display没有意义。它用未初始化的新创建的 temp.

覆盖数据成员 head

    node * temp = new node;
    head=temp;

所以函数调用了未定义的行为。

函数看起来像

void display()
{
    for ( node * temp = head; temp != nullptr; temp = temp->next )
    {
        cout << temp->data << "\t";
    }
}

或者下面这样定义比较好

std::ostream & display( std::ostream &os = std::cout )
{
    for ( node * temp = head; temp != nullptr; temp = temp->next )
    {
        os << temp->data << "\t";
    }

    return os;
}

数据成员insert_end也是错误的。它没有考虑到 head 和 tail 可以等于 nullptr 并且不会改变它们。

函数可以这样定义

void insert_end(int value)
{
    node *newnode = new node { value, nullptr };

    if ( tail == nullptr )
    {
        head = tail = newnode;
    }
    else
    {
        tail = tail->next = newnode;
    }
}

成员函数delete_node首先对单向链表没有意义，然后又是错误的并调用了未定义的行为。该函数应从列表中删除第一个节点。

然而，如果你想从列表中删除最后一个节点，那么函数可以看起来像

void delete_node()
{
    if ( head != nullptr )
    {
        tail = nullptr;
        node *current = head;

        while ( current->next )
        {
            tail = current;
            current = current->next;
        }

        if ( tail == nullptr )
        {
            head = tail;
        }
        else
        {
            tail->next = nullptr;
        }

        delete current;
    }
}

单链表无限循环

Singly Linked List Infinite Loop

c++

linked-list

singly-linked-list