我对堆栈溢出没有太多的经验,我认为它们是由超过某个递归深度的递归函数引起的,为什么它们会在合并排序的这种迭代实现中在这里出现!

    #include<iostream>
    #include <stdlib.h>
    #define SIZE 3000000

    int L[2500002];
    int R[2500002];

    using namespace std;

    int min(int a, int b) {
        return !(b<a) ? a : b;
    }

    void Merge(int data[], int p, int q, int r)
    {
        if (q >= SIZE)q = (r + p) / 2;
        int sizeL = q - p + 2;
        int sizeR = r - q + 1;

        for (int i = 0; i < sizeL - 1; i++)
            L[i] = data[i + p];
        for (int i = 0; i < sizeR - 1; i++)
            R[i] = data[i + q + 1];

        int max;
        if (L[sizeL - 2]>R[sizeR - 2])
            max = L[sizeL - 2] + 1;
        else
            max = R[sizeR - 2] + 1;
        L[sizeL - 1] = R[sizeR - 1] = max;

        int indexL = 0, indexR = 0;
        for (int i = p; i <= r; i++){
            if (L[indexL] <= R[indexR]){
                data[i] = L[indexL];
                indexL++;
            }
            else{
                data[i] = R[indexR];
                indexR++;
            }
        }


    }

    void MergeSort(int data[], int p, int r)
    {
        for (int i = 1; i< SIZE; i *= 2)
            for (int j = 0; j < SIZE; j += 2 * i)
                Merge(data, j, j + i - 1, min((j + 2 * i - 1), SIZE - 1));
    }
    /*****************************************************************************/

    bool IsSorted(int data[], int size)
    {
        int i;

        for (i = 0; i<(size - 1); i++)
        {
            if (data[i] > data[i + 1])
                return false;
        }
        return true;
    }

    int main()
    {
        int data[SIZE];
        for (int i = 0; i < SIZE; i++)
            data[i] = rand();
        MergeSort(data,0,SIZE-1);
        if(IsSorted(data, SIZE))
            cout << "Sorted correctly";
        else
            cout << "incorrect sorting";
        getchar();
        return 0;
    }

最佳答案

int main()
{
    int data[SIZE];
    ...

在堆栈上声明数组。堆栈大小有限制。它随操作系统和配置的不同而不同,但是很容易小于您要求的大小(假设32位整数)小于12 MB。尝试在堆上分配数组,而不是使用std::vector

编译器不可能就此问题警告您,因为堆栈大小是由OS在加载程序时设置的。您可以将操作系统重新配置为默认使用一个很小的堆栈,而以前运行过的程序将突然开始溢出。

如果您想了解有关操作系统如何检测堆栈溢出的更多信息,请查找虚拟内存,MMU和保护页面。

09-10 04:44
查看更多