带有合并排序的Segfault在链接列表上排序

mpgiii

我使用此代码的目标是,使用巨大的链表,按其“计数”数据排序,如果是平局,则按其“名称”数据排序。

这是我正在实现的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 *名称和一个下一步的结构nlist *。

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

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

(a =错误读取变量:无法访问地址0x7fffff7fefe8处的内存,b =错误读取变量:无法访问地址0x7fffff7fefe0处的内存)

关于什么可能导致此的任何想法?

用户名

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

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章