c - 在链接列表上使用合并排序的段错误

Question

我对这段代码的目标是，对于一个巨大的链表，按其“计数”数据排序，如果是平局，则按其“名称”数据排序。

这是我正在实现的归并排序算法:

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);
}

我在列表头部调用合并排序的地方。

一个 nlist 结构包含三个东西，一个 int 计数，一个 char* 名称和一个 struct nlist* next。

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

当通过 gdb 运行它时，我看到我在 SortedMerge 中遇到段错误，特别是在检查 a->count 或 b->count 时。我得到的错误是

( a=error reading variable: Cannot access memory at address 0x7fffff7fefe8, b=error reading variable: Cannot access memory at address 0x7fffff7fefe0)

关于可能导致此问题的任何想法？

Answer 1

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