链表上带合并排序的Segfault

Question

我使用这段代码的目标是，使用一个巨大的链表，按其“count”数据排序，如果是并列的，则按其“name”数据排序。

这是我正在实现的mergesort算法：

void split(struct nlist* source, struct nlist** front, struct nlist** back) {
   struct nlist* fast;
   struct nlist* slow;

   if (source == NULL || source->next == NULL) {
      *front = source;
      *back = NULL;
      return;      
   }

   slow = source;
   fast = source->next;

   while (fast != NULL) {
      fast = fast->next;
      if (fast != NULL) {
         slow = slow->next;
         fast = fast->next;
      }
   }

   *front = source;
   *back = slow->next;
   slow->next = NULL;
}

struct nlist* SortedMerge(struct nlist* a, struct nlist* b) {
   struct nlist* result = NULL;

   if (a == NULL)
      return(b);
   else if (b == NULL)
      return(a);

   if (a->count > b->count) {
      result = a;
      result->next = SortedMerge(a->next, b);
   }

   else if (a->count == b->count) {
      if (strcmp(a->name, b->name) > 0) {
         result = a;
         result->next = SortedMerge(a->next, b);
      }
      else {
         result = b;
         result->next = SortedMerge(a, b->next);
      }
   }

   else {
      result = b;
      result->next = SortedMerge(a, b->next);
   }

   return(result);
}

void mergesort(struct nlist **start) {
   struct nlist* head = *start;
   struct nlist* a;
   struct nlist* b;

   if ((head == NULL) || (head->next == NULL)) {
      return;
   }

   split(head, &a, &b);

   mergesort(&a);
   mergesort(&b);

   *start = SortedMerge(a, b);
}

我把mergesort放在列表的最前面。

nlist结构包含三件事，一个int计数、一个char*name和一个结构nlist*下一步。

此代码通常没有问题，但是当通过在所有字典中运行此代码来测试边缘情况时，我在对列表进行排序时会出现分段错误。这不是列表大小的问题，因为当我不排序而只是返回未排序的列表时，没有问题。

当通过gdb运行它时，我看到我在SortedMerge中得到了分段错误，特别是在检查a-

（a=错误读取变量：无法访问地址0x7FFFFF7FE8处的内存，b=错误读取变量：无法访问地址0x7FFFFF7FE0处的内存）

有什么想法可能导致这种情况吗？

Answer 1

发生的情况是您的代码递归得太深，并且您的堆栈正在运行到您的堆中。避免这种情况的方法是限制列表中的节点数量或非递归地重写您的代码。