数据结构稀疏矩阵基本运算实验报告.doc

《数据结构稀疏矩阵基本运算实验报告.doc》由会员分享，可在线阅读，更多相关《数据结构稀疏矩阵基本运算实验报告.doc（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、课 程 设 计课程：数据结构题目：稀疏矩阵4 三元组单链表 结构体(行数、列数、头) 矩阵运算重载运算符 优班级：姓名：学号：设计时间：2010年1月17日2010年5月XX日成绩：指导教师：楼建华一、题目题目稀疏矩阵4结构三元组单链表表示结构体(行数、列数、头)回传方式重载运算符操作矩阵运算 二、概要设计1.存储结构typedef structint row,col;/行，列datatype v;/非0数值Node;typedef structNode datamax;/稀疏矩阵int m,n,t;/m行，n列，t非0数个数Matrix;矩阵a非零数值data1非零数值data2行数m列数n

2、头h行r列c值d行r列c值dmnDatamaxrowcolvrowcolv2.基本操作 istream& operator (istream& input,Matrix *A)/输入 ostream& operator data00481101212332124306max-1（2）乘法运算要点已知稀疏矩阵A(m1 n1)和B(m2 n2)，求乘积C(m1 n2)。稀疏矩阵A、B、C及它们对应的三元组表A.data、B.data、C.data如图6所示。由矩阵乘法规则知：C(i，j)=A(i,1)B(1,j)+A(i,2)B(2,j)+A(i,n)B(n,j)=这就是说只有A(i,k)与B(k

3、,p)(即A元素的列与B元素的行相等的两项)才有相乘的机会，且当两项都不为零时，乘积中的这一项才不为零。矩阵用二维数组表示时，a11只有可能和B中第1行的非零元素相乘，a12只有可能和B中第2行的非零元素相乘，而同一行的非零元是相邻存放的，所以求c11和c12同时进行：求a11*b11累加到c11，求a11*b12累加到c12，再求a12*b21累加到c11，再求a12*b22累加到c22.，当然只有aik和bkj(列号与行号相等)且均不为零(三元组存在)时才相乘，并且累加到cij当中去。（3）稀疏矩阵的快速转置要点：矩阵A中三元组的存放顺序是先行后列，对同一行来说，必定先遇到列号小的元素，这

4、样只需扫描一遍A.data 。所以需引入两个向量来实现 ：numn+1和position n+1，numcol表示矩阵A中第col列的非零元素的个数(为了方便均从1单元用起)，position col初始值表示矩阵A中的第col列的第一个非零元素在B.data中的位置。于是position的初始值为：position 1=1;position col= position col-1+numcol-1; 2coln依次扫描A.data，当扫描到一个col列元素时，直接将其存放在B.data的position col位置上，position col加1，position col中始终是下一个col

5、列元素在B.data中的位置。A-row00112334（4）逆矩阵判断矩阵是否为方阵逆矩阵的算法： 求行列式的值求矩阵的伴随矩阵用伴随矩阵除以行列式 求逆矩阵的流程：四、源程序（测试结果）#include#include#include#includeusing namespace std;#define max 100#define datatype int typedef structint row,col;/行，列datatype v;/非0数值Node;typedef structNode datamax;/稀疏矩阵int m,n,t;/m行，n列，t非0数个数Matrix; /*求

6、逆矩阵存储*/typedef struct /存储结构int m, n; /行、列数double *p; /矩阵基址nMatrix;void In(nMatrix a) /求逆输入 couta.ma.n;int m = a.m, n = a.n;int i, j;double *p = a.p = new doublem * n; /p是行指针cout请按行优先输入矩阵a的全部数值：n;for (i = 0; i m; p += n, i+)for (j = 0; j pj; /即a.pi*n+jvoid Out(nMatrix a) /求逆输出 int m = a.m, n = a.n;in

7、t i, j;double *p = a.p;for (i = 0; i m; p += n, i+)for (j = 0; j n; j+)coutpjt;cout(istream& input,Matrix &A)int i;coutA.m;coutA.n;coutA.t;for(i=1;i=A.t;i+)cout请输入行数，列数，非0值:(iA.datai.rowA.datai.colA.datai.v;return input;ostream& operator (ostream& output,Matrix &A)int i,j,t=1,k=0;for(i=1;i=A.m;i+)fo

8、r(j=1;j=A.n;j+)if(A.datat.row=i&A.datat.col=j)outputA.datat.vt;t+;else outputkt;coutn;return output;Matrix operator +(Matrix A,Matrix B)/加法int i,j,k;Matrix C;if(A.m!=B.m|A.n!=B.n) cout这两个矩阵不能相加endl;exit(0);C.m=A.m;C.n=A.n;C.t=0;if(A.t=0&B.t=0) exit(0);i=j=k=1;while(i=A.t&j=B.t)if(A.datai.rowB.dataj.

9、row)C.datak=B.dataj;j+;k+;elseif(A.datai.colB.dataj.col)C.datak=B.dataj;j+;k+;elseif(A.datai.v+B.dataj.v!=0)C.datak.row=A.datai.row;C.datak.col=A.datai.col;C.datak.v=A.datai.v+B.dataj.v;k+;i+;j+; while(iA.t)C.datak=A.datai;i+;k+;while(jB.t)C.datak=B.dataj;j+;k+;C.t=k; return C;Matrix operator -(Matr

10、ix A,Matrix B)Matrix C;int i,j,k; if(A.m!=B.m|A.n!=B.n) cout这两个矩阵不能相减;exit(0); C.m=A.m;C.n=A.n; C.t=0; if(A.t=0&B.t=0) exit(0); i=j=k=1; while(i=A.t&j=B.t) if(A.datai.rowB.dataj.row) C.datak=B.dataj; j+;k+; else if(A.datai.colB.dataj.col) C.datak=B.dataj; j+;k+; else if(A.datai.v-B.dataj.v!=0) C.dat

11、ak.row=A.datai.row; C.datak.col=A.datai.col; C.datak.v=A.datai.v-B.dataj.v; k+; i+;j+; while(iA.t) C.datak=A.datai; i+;k+; while(jB.t) C.datak=B.dataj; j+;k+; C.t=k; return C;Matrix operator *(Matrix A,Matrix B)Matrix C;int k,p,crow,brow,q,ccol;int nummax,posmax,ctempmax;if (A.n=B.m)for(k=1;k=B.m;k+

12、)numk=0;for(k=1;k=B.t;k+)numB.datak.row+;pos1=1;for(k=2;k=B.t;k+)posk=posk-1+numk-1;pos1+B.t=posB.t+1;C.m=A.m; C.n=B.n; C.t=0; p=1;while(p=A.t)crow=A.datap.row;for(k=1;k=C.n;k+)ctempk=0;while (p=A.t&A.datap.row=crow)brow=A.datap.col;for(q=posbrow;q=posbrow+1-1;q+)ccol=B.dataq.col;ctempccol=ctempccol

13、+A.datap.v*B.dataq.v;p=p+1;for(ccol=1;ccol=B.n;ccol+)if(ctempccol!=0)C.t=C.t+1;C.dataC.t.row=crow;C.dataC.t.col=ccol;C.dataC.t.v=ctempccol;else cout这两个矩阵不能相乘;return C;Matrix operator (Matrix A)Matrix B;int col,i,p,q;int nummax,positionmax;B.t=A.t;B.m=A.n; B.n=A.m;if(B.t)for(col=1;col=A.n;col+)numcol

14、=0;for(i=1;i=A.t;i+)numA.datai.col+;position1=1;for(col=2;col=A.n;col+)positioncol=positioncol-1+numcol-1;for(p=1;p=A.t;p+)col=A.datap.col;q=positioncol;B.dataq.row=A.datap.col;B.dataq.col=A.datap.row;B.dataq.v=A.datap.v;positioncol+;return B;nMatrix Trs(nMatrix a) /求逆矩阵的先转置nMatrix trs;trs.m = a.n;t

15、rs.n = a.m;trs.p = new doublea.m * a.n;for (int i = 0; i a.m; i+)for (int j = 0; j a.n; j+)trs.pj * a.m + i = a.pi * a.n + j;return trs;nMatrix Adjunct(nMatrix a, int indexm, int indexn) /求第indexm行indexn列元素的代数余子式nMatrix adj;adj.m=a.m - 1;adj.n=a.n - 1;adj.p = new double(a.n - 1) * (a.n - 1);for (int

16、 i = 0; i indexm; i+)for (int j = 0; j indexn; j+)adj.pi * (a.n - 1) + j = a.pi * a.n + j;for (int k = indexn + 1; k a.n; k+)adj.pi *(a.n - 1) + k -1 = a.pi * a.n + k;for (int m = indexm + 1; m a.n; m+)for (int j = 0; j a.n - 1; j+)adj.p(m - 1) * (a.n - 1) + j = a.pm * a.n + j;for (int k = indexn +

17、1; k a.n; k+)adj.p(m - 1) * (a.n - 1) + k - 1 = a.pm * a.n + k;return adj;double Det(nMatrix a) /递归求行列式double det = 0;if (a.m != a.n)cout不是方阵，没有行列式!endl;cout求行列式退出endl;if (a.n = 1)det = a.p0;return det;elsefor (int i = 0; i a.n; i+)if (i % 2 = 0)det += a.pi * a.n * Det(Adjunct(a, i, 0);else det -= a

18、.pi * a.n * Det(Adjunct(a, i, 0);return det;nMatrix operator !(nMatrix a) /求矩阵的逆nMatrix temp;temp.m=a.n;temp.n=a.m;temp.p = new doublea.m * a.n;/矩阵的逆 = 伴随矩阵 / 行列式double det = Det(a);if (det = 0) /如果行列式的值为0，则没有逆cout此矩阵没有逆!endl;cout求矩阵逆退出!endl;for (int i = 0; i temp.m; i+)for (int j = 0; j A; couta=nB

19、; coutb=nB;C=A+B;couta+b=nC;C=A-B;couta-b=nC;C=A*B;couta*b=nC;C=A;couta=nC;In(a);cout矩阵的行列式为:endl;coutDet(a)endl;cout矩阵的逆为:endl;temp=!a;cout!a=nTrsendl;五、测试请输入行数:2请输入列数:2请输入非0值个数:2请输入行数，列数，非0值:(1)1 1 1请输入行数，列数，非0值:(2)1 2 1a=1 10 0请输入行数:2请输入列数:2请输入非0值个数:2请输入行数，列数，非0值:(1)2 2 1请输入行数，列数，非0值:(2)2 1 2b=0

20、00 1a+b=1 10 1a-b=1 10 1a*b=0 10 0a=1 01 0请将稀疏矩阵a的行、列数再次输入：2 2请按行优先输入稀疏矩阵a的全部数值：1 10 0矩阵的行列式为:-1矩阵的逆为:!a=1 01 0Press any key to continue六、总结这次数据结构课程设计的制作使我对数据结构和C语言的理解更加深刻，也使我认识到了自己很多不足之处。我发现自己在处理稍微具体的程序时显得无从下手，以前学习的知识只是理论性的知识，并没有真正实践过，当我通过网上查询、请教学生老师、复习知识后才对编写程序有了初步的思路。后来编写程序时也碰到了许多错误，我对于指针的掌握程度较差导致了我在使用的时候产生了很多错误，请教了学习较好的同学后才逐步完成。最后还有很多细节方面难以修改，于是就改进算法，使自己的程序有了雏形。这次程序设计使我认识到，要做成编写一个完整的程序绝对不是一件简单的事情，不单要掌握基础知识更要勇于实践，不单要舍得花费时间更要用心去完成它。无论是编写程序还是完成现实生活中的其他事情，我们都必须按部就班地从点滴做起，逐步完成。不但要完成更要做到尽善尽美。学习数据结构的历程不会因为完成本次课程设计而停止，我是为了用知识武装大脑而学习，通过学习充实自己的生活，我一定会努力学习，争取以后能够完成规模更大的程序。