黄山小妖是我老婆
解题思路:
① 只需要计算两矩阵非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#include#includetypedef 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"); }} |
