具有动态数组的合并排序

Question

我正在尝试实现一个功能mergeSort，该函数返回类型为intervalo_t的动态数组。实际上，该函数运行良好，我遇到的问题是，当我运行Valgrind来检查内存丢失时，发现我失去了很多。

Intervalo_t定义：

struct intervalo_t {
    nat inicio;
    nat fin;
};

这是代码：

intervalo_t* mergeSort(intervalo_t *intervalos, nat n)
{   
    intervalo_t* ret=new intervalo_t[n];
    if(n==2){
        if (intervalos[0].fin>intervalos[1].fin){
            ret[0]=intervalos[1];
            ret[1]=intervalos[0];
        }else{
            ret[0]=intervalos[0];
            ret[1]=intervalos[1];
        }
    //caso base
    }else if (n==1){
        ret[0]=intervalos[0];
    //caso base
    }else{
        nat k=0;        
        if((n%2)!=0){
            k=1;
        }//Si es par o no
        intervalo_t* interA =new intervalo_t[n/2 + k];
        intervalo_t* interB =new intervalo_t[n/2];
        for (nat i=0; i<n/2; i++){
            interA[i]=intervalos[i];
            interB[i]=intervalos[i+(n/2)];
        }//for
        if (k==1){ 
            interA[(n/2)]=intervalos[n-1];
        }
        interA=mergeSort(interA, n/2 + k);
        interB=mergeSort(interB, n/2);
        nat i=0;
        nat j=0;
        nat r=0;
        while((i<((n/2)+k)) && (j<(n/2))){
            if (interA[i].fin>interB[j].fin){
                ret[r]=interB[j];
                j++;
            }else{
                ret[r]=interA[i];
                i++;
            }
            r++;
        }
        while(i<(n/2)+k){
            ret[r]=interA[i];
            i++;
            r++;
        }
        while(j<(n/2)){
            ret[r]=interA[j];
            i++;
            j++;
        }
        delete[] interA;
        delete[] interB;
    //recursion
    }
    return ret; 
}

这是Valgrind的输出：

==15556== 
==15556== HEAP SUMMARY:
==15556==     in use at exit: 24 bytes in 2 blocks
==15556==   total heap usage: 12 allocs, 10 frees, 77,959 bytes allocated
==15556== 
==15556== 8 bytes in 1 blocks are definitely lost in loss record 1 of 2
==15556==    at 0x4C2F06F: operator new[](unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==15556==    by 0x401536: mergeSort(intervalo_t*, unsigned int) (intervalos.cpp:26) 
==15556==    by 0x4017C3: max_cantidad(intervalo_t*, unsigned int) (intervalos.cpp:67)
==15556==    by 0x401130: main (principal.cpp:170)
==15556== 
==15556== 16 bytes in 1 blocks are definitely lost in loss record 2 of 2
==15556==    at 0x4C2F06F: operator new[](unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==15556==    by 0x401509: mergeSort(intervalo_t*, unsigned int) (intervalos.cpp:25)
==15556==    by 0x4017C3: max_cantidad(intervalo_t*, unsigned int) (intervalos.cpp:67)
==15556==    by 0x401130: main (principal.cpp:170)
==15556== 
==15556== LEAK SUMMARY:
==15556==    definitely lost: 24 bytes in 2 blocks
==15556==    indirectly lost: 0 bytes in 0 blocks
==15556==      possibly lost: 0 bytes in 0 blocks
==15556==    still reachable: 0 bytes in 0 blocks
==15556==         suppressed: 0 bytes in 0 blocks
==15556== 
==15556== For lists of detected and suppressed errors, rerun with: -s
==15556== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)

我用以下方法运行valgrind：

valgrind --leak-check=full ./myFile <test.in

Test.in：

mergeSort
15
30
45

感谢您的帮助！

Answer 1

问题是您在此处分配的内存：

intervalo_t* interA =new intervalo_t[n/2 + k];
intervalo_t* interB =new intervalo_t[n/2];

在此处覆盖这些指针时泄漏：

interA=mergeSort(interA, n/2 + k);
interB=mergeSort(interB, n/2);

将变量用于多个目的很少是一个好主意，因此请对递归结果使用单独的变量：

intervalo_t* resultA=mergeSort(interA, n/2 + k);
intervalo_t* resultB=mergeSort(interB, n/2);

，然后使用它们进行合并（并记住释放它们）。我还建议在递归后立即处理输入，以免您忘记它。

或者，您可以使用std::vector并省去一些头痛。