Malloc堆栈溢出
问题描述:
下面的代码可以正常工作,直到size = 100000.然而它会在size = 200000后给我堆栈溢出错误。 我该如何解决这个问题? 有什么方法可以优化它吗?Malloc堆栈溢出
#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;
}
答
正如所指出的其他人,问题是树的深度将在最坏的情况下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
}
答
如果你得到一个堆栈溢出,这意味着你的函数调用堆栈变得过深。如果树最终失去平衡,那么在构建二叉搜索树时会发生这种情况。
最好的情况下,你的树的高度将是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);
}
为什么你认为这是一个堆栈溢出? – Slava
“malloc堆栈溢出” - “malloc”在堆上分配内存,它返回一个指向分配内存块的指针。如果失败,则返回0('NULL')。你最好在使用之前检查'malloc'的返回值。堆栈溢出与'malloc'无关。那么,你会得到什么样的错误**? –
感谢您的意见,@AlexLop是确切的错误是堆栈溢出,因为视觉工作室告诉我。这就是为什么我卡住 –