c++ - 按排序顺序在链表中插入多个元素时出现段错误

Question

我试图在链表中进行插入排序。当只插入一个元素时(即第一个元素)，它执行得很好并且很好但是对于多个元素它会给出段错误。谁能告诉我问题出在哪里？

#include <iostream>
using namespace std;

struct node
{
    int data;
    node* next;
} *head = NULL;

node* createNode(int x)
{
    node *temp = new node;
    temp->data = x;
    temp->next = NULL;
    return temp;
}

void insertSort(int x)
{
    if(head==NULL)
    {
        node  *temp = createNode(x);
        head = temp;
        return;
    }

    node *temp = createNode(x);
    node *prev = NULL;
    node *curr = head;
    bool inserted = false;

    while(curr != NULL || !inserted)
    {
        if(temp->data < head->data)
        {
            temp->next = head;
            head = temp;
            inserted = true;
        }

        else
        {
        if(temp->data < curr->data)
            {
                prev->next = temp;
                temp->next = curr;
                inserted = true;
             }
            else
            {
                prev = curr;
                curr = curr->next;
            }
        }


    }

    if(!inserted)
    {
    prev->next = temp;
    }

}

void display()
{
    node *p = head;
    while(p != NULL)
    {
        cout<<p->data<<" ";
        p = p->next;
    }

}

Answer 1

对于初学者来说，insertSort 函数有冗余代码

if(head==NULL)
{
    node  *temp = createNode(x);
    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    head = temp;
    return;
}
node *temp = createNode(x);
^^^^^^^^^^^^^^^^^^^^^^^^^^^

其次是while语句中的条件

while(curr != NULL || !inserted)

不正确。必须有

while(curr != NULL && !inserted)

无论如何，函数太复杂了。它可以写得更简单。

这是一个演示程序，展示了如何实现该功能。

#include <iostream>
#include <cstdlib>
#include <ctime>

struct node
{
    int data;
    node* next;
} *head = nullptr;

node* createNode(int x)
{
    return new node { x, nullptr };
}

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

    return os << "NULL";
}

void insertSort( int x )
{
    node *new_node = createNode( x );

    node **current = &head;

    while ( *current != NULL && not ( x < ( *current )->data ) ) 
    {
        current = &( *current )->next;
    }

    new_node->next = *current;
    *current = new_node;
}

int main() 
{
    const int N = 10;

    std::srand( ( unsigned int )std::time( nullptr ) );

    for ( int i = 0; i < N; i++ ) insertSort( std::rand() % N );

    display() << '\n';

    return 0;
}

程序输出可能是这样的

1 - > 2 - > 2 - > 3 - > 3 - > 3 - > 3 - > 8 - > 9 - > 9 - > NULL