《数据结构课程设计-稀疏矩阵运算器.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计-稀疏矩阵运算器.docx（12页珍藏版）》请在金锄头文库上搜索。
1、实习4、稀疏矩阵运算器一、需求分析1. 问题描述 稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。2. 基本要求以带“行逻辑连接信息”的三元组顺序表表示稀疏矩阵，实现两个矩阵的相加、相减和相乘运算。稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则以通常的阵列形式列出。3. 实现提示(1)首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行、列数对于所要求作的运算是否匹配。可设聚矩阵的行数和列数不超过20。(2)程序可以对三元组的输入顺序加以限制，例如，按行优先。注意研究教科书5.3.2节中的算法，
2、以便提高计算效率。(3)在用三元组表示稀疏矩阵时，相加或相减所得的结果矩阵应该另生成，乘积矩阵也可以用二维数组存放。二、概要设计ADT SparseMatrix 数据对象：D=aij|i=1,2,3m;j = 1,2,3n;ai,jintSet,m和n分别称为矩阵的行数和列数 数据关系：R = Row,col Row =|1im，1jn-1 Col = |1im-1，1jn 基本操作：CreateSMatrix(*T);操作结果：创建稀疏矩阵T。AddRLSMatrix(M,N,*Q);初始条件：稀疏矩阵M和N的行数列数对应相等。操作结果：求稀疏矩阵的和Q=M+N。SubRLSSMatrix(
3、M,N,*Q);初始条件：稀疏矩阵M和N的行数列数对应相等。操作结果：求稀疏矩阵的差Q=M-N。SMatrixrpos(*T)初始条件：稀疏矩阵T存在。操作结果：求稀疏矩阵的各行第一个非零元的位置表。MulTSMatrix(M,N,*Q);初始条件：稀疏矩阵M的列数与N的行数对应相等。操作结果：求稀疏矩阵的乘积Q=M*N;PrintSMatrix(RLSMatrix Q)初始条件：稀疏矩阵Q存在。操作结果：输出稀疏矩阵Q。DestorySMatrix(T);初始条件：稀疏矩阵T存在。操作结果：销毁稀疏矩阵T。ADT SparseMatrix三、详细设计（源代码）（使用C语言）#include#
4、include#define MAXSIZE 400/矩阵非零元个数的最大值为400#define MAXRC 20/矩阵的行数（列数）的最大值为20typedef struct/稀疏矩阵的三元组顺序表存储表示int i,j; /该非零元的行下标和列下标int e;Triple;typedef structTriple dataMAXSIZE+1; /非零元三元组表，data0未用int rposMAXRC+1; /各行第一个非零元的位置表int mu,nu,tu; /矩阵的行数列数和非零元的个数RLSMatrix;void CreateSMatrix(RLSMatrix *T)/输入并创建稀
5、疏矩阵int k;printf( n请输入矩阵行数、列数及非零元个数: );scanf(%d%d%d,&T-mu,&T-nu,&T-tu);printf(n);if(T-tuMAXSIZE|T-mu20|T-nu20)printf(出错：非零个数或行数（列数）超出定义范围！);exit(0);for(k=1;ktu;k+)printf(请输入第%d个非零元素的行数,列数及其值: ,k);scanf(%d%d%d,&T-datak.i,&T-datak.j,&T-datak.e);int AddRLSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix *Q)/稀疏矩
6、阵的加法运算，运算失败返回0int p,q,k=0;if(M.mu!=N.mu|M.nu!=N.nu)/传入的稀疏矩阵不符合加法运算条件 return 0;Q-mu=M.mu;Q-nu=M.nu;k+;for(p=1,q=1;p=M.tu&qdatak.i=M.datap.i;Q-datak.j=M.datap.j;Q-datak.e=M.datap.e+N.dataq.e;p+;q+;k+;/非零元与零元的相加else if(M.datap.jdatak.i=M.datap.i;Q-datak.j=M.datap.j;Q-datak.e=M.datap.e;k+;p+;else if(M.d
7、atap.jN.dataq.j)Q-datak.i=N.dataq.i;Q-datak.j=N.dataq.j;Q-datak.e=N.dataq.e;k+;p+;else if(M.datap.idatak.i=M.datap.i;Q-datak.j=M.datap.j;Q-datak.e=M.datap.e;k+;p+;else if(M.datap.iN.dataq.i)Q-datak.i=N.dataq.i;Q-datak.j=N.dataq.j;Q-datak.e=N.dataq.e;k+;q+;if(p!=M.tu+1)for(;pdatak.i=M.datap.i;Q-datak
8、.j=M.datap.j; Q-datak.e=M.datap.e;k+;if(q!=N.tu+1)for(;qdatak.i=N.dataq.i;Q-datak.j=N.dataq.j;Q-datak.e=N.dataq.e;k+; Q-tu=k; return 1;int SubRLSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix *Q)/稀疏矩阵的减法运算，运算失败返回0if(M.mu!=N.mu|M.nu!=N.nu)/传入的稀疏矩阵不符合加法运算条件 return 0;int i; for(i=1;i=N.tu;i+)/将稀疏矩阵N的非零元置为其各自
9、的相反数 N.datai.e=-N.datai.e; return AddRLSMatrix(M,N,Q);/调用稀疏矩阵的加法运算函数void SMatrixrpos(RLSMatrix *T)/求稀疏矩阵的各行第一个非零元的位置表 int num20,col,t;/numcol为各行非零元的个数 for(col=1;colmu;+col) numcol=0; for(t=1;ttu;+t)/计算各行非零元的个数 +numT-datat.i; T-rpos1=1; for(col=2;colmu;+col)/求各行第一个非零元的位置表 T-rposcol=T-rposcol-1+numcol
10、-1;int MulTSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix *Q)/稀疏矩阵的乘法运算，采用逻辑连接存储表示，运算失败返回0int ccol=0,tp,brow,t,arow,p,q,i;int ctempMAXSIZE+1;if(M.nu!=N.mu) return 0; /求各稀疏矩阵的各行第一个非零元的位置表 SMatrixrpos(&M); SMatrixrpos(&N); /Q初始化Q-mu=M.mu;Q-nu=N.nu;Q-tu=0;if(M.tu*N.tu!=0)/Q是非零矩阵for(arow=1;arow=M.mu;+arow)/处
11、理M的每一行 for(i=1;irposarow=Q-tu+1;if(arowM.mu) tp=M.rposarow+1;else tp=M.tu+1;for(p=M.rposarow;ptp;+p)/对当前行中每一个非零元找到对应元在N中的行号brow=M.datap.j;if(browN.mu) t=N.rposbrow+1;else t=N.tu+1;for(q=N.rposbrow;qt;+q)ccol=N.dataq.j;/乘积元素在Q中的列号ctempccol+=M.datap.e*N.dataq.e;/求得Q中第arow行的非零元for(ccol=1;ccolnu;+ccol)/压缩存储该行非零元if(ctempccol) Q-tu+;if(Q-tuMAXSIZE) return 0; else Q-dataQ-tu.i=arow; Q-dataQ-tu.
