数据结构-行逻辑链接的矩阵乘法 （C语言代码）

解题思路:

    ① 只需要计算两矩阵非0元素间的乘法；

    ② 使用行逻辑链接可得到该行首个非0元位置，也可以间接得到该行非0元个数；

    ③ 在行逻辑链接的基础上，可以成行确定Q的元素，即需要M该行的遍历 + N全行的遍历。

参考代码:

#include<stdio.h>
#include<malloc.h>
#include<string.h>

typedef struct Triple {
	int i, j; // 所在行、列
	int data; // 数值
} Triple;

typedef struct RLSMatrix {
	Triple *data;
	int *rpos; // 记录每行首个非0元的位置
	int mu, nu, tu; // 行、列、非0元个数
} RLSMatrix;

// 创建行逻辑链接的顺序表
void CreateRLSMatrix(RLSMatrix *M);
// 矩阵乘法，在M中遍历非0元进行
void MultRLSMatrix(RLSMatrix *M, RLSMatrix *N, RLSMatrix *Q);
// 按行输出矩阵
void DisplayRLSMatrix(RLSMatrix *Q);

int main()
{
	RLSMatrix M, N, Q;
	M.data = NULL; M.rpos = NULL;
	N.data = NULL; N.rpos = NULL;
	Q.data = NULL; Q.rpos = NULL;
	CreateRLSMatrix(&M);
	CreateRLSMatrix(&N);
	MultRLSMatrix(&M, &N, &Q);
	DisplayRLSMatrix(&Q);
	return 0;
}

void CreateRLSMatrix(RLSMatrix *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 MultRLSMatrix(RLSMatrix *M, RLSMatrix *N, RLSMatrix *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 DisplayRLSMatrix(RLSMatrix *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");
	}
}