数据构造课程方案之稀疏矩阵实现与应用.docx

《数据构造课程方案之稀疏矩阵实现与应用.docx》由会员分享，可在线阅读，更多相关《数据构造课程方案之稀疏矩阵实现与应用.docx（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据构造课程方案之稀疏矩阵实现与应用当前位置：文档视界数据构造课程方案之稀疏矩阵实现与应用数据构造课程方案之稀疏矩阵实现与应用3.输入输出1设计函数建立稀疏矩阵，初始化值.2设计函数输出稀疏矩阵地值.3构造函数进行两个稀疏矩阵相加，输出最终地稀疏矩阵.4构造函数进行两个稀疏矩阵地相乘，输出最终地稀疏矩阵.5构造函数进行稀疏矩阵地转置，并输出结果.6退出系统.二、概要设计1.设计思路：本实验要求在三元组，十字链表下实现稀疏矩阵地加、转、乘.首先要进行矩阵地初始化操作，定义三元组和十字链表地元素对象.写出转置，加法，乘法地操作函数.通过主函数调用实如今一个程序下进行矩阵地运算操作.2.数据构造设计

2、：抽象数据类型稀疏矩阵地定义如下：ADTSparseMatrix数据对象：D=aij|i=1,2,m;j=1,2,.,n;aijElemset,m和n分别称为矩阵地行数和列数.数据关系：R=Row,ColRow=|1|12稀疏矩阵模块实现矩阵地相加boolAddSMatrix()；实现矩阵地相乘boolMultSMatrix()；实验矩阵地转置boolTransposeSMatrix()；3十字链表模块创立十字链表boolCreateSMatrix_OL(CrossList&M)；输出十字链表boolOutPutSMatrix_OL(CrossListT)；(4)主程序模块稀疏矩阵模块十字链表

3、模块三、具体设计1.定义程序中所有用到地数据及其数据构造，及其基本操作地实现；typedefstructinti,j;inte;Triple;/定义三元组地元素typedefstructTripledataMAXSIZE+1;intmu,nu,tu;TSMatrix;/定义普通三元组对象typedefstructTripledataMAXSIZE+2;intrposMAXROW+1;intmu,nu,tu;RLSMatrix;/定义带链接信息地三元组对象typedefstructOLNode/定义十字链表元素inti,j;inte;structOLNode*right,*down;/该非零元所

4、在行表和列表地后继元素OLNode,*OLink;/定义十字链表元素typedefstruct/定义十字链表对象构造体OLink*rhead,*chead;intmu,nu,tu;/系数矩阵地行数，列数，和非零元素个数CrossList;/定义十字链表对象构造体2主函数intmain()intt;cout.fill(*);coutt;switch(t)case1:TransposeSMatrix();/调用矩阵转置函数break;case2:AddSMatrix();/调用矩阵相加函数break;case3:MultSMatrix();/调用矩阵相乘函数break;case4:t=0;brea

5、k;return0;矩阵地转置函数boolTransposeSMatrix()/求矩阵地转置矩阵TSMatrixM,T;/定义预转置地矩阵InPutTSMatrix(M,0);/输入矩阵intnumMAXROW+1;intcpotMAXROW+1;/构建辅助数组intq,p,t;T.tu=M.tu;T.mu=M.nu;T.nu=M.mu;if(T.tu)for(intcol=1;col当前位置：文档视界数据构造课程方案之稀疏矩阵实现与应用数据构造课程方案之稀疏矩阵实现与应用if(+Q.tuMAXSIZE)returnfalse;Q.dataQ.tu.e=ctempccol;Q.dataQ.tu

6、.i=arow;Q.dataQ.tu.j=ccol;OutPutSMatrix(Q);returntrue;矩阵地加法函数boolAddSMatrix()/矩阵地加法CrossListM,N;/创立两个十字链表对象，并初始化CreateSMatrix_OL(M);CreateSMatrix_OL(N);coute=pb-e;p-i=pb-i;p-j=pb-j;if(NULL=pa|pa-jpb-j)/当M此行已经检查完或者pb因该放在pa前面if(NULL=pre)M.rheadp-i=p;elsepre-right=p;p-right=pa;pre=p;if(NULL=M.cheadp-j)

7、/进行列插入M.cheadp-j=p;p-down=NULL;elsep-down=hlp-j-down;hlp-j-down=p;hlp-j=p;pb=pb-right;elseif(NULL!=pa)&pa-jj)/假如此时地pb元素因该放在pa后面，则取以后地pa再来比拟pre=pa;pa=pa-right;elseif(pa-j=pb-j)/假如pa，pb位于同一个位置上，则将值相加pa-e+=pb-e;if(!pa-e)/假如相加后地和为0，则删除此节点，同时改变此元素坐在行，列地前驱元素地相应值if(NULL=pre)/修改行前驱元素值M.rheadpa-i=pa-right;el

8、sepre-right=pa-right;p=pa;pa=pa-right;if(M.cheadp-j=p)M.cheadp-j=hlp-j=p-down;/修改列前驱元素值elsehlp-j-down=p-down;free(p);pb=pb-right;elsepa=pa-right;pb=pb-right;OutPutSMatrix_OL(M);returntrue;创立十字链表boolCreateSMatrix_OL(CrossList&M)/创立十字链表intx,y,m;coutM.muM.nuM.tu;if(!(M.rhead=(OLink*)malloc(M.mu+1)*size

9、of(OLink)exit(0);if(!(M.chead=(OLink*)malloc(M.nu+1)*sizeof(OLink)exit(0);for(x=0;xxym;/按任意顺序输入非零元，普通三元组形式输入OLinkp,q;if(!(p=(OLink)malloc(sizeof(OLNode)exit(0);/开拓新节点，用来存储输入地新元素p-i=x;p-j=y;p-e=m;if(M.rheadx=NULL|M.rheadx-jy)p-right=M.rheadx;M.rheadx=p;elsefor(q=M.rheadx;(q-right)&(q-right-jright);/查

10、找节点在行表中地插入位置p-right=q-right;q-right=p;/完成行插入if(M.cheady=NULL|M.cheady-ix)p-down=M.cheady;M.cheady=p;elsefor(q=M.cheady;(q-down)&(q-down-idown);/查找节点在列表中地插入位置p-down=q-down;q-down=p;/完成列插入returntrue;十字链表地输出boolOutPutSMatrix_OL(CrossListT)/输出十字链表，用普通数组形式输出for(inti=1;ij)coute;p=p-right;elsecout当前位置：文档视界数据构造课程方案之稀疏矩阵实现与应用数据构造课程方案之稀疏矩阵实现与应用