1

编辑：部分解决。按照第一个答案的建议，我将 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;

我遇到问题的代码在识别“运行”的函数中，或者数据已经排序的数据区域。它将队列作为输入，遍历并识别第一个节点是否小于或大于下一个节点。然后它选择要运行的循环并将每个值出列到新队列中，然后将作为“运行”返回，这是已排序数据的子集。
出于某种原因，每当我尝试使用 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);

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

4

2 回答 2

3

您已将问题缩小到此 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您可能根本没有空检查，实际上，一些编译器可能会优化它。

为了使空值检查有效，必须在它用于保护的任何评估之前对其进行评估。

于 2017-03-16T18:25:26.543 回答
0

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

于 2017-03-16T21:49:06.067 回答