算法导论 - 一个递归调用的c++程序,指针传参, delete回收放在下一层递归,为什么没有被释放资源?
是Strassen矩阵相乘的算法, 这里有一篇介绍博客: 矩阵乘法Strassen算法，因为太占内存了，想尽可能快地回收内存：
void Strassen(int **A, int **B, int **C, int N, bool delA, bool delB)
{
int i, j;
if (N <= 256 || N % 2 == 1)
{
matrixMul(A, B, C, N);
return;
}
int newn = N / 2;
int ** A11, **A12, **A21, **B11, **B12, **B21;
int **A22;
int **B22;
/*
int **C11, **C12, **C21, **C22;
*/
int **P1, **P2, **P3, **P4, **P5, **P7;
// int **temp1, **temp2, **P6;
// 申请空间
A11 = new int *[newn];
A12 = new int *[newn];
A21 = new int *[newn];
A22 = new int *[newn];
B11 = new int *[newn];
B12 = new int *[newn];
B21 = new int *[newn];
B22 = new int *[newn];
/*
C11 = new int *[newn];
C12 = new int *[newn];
C21 = new int *[newn];
C22 = new int *[newn];
*/
P1 = new int *[newn];
P2 = new int *[newn];
P3 = new int *[newn];
P4 = new int *[newn];
P5 = new int *[newn];
P7 = new int *[newn];
//P6 = new int *[newn];
/*
temp1 = new int *[newn];
temp2 = new int *[newn];
*/
for (i = 0; i < newn; i++)
{
A11[i] = new int[newn];
A12[i] = new int[newn];
A21[i] = new int[newn];
A22[i] = new int[newn];
B11[i] = new int[newn];
B12[i] = new int[newn];
B21[i] = new int[newn];
B22[i] = new int[newn];
/*
C11[i] = new int[newn];
C12[i] = new int[newn];
C21[i] = new int[newn];
C22[i] = new int[newn];
*/
P1[i] = new int[newn];
P2[i] = new int[newn];
P3[i] = new int[newn];
P4[i] = new int[newn];
P5[i] = new int[newn];
P7[i] = new int[newn];
//P6[i] = new int[newn];
/*
temp1[i] = new int[newn];
temp2[i] = new int[newn];
*/
}
// 切分矩阵A、B
for (i = 0; i < newn; i++)
{
for (j = 0; j < newn; j++)
{
A11[i][j] = A[i][j];
A12[i][j] = A[i][j + newn];
A21[i][j] = A[i + newn][j];
A22[i][j] = A[i + newn][j + newn];
B11[i][j] = B[i][j];
B12[i][j] = B[i][j + newn];
B21[i][j] = B[i + newn][j];
B22[i][j] = B[i + newn][j + newn];
}
}
/*
下面删除已经没有价值的矩阵
*/
if (delA)
{
for (i = 0; i < N; i++)
{
delete[] A[i];
}
delete[] A;
A = NULL;
}
if (delB)
{
for (i = 0; i < N; i++)
{
delete[] B[i];
}
delete[] B;
B = NULL;
}
/*
上面删除已经没有价值的矩阵
*/
// S1 = B12 - B22
// P1 = A11 ? S1
// * P7 作为 temp
matrixSub(B12, B22, P7, newn);
Strassen(A11, P7, P1, newn, false, false);
// S9 = A11 - A21
// S10 = B11 + B12
// P7 = S9 ? S10
// * P2 P4 作为 temp
matrixSub(A11, A21, P2, newn);
matrixAdd(B11, B12, P4, newn);
Strassen(P2, P4, P7, newn, false, false);
// * B12 已利用完 可以作为 temp
// S3 = A21 + A22
// P3 = S3 ? B11
matrixAdd(A21, A22, B12, newn);
Strassen(B12, B11, P3, newn, true, false); //删了B12
// * A21 已利用完 可以作为 temp
// S5 = A11 + A22
// S6 = B11 + B22
// P5 = S5 ? S6
// * P2作为 temp
matrixAdd(A11, A22, A21, newn);
matrixAdd(B11, B22, P2, newn);
Strassen(A21, P2, P5, newn, true, false);//删了A21
// C22 -> P7
// C22 = P5 + P1 - P3 - P7
matrixGetC22(P5, P1, P3, P7, P7, newn);
// * P7 已经利用完，可作 C22 -> P7
// * 当前可用作为temp的： B12(X)，A21(X)
// S2 = A11 + A12
// P2 = S2 ? B22
matrixAdd(A11, A12, A11, newn);
Strassen(A11, B22, P2, newn, true, false);//删了A11
// * A11 已被利用完， 可以作为 temp
// C22 -> P7
// C12 <- P1 = P1 + P2
matrixAdd(P1, P2, P1, newn);
// *P1 已被利用完，可 C12 <- P1 当前temp： A11，B12(X)，A21(X)
// S4 = B21 - B11
// P4 = A22 ? S4
matrixSub(B21, B11, B11, newn);
Strassen(A22, B11, P4, newn, false, true); //删了B11
// *B11 已被利用完，当前temp： B11(X)，A11(X)，B12(X)，A21(X)
// C22 -> P7
// C12 <- P1 = P1 + P2
// C21 <- P3 = P3 + P4
matrixAdd(P3, P4, P3, newn);
// *P3 已被利用完，可 C21 <- P3 当前temp： B11(X)，A11(X)，B12(X)，A21(X)
// S7 = A12 - A22
// S8 = B21 + B22
// P6 <- B22 = S7 ? S8
matrixSub(A12, A22, A12, newn);
matrixAdd(B21, B22, B21, newn);
Strassen(A12, B21, B22, newn, true, true); //删了A12 B21
// *当前temp： B11(X)，A11(X)，B12(X)，A21(X)，A12(X)，B21(X)
// C22 -> P7
// C12 <- P1 = P1 + P2
// C21 <- P3 = P3 + P4
// C11 <- P5 = P5 + P4 - P2 + P6
matrixGetC11(P5, P4, P2, B22, P5, newn);
// 合并矩阵C
for (i = 0; i < newn; i++)
{
for (j = 0; j < newn; j++)
{
C[i][j] = P5[i][j];
C[i][j + newn] = P1[i][j];
C[i + newn][j] = P3[i][j];
C[i + newn][j + newn] = P7[i][j];
}
}
// 释放内存
for (i = 0; i < newn; i++)
{
/*
delete[] A11[i];
delete[] A12[i];
delete[] A21[i];
*/
delete[] A22[i];
/*
delete[] B11[i];
delete[] B12[i];
delete[] B21[i];
*/
delete[] B22[i];
/*
delete[] C11[i];
delete[] C12[i];
delete[] C21[i];
delete[] C22[i];
*/
delete[] P1[i];
delete[] P2[i];
delete[] P3[i];
delete[] P4[i];
delete[] P5[i];
delete[] P7[i];
/*
delete[] P6[i];
delete[] temp1[i];
delete[] temp2[i];
*/
}
/*
delete[] A11;
delete[] A12;
delete[] A21;
*/
delete[] A22;
/*
delete[] B11;
delete[] B12;
delete[] B21;
*/
delete[] B22;
/*
delete[] C11;
delete[] C12;
delete[] C21;
delete[] C22;
*/
delete[] P1;
delete[] P2;
delete[] P3;
delete[] P4;
delete[] P5;
delete[] P7;
/*
delete[] P6;
delete[] temp1;
delete[] temp2;*/
}省略了无关的代码，通过看任务管理，发现通过传给下一层递归的矩阵并没有成功被回收（和都放在递归调用后面删除的方法相比，占用内存多了，多了的部分是传给下一层递归的矩阵）
表达能力可能不好，先谢谢了
