C：带有链表实现的奇怪的段错误

Question

编辑：部分解决。我按照第一个答案的建议将 NULL 检查切换为 while 循环检查中的第一个，但是我仍然无法访问队列中除第一个元素之外的任何元素。我可以访问 data->head，但我无法访问 data->head->next，除非我专门创建一个指向 data->head->next 的节点结构。如果我专门创建了那个节点（我们称它为 temp），那么 temp->next 也是不可访问的。基本上，当我将队列传递给此函数时，->next 功能完全丢失，我不知道为什么。

我正在为 Uni 做一个学校项目，在这个项目中我们构建了一个修改后的合并排序（编辑：一位评论者指出这是 TimSort 的一种形式），而不是正常的合并排序算法，它将数据集分成块已经排序的数据，然后重新组合它们理论上可以减少运行时间。
以集合

为例

3 4 5 2 9 4 3 2

将拆分为

[3 4 5] [2 9] [4 3 2]

然后按排序顺序合并回一起。我们的特定实现必须使用链表、队列和堆栈来完成。
这是我的链表定义和队列定义：

typedef struct node_t
{
   int value;

   struct node_t * next;
} node_t;

typedef struct queue_t
{
   node_t *head, *tail;

} queue_t;

我遇到问题的代码位于识别 "runs" 或数据已排序的数据区域的函数中。它以队列作为输入，遍历并确定第一个节点是小于还是大于下一个节点。然后它选择哪个循环到运行并将每个值从队列中取出到一个新队列中，然后它将作为 "run" 返回，这是排序数据的子集。
出于某种原因，每当我尝试使用 data->head->next 或 data->head->next->value 时，它都会抛出一个分段错误，即使我知道节点存在并且值存在。我一直在运行通过 gdb 调试我的程序以查找错误点，我在 windows 上，但我不能使用 valgrind。这是我遇到问题的函数的代码：

queue_t * extract_next_run(queue_t * data)
{
    queue_t * queue = queue_create();

int ascend = 0;

//when there is only one value in the list
if(data->head->next = NULL)
{
    queue_enqueue(queue, queue_dequeue(data));
    return queue;
}


//ascending run *CRASHES ON THIS WHILE LOOP*
while(data->head->value <= data->head->next->value && data->head->next != NULL)
{   
    queue_enqueue(queue, queue_dequeue(data));

    //not sure if this improves runtime over just "ascend = 1" every iteration
    if(ascend != 1)
        ascend = 1;
}

//descending run
while(data->head->value > data->head->next->value && data->head->next != NULL)
{   
    queue_enqueue(queue, queue_dequeue(data));
}

if(ascend == 0)
    queue_reverse(queue);

queue->tail->next = NULL;
return queue;
}

以下是让我难以理解的原因：

//things I have tested in this function

printf("%d", data->head->value); // works fine
printf("%d", data->head->next->value); // segmentation fault
data->head = data->head->next; //segmentation fault    

if(data->head->next == NULL) //works fine

node_t * temp = data->head->next; // works fine
printf("%d", temp->value); // works fine
temp = temp->next; //segmentation fault

让我烦恼的另一件事是我可以在其他函数中使用 queue->head = queue->head->next 并且它工作正常，我可以使用 node = node->next 并且它可以工作很好，所以我真的不知道问题出在哪里。我知道此函数中调用的函数有效，但我很乐意为它们提供代码。这里有声明，如果需要我可以提供我所有的代码（不想让这个问题太长）：

// mallocs a queue and sets its head and tail to NULL
queue_t * queue_create();  

// takes a value and adds it to the end of the queue
void queue_enqueue(queue_t * queue, int data);

// removes the first node of the queue and returns its value
int queue_dequeue(queue_t * queue);

// takes a queue, reads it into a stack, 
// then uses stack_pop to return values in reverse order
void queue_reverse(queue_t * queue);

任何帮助将不胜感激，我一直在努力找出问题所在，但到目前为止我没有成功。提前致谢！

Answer 1

您已将问题缩小到这个 while 循环：

while(data->head->value <= data->head->next->value && data->head->next != NULL) {

事实上，您似乎在指法循环控制表达式。然后考虑该表达式：为什么它包含 data->head->next != NULL?

的测试

考虑当条件的那部分为假时会发生什么——也就是说，当 data->head->next == NULL 为真时会发生什么。该程序不会（永远）在首先评估 && 的左侧操作数之前评估该条件，其中包括评估 data->head->next->value，并且当 data->head->next 为空时会产生未定义的行为。您可能根本没有空检查，事实上，一些编译器可能会优化它。

要使 null 检查有效，必须在它用于保护的任何计算之前对其进行计算。

Answer 2

我修复了它，函数中的第一个 if 语句是 if(queue->head->next = NULL)，但我应该有 if(queue->head->next == NULL)。我使用赋值运算符 = 而不是比较运算符 == 并且它将 queue->head->next 赋值给 NULL，这导致了段错误。

C：带有链表实现的奇怪的段错误

C: Weird SegFault with Linked List implementation

c

queue

mergesort

linked-list

timsort