Эффективно хранить треугольную матрицу

Мне нужно эффективно хранить нижнюю треугольную матрицу, не сохраняя все нули в памяти, поэтому я подумал об этом следующим образом: сначала я выделяю память для каждой строки, затем для каждой строки я выделяю i + 1 байт, поэтому я никогда приходится беспокоиться об нулях, но что-то не так при первом распределении. Что я делаю неправильно? Это мой код, и компилятор выходит из программы в строке 8, сразу после чтения измерения матрицы.

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

РЕДАКТИРОВАТЬ

хорошо, поэтому, изменив код так, как вы мне помогли, я должен прочитать верхнюю треугольную и нижнюю треугольную матрицу и показать их продукт. Проблема заключается в том, что я не храню нули в памяти, поэтому, если я использую традиционный алгоритм 3-для, он покажет некоторые значения нежелательной информации. И если я инициализирую остальную часть каждой из матриц с помощью 0, бесполезно распределять память динамически, потому что у меня также будут храниться нули, поэтому я ничего не сделал для улучшения эффективность хранилища. Я думаю, что мне нужно изменить код где-нибудь или, может быть, интервалы времени, но в любом случае я изменяю выходы программы (для матрицы 3×3) 2 значения нежелательной почты в верхнем правом углу. Как я могу это сделать?

 #include  #include  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-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=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; 

}

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

mat1 – это двойной указатель. Вам нужно выделить память для вашего массива указателей, а затем вам нужно выделить память каждому из ваших указателей в отдельности. Не нужно бросать calloc()

Если вы хотите сохранить пространство и накладные расходы на распределение каждой строки матрицы, вы можете реализовать треугольную матрицу, используя умную индексацию одного массива.

Нижняя треугольная matrix (включая диагонали) обладает следующими свойствами:

  Матрица измерений Элементы / ряд Всего элементов
 1 х.  ,  ,  1 1
 2 xx.  ,  2 3
 3 xxx.  3 6
 4 xxxx 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(dr) + cr 

Образец кода:

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

Обратите внимание, что это тривиальный пример. Вы можете расширить его, чтобы обернуть указатель на матрицу внутри структуры, в которой также хранится тип матрицы (верхний или нижний треугольник или квадрат), а также размеры и функции доступа к записи, которые работают соответственно в зависимости от типа матрицы.

Для любого нетривиального использования матриц вы, вероятно, должны использовать стороннюю библиотеку, которая специализируется на matrixх.

Вы разыгрываете mat1 в строке 8, прежде чем он даже настроен на то, чтобы указывать в любом месте. Вы выделяете массив указателей на 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*));