链接列表mergesort溢出错误

-1

所以我终于能够得到测试函数的工作，但我没有通过链接列表的mergesort测试函数。经过几个小时的调试后，出现以下溢出错误会变得很糟糕。链接列表mergesort溢出错误

ConsoleApplication2.exe中的0x01041719未处理的异常：0xC00000FD：堆栈溢出（参数：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 sort\n"); 
    node = sort(node); 
    printf("\n checking sorted list\n"); 
    for (i = 0; i < 500000; i++) 
    { 
     if (node == NULL) 
     { 
      printf("List ended early\n"); 

     } 
     if (node->key != 2 * i) 
     { 
      printf("Node contains wrong value\n"); 

     } 
     node = node->next; 
    } 
    printf("Sort successful\n"); 
    return 0; 
}

来源

2016-09-15 user6820297

这看起来更像C而不是C++。 –

测试函数以C格式提供，但之前也在C++中工作。 – user6820297

它可能是堆栈溢出。您的编译器的堆栈大小是否足够处理500,000次递归到merge？可能不会，如果你使用的是Visual Studio（默认为1MB）。 –

这是因为递归调用过多（本例中为500 000）。如果可能的话减少列表大小（很少发生），或者找到一种方法用迭代替换递归。您可以使用自己的堆栈结构来存储指针，并使用循环而不是递归调用该函数。

假设指针大小是4个字节，在函数和EIP中有3个指针，在最后一次递归调用时，消耗的内存将是500 000 * 4 * 4（大于7.5MB）。你的程序的堆栈大小是否大于7.5MB？

顺便说一下，考虑使500000一个常数，avoid using magic number。

来源

2016-09-15 06:45:04

链接列表mergesort溢出错误

回答

相关问题