解题思路:
① 只需要计算两矩阵非0元素间的乘法;
② 使用行逻辑链接可得到该行首个非0元位置,也可以间接得到该行非0元个数;
③ 在行逻辑链接的基础上,可以成行确定Q的元素,即需要M该行的遍历 + N全行的遍历。
参考代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 | #include<stdio.h> #include<malloc.h> #include<string.h> typedef struct Triple { int i, j; // 所在行、列 int data; // 数值 } Triple; typedef struct RL**atrix { Triple *data; int *rpos; // 记录每行首个非0元的位置 int mu, nu, tu; // 行、列、非0元个数 } RL**atrix; // 创建行逻辑链接的顺序表 void CreateRL**atrix(RL**atrix *M); // 矩阵乘法,在M中遍历非0元进行 void MultRL**atrix(RL**atrix *M, RL**atrix *N, RL**atrix *Q); // 按行输出矩阵 void DisplayRL**atrix(RL**atrix *Q); int main() { RL**atrix M, N, Q; M.data = NULL; M.rpos = NULL; N.data = NULL; N.rpos = NULL; Q.data = NULL; Q.rpos = NULL; CreateRL**atrix(&M); CreateRL**atrix(&N); MultRL**atrix(&M, &N, &Q); DisplayRL**atrix(&Q); return 0; } void CreateRL**atrix(RL**atrix *M) { int i, j, data, size; M->tu = 1; scanf ( "%d%d" , &M->mu, &M->nu); M->data = (Triple *) malloc ( sizeof (Triple) * M->nu * 2); M->rpos = ( int *) malloc ( sizeof ( int ) * (M->mu + 1)); size = M->nu * 2; for (i = 1; i <= M->mu; i++) { M->rpos[i] = M->tu; // 该行首个非0元位置在上一行输入完时确定 for (j = 1; j <= M->nu; j++) { scanf ( "%d" , &data); if (data) { // 存放非0元 // 注意这里第0个位置不存放非0元,从第1个开始,和行逻辑对应 M->data[M->tu].i = i; M->data[M->tu].j = j; M->data[M->tu++].data = data; } } if (size - M->tu < M->nu) { M->data = (Triple *) realloc (M->data, sizeof (Triple) * (size + M->nu)); size += M->nu; } } M->tu--; // 此前始终比非0元个数大1,此时减去 } void MultRL**atrix(RL**atrix *M, RL**atrix *N, RL**atrix *Q) { int i, j, k1, k2, k3, k4, row, col, size, *temp; Q->mu = M->mu; Q->nu = N->nu; Q->tu = 0; Q->data = (Triple *) malloc ( sizeof (Triple) * Q->nu * 2); size = Q->nu * 2; // temp暂时存放乘积结果,每次存放Q[i]行的结果,个数为N的列数 temp = ( int *) malloc ( sizeof ( int ) * (Q->nu + 1)); for (row = 1; row <= M->mu; row++) { // 遍历M每行的非0元 memset (temp, 0, sizeof ( int ) * (Q->nu + 1)); // 每行都需要将temp重置 k1 = M->rpos[row]; // 获取该行首个非0元 if (row == M->mu) { k2 = M->tu + 1; // 若是最后一行,直接遍历完 } else { k2 = M->rpos[row + 1]; // 否则,遍历完到下一行首个非0元之前 } // M中从k1遍历到k2 while (k1 < k2) { j = M->data[k1].j; // 获取非0元在M中的所在列 k3 = N->rpos[j]; // 找到对应N的那行 if (j == N->mu) { k4 = N->tu + 1; } else { k4 = N->rpos[j + 1]; } // 对M中每个非0元取所在列,在N中找到对应行非0元,记录分积 while (k3 < k4) { col = N->data[k3].j; // 获取N中该非0元所在列 temp[col] += M->data[k1].data * N->data[k3].data; k3++; } k1++; } // 当M的该行遍历完成,Q的该行元素全部确定 for (i = 1; i <= Q->nu; i++) { if (temp[i]) { // 只存放非0元 Q->data[++Q->tu].i = row; Q->data[Q->tu].j = i; Q->data[Q->tu].data = temp[i]; } } // 偷懒,没有进行Q的行逻辑链接。 if (size - Q->tu < Q->nu) { Q->data = (Triple *) realloc (Q->data, sizeof (Triple) * (size + Q->nu)); size += Q->nu; } } } void DisplayRL**atrix(RL**atrix *Q) { int i, j, k = 1; for (i = 1; i <= Q->mu; i++) { for (j = 1; j <= Q->nu; j++) { if (Q->data[k].i == i && Q->data[k].j == j) { printf ( "%d " , Q->data[k++].data); } else { printf ( "0 " ); } } printf ( "\n" ); } } |