题目

假设稀疏矩阵A和B（分别为mxn和nxk矩阵）采用三元组表示，编写一个函数，计算C=AxB，要求C也用三元组表示的稀疏矩阵。

分析

第一种思路是先将A和B由三元组转换成稀疏矩阵形式，然后进行矩阵相乘，再将相乘后的C用三元组表示。

第二种思路是本题在原理上与普通的矩阵相乘算法没有太大区别，其核心问题在于，根据给出的行号和列号找出原矩阵中的对应元素值，因此构造了一个函数getvalue0,当在三元组表示中找到时返回其元素值，找不到说明原该位置处的元素值为0，因此返回0.然后利用该函数计算出C的行号i和列号j处的元素值，若该值不为0，则存入其三元组表示的矩阵中，否则不存入。

代码

第一种思路的代码如下：

/* 将三元组转换成稀疏矩阵 */ 
int trimatToMat(int A[][3],int mat[][MAXSIZE]){
	int m=A[0][1];// 稀疏矩阵的行数
	int n=A[0][2];// 稀疏矩阵的列数
	int k=1;// 三元组数组的下标，初始为1，因为trimat[0][0-2]保存的是三元组的一些基本信息
	for(int i=0; i<m; i++) {
		for(int j=0; j<n; j++) { // 双层循环遍历稀疏矩阵
			if(i==A[k][1]&&j==A[k][2]) { // 如果i和j能够匹配三元组的下标trimat[k][1]和trimat[k][2]
				mat[i][j]=A[k][0];
				k++;// 继续遍历三元组的元素
			} else {
				mat[i][j]=0;
			}
		}
	}
}

/* 矩阵的相乘 */
/* C[][MAXSIZE]指的是相乘的结果矩阵；A[][MAXSIZE]指要参与相乘运算的矩阵；B[][MAXSIZE]指要参与相乘运算的矩阵；m指的是A矩阵的行数；n指的是A矩阵的列数也是B矩阵的行数；k指的是B矩阵的列数 */ 
void mutmat(int C[][MAXSIZE],int A[][MAXSIZE],int B[][MAXSIZE],int m,int n,int k){
	for(int i=0;i<m;i++){
		for(int j=0;j<k;j++){
			C[i][j]=0;
			for(int h=0;h<n;h++){ 
				C[i][j]+=A[i][h]*B[h][j];// 相乘 
			}
		}
	}
}

/* 根据给定的稀疏矩阵A(int型)创建三元组存储结构 */
/* A[][MAXSIZE]指的是稀疏矩阵；m指的是稀疏矩阵的行数；n指的是稀疏矩阵的列数；trimat[][3]指的是三元组 */ 
void createTrimat(int A[][MAXSIZE],int m,int n,int trimat[][3]) {
	int k=1;// 计数器，记录三元组的行下标，从1开始，0存储稀疏矩阵的基本信息
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){// 双层嵌套循环，遍历稀疏矩阵的所有元素
			if(A[i][j]!=0){
				trimat[k][0]=A[i][j];// trimat[k][0]存储稀疏矩阵中非零元素的值
				trimat[k][1]=i;// trimat[k][1]存储稀疏矩阵中非零元素的行下标 
				trimat[k][2]=j;// trimat[k][2]存储稀疏矩阵中非零元素的列下标 
				k++;// 计数器加1 
			} 
		}
	} 
	/* 存储一些稀疏矩阵的基本信息 */
	trimat[0][0]=k-1;// 保存矩阵中非零元素的个数
	trimat[0][1]=m;// 保存矩阵的行数 
	trimat[0][2]=n;// 保存矩阵的列数 
}

/* 稀疏矩阵A和B都采用三元组表示，计算C=A*B，要求C也用三元组表示 */
mutTrimat(int A[][3],int B[][3],int C[][3]){
	int matA[MAXSIZE][MAXSIZE];
	int matB[MAXSIZE][MAXSIZE];
	int matC[MAXSIZE][MAXSIZE];
	trimatToMat(A,matA);
	trimatToMat(B,matB);
	mutmat(matC,matA,matB,A[0][1],A[0][2],B[0][2]);
	createTrimat(matC,A[0][1],A[0][2],C);
}

完整代码如下：

#include<stdio.h>
#include<stdlib.h>
/* 稀疏矩阵A(mxn)和B(nxk)都采用三元组表示，计算C=A*B，要求C也用三元组表示 */
#define MAXSIZE 20

/* 将三元组转换成稀疏矩阵 */ 
int trimatToMat(int A[][3],int mat[][MAXSIZE]){
	int m=A[0][1];// 稀疏矩阵的行数
	int n=A[0][2];// 稀疏矩阵的列数
	int k=1;// 三元组数组的下标，初始为1，因为trimat[0][0-2]保存的是三元组的一些基本信息
	for(int i=0; i<m; i++) {
		for(int j=0; j<n; j++) { // 双层循环遍历稀疏矩阵
			if(i==A[k][1]&&j==A[k][2]) { // 如果i和j能够匹配三元组的下标trimat[k][1]和trimat[k][2]
				mat[i][j]=A[k][0];
				k++;// 继续遍历三元组的元素
			} else {
				mat[i][j]=0;
			}
		}
	}
}

/* 矩阵的相乘 */
/* C[][MAXSIZE]指的是相乘的结果矩阵；A[][MAXSIZE]指要参与相乘运算的矩阵；B[][MAXSIZE]指要参与相乘运算的矩阵；m指的是A矩阵的行数；n指的是A矩阵的列数也是B矩阵的行数；k指的是B矩阵的列数 */ 
void mutmat(int C[][MAXSIZE],int A[][MAXSIZE],int B[][MAXSIZE],int m,int n,int k){
	for(int i=0;i<m;i++){
		for(int j=0;j<k;j++){
			C[i][j]=0;
			for(int h=0;h<n;h++){ 
				C[i][j]+=A[i][h]*B[h][j];// 相乘 
			}
		}
	}
}

/* 根据给定的稀疏矩阵A(int型)创建三元组存储结构 */
/* A[][MAXSIZE]指的是稀疏矩阵；m指的是稀疏矩阵的行数；n指的是稀疏矩阵的列数；trimat[][3]指的是三元组 */ 
void createTrimat(int A[][MAXSIZE],int m,int n,int trimat[][3]) {
	int k=1;// 计数器，记录三元组的行下标，从1开始，0存储稀疏矩阵的基本信息
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){// 双层嵌套循环，遍历稀疏矩阵的所有元素
			if(A[i][j]!=0){
				trimat[k][0]=A[i][j];// trimat[k][0]存储稀疏矩阵中非零元素的值
				trimat[k][1]=i;// trimat[k][1]存储稀疏矩阵中非零元素的行下标 
				trimat[k][2]=j;// trimat[k][2]存储稀疏矩阵中非零元素的列下标 
				k++;// 计数器加1 
			} 
		}
	} 
	/* 存储一些稀疏矩阵的基本信息 */
	trimat[0][0]=k-1;// 保存矩阵中非零元素的个数
	trimat[0][1]=m;// 保存矩阵的行数 
	trimat[0][2]=n;// 保存矩阵的列数 
}

/* 稀疏矩阵A和B都采用三元组表示，计算C=A*B，要求C也用三元组表示 */
mutTrimat(int A[][3],int B[][3],int C[][3]){
	int matA[MAXSIZE][MAXSIZE];
	int matB[MAXSIZE][MAXSIZE];
	int matC[MAXSIZE][MAXSIZE];
	trimatToMat(A,matA);
	trimatToMat(B,matB);
	mutmat(matC,matA,matB,A[0][1],A[0][2],B[0][2]);
	createTrimat(matC,A[0][1],A[0][2],C);
}


/* 打印矩阵 */
/* A[][MAXSIZE]指的是矩阵；m指的是矩阵的行数；n指的是矩阵的列数 */
void printMat(int A[][MAXSIZE],int m,int n) {
	for(int i=0; i<m; i++) {
		for(int j=0; j<n; j++) {
			printf("%d\t",A[i][j]);
		}
		printf("\n");
	}
}

/* 打印三元组 */
void print(int trimat[][3]){
	printf("\n");
	for(int k=1;k<=trimat[0][0];k++){
		printf("%d\t",trimat[k][0]);
	}
	printf("\n");
} 


int main() {

	int A[][MAXSIZE]= {
		{0,0,0,1},
		{0,0,3,2},
		{1,0,0,0},
		{0,2,0,0},
		{1,0,0,0}
	};
	int m=5,n=4;// 指的是矩阵的行数和列数
	printf("原矩阵A：\n");
	printMat(A,m,n);// 打印原矩阵

	int B[][MAXSIZE]= {
		{0,0,0,1},
		{0,0,3,2},
		{1,0,0,0},
		{0,2,0,0},
	};
	int k=4;
	printf("原矩阵B：\n");
	printMat(B,n,k);// 打印原矩阵
	
	int C[MAXSIZE][MAXSIZE]; 
	mutmat(C,A,B,m,n,k);// 矩阵的相乘
	printf("相乘后的矩阵C：\n");
	printMat(C,m,n);// 打印相乘后的矩阵

	int matA[MAXSIZE][3];
	createTrimat(A,m,n,matA);
	int matB[MAXSIZE][3];
	createTrimat(B,n,k,matB);
	int matC[MAXSIZE][3];
	mutTrimat(matA,matB,matC);
	print(matC);// 打印A*B后的三元组 

	return 0;
} 

运行结果如下：

第二种思路的代码如下：

/* 返回D对应的稀疏矩阵A中(i,j)位置上的值 */ 
int getValue(int D[][3],int i,int j){
	int k=1;
	while(k<=D[0][0]&&D[k][1]!=i||D[k][2]!=j){
		k++;
	}
	if(k<=D[0][0]){
		return D[k][0];
	}else{
		return 0;
	}
} 
/* 矩阵相乘 */
void mul(int A[][3],int B[][3],int C[][3],int m,int n,int k){
	int i,j,l,p=1,s;
	for(i=0;i<m;i++){
		for(j=0;j<k;j++){
			s=0;
			for(l=0;l<n;l++){
				s+=getValue(A,i,l)*getValue(B,l,j);
			}
			if(s!=0){
				C[p][1]=i;
				C[p][2]=j;
				C[p][0]=s;
				p++;
			}
		}
	}
	C[0][1]=m;
	C[0][2]=k;
	C[0][0]=p-1;
} 

完整代码如下：

#include<stdio.h>
#include<stdlib.h>
/* 稀疏矩阵A(mxn)和B(nxk)都采用三元组表示，计算C=A*B，要求C也用三元组表示 */
#define MAXSIZE 20

/* 根据给定的稀疏矩阵A(int型)创建三元组存储结构 */
/* A[][MAXSIZE]指的是稀疏矩阵；m指的是稀疏矩阵的行数；n指的是稀疏矩阵的列数；trimat[][3]指的是三元组 */ 
void createTrimat(int A[][MAXSIZE],int m,int n,int trimat[][3]) {
	int k=1;// 计数器，记录三元组的行下标，从1开始，0存储稀疏矩阵的基本信息
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){// 双层嵌套循环，遍历稀疏矩阵的所有元素
			if(A[i][j]!=0){
				trimat[k][0]=A[i][j];// trimat[k][0]存储稀疏矩阵中非零元素的值
				trimat[k][1]=i;// trimat[k][1]存储稀疏矩阵中非零元素的行下标 
				trimat[k][2]=j;// trimat[k][2]存储稀疏矩阵中非零元素的列下标 
				k++;// 计数器加1 
			} 
		}
	} 
	/* 存储一些稀疏矩阵的基本信息 */
	trimat[0][0]=k-1;// 保存矩阵中非零元素的个数
	trimat[0][1]=m;// 保存矩阵的行数 
	trimat[0][2]=n;// 保存矩阵的列数 
}

/* 返回D对应的稀疏矩阵A中(i,j)位置上的值 */ 
int getValue(int D[][3],int i,int j){
	int k=1;
	while(k<=D[0][0]&&D[k][1]!=i||D[k][2]!=j){
		k++;
	}
	if(k<=D[0][0]){
		return D[k][0];
	}else{
		return 0;
	}
} 
/* 矩阵相乘 */
void mul(int A[][3],int B[][3],int C[][3],int m,int n,int k){
	int i,j,l,p=1,s;
	for(i=0;i<m;i++){
		for(j=0;j<k;j++){
			s=0;
			for(l=0;l<n;l++){
				s+=getValue(A,i,l)*getValue(B,l,j);
			}
			if(s!=0){
				C[p][1]=i;
				C[p][2]=j;
				C[p][0]=s;
				p++;
			}
		}
	}
	C[0][1]=m;
	C[0][2]=k;
	C[0][0]=p-1;
} 

/* 打印矩阵 */
/* A[][MAXSIZE]指的是矩阵；m指的是矩阵的行数；n指的是矩阵的列数 */
void printMat(int A[][MAXSIZE],int m,int n) {
	for(int i=0; i<m; i++) {
		for(int j=0; j<n; j++) {
			printf("%d\t",A[i][j]);
		}
		printf("\n");
	}
}

/* 打印三元组 */
void print(int trimat[][3]){
	printf("\n");
	for(int k=1;k<=trimat[0][0];k++){
		printf("%d\t",trimat[k][0]);
	}
	printf("\n");
} 


int main() {

	int A[][MAXSIZE]= {
		{0,0,0,1},
		{0,0,3,2},
		{1,0,0,0},
		{0,2,0,0},
		{1,0,0,0}
	};
	int m=5,n=4;// 指的是矩阵的行数和列数
	printf("原矩阵A：\n");
	printMat(A,m,n);// 打印原矩阵

	int B[][MAXSIZE]= {
		{0,0,0,1},
		{0,0,3,2},
		{1,0,0,0},
		{0,2,0,0}
	};
	int k=4;
	printf("原矩阵B：\n");
	printMat(B,n,k);// 打印原矩阵

	int matA[MAXSIZE][3];
	createTrimat(A,m,n,matA);
	print(matA);
	int matB[MAXSIZE][3];
	createTrimat(B,n,k,matB);
	print(matB);
	int matC[MAXSIZE][3];
	mul(matA,matB,matC,m,n,k);
	print(matC);// 打印A*B后的三元组 

	return 0;
}