数据结构课程设计-稀疏矩阵运算器.docx

实习4、稀疏矩阵运算器一、需求分析1. 问题描述 稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。2. 基本要求以带“行逻辑连接信息”的三元组顺序表表示稀疏矩阵，实现两个矩阵的相加、相减和相乘运算。稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则以通常的阵列形式列出。3. 实现提示(1)首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行、列数对于所要求作的运算是否匹配。可设聚矩阵的行数和列数不超过20。(2)程序可以对三元组的输入顺序加以限制，例如，按行优先。注意研究教科书5.3.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(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#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)/输入并创建稀疏矩阵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)/稀疏矩阵的加法运算，运算失败返回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.datap.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.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的非零元置为其各自的相反数 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-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)/处理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.j=ccol; q-dataq-tu.e=ctempccol; return 1;void printsmatrix(rlsmatrix q)/输出稀疏矩阵int k=1,row,line;printf(n运算结果: );if(q.tu=0) printf(0);elsefor(row=1;row=q.mu;row+)for(line=1;linemu=0; t-nu=0; t-tu=0;int main()/主函数rlsmatrix m,n,q;char c;/输出菜单printf(*n); printf(* *n); printf(* 稀疏矩阵运算器 *n); printf(* *n); printf(* a: 输入矩阵m与n b: 输出矩阵m与n的和 *n); printf(* *n); printf(* c: 输出矩阵m与n的差 d: 输出矩阵m与n的积 *n); printf(* *n); printf(* e: 退出 *n); printf(* *n); printf(*n);doprintf(n请选择: n);scanf(%c,&c);if(c=e|c=e) goto end;else switch(c) case a: case a: printf(请输入第一个矩阵m:n); createsmatrix(&m); printf(请输入第二个矩阵n:n); createsmatrix(&n); break; case b: case b: if(addrlsmatrix(m,n,&q) printsmatrix(q); else printf(您的输入不满足矩阵相加的条件!n); break; case c: case c: if(subrlsmatrix(m,n,&q) printsmatrix(q); else printf(您的输入不满足矩阵相减的条件!n); break; case d: case d: if(multsmatrix(m,n,&