我使用此代码的目标是,使用巨大的链表,按其“计数”数据排序,如果是平局,则按其“名称”数据排序。
这是我正在实现的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] 删除。
我来说两句