更改矩阵大小后访问未分配的内存

Question

我不会用所有枯燥的细节来打扰你，关于什么是作业和我要解决的问题，我会开门见山。

我需要用数据填充矩阵。矩阵是正方形的，除前 2 条对角线外，所有内容均为零（意味着 M[i][i] 对于 i 在 0 和 n-1 之间，M[i][i+1] 对于 i 在 0 和 n-2 之间已满）

我们想用这个有点复杂的公式来填充矩阵。

M[i][j]=max(a+min(M[i+2][j],M[i+1][j-1]) , b+min(M[i+1][j-1],M[i][j-2]))

结果是一个上三角矩阵。从上面的公式可以看出，要计算第 k 条对角线，我们需要 k-2 条对角线。我说的是前两个。

我写了一个代码来填充矩阵，它按预期工作。

这是我的问题：

由于是上三角矩阵，所以下半部分全为零。所以浪费内存并保存它是没有意义的。所以我心想，与其分配一个 n 乘 n 的矩阵，不如分配 n 行，第一行分配 n 个空间，第二个 n-1，第三个 n-2，依此类推...

但是由于我们改变了矩阵的维度，我上面写的计算 M[i][j] 的公式现在不同了。在我看来，我们将 i'th 行、i 列中的所有值都移到了左边。第 0 行没有任何变化。在第 1 行，我们将所有值拉到左侧 1 列，依此类推。所以如果我理解正确的话：

M[i][j]=M'[i][j-i]

其中 M' 是我们的新矩阵。所以将其插入上面的公式：

M'[i][j]=max(a+min(M'[i+2][j-i],M'[i+1][j-1-i]) , b+min(M'[i+1][j-1-i],M'[i][j-2-i]))

但是现在填充矩阵的程序无法正常工作。它正在用垃圾填充矩阵。

下面是填充矩阵的代码：

void fill_matrix() //fills the matrix with data of optimal path, we use memoization rather than recursion, so this step is necessary. 
{ //first step is to allocate the matrix. we can assume right_index==size-1 since this is the first thing we do after generating the array
    int i,j;
    optimum_matrix=(int**)malloc((right_index+1)*sizeof(int**));
    for(j=0;j<=right_index;j++)
        optimum_matrix[j]=(int*)malloc((right_index+1-j)*sizeof(int*)); //matrix allocated. upper triangular matrix. no need to allocate n^2 spaces. //to fix indices, M[i][j]=M'[i][j-i+1]. subtract i and add 1 to each column, since we moved each entry in row i, i-1 columns back.
    for(i=0;i<=right_index;i++) //first diagonal
        optimum_matrix[i][0]=data_array[i];
    for(i=0;i<right_index;i++) //second diagonal
        optimum_matrix[i][1]=get_max(data_array[i],data_array[i+1]);
    for(i=0;i<=right_index;i++)
    {
        for(j=2;j<=right_index-i;j++)
            optimum_matrix[i][j]=get_max(data_array[i]+get_min(optimum_matrix[i+2][j-i],optimum_matrix[i+1][j-i-1]),data_array[j]+get_min(optimum_matrix[i+1][j-i-1],optimum_matrix[i][j-i-2])); //here is the problem
    }
}

这是打印矩阵的代码

void print_matrix()
{
    int i,j,k;
    for(i=0;i<=right_index;i++)
    {
        for(k=0;k<i;k++)
            printf("0 ");
        for(j=0;j<=right_index-i;j++)
            printf("%d ",optimum_matrix[i][j]);
        printf("\n");
    }
}

即使在填充第三条对角线的第一次迭代中，当它进入它说 "here is the problem" 的 for 循环时，如果我键入 printf("%d",optimum_matrix[i+2][j-i]);，它也会打印垃圾。而且我不明白为什么因为公式一致。

希望得到帮助。谢谢。

Answer 1

optimum_matrix=(int**)malloc((right_index+1)*sizeof(int**));

这不是分配双精度数组的正确方法。它只分配双精度数组的一维。我很难按照您希望每行和每列有多大的逻辑进行操作。所以下面可能不是您想要的正确尺寸。但希望它确实说明了如何更正确地分配双数组。

int **optimum_matrix = malloc((right_index+1)*sizeof(int*));

for (i = 0; i < (right_index+1); i++) {
    optium_matrix[i] = malloc((right_index+1)*sizeof(int));
}

顺便说一句，为简洁起见，我省略了 malloc return 值的检查。而且您的原始代码也不检查 malloc 的 return 值。应该始终这样做。

更改矩阵大小后访问未分配的内存

accessing unallocatted memory after changing matrix size

c

math

memory

matrix

jagged-arrays