更改矩陣大小後訪問未分配的內存

Question

我不會打擾所有關於什麼是任務和我試圖解決的問題的乾燥細節，我會盡快解決問題。

我需要用數據填充矩陣。基體爲方形，一切都是除了第2個對角線（0 n-1和用於i之間M[i][i+1]意義M[i][i]爲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"); 
    } 
} 

即使在填充第三對角的第一次迭代中，當它進入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返回值的檢查。而你的原始代碼也不檢查malloc的返回值。這應該總是完成。