所以我终于能够让测试函数工作,但我没有通过这个链表合并排序的测试函数。经过几个小时的调试,现在它变得最糟糕,出现以下溢出错误:
ConsoleApplication2.exe中0x01041719未处理异常:0xC00000FD: Stack overflow(参数:0x00000001, 0x006E2FC0).
#include <stdio.h>
#include <stdlib.h>
struct listnode {struct listnode * next; int key; };
struct listnode * merge(struct listnode * left, struct listnode * right)
{
struct listnode * right2;
if (left == NULL)
return right;
if (right == NULL)
return left;
if (left->key < right->key)
{
right2 = left;
right2->next = merge(left->next, right);
}
else
{
right2 = right;
right2->next = merge(left, right->next);
}
return right2;
}
struct listnode *sort(struct listnode * a)
{
struct listnode * left, * right;
if (a== NULL || a->next == NULL)
return a;
left = a; right = a->next;
while (right!= NULL && right->next != NULL)
{
left = left->next;
right = right->next->next;
}
right = left->next;
left->next = NULL;
return merge(sort(a), sort(right));
}
int main()
{
long i;
struct listnode *node, *tmpnode, *space;
space = (struct listnode *) malloc(500000 * sizeof(struct listnode));
for (i = 0; i < 500000; i++)
{
(space + i)->key = 2 * ((17 * i) % 500000);
(space + i)->next = space + (i + 1);
}
(space + 499999)->next = NULL;
node = space;
printf("n prepared list, now starting sortn");
node = sort(node);
printf("n checking sorted listn");
for (i = 0; i < 500000; i++)
{
if (node == NULL)
{
printf("List ended earlyn");
}
if (node->key != 2 * i)
{
printf("Node contains wrong valuen");
}
node = node->next;
}
printf("Sort successfuln");
return 0;
}
这是因为太多的递归调用(在本例中为500000)。如果可能的话减少列表大小(这种情况很少发生),或者找到一种用迭代代替递归的方法。您可以使用自己的堆栈结构来存储指针,并使用循环而不是递归地调用函数。
假设指针大小为4字节,函数和EIP中有3个指针,在最后一次递归调用时,消耗的内存将为500000 * 4 * 4(大于7.5MB)。您的程序的堆栈大小是否大于7.5MB?
顺便说一下,考虑让500000成为一个常数,避免使用幻数