数据结构稀疏矩阵基本运算试验报告

1、课程设计课程：数据结构题目：稀疏矩阵 4 4 三元组单链表 结构体（行数、列数、头）矩阵运算重载运算符优班级：姓名：学号：设计时间：20102010 年 1 1 月 1717 日20102010 年 5 5 月 XXXX 日成绩：指导教师：楼建华max-1i、题目题目稀疏矩阵4结构二兀组单链表表示结构体（行数、列数、习(istream& input,Matrix *A)/输入 ostream& operator data01234t），三元组，., 三元组）32row col v33(2)乘法运算要点已知稀疏矩阵A(mix n1)和B(m2 n2),求乘积C(mix n2)。稀

2、疏矩阵A、B、C及它们对应的三元组表A.data、B.data、C.data如图6所示1 i v_i j为为_ _i j甲甲114j1 1 12214 7212 121 2 1532 4-133 1 132 2 -243 2 243 2-15 422A dataB. dataC data图图6稀疏拒阵稀疏拒阵N Bc及对应的三元蛆表及对应的三元蛆表由矩阵乘法规则知：ftC(i, j)=A(i,1) X B(1,j)+A(i,2) X B(2,j)+ +A(i,n) XBrow012B.data的position col位置col列元素在B.data中的位置。4(4)逆矩阵L判断矩阵是否为方阵2

3、.逆矩阵的算法：1求行列式的值2求矩阵的伴随矩阵3用伴随矩阵除以行列式3.求逆矩阵的流程：带入矩阵除以行列式，求出逆矩阵5四、源程序(测试结果)#include#include#include#includeusing namespace std;#define max 100#define datatype inttypedef structint row,col;/行，歹Udatatype v;/非0数值Node;typedef structNode datamax;/稀疏矩阵int m,n,t;/m行，n列，t非0数个数Matrix;/*求逆矩阵存储*/typedef struct /存

4、储结构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+j void Out(nMatrix a) /求逆输出int m = a.m, n = a.n;int i, j;double *p = a.p;f

5、or (i = 0; i m; p += n, i+)for (j = 0; j n; j+)coutp亦t;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;6return input;ostream& operator (ostream& output,Matrix &A) int i,j,t=1,k=0;for(i=1;i=A.m;i+)fo

6、r(j=1;j=A.n;j+)if(A.datat.row=i&A.datat.col=j)outputA.datat.vt;t+;elseoutputkt;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.r

7、owB.dataj.row)C.datak=B.dataj;j+;k+;elseif(A.datai.colB.dataj.col)C.datak=B.dataj; j+;k+;else(if(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+;7while(iA.t)(C.datak=A.datai;i+;k+;while(jB.t)(C.datak=B.dataj;j+;k+;C.t=k;return C;Matrix

8、 operator -(Matrix 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.

9、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+;8while(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)

10、(for(k=1;k=B.m;k+)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.c

11、ol;9ctempccol=ctempccol+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;elsecout这两个矩阵不能相乘;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(

12、col=1;col=A.n;col+)numcol=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)( /求逆矩阵的先

13、转置nMatrix trs;trs.m = a.n;trs.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歹U元素的代数余子式nMatrix adj;adj.m=a.m - 1;adj.n=a.n - 1;10adj.p = new dou

14、ble(a.n - 1) * (a.n - 1);for (int 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 =

15、 a.pm * a.n + j;for (int k = indexn + 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;else(for (int i = 0; i a.n; i+)i oif (i % 2 = 0)det += a

16、.pi * a.n * Det(Adjunct(a, i, 0); elsedet -= a.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

17、; i temp.m; i+)(for (int j = 0; j A; couta=nB; coutb=nB;C=A+B;couta+b=nC;C=A-B;couta-b=nC;C=A*B;couta*b=nC;C=A;cout”a=nC;In(a);cout矩阵的行列式为:endl;coutDet(a)endl;cout矩阵的逆为:endl;temp=!a;cout!a=nTrsendl;1 1五、测试请输入行数：2请输入列数：2请输入非0值个数 请输入行数，列数，：2非0值：(1)1 1 1请输入行数，列数， 非0值:(2)1 2 1a=1100请输入行数：2请输入列数：2请输入非0值个

18、数请输入行数，列数，：2非0值:(1)2 2 1请输入行数，列数， 非0值:(2)2 1 2b=0001a+b=1101a-b=1101a*b=0100a=1010请将稀疏矩阵a的行、列数再次输入：22请按行优先输入稀疏矩阵a的全部数值：1 10 0矩阵的行列式为：-1矩阵的逆为：!a=1010Press any key to continue六、总结这次数据结构课程设计的制作使我对数据结构和C语言的理解更加深刻，也使我认识到了自己很多不足之处。我发现自己在处理稍微具体的程序时显得无从下手，以前学习的知识只是理论性的知识，并 没有真正实践过，当我通过网上查询、 请教学生老师、 复习知识后才对编写程序有了初步的思路。后来编写程序时也碰到了许多错误，我对于指针的掌