数据结构----稀疏矩阵运算器课程设计参考模板

1、内蒙古科技大学数据结构课程设计说明书题 目：稀疏矩阵运算器设计学生姓名：学 号：专 业：计算机科学与技术班 级：计09-1班指导教师：刘 月 峰 2011 年 6 月 24 日0 / 32稀疏矩阵运算器设计摘 要 摘要：设计一稀疏矩阵运算器。实现转置，相加，相乘的功能。用“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现两个矩阵相转置、相加和相乘的运算，采用分级的设计方法，分别设计出转置、加、乘运算器的子程序，相加运算时只要依次扫描两矩阵的行号和列号，若相等则相加后存入结果矩阵，不等时则存入较小的。相减运算与相加运算相同，同样比较两矩阵的行号和列号，只是不等时，若第一个小，则存入第一个的元素

2、，若第二个小，则存入其相反数。相乘运算要先判断两矩阵能否相乘。通过给顶的行号和列号找出原矩阵对应的元素值。当在三元组表示中找到时返回其元素值，找不到时，说明该位置为0，因此返回0。然后利用该函数计算出C的行号i和列号j 处的元素值，若该值不为0，则存入矩阵，否则不存入。通过实验表明本程序能够进行稀疏矩阵的相加，相减，相乘运算。具备矩阵的加、减、乘功能。关键词：转置运算器；相加运算器；相乘运算器 目 录稀疏矩阵运算器设计I摘 要II第一章 需求分析1第二章 概要设计2第三章 设计步骤6 3.1 函数说明6 3.2 设计步骤7第四章 设计理论分析方法20 4.1 算法一：矩阵转置20 4.2 算法

3、二：矩阵加法20 4.3 算法三：矩阵乘法21第五章 程序调试23第六章 心得体会25 参考文献26 第一章 需求分析1 稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。2 以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现矩阵转置，求逆，实现两个矩阵相加、相减和相乘的运算。稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则以通常的阵列形式列出。 3 演示程序以用户和计算机的对话方式执行，数组的建立方式为边输入边建立。4 由题目要求可知：首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行、列数

4、对于所要求作的运算是否相匹配。5 程序可以对三元组的输入顺序不加以限制；根据对矩阵的行列，三元组作直接插入排序，从而进行运算时,不会产生错误。6 在用三元组表示稀疏矩阵时，相加、乘积和相减所得结果矩阵应该另生成；矩阵求逆时，为了算法方便，使用二维数组存放。7 程序在VC6.0环境下设计。程序执行的命令为：1.稀疏矩阵转置; 2.稀疏矩阵加法; ;3. 稀疏矩阵乘法; 4.退出的工作。第二章 概要设计1 抽象数据类型稀疏矩阵的定义如下：ADT SparseMatrix 数据对象：D=aij|i=1,2,m; j=1,2,n; aijElemSet, m和n分别为矩阵的行数和列数 数据关系：R=R

5、ow,Col Row=ai,j, ai,j+1| 1im, 1jn-1 Col = ai,j, ai+1,j| 1im-1, 1jn 基本操作：create(TSMatrix &TM)操作结果：创建稀疏矩阵矩阵TM LocateELem(TSMatrix M,int i,int j,int e)初始条件：稀疏矩阵M存在 操作结果：稀疏矩阵中是否存在非零元素Aij，若存在返回edisp(TSMatrix TM)初始条件：稀疏矩阵TM存在操作结果：通常形式输出稀疏矩阵InsertSortMatrix(TSMatrix &TM) 初始条件：稀疏矩阵TM存在操作结果：根据对矩阵的行列，

6、三元组TM作直接插入排序TransposeSMatrix(TSMatrix M,TSMatrix &T)初始条件：稀疏矩阵M和T存在操作结果：求稀疏矩阵M转置的稀疏矩阵TAddTSM(TSMatrix A,TSMatrix B,TSMatrix &C)初始条件：稀疏矩阵A，B和C存在 操作结果：稀疏矩阵的加法运算:C=A+BSubTSM(TSMatrix A,TSMatrix B,TSMatrix &C)初始条件：稀疏矩阵A，B和C存在 操作结果：稀疏矩阵的减法运算:C=A-BMultSMatrix(TSMatrix A,TSMatrix B,TSMatrix &

7、;C)初始条件：稀疏矩阵A，B和C存在操作结果：稀疏矩阵的乘法运算:C=A×B NiMatrix(TSMatrix &TM)初始条件：稀疏矩阵TM存在操作结果：稀疏矩阵求逆ADT SparseMatrix;2. 主程序：void main( )初始化；do 接受命令；选择处理命令； while(命令！=“退出”)3. 本程序有四个模块，调用关系如下：主程序模块矩阵输入模块 矩阵运算模块矩阵输出模块 图2.14 本程序的流程图开始选择要执行的操作作选择4，退出程序选择2，进行矩阵加法运算选择1，进行矩阵转置运算选择3，进行矩阵乘法运算 输入n个矩阵A的行数、列数、非零元个数输出

8、结果结束 图2.2第3章 设计步骤3.1函数说明稀疏矩阵的三元组顺序表存储表示：typedef struct / 定义三元组的元素 int i,j; int v; Triple; class tripletable /设计类来描述稀疏矩阵及其操作public: aaa *pdata; triple datamaxsize; int rposmaxsize; tripletable();tripletable(); void convert() ;void add( ); void multi ( );private:int m ; int n ; int t ; int a ;主要函数： tr

9、ipletable(); tripletable(); void convert( ) ; void add( ); void multi ( ); void main( );3.2设计步骤：设计一个矩阵类实现矩阵的运算：class tripletable(包含矩阵的各种运算函数)。输入矩阵（以三元组形式输入非零元） int k; tripletable A,B; cout<<"输入稀疏矩阵A的行数，列数和非零元个数：" cin>>A.m>>A.n>>A.t; for(k=1;k<=A.t;k+) printf(&quo

10、t;输入第%d个非0元素的行数，列数和值:",k); cin>>A.datak.i>>A.datak.j>>A.datak.v; 输出矩阵：int c100100=0; for(k=1;k<=B.t;k+) cB.datak.iB.datak.j=B.datak.v; cout<<"转置（加法，乘法）结果为："<<endl; for(k=1;k<=B.n;k+) for(int l=1;l<=B.m;l+) cout<<ckl<<" " cou

11、t<<endl; 转置矩阵：void tripletable:convert( ) /矩阵的转置 int k; tripletable A,B; cout<<"输入稀疏矩阵A的行数，列数和非零元个数：" cin>>A.m>>A.n>>A.t; for(k=1;k<=A.t;k+) printf("输入第%d个非0元素的行数，列数和值:",k); cin>>A.datak.i>>A.datak.j>>A.datak.v; B.m=A.m;B.n=A.n;B

12、.t=A.t; if(B.t) int q=1,col; for(col=1;col<=A.n;+col) for(int p=1;p<=A.t;+p) if(A.datap.j=col) B.dataq.i=A.datap.j; B.dataq.j=A.datap.i; B.dataq.v=A.datap.v; +q; int shuru100100=0; for(k=1;k<=B.t;k+) shuruB.datak.jB.datak.i=B.datak.v; cout<<"输入为："<<endl; for(k=1;k<=

13、B.m;k+) for(int l=1;l<=B.n;l+) cout<<shurukl<<" " cout<<endl; int result100100=0; for(k=1;k<=B.t;k+) resultB.datak.iB.datak.j=B.datak.v; cout<<"结果为："<<endl; for(k=1;k<=B.n;k+) for(int l=1;l<=B.m;l+) cout<<resultkl<<" &quo

14、t; cout<<endl; 以上主要设计思想：通过三元组输入一个矩阵A，为了找到A的每一列中所有非零元素，需要对其三元组表A.data从第一行起整个扫描一遍，由于A.data是以A的行序为主序来存放每个非零元的，由此得到的恰是B.data的应有的顺序。加法矩阵：void tripletable:add( ) /矩阵的加法 int k; tripletable A,B; cout<<"输入稀疏矩阵A的行数，列数和非零元个数：" cin>>A.m>>A.n>>A.t; for(k=1;k<=A.t;k+) pr

15、intf("输入第%d个非0元素的行数，列数和值:",k); cin>>A.datak.i>>A.datak.j>>A.datak.v; cout<<"输入稀疏矩阵B的行数，列数和非零元个数：" cin>>B.m>>B.n>>B.t; for(k=1;k<=B.t;k+) printf("输入第%d个非0元素的行数，列数和值:",k); cin>>B.datak.i>>B.datak.j>>B.datak.v;

16、 if(A.m!=B.m|A.n!=B.n) cout<<"输入错误：A与B的行数或列数不相同，请重新输入"<<endl; return; int a100100=0; for(k=1;k<=A.t;k+) aA.datak.iA.datak.j=A.datak.v; cout<<"A输入为："<<endl; for(k=1;k<=A.m;k+) for(int l=1;l<=A.n;l+) cout<<akl<<" " cout<<

17、endl; int b100100=0; for(k=1;k<=B.t;k+) bB.datak.iB.datak.j=B.datak.v; cout<<"B输入为："<<endl; for(k=1;k<=B.m;k+) for(int l=1;l<=B.n;l+) cout<<bkl<<" " cout<<endl; int c100100=0; for(k=1;k<=A.m;k+) for(int l=1;l<=A.n;l+) ckl=akl+bkl; cout

18、<<"加法结果C为："<<endl; for(k=1;k<=A.m;k+) for(int l=1;l<=A.n;l+) cout<<ckl<<" " cout<<endl; 以上主要设计思想：此功能由函数add( )实现，当用户选择该功能时系统即提示用户初始化要进行加法的两个矩阵的信息。然后检测这两个矩阵是否符合矩阵相加的规则，如果符合，进行加法。否则重新输入第二个矩阵来保证两个矩阵可以相加。最后输出结果。乘法矩阵：void tripletable:multi() /矩阵的乘法 i

19、nt k; tripletable A,B,C; cout<<"输入稀疏矩阵A的行数，列数和非零元个数：" cin>>A.m>>A.n>>A.t; for(k=1;k<=A.t;k+) printf("输入第%d个非0元素的行数，列数和值:",k); cin>>A.datak.i>>A.datak.j>>A.datak.v; int row=1; for(k=1;k<=A.t;k+) while(row<=A.datak.i) A.rposrow+=k;

20、 while(row<=A.m)A.rposrow+=A.t+1; cout<<"输入稀疏矩阵B的行数，列数和非零元个数：" cin>>B.m>>B.n>>B.t; for(k=1;k<=B.t;k+) printf("输入第%d个非0元素的行数，列数和值:",k); cin>>B.datak.i>>B.datak.j>>B.datak.v; row=1; for(k=1;k<=B.t;k+) while(row<=B.datak.i) B.rpo

21、srow+=k; while(row<=B.m)B.rposrow+=B.t+1; if(A.n!=B.m) cout<<"输入错误：A的列数不等于B的行数，请重新输入"<<endl; return; C.m=A.m;C.n=B.n;C.t=0; int arow,p,q,ccol,t,tp; if(A.t*B.t!=0) for(arow=1;arow<=A.m;+arow) int ctempmaxsize=0; C.rposarow=C.t+1; if(arow<A.m)tp=A.rposarow+1; elsetp=A.t+

22、1; for(p=A.rposarow;p<tp;+p) int brow=A.datap.j; if(brow<B.m)t=B.rposbrow+1; elset=B.t+1; for(q=B.rposbrow;q<t;+q) ccol=B.dataq.j; ctempccol+=A.datap.v*B.dataq.v; for(ccol=1;ccol<=C.n;+ccol) if(ctempccol) if(+C.t>maxsize)return; C.dataC.t.i=arow; C.dataC.t.j=ccol; C.dataC.t.v=ctempcco

23、l; int a100100=0; for(k=1;k<=A.t;k+) aA.datak.iA.datak.j=A.datak.v; cout<<"A输入为：" cout<<endl; for(k=1;k<=A.m;k+) for(int l=1;l<=A.n;l+) cout<<akl<<" " cout<<endl; int b100100=0; for(k=1;k<=B.t;k+) bB.datak.iB.datak.j=B.datak.v; cout<&l

24、t;"B输入为："<<endl; for(k=1;k<=B.m;k+) for(int l=1;l<=B.n;l+) cout<<bkl<<" " cout<<endl; int c100100=0; for(k=1;k<=C.t;k+) cC.datak.iC.datak.j=C.datak.v; cout<<"乘法结果C为："<<endl; for(k=1;k<=C.m;k+) for(int l=1;l<=C.n;l+) cou

25、t<<ckl<<" " cout<<endl; 以上主要设计思想为：此功能由函数multi( )实现。当用户选择该功能，系统提示输入要进行相乘的两个矩阵的详细信息。然后检测两者是否可以相乘，如果不能，则重新初始化第二个矩阵。先对矩阵B进行逐行处理，先求得累计求和的中间结果（C的每一行），然后再压缩存储到c.data中去，最后得到结果。 第四章 设计理论分析方法4.1 算法一：矩阵转置转置运算时一种最简单的矩阵运算，对于一个m*n的矩阵M，他的转置矩阵T是一个n*m的矩阵，且T（i，j）=M（j，i），1<=i<=n,1<

26、=j<=m。显然，一个稀疏矩阵的转置矩阵仍然是稀疏矩阵。(1)将矩阵的行列值相互交换;(2)将每个三元组中的i和j相互调换；（3）重排三元组之间的次序便可实现矩阵的转置。 一般矩阵转置算法为for(col=1;col<=nu;+col) for(row=1;row<=mu;+row)Tcolrow=Mrowcol;按照a.data中三元组的次序进行转置，并将转置后的三元组置入b中恰当的位置。在此，需要附设num和cpot两个向量。Numcol表示矩阵M中第col列中非零元的个数，cpotcol指示M中第col列的第一个非零元在b.data中的恰当位置。cpot1=1cpotc

27、ol=cpotcol-1+numcol-1 2<=col<=a.nu这就是快速转置。4.2 算法二：矩阵加法 稀疏矩阵使用三元组存储，则运算时只需考虑非零元的值即可。两个矩阵相加首先必须保证M.mu=N.mu&&M.nu=N.nu即同行同列的矩阵才能相加。 for(k=1;k<=M.tu;k+)for(i=1;i<=N.tu;i+)if(M.datak.i = N.datai.i && M.datak.j = N.datai.j) Q.datacount.e = M.datak.e + N.datai.e;flagi = true;如果非零元位置一样就直接相加if(i>N.tu)Q.datacount.e = M.datak.e;如果没有找到与M非零元位置一样的元素就直接把M中的非零元赋值给矩阵Q。for(k=1;k<=N.tu;k+)if(!flagk)Q.datacount.e = N.datak.e;如果N中的元素没有被查找，则直接把N中的非零元赋值给矩阵Q。4.3 算法三：矩阵乘法矩阵乘法采用“带行链接信息”的三元组存储。经典算法如下：