リンクされたリストのmergesortのオーバーフローエラー

Question

私は最終的に動作するテスト機能を得ることができましたが、リンクされたリストのこの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; 
} 

Answer 1

これは再帰呼び出しが多すぎるためです（この場合は500 000）。可能であれば（可能性が低い）リストサイズを減らすか、反復を反復で置き換える方法を見つけてください。独自のスタック構造を使用してポインタを格納し、関数を再帰的に呼び出す代わりにループを使用することができます。

ポインタサイズが4バイトで、関数内に3つのポインタがあり、最後の再帰呼び出しでEIPが使用されると仮定すると、消費されるメモリは500 000 * 4 * 4（7.5MB以上）です。あなたのプログラムのスタックサイズは7.5MBよりも大きいですか？

ところで、500000を一定とすることを考慮して、avoid using magic number。