-1

使用从互联网上某处获取的代码，我尝试在我的程序中实现基数排序功能。该程序的输入是一个包含大约 120 万个长整数的文本文件。我已经有一个 maxSize = 1200000 的数组，它存储来自文本文件的整数，所以当我在 radixSort 函数中创建工作数组时，我得到了一个段错误。有什么办法可以避免这种情况吗？

这是驱动程序代码：

case 5:
    //Sort using Radix Sort
    startTime = clock();

        radixSort(array, size);
        writeArray(radixFile, array, size);
        radixFile.close();

    endTime = clock();
    timeUsed = (endTime-startTime)/(double)CLOCKS_PER_SEC;
    cout << "Time elapsed: " << timeUsed << " seconds" << endl;
    break;

这是功能

void radixSort(int *array,int size){

    int i,b[maxSize],m=0,exp=1;

    for(i=0;i<size;i++){
        if(array[i]>m)
            m=array[i];
    }

    while(m/exp>0)
    {
        int bucket[10]={0};

        for(i=0;i<size;i++)
            bucket[array[i]/exp%10]++;

        for(i=1;i<10;i++)
            bucket[i]+=bucket[i-1];

        for(i=size-1;i>=0;i--)
            b[--bucket[array[i]/exp%10]]=array[i];

        for(i=0;i<size;i++)
            array[i]=b[i];

        exp*=10;
    }
}

另外，创建数组的 main 的摘录：

    int main(){

      int choice, size=0, x=0;
      int *array = NULL;
      array = new int[maxSize];

并确定大小：

void readArray(ifstream &inputFile, int arr[], int &size){
size = 0;
while (inputFile >> arr[size]){
    size++;
}}
4

2 回答 2

1

1200000 int 至少需要 1200000*4/1024^2 = 4.7 MiB 并且您正在堆栈上声明您的数组，这对于堆栈大小可能不够......

您是否尝试过在堆上声明 b[] ？

尝试

int *b = new int[maxSize];

代替

int b[maxSize];
于 2012-11-25T02:39:23.107 回答
0

您正在错误地读取文件。您应该检查 EOF，因为提取运算符始终返回您提供给它的流（请参阅http://www.cplusplus.com/reference/istream/istream/operator%3E%3E/）。你很可能在这里破坏了记忆，之后所有的赌注都被取消了。尝试：

while (!inputFile.eof() && size<maxSize)
{
     inputFile >> arr[size++];
}
于 2012-11-25T03:06:41.630 回答