《数据构造课程设计之稀疏矩阵实现与应用1.docx》由会员分享，可在线阅读，更多相关《数据构造课程设计之稀疏矩阵实现与应用1.docx（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据构造课程设计之稀疏矩阵实现与应用1当前位置：文档视界数据构造课程设计之稀疏矩阵实现与应用1数据构造课程设计之稀疏矩阵实现与应用1一、需求分析1.问题描绘：要求：十字链表下的稀疏矩阵的加、转、乘的实现。2.基本功能实现十字链表下的转置，乘法，加法运算。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|11主程序模块：Voidmain初始化；do接授命令；处理命令；while“命令=“退出；2稀疏矩阵模块实现矩阵的相加boolAddSMatrix()；实现矩阵的相乘boolMultSMatrix()；实验矩阵的转置boolTransposeSMatri
3、x()；3十字链表模块创立十字链表boolCreateSMatrix_OL(CrossList&M)；输出十字链表boolOutPutSMatrix_OL(CrossListT)；(4)主程序模块稀疏矩阵模块十字链表模块三、具体设计1.定义程序中所有用到的数据及其数据构造，及其基本操作的实现；typedefstructinti,j;inte;Triple;/定义三元组的元素typedefstructTripledataMAXSIZE+1;intmu,nu,tu;TSMatrix;/定义普通三元组对象typedefstructTripledataMAXSIZE+2;intrposMAXROW+1
4、;intmu,nu,tu;RLSMatrix;/定义带链接信息的三元组对象typedefstructOLNode/定义十字链表元素inti,j;inte;structOLNode*right,*down;/该非零元所在行表和列表的后继元素OLNode,*OLink;/定义十字链表元素typedefstruct/定义十字链表对象构造体OLink*rhead,*chead;intmu,nu,tu;/系数矩阵的行数，列数，和非零元素个数CrossList;/定义十字链表对象构造体2主函数intmain()intt;cout.fill(*);coutt;switch(t)case1:Transpose
5、SMatrix();/调用矩阵转置函数break;case2:AddSMatrix();/调用矩阵相加函数break;case3:MultSMatrix();/调用矩阵相乘函数break;case4:t=0;break;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;c
6、ol当前位置：文档视界数据构造课程设计之稀疏矩阵实现与应用1数据构造课程设计之稀疏矩阵实现与应用1ctempccol+=M.datap.e*N.dataq.e;/将乘得到对应值放在相应的元素累加器里面for(ccol=1;ccolMAXSIZE)returnfalse;Q.dataQ.tu.e=ctempccol;Q.dataQ.tu.i=arow;Q.dataQ.tu.j=ccol;OutPutSMatrix(Q);returntrue;矩阵的加法函数boolAddSMatrix()/矩阵的加法CrossListM,N;/创立两个十字链表对象，并初始化CreateSMatrix_OL(M);
7、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)/进行列插入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后面，则取以后
8、的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;elsepre-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;els
9、epa=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)*sizeof(OLink)exit(0);if(!(M.chead=(OLink*)malloc(M.nu+1)*sizeof(OLink)exit(0);for(x=0;xxym;/按任意顺序输入非零元，普通三元组形式输入OLinkp,q;if(!(p=(OLink)m
10、alloc(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);/查找节点在行表中的插入位置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当前位置：文档视界数据构造课程设计之稀疏矩阵实现与应用1数据构造课程设计之稀疏矩阵实现与应用1