有效存儲三角矩陣

Question

我需要通過不將所有的零存儲在內存中來有效地存儲下三角矩陣，所以我這樣想：首先爲每一行分配內存，然後爲每一行分配i +1字節，所以我從來不必擔心零，但在第一次分配時出現錯誤。我究竟做錯了什麼？這是我的代碼，編譯器在讀取矩陣的維數之後，在第8行退出程序。

#include <stdio.h> 
#include <stdlib.h> 

int main() 
{ 
    int i, j, **mat1, dim; 

    scanf("%d",&dim); 
    *mat1 = (int**)calloc(dim, sizeof(int*)); 

    for(i = 0; i<dim; i++) 
    mat1[i] = (int*)calloc(i+1, sizeof(int)); 

    for(i = 0; i < dim; i++) 
    for(j = 0; j < i+1; j++) 
     scanf("%d", &mat1[i][j]); 

    for(i=0; i<dim; i++) 
    for(j=0; j<(i+1); j++) 
     printf("%d%c", mat1[i][j], j != (dim-1) ? ' ' : '\n'); 

    return 0; 
} 

編輯

確定，所以修改代碼你幫了我的道，我要讀上三角和下三角矩陣，並展示自己的產物。問題這是我不要將0存儲在內存中，所以如果我使用傳統的3-for算法，它將顯示一些垃圾值。如果我用0初始化每個矩陣的其餘部分，則動態分配內存是無用的，因爲我會也有零存儲，所以我沒有做任何事情來提高存儲效率。我想我必須修改代碼的地方，或者可能是間隔，但無論如何，我修改公關圖仍然輸出（對於3x3矩陣）右上角的2個垃圾值。我該如何做？

#include <stdio.h> 
#include <stdlib.h> 
int main() 
{ 
int i,j,k,**mat1,**mat2,**prod,dim; 


printf("Give dimension: \n"); 
scanf("%d",&dim); 

mat1 = (int**)calloc(dim,sizeof(int*)); 

for(i=0; i<dim; i++) 
    mat1[i] = (int*)calloc(i+1,sizeof(int)); 

mat2 = (int**)calloc(dim,sizeof(int*)); 

for(i=dim-1; i>-1; i--) 
    mat2[i]=(int*)calloc(i+1,sizeof(int)); 

prod = (int**)calloc(dim,sizeof(int*)); 
for(i=0; i<dim; i++) 
    prod[i] = (int*)calloc(dim,sizeof(int)); 

printf("Give lower triangular matrix(non 0 values only): \n"); 
for(i=0; i<dim; i++) 
    for(j=0; j<i+1; j++) 
     scanf("%d",&mat1[i][j]); 

printf("Give upper triangular matrix(non 0 values): \n"); 
for(i=0; i<dim; i++) 
    for(j=i; j<dim;j++) 
     scanf("%d",&mat2[i][j]); 

printf("Matrix A is: \n"); 
for(i=0; i<dim; i++) 
    for(j=0; j<dim; j++) 
     printf("%d%c",j<=i?mat1[i][j]:0,j!=dim-1?' ':'\n'); 

printf("Matrix B is: \n"); 
for(i=0; i<dim; i++) 
    for(j=0; j<dim; j++) 
     printf("%d%c",j>=i?mat2[i][j]:0,j!=dim-1?' ':'\n'); 

for(i=0; i<dim; i++) 
    for(j=0; j<dim; j++) 
     for(k=0; k<dim; k++) 
      prod[i][j]+=mat1[i][k]*mat2[k][j]; 


printf("The product of the two matrix is: \n"); 
for(i=0; i<dim; i++) 
    for(j=0; j<dim; j++) 
     printf("%d%c",prod[i][j],j!=dim-1?' ':'\n'); 


return 0; 

}

Answer 1

mat1 = calloc(dim,sizeof(int*)); 

mat1是雙pointer.You需要爲指針數組分配內存，以後你需要分配內存以每個指針individually.No需要轉換calloc()

Answer 2

您已在第8行取消引用mat1，然後它甚至已設置爲指向任何位置。你正在爲int分配一個指針數組，但是你並沒有將它分配給mat1，而是對未初始化的mat1解引用，我們不知道它指向什麼。

所以這行：

// ERROR: You are saying an unknown memory location should have the value of calloc. 
*mat1 = (int**)calloc(dim,sizeof(int*)); 

應更改爲：

// OK: Now you are assigning the allocation to the pointer variable. 
mat1 = (int**)calloc(dim,sizeof(int*)); 

Answer 3

如果你想節省空間和分配矩陣中的每一行的開銷，你可以通過實現一個三角矩陣使用巧妙的索引單個數組。

下三角矩陣（包括對角線）具有以下性質：

Dimension Matrix Elements/row Total elements 
1   x . . . 1    1 
2   x x . . 2    3 
3   x x x . 3    6 
4   x x x x 4    10 
... 

對於給定尺寸的元件的總數是：

size(d) = 1 + 2 + 3 + ... + d = (d+1)(d/2) 

如果打好行出在單個數組中，可以使用上面的公式計算矩陣內給定行和列（均爲零）的偏移量：

index(r,c) = size(r-1) + c 

上面的公式適用於下三角矩陣。你可以通過簡單地顛倒索引訪問上矩陣，如果它是一個較低的矩陣：

index((d-1)-r, (d-1)-c) 

如果您有關於更改陣列的方向有疑慮，可以設計爲上部陣列不同的偏移計算如：

uindex(r,c) = size(d)-size(d-r) + c-r 

樣品的編號：

#include <time.h> 
#include <stdio.h> 
#include <stdlib.h> 

#define TRM_SIZE(dim) (((dim)*(dim+1))/2) 
#define TRM_OFFSET(r,c) (TRM_SIZE((r)-1)+(c)) 
#define TRM_INDEX(m,r,c) ((r)<(c) ? 0 : (m)[TRM_OFFSET((r),(c))]) 
#define TRM_UINDEX(m,r,c,d) ((r)>(c)?0:(m)[TRM_SIZE(d)-TRM_SIZE((d)-(r))+(c)-(r)]) 
#define UMACRO 0 


int main (void) 
{ 
    int i, j, k, dimension; 
    int *ml, *mu, *mr; 

    printf ("Enter dimension: "); 
    if (!scanf ("%2d", &dimension)) { 
    return 1; 
    } 

    ml = calloc (TRM_SIZE(dimension), sizeof *ml); 
    mu = calloc (TRM_SIZE(dimension), sizeof *mu); 
    mr = calloc (dimension*dimension, sizeof *mr); 
    if (!ml || !mu || !mr) { 
    free (ml); 
    free (mu); 
    free (mr); 
    return 2; 
    } 

    /* Initialization */ 

    srand (time (0)); 
    for (i = 0; i < TRM_SIZE(dimension); i++) { 
    ml[i] = 100.0*rand()/RAND_MAX; 
    mu[i] = 100.0*rand()/RAND_MAX; 
    } 

    /* Multiplication */ 

    for (i = 0; i < dimension; i++) { 
    for (j = 0; j < dimension; j++) { 
     for (k = 0; k < dimension; k++) { 
     mr[i*dimension + j] += 
#if UMACRO 
      TRM_INDEX(ml, i, k) * 
      TRM_UINDEX(mu, k, j, dimension); 
#else 
      TRM_INDEX(ml, i, k) * 
      TRM_INDEX(mu, dimension-1-k, dimension-1-j); 
#endif 
     } 
    } 
    } 

    /* Output */ 

    puts ("Lower array"); 
    for (i = 0; i < dimension; i++) { 
    for (j = 0; j < dimension; j++) { 
     printf (" %2d", TRM_INDEX(ml, i, j)); 
    } 
    putchar ('\n'); 
    } 
    puts ("Upper array"); 
    for (i = 0; i < dimension; i++) { 
    for (j = 0; j < dimension; j++) { 
#if UMACRO 
     printf (" %2d", TRM_UINDEX(mu, i, j, dimension)); 
#else 
     printf (" %2d", TRM_INDEX(mu, dimension-1-i, dimension-1-j)); 
#endif 
    } 
    putchar ('\n'); 
    } 
    puts ("Result"); 
    for (i = 0; i < dimension; i++) { 
    for (j = 0; j < dimension; j++) { 
     printf (" %5d", mr[i*dimension + j]); 
    } 
    putchar ('\n'); 
    } 

    free (mu); 
    free (ml); 
    free (mr); 

    return 0; 
} 

注意，這是一個簡單的例子。您可以擴展它以將矩陣指針包裝在也存儲矩陣類型（上或下三角形，或方形）和維度的結構中，並根據矩陣的類型編寫適當運行的訪問函數。

對於任何非平凡的矩陣使用，您應該使用專門用於矩陣的第三方庫。