尝试声明 int 数组时数组声明失败

Question

我一直在学习和编码排序算法，最近我用C编写了合并排序代码，我还编写了一个sort_test函数来测试我编写的函数。在排序测试函数中，我声明了一个数组并为其分配随机值，但是当数组大小达到 1,000,000 时，程序崩溃。为什么会这样？

sort_test.c

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "merge_sort.h"
#include "sort_test.h"
// test size
#define MIN 10
#define MAX 1000000
// int comparator
int cmpInt(const void *elem1,const void * elem2){
int e1 = *(int *)elem1; // i-1
int e2 = *(int *)elem2; // i
if(e2 < e1){
return -1;
} else if(e2 > e1){
return 1;
} else {
return 0;
}
}
// double comparator
int cmpDouble(const void *elem1,const void *elem2){
double e1 = *(double *)elem1;
double e2 = *(double *)elem2;
if(e2 < e1){
return -1;
} else if(e2 > e1){
return 1;
} else {
return 0;
}
}
void initSeed(){
srand(time(NULL));
}
void intSortTest(){
initSeed();
for(size_t i = MIN;i <= MAX;i *=10){
int arr[i];
for(size_t j = 0; j < i;j++){
arr[j] = rand();
}
// sorting the array
mergesort(arr,0,i);
// checking if sorted array hold the 
// condition i[0] <= i[1] ... <= i[n].
for(size_t j = 1;j < i;j++){
int *e1 = &arr[j-1];
int *e2 = &arr[j];
assert(cmpInt(e2,e1) <= 0);
}
printf("INT TEST : %7dtPASSEDn",i);
}
printf("n");
}
void doubleSortTest(){
initSeed();
for(int i = MIN; i <= MAX; i *= 10){
double arr[i];
for(int j = 0 ; j < i;j++){
arr[j] = (double)(rand() % 100) + 1.0;
}
// perform sort
//insertion_sort(arr,sizeof (double),i,cmpDouble);
for(int j = 1; j < i;j++){
double *e1 = &arr[j-1];
double *e2 = &arr[j];
assert(cmpDouble(e2,e1) <= 0);
}
printf("Double Test : %5dtPASSEDn",i);
}
printf("n");
}

sort_test.h

#ifndef SORT_TEST_H
#define SORT_TEST_H
void initSeed();
void intSortTest();
void doubleSortTest();
int cmpDouble(const void *elem1,const void *elem2);
int cmpInt(const void *elem1,const void * elem2);
#endif // SORT_TEST_H

merge_sort.h

#ifndef MERGE_SORT_H
#define MERGE_SORT_H
void mergesort(int *arr,int start,int end);
void merge(int *arr,int start,int med,int end);
#endif // MERGE_SORT_H

merge_sort.c

#include <stdio.h>
#include "sort_test.h"
#include "merge_sort.h"
int main(){
intSortTest();
return 0;
}
void mergesort(int *arr,int start,int end){
if(start < end){
int median = (end + start) / 2;
mergesort(arr,start,median);
mergesort(arr,median+1,end);
merge(arr,start,median,end);
}
}
void merge(int *arr,int start,int median,int end){
int i = start; int j = median+1;
int copy[end+1];
int cIndex = 0;
while(i <= median && j <= end) {
if(arr[j] <= arr[i]){
copy[cIndex++] = arr[j++];
} else {
copy[cIndex++] = arr[i++];
}
}
while(i <= median){
copy[cIndex++] = arr[i++];
}
while(j <= end){
copy[cIndex++] = arr[j++];
}
for(int k = 0; k < cIndex; k++){
arr[start++] = copy[k];
}
}

Answer 1

这是因为您在堆栈上分配数组。请改为尝试以下代码。

void intSortTest(){
initSeed();
for(size_t i = MIN;i <= MAX;i *=10){
int *arr = malloc(i*sizeof(int));  // <-- changed this
for(size_t j = 0; j < i;j++){
arr[j] = rand();
}
// sorting the array
mergesort(arr,0,i);
// checking if sorted array hold the 
// condition i[0] <= i[1] ... <= i[n].
for(size_t j = 1;j < i;j++){
int *e1 = &arr[j-1];
int *e2 = &arr[j];
assert(cmpInt(e2,e1) <= 0);
}
printf("INT TEST : %7dtPASSEDn",i);
free(arr);   // <-- added this
}
printf("n");
}

编辑

合并算法也不正确。更准确地说，值列表边界有问题。

定义值列表的开始索引和结束索引时，值arr[start]arr[end-1]，而不是arr[end]。然后end-start值的数量。使用此约定，您在start == end时有一个空列表。

因此，函数mergesort变为：

void mergesort(int *arr,int start,int end){
if (start+1 >= end) 
return; // a list with 0 or 1 values is already sorted
int median = (end + start) / 2;
mergesort(arr,start,median);
mergesort(arr,median,end);
merge(arr,start,median,end);
}

然后合并函数变为如下：

void merge(int *arr,int start,int median,int end){
int i = start; int j = median;
int *copy = malloc((end-start)*sizeof(int)); // use malloc for huge arrays
int cIndex = 0;
while(i < median && j < end) {  // not i <= median && j <= end
if(arr[j] <= arr[i]){
copy[cIndex++] = arr[j++];
} else {
copy[cIndex++] = arr[i++];
}
}
while(i < median){ // not i <= median
copy[cIndex++] = arr[i++];
}
while(j < end){  // not j <= median
copy[cIndex++] = arr[j++];
}
for(int k = 0; k < cIndex; k++){
arr[start++] = copy[k];
}
free(copy);
}

如您所见，只有细微的区别。

使用此代码，程序可以正常运行。

Answer 2

现在代码是可见的，很容易看出你确实在吹堆栈，正如我在众多评论之一中所建议的那样。

在merge()中，您有：

int copy[end+1];

以及intSortTest()具有：

int arr[i];

其中i达到 1,000,000。

当end为 1,000,000 时(它是从i开始设置的(，您有一个包含 100 万个int值的数组正在排序，还有一个包含另外 100 万个int值(加 1(的副本，因此您尝试在堆栈上放置 200 万个 4 字节int值 — 8,000,000 字节会破坏堆栈限制。 由于 800,000 字节(以前的大小(适合 Unix 和 Windows 中的堆栈，因此并非 100% 清楚您使用的是哪个。 在 Unix/Linux 上没有太多的错误余地;这个限制在 Windows 上被彻底吹了，因为堆栈上没有 4 MB 的数组。

建议的解决方法是使用动态内存分配(malloc()等(而不是堆栈分配 - 在排序测试函数和主merge()代码中。