合并排序在 C++ 中不起作用

Question

这三个函数的"return"值的用法有什么问题吗？打印出来的值是看似随机数的垃圾值，因为 outputs.I 还想补充一点，我没有让它递归，因为我想检查这是否有效。

我见过的大多数合并排序实现几乎不包含任何 return 值，这是我做错了什么。如果您要进行类似类型的实施，您会怎么做？

#include <iostream>

using namespace std;

int* goleft(int array[], int size)
{
    int halved=size/2;
    int left[halved];

    for(int i=0;i<halved;i++)
        {
            left[i]=array[i];
        }
    return left;
}

int* goright(int array[],int size)
{
    int halved=size/2;
    int right[size-halved];

    for(int i=halved,j=0;i<size;i++,j++)
        {
            right[j]=array[i];
        }
    return right;
}

int* mergesort(int array[],int size)
{
    int *l,*r;
    l=goleft(array,size);
    r=goright(array,size);
    int merger[size];
    int halved = size/2;
    int i;
    for(i=0;i<halved;i++)
        cout<<l[i]<<endl;

    for(i=0;i<halved;i++)
        cout<<r[i]<<endl;

    int x=0,y=0,k=0;
    while(x+y!=size)
    {
        if(l[x]<r[y])
        {
            merger[k]=l[x];
            x++;k++;
        }
        else if(l[x]>=r[y])
        {
            merger[k]=r[y];
            y++;k++;
        }
    }
    return merger;
}

int main()
{
    int size;
    cin>>size;
    int array[size];

    for(int i=0;i<size;i++)
        cin>>array[i];

    int *merged=mergesort(array,size);

    cout<<"sorted array"<<endl;
    for(int i=0;i<size;i++)
        cout<<merged[i]<<endl;

    return 0;
}

当我们在循环和递归过程中创建同名变量时，是否为每次循环迭代或递归创建新变量？或者他们是否覆盖了前一个变量的值。例如，当我们写

while(true)
{
int i=0;
}

是否会在每次迭代时创建一个新变量和

genericFunction()
{
 int i = SomeRandomValue
 genericFunction();
}

同样会在每次递归时创建一个新变量吗？

Answer 1

如您所想，错误在"scopes"。回答您的问题：

while(true)
{
int i=0;
}

过程是：

//iteration N start
create scope
allocate memory for an int variable named 'i' in the current scope
//statements done
delete current scope //deallocate the variables in the current scope
//iteration N end
//iteration N+1 start
/*...*/

因此在每次迭代中它都是一个不同的变量。您可以使用此代码对其进行测试：

while (true) {
    int i;
    std::cout << &i << std::endl; //displays the memory location of i
    system("PAUSE"); //waiting user input between each iteration
}

在使用genericfunction的例子中，过程是：

//N call to genericFunction
create scope //scope N
    //N+1 call to generic Function
    create scope //scope N+1
        /* statements */
    delete current scope //scope N+1
    // exit of call N+1
delete current scope //scope N
//exit of call N

您可以使用以下完整代码对其进行测试：

#include <iostream>

void genericFunction(int a)
{
    int i = 0;
    std::cout << "scope " << a << " : " << &i << std::endl;
    if (a < 9) { //to prevent infinite call
        genericFunction(a + 1);
    }
    std::cout << "scope " << a << " : " << &i << std::endl;
}

int main() {
    genericFunction(0);
    system("PAUSE");
    return 0;
}

通用规则是：当您有 { 时，您创建一个新范围并将其 select 作为当前范围，当您有 } 时，您删除当前范围并select 上一个作用域。一些作用域允许访问以前的作用域（例如 a WHILE LOOP ：在代码 int a; while(true) {a++;} 中，它修改了先前作用域中 a 的值），但是当创建函数作用域时，您无权访问以前的范围。

现在对于合并排序的具体问题，它是函数 mergesort 内变量 merger 的声明。查看过程：

/* ... */
int *merged=mergesort(array,size);
//Call to mergesort
    //Creation of scope A
    /* ... */
    int merger[size]; //Allocation of memory for 'merger' in scope A
    /* ... */
    return merger; //Affect the location of 'merger' to location pointed by 'merged' in previous scope
    //Deletion of scope A (including deallocation of 'merger')
// Now 'merged' points to location of 'merger' which is a deallocated variable :
//no guarantees of the data stored at this location

这就是为什么你的代码有问题。纠正它的一种方法是为您的变量手动分配一些 space ：手动分配的变量必须手动释放，因此在销毁作用域时不会释放它们。实际上函数内部的实现是使用 c++ 关键字 new : int *merger = new int[size];。通过替换此声明，您的代码将是运行：但要小心：这是另一条规则，如果您在某处使用关键字 new，则必须在其他地方使用 delete：手动分配之后必须手动解除分配。所以在你的main函数的末尾，你必须添加delete[] merged;。这样就没有问题了;) .

合并排序在 C++ 中不起作用

mergesort not working in c++

c++

recursion

mergesort

return