在 LinkedList 中插入一个节点会产生分段错误

Question

struct Node
{
   int data;
   Node * next;
   Node (int x)
   {
     data=x;
     next=NULL;
   }     
};

Node * insertInSorted(Node * head, int data)
{
    Node* temp = new Node(data);

    if (head == NULL){
       return temp;
    }

   if (data < head->data){
    temp->next = head
    return temp;
   }
    
    Node* curr = head;
    
    while (curr->next->data < data && curr->next != NULL){
        curr = curr->next;
    }

    temp->next = curr->next;
    curr->next = temp;
    return head;
}

你好，我最近学了C++，一直在练习LinkedList，这道题很简单，我要做的就是在正确的位置插入一个元素，同时保持排序。我的问题是为什么我会出现分段错误。我注意到在 while 循环中，如果我从 while (curr->next->data < data && curr->next != NULL) to while (curr->next != NULL && curr->next->data < data)不会出现分段错误。有人可以帮我理解这个问题吗？

Answer 1

你写的方式，这个：

curr->next->data < data

在此之前评价：

curr->next != NULL

因此，当您尝试在 curr->next->data 中取消引用它时，curr->next 可能为 NULL，因此您访问了内存的某个随机部分并出现了分段错误。

正如您所说，更改顺序即可解决问题，这是正确的解决方案。当 AND 表达式的第一部分为 false 时，不会计算第二部分，因此您不会尝试取消引用无效地址，因此您的问题已解决。

Answer 2

这个while循环

while (curr->next->data < data && curr->next != NULL){
    curr = curr->next;
}

可以调用未定义的行为，因为在访问数据成员 curr->next->data 之前没有检查 curr->next 是否等于 nullptr。您需要交换逻辑 AND 运算符的操作数，如

while (curr->next != NULL && curr->next->data < data ){
    curr = curr->next;
}

在任何情况下，如果使用指向指针的指针，都可以在不检查大量条件的情况下按以下方式编写函数。

Node * insertInSorted( Node *head, int data )
{
    Node *temp = new Node( data );

    Node **current = &head;

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

    temp->next = *current;
    *current = temp;

    return head;
}

注意可以通过引用将指向头节点的指针传递给函数。在这种情况下，不需要 return 从函数指向头节点的指针。原始函数的用户可能忘记将函数的 returned 指针分配给函数调用者中的指针。

所以更安全的函数定义可以看下面的方式

void insertInSorted( Node * &head, int data )
{
    Node *temp = new Node( data );

    Node **current = &head;

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

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

在 LinkedList 中插入一个节点会产生分段错误

Inserting a node in LinkedList is giving segmentation error

c++

linked-list

while-loop

data-structures

singly-linked-list