一、问题描述：
稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储（只存储非零元）和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。
二、需求分析：
以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现两个矩阵相加、相减和相乘的运算。稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则以通常的阵列形式列出。稀疏矩阵的输出要求：矩阵的行数、列数、非零元个数，以及详细的矩阵阵列形式。
三、代码实现
代码语言：javascript复制#include <stdio.h>
#include <iostream>
#define ERROR -1
#define MAXSIZE 12500 //非零元个数最大值MAXSIZE
#define MAXRC 21 //各行第一个非零元位置最大值MAXRC
#define OK 1
typedef int ElemType;
typedef struct //同课本P98
{
int i,j;
ElemType e;
} Triple;
typedef struct //同课本P100
{
Triple data[MAXSIZE 1]; //非零元三元组表
int rpos[MAXRC 1]; //各行第一个非零元的位置表
int mu,nu,tu; //矩阵的行数、列数和非零元个数
} RLSMatrix;
void CreatSMatrix(RLSMatrix &M) //建立以“带行链接信息”的三元组顺序表示的稀疏矩阵
{
for(int i=1; i<=MAXRC 1; i )
M.rpos[i]=0; //令所有的位置都为0
printf("请输入矩阵的行数、列数和非零元个数(以空格隔开):");
scanf("%d %d %d",&M.mu,&M.nu,&M.tu);
for(int i=1; i<=M.tu; i )
{
printf("请用三元组形式输入矩阵的元素(行 列 非零元素):");
scanf("%d %d %d",&M.data[i].i,&M.data[i].j,&M.data[i].e);
}
for(int i=1,j=1; i<=M.mu; i ) //求M.rpos[i]
{
M.rpos[i]=j;
while(M.data[j].i==i && j<=M.tu) j ; //若某一行的元素多于1个时
}
}
int MultsMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix &Q)
{
int brow,ccol,p,q,t,tp,ctemp[MAXRC 1],i;
Q.mu=M.mu; //Q初始化
Q.nu=N.nu;
Q.tu=0;
if(M.nu!=N.mu)return ERROR;
if(M.tu*N.tu) //Q是非零矩阵
{
for(int arow=1; arow<=M.mu; arow) //处理M的每一行
{
for( i=1; i<=MAXRC 1; i )
ctemp[i]=0; //当前行各元素累加器清零
Q.rpos[arow]=Q.tu 1;
if(arow<M.mu)
tp=M.rpos[arow 1];
else
{
tp=M.tu 1;
}
for(p=M.rpos[arow]; p<tp; p) //对当前行中每一个非零元
{
brow=M.data[p].j; //找到对应元在N中的行号
if(brow<N.mu)
t=N.rpos[brow 1];
else
{
t=N.tu 1;
}
for(q=N.rpos[brow]; q<t; q)
{
ccol=N.data[q].j; //乘积元素在Q中列号
ctemp[ccol] =M.data[p].e*N.data[q].e;
}//for q
}//求得Q中第crow(=arow)行的非零元
for(ccol=1; ccol<=Q.nu; ccol) //压缩存储该非零元
if(ctemp[ccol])
{
if( Q.tu>MAXSIZE)
return ERROR;
Q.data[Q.tu].i=arow;
Q.data[Q.tu].j=ccol;
Q.data[Q.tu].e=ctemp[ccol];
}//if
}//for arow
}//if
return 1;
}
bool AddSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix &Q) //矩阵相加
{
if(M.mu!=N.mu||M.nu!=N.nu)return ERROR;
int i,j,k=1;
Q.mu=M.mu;
Q.nu=M.nu;
for(i=1,j=1; i<=M.tu&&j<=N.tu;)
{
//按行优先，故分以下几种情况
if(M.data[i].i==N.data[j].i) //两元素同一行
{
if(M.data[i].j==N.data[j].j) //两元素同一行且同一列（同位置）
{
Q.data[k].i=M.data[i].i;
Q.data[k].j=M.data[i].j;
Q.data[k].e=M.data[i].e N.data[j].e;
i ;
j ;
k ;
}
else if(M.data[i].j<N.data[j].j) //两元素同一行，但M中的元素列数较小
{
Q.data[k].i=M.data[i].i;
Q.data[k].j=M.data[i].j;
Q.data[k].e=M.data[i].e;
k ;
i ;
}
else if(M.data[i].j>N.data[j].j) //两元素同一行，但M中的元素列数较大
{
Q.data[k].i=N.data[j].i;
Q.data[k].j=N.data[j].j;
Q.data[k].e=N.data[j].e;
k ;
j ;
}
}
else if(M.data[i].i<N.data[j].i) //M中的元素行数较小
{
Q.data[k].i=M.data[i].i;
Q.data[k].j=M.data[i].j;
Q.data[k].e=M.data[i].e;
k ;
i ;
}
else if(M.data[i].i>N.data[j].i) //M中的元素行数较大
{
Q.data[k].i=N.data[j].i;
Q.data[k].j=N.data[j].j;
Q.data[k].e=N.data[j].e;
k ;
j ;
}
}
if(i!=M.tu 1) //计算最后的元素
for(; i<=M.tu; i )
{
Q.data[k].i=M.data[i].i;
Q.data[k].j=M.data[i].j;
Q.data[k].e=M.data[i].e;
k ;
}
if(j!=N.tu 1)
for(; j<=N.tu; j )
{
Q.data[k].i=N.data[j].i;
Q.data[k].j=N.data[j].j;
Q.data[k].e=N.data[j].e;
k ;
}
for(i=1,j=1; i<=Q.mu; i ) //求Q.rpos[i]
{
Q.rpos[i]=j;
while(Q.data[j].i==i && j<=Q.tu) //若某一行的元素多于1个时
j ;
}
return OK;
}
void SubtSMatrix(RLSMatrix M,RLSMatrix &N,RLSMatrix &Q)
{
//矩阵减法
int i=1;
for(; i<=N.tu; i )
{
N.data[i].e=-N.data[i].e;
}
AddSMatrix(M,N,Q);
}
void PrintSMatrix(RLSMatrix M)
{
//以通常阵列形式输出稀疏矩阵
int k,l,n;
for(k=1,n=1; k<=M.mu; k )
{
for(l=1; l<=M.nu; l )
{
if(M.data[n].i==k && M.data[n].j==l)
{
printf("]",M.data[n].e);
n ;
}
else
printf("]",0);
}
printf("n");
}
printf("n");
}
int Destory_SMatrix(RLSMatrix &M)
{
M.mu=M.nu=M.tu=0;
return 1;
}
int main()
{
RLSMatrix A,B,C;
int flag;
while(1)
{
printf("━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━n");
printf(" 稀疏矩阵的加、减、乘 n");
printf("━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━n");
printf(" 1、稀疏矩阵的加法 n");
printf(" 2、稀疏矩阵的减法 n");
printf(" 3、稀疏矩阵的乘法 n");
printf(" 4、退出程序 n");
printf("━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━n");
printf("输入要进行的运算功能的编号:");
scanf("%d",&flag);
if(flag==4)
{
printf(" n程序已经退出! n");
exit(0);
}
switch(flag)
{
case 1: //加法
CreatSMatrix(A);
printf("矩阵A=n");
PrintSMatrix(A);
CreatSMatrix(B);
printf("矩阵B=n");
PrintSMatrix(B);
if(A.mu==B.mu && A.nu==B.nu)
{
printf("A B=n");
AddSMatrix(A,B,C);
PrintSMatrix(C);
}
else
printf("错误!两矩阵的行列数不一致n");
break;
case 2://减法
CreatSMatrix(A);
printf("矩阵A=n");
PrintSMatrix(A);
CreatSMatrix(B);;
printf("矩阵B=n");
PrintSMatrix(B);
if(A.mu==B.mu && A.nu==B.nu)
{
printf("A-B=n");
SubtSMatrix(A,B,C);
PrintSMatrix(C);
}
else
printf("错误!两矩阵的行列数不一致n");
break;
case 3://乘法
CreatSMatrix(A);
printf("矩阵A=n");
PrintSMatrix(A);
CreatSMatrix(B);
printf("矩阵B=n");
PrintSMatrix(B);
if(A.nu==B.mu)
{
printf("A*B=n");
MultsMatrix(A,B,C);
PrintSMatrix(C);
}
else
printf("错误!矩阵A的列数不等于矩阵B的行数n");
break;
default:
printf("输入错误!n");
}
Destory_SMatrix(A);
Destory_SMatrix(B);
Destory_SMatrix(C);
}
return 0;
}
