Speichern Sie die Dreiecksmatrix effizient

Question

Ich muss effizient eine untere Dreiecksmatrix speichern, indem ich nicht alle Nullen im Speicher ablege, also habe ich darüber nachgedacht: Zuerst gebe ich Speicher für jede Zeile, dann für jede Zeile i +1 Bytes, also muss ich mich nie um die Nullen kümmern, aber bei der ersten Zuweisung stimmt etwas nicht. Was mache ich falsch? Dies ist mein Code, und der Compiler beendet das Programm in Zeile 8, gleich nachdem er die Dimension der Matrix gelesen hat.

#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; 
} 

EDIT

ok so, nachdem Sie den Code die Art und Weise zu modifizierten Sie mir geholfen, ich habe ein oberes Dreieck lesen und eine untere Dreiecksmatrix und ihr product.The Problem zeigt damit, dass ich ist Speichern Sie die Nullen nicht im Speicher. Wenn ich also den traditionellen 3-for-Algorithmus verwende, werden einige Junk-Werte angezeigt. Und wenn ich den Rest jeder der Matrizen mit 0 initialisiere, ist es nutzlos, den Speicher dynamisch zuzuweisen, weil ich es tun würde habe auch die Nullen gespeichert, also habe ich nichts getan, um die Effizienz des Speichers zu verbessern. Ich denke, ich muss den Code irgendwo ändern, oder vielleicht die für Intervalle, aber ich modifiziere sowieso den pr ogram gibt immer noch (für 3x3 Matrix) 2 Junk-Werte in der oberen rechten Ecke aus. Wie könnte ich das machen?

#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 ist ein Doppel pointer.You benötigen Speicher für Ihre Array von Zeigern verteilen und später müssen Sie Speicher an jeden Ihrer Zeiger zuzuweisen individually.No müssen calloc() werfen

Answer 2

Sie deneferenzieren mat1 in Zeile 8, bevor es überhaupt auf irgendeinen Punkt gesetzt wurde. Sie ordnen ein Array von Zeigern zu int zu, aber Sie ordnen das dem mat1 nicht zu, aber zu der Dereferenz von Mat1, das nicht initialisiert wird, wissen wir nicht, worauf es hinweist.

Also diese Zeile:

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

Sollte sich ändern:

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

Answer 3

Wenn Sie Platz sparen möchten und den Aufwand für jede Zeile der Matrix Zuweisung Sie eine Dreiecksmatrix implementieren könnte durch clevere Indizierung eines einzelnen Arrays.

eine untere Dreiecksmatrix (einschließlich der Diagonalen) hat die folgenden Eigenschaften:

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 
... 

Die Gesamtzahl der Elemente für eine gegebene Dimension ist:

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

Wenn die Zeilen heraus lag Anschließend können Sie in einem Array die Formel oben verwenden, um den Versatz einer gegebenen Zeile und Spalte (beide nullbasiert) in der Matrix zu berechnen:

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

Die obigen Formeln gelten für die untere Dreiecksmatrix.Sie können die obere Matrix zugreifen, als ob es sich um eine untere Matrix durch einfaches Umkehren der Indizes war:

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

Wenn Sie Bedenken über die Ausrichtung des Arrays zu ändern, Sie eine andere Berechnung für die obere Reihe versetzt ersinnen kann, wie zum Beispiel:

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

Beispielcode:

#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; 
} 

Beachten Sie, dass dies ein triviales Beispiel ist. Sie können es erweitern, um den Matrixzeiger innerhalb einer Struktur zu wickeln, die auch den Typ der Matrix (oberes oder unteres Dreieck oder Quadrat) und die Dimensionen speichert, und Schreibzugriffsfunktionen, die abhängig vom Typ der Matrix entsprechend arbeiten.

Für jede nicht-triviale Verwendung von Matrizen sollten Sie wahrscheinlich eine Bibliothek von Drittanbietern verwenden, die auf Matrizen spezialisiert ist.