遞歸內存泄漏

Question

我想實現一個算法，使用遞歸。 在遞歸中，我使用new分配內存並將其刪除，但仍然出現內存泄漏。我試圖瞭解我做錯了什麼，但無法弄清楚。 有人可以看看嗎？

• 我知道我可以使用矢量，但想了解我做錯了什麼，以及如何解決它。

這是代碼：

#include <iostream> 
#include <fstream> 
#include <math.h> 
#define _CRTDBG_MAP_ALLOC 
#include <stdlib.h> 
#include <crtdbg.h> 
using namespace std; 



int sortInv(int*,int); 
int Sort_And_count_split_Inv(int*,int,int,int); 
int Sort_And_count(int *,int,int); 

int main() 
{ 
    _CrtSetDbgFlag (_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF); 
    int Siz = 9; 
    int Arr[9] = {66,3,11,76,93,9,22,56,89};  
    int b = Sort_And_count(Arr,0,Siz-1); 
    for (int i=0; i<Siz; i++) 
     Arr[i] = Arr[i]; 
    return 0; 
} 

int Sort_And_count(int *a,int low,int high) 
{ 
    int mid; 
    int n = 0; 
    if (low >= high) 
     return 0; 
    else 
     mid = (high+low)/2; 
     n+= Sort_And_count(a,low, mid); 
     n+= Sort_And_count(a, mid+1, high); 
     n+= Sort_And_count_split_Inv(a,low,mid,high); 
     return n; 
} 

int Sort_And_count_split_Inv(int* a, int low, int mid, int high) 
{ 
    int i,j,k; 
    i=low; 
    j=mid+1; 
    k=low; 
    int count = 0; 
    int* tmp = new int[high-low+1]; 
    while (i<=mid && j<=high) 
    { 
     if (a[i]<a[j]) 
     { 
      tmp[k] = a[i]; 
      i++; 
     } 
     else 
     { 
      tmp[k] = a[j]; 
      j++; 
      count += mid-i == 0? 1: mid+1-i; 
     } 
     k++; 
    } 
    while (i<=mid) 
     tmp[k++] = a[i++]; 
    while (j<=high) 
     tmp[k++] = a[j++]; 
    for (i=low; i<=high; i++) 
     a[i] = tmp[i]; 
    delete[] tmp; 
    _CrtDumpMemoryLeaks; 
    return count; 
} 

Answer 1

編譯代碼，並在valgrind運行它產生這是您的內存泄漏的第一次出現：

==20797== Invalid write of size 4 
==20797== at 0x400BA0: Sort_And_count_split_Inv(int*, int, int, int) (in /home/test/TestCPP) 
==20797== by 0x4009D4: Sort_And_count(int*, int, int) (in /home/test/TestCPP) 
==20797== by 0x4009BC: Sort_And_count(int*, int, int) (in /home/test/TestCPP) 
==20797== by 0x4009A2: Sort_And_count(int*, int, int) (in /home/test/TestCPP) 
==20797== by 0x400921: main (in /home/test/TestCPP) 
==20797== Address 0x5a1d0ec is 4 bytes after a block of size 8 alloc'd 
==20797== at 0x4C2B800: operator new[](unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==20797== by 0x400AE8: Sort_And_count_split_Inv(int*, int, int, int) (in /home/test/TestCPP) 
==20797== by 0x4009D4: Sort_And_count(int*, int, int) (in /home/test/TestCPP) 
==20797== by 0x4009BC: Sort_And_count(int*, int, int) (in /home/test/TestCPP) 
==20797== by 0x4009A2: Sort_And_count(int*, int, int) (in /home/test/TestCPP) 
==20797== by 0x400921: main (in /home/test/TestCPP) 

我釘下來到這line：

tmp[k] = a[i]; 

This mea ns表示k的數字大於分配的int[]數組的長度。由於您分配的長度爲high - low + 1和k = low，因此您超過邊界案例2*low = high + 1。

我沒去詳細講述你的實際排序算法和爲什麼你在錯誤的low（或high）餵養，但是這是你的內存泄漏的來源。