Malloc堆栈溢出

Question

下面的代码可以正常工作，直到size = 100000.然而它会在size = 200000后给我堆栈溢出错误。 我该如何解决这个问题？ 有什么方法可以优化它吗？

#include <stdio.h> 
#include <stdlib.h> 
#include <malloc.h> 
#define SIZE 500000 
// HELPER ARRAY FUNCTIONS 
void check(int *arr) 
{ 
    int i = 0; 
    for (i = 0; i < SIZE - 1; i++) 
    { 
     if (arr[i]>arr[i + 1]) 
     { 
      printf("Not sorted.\n"); 
      return; 
     } 
    } 
    printf("Sorted.\n"); 
} 
void fill_array(int *arr) 
{ 
    int i = 0; 
    for (i = 0; i < SIZE; i++) 
     arr[i] =rand()%100; 
} 
void print_array(int *arr) 
{ 
    int i; 
    for (i = 0; i < SIZE; i++) 
     printf("%d ", arr[i]); 
    printf("\n"); 
} 
// NODE STRUCT 
typedef struct BST_NODE 
{ 
    struct BST_NODE *left, *right; 
    int data; 
}node; 
// TREE FUNCTIONS 
node* generate_node(int *value) 
{ 
    node *n = (node*)malloc(sizeof(node)); 
    n->left = NULL; 
    n->right = NULL; 
    n->data = *value; 
    return n; 
} 
node* insert_node(node *n, int *value) 
{ 
    if (n == NULL) 
     return generate_node(value); 
    if (*value < n->data) 
     n->left = insert_node(n->left, value); 
    else 
     n->right = insert_node(n->right, value); 
    return n; 
} 
node* construct_BST(int *arr, node* n) 
{ 
    int i; 
    n = NULL; 
    for (i = 0; i < SIZE; i++) 
     n = insert_node(n, &arr[i]); 
    return n; 
} 
int s = 0; 
void LVR(int *arr, node* n) 
{ 
    if (n != NULL) 
    { 
     LVR(arr, n->left); 
     arr[s] = n->data; 
     s++; 
     LVR(arr, n->right); 
    } 
} 
void tree_sort(int *arr) 
{ 
    node *root = (node*)malloc(sizeof(node)); 
    root = construct_BST(arr, root); 
    LVR(arr, root); 
} 
// DRIVER PROGRAM 
int main() 
{ 
    int *Array = (int*)malloc(sizeof(int)*SIZE); 
    fill_array(Array); 
    tree_sort(Array); 
    print_array(Array); 
    check(Array); 
    free(Array); 
    getchar(); 
    return 0; 
} 

它以低于此部分给出了一个错误：

node* generate_node(int *value) 
{ 
    node *n = (node*)malloc(sizeof(node)); 
    n->left = NULL; 
    n->right = NULL; 
    n->data = *value; 
    return n; 
} 

Answer 1

正如所指出的其他人，问题是树的深度将在最坏的情况下SIZE。

在你的代码的情况下，由于持有该值小于100的值，你可以通过不创造同样的价值一个新的节点抑制树的深度。

如果相同的值更改计数如下。

#include <stdio.h> 
#include <stdlib.h> //stdlib.h include malloc and free 

#define SIZE 500000 


typedef struct BST_NODE { 
    struct BST_NODE *left, *right; 
    int data; 
    int count;//Add for count 
} node; 

node* generate_node(int value){//just use int 
    node *n = (node*)malloc(sizeof(node));//C does not need to cast from void *. 
    n->right = n->left = NULL; 
    n->data = value; 
    n->count = 1;//set 1 at first time 
    return n; 
} 

node* insert_node(node *n, int value){ 
    if(n == NULL) 
     return generate_node(value); 
    if(value < n->data) 
     n->left = insert_node(n->left, value); 
    else if (value > n->data) 
     n->right = insert_node(n->right, value); 
    else 
     n->count++;//Add count up 
    return n; 
} 

node* construct_BST(int *arr){//no need node *n as argument 
    int i; 
    node *n = NULL; 
    for (i = 0; i < SIZE; i++) 
     n = insert_node(n, arr[i]); 
    return n; 
} 

int s = 0; 
void LVR(int *arr, node *n){ 
    if (n != NULL){ 
     int i; 
     LVR(arr, n->left); 
     for(i = 0; i < n->count; ++i) 
      arr[s++] = n->data;//Repeat as many times as count 
     LVR(arr, n->right); 
    } 
} 

void tree_free(node *n){ 
    if(n){ 
     tree_free(n->left); 
     tree_free(n->right); 
     free(n); 
    } 
} 

void tree_sort(int *arr){ 
    node *root = construct_BST(arr); 
    s = 0;//Necessary for different calls 
    LVR(arr, root); 
    tree_free(root);//release tree 
} 

Answer 2

如果你得到一个堆栈溢出，这意味着你的函数调用堆栈变得过深。如果树最终失去平衡，那么在构建二叉搜索树时会发生这种情况。

最好的情况下，你的树的高度将是O(log n)，这将是O(n)最坏的情况。如果按照排序顺序将项目放入树中，则二叉树将退化为链接列表，您将遇到最糟糕的情况。

对于这个特殊的例子，你从0到99来产生随机数你可能会得到更多的随机化的结果，如果你增加数字的范围。因此，不要使用rand()%100，而应使用类似rand()%10000的东西。这可能有助于保持树的高度。

在一个不相关的音符，你有内存泄漏。首先，你为树的根分配的初始节点被覆盖，所以你不需要它。其次，你永远不会放松树状结构。

如下您可以照顾这些：

void free_tree(node *root) 
{ 
    if (root) { 
     free_tree(root->left); 
     free_tree(root->right); 
     free(root); 
    } 
} 

void tree_sort(int *arr) 
{ 
    node *root = NULL 
    root = construct_BST(arr, root); 
    LVR(arr, root); 
    free_tree(root); 
}