还剩21页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
数据结构课程设计报告题目十字链表成为存储结构,实现稀疏矩阵的求和运算学生姓名:张旋班级:软件三班学号:201213040304 指导教师:吴小平
一、需求分析
1.问题描述要求十字链表下的稀疏矩阵的加、转、乘的实现
2.基本功能实现十字链表下的转置,乘法,加法运算
3.输入输出
(1)设计函数建立稀疏矩阵,初始化值
(2)设计函数输出稀疏矩阵的值
(3)构造函数进行两个稀疏矩阵相加,输出最终的稀疏矩阵
(4)构造函数进行两个稀疏矩阵的相乘,输出最终的稀疏矩阵
(5)构造函数进行稀疏矩阵的转置,并输出结果
(6)退出系统
二、概要设计
1.设计思路本实验要求在三元组,十字链表下实现稀疏矩阵的加、转、乘首先要进行矩阵的初始化操作,定义三元组和十字链表的元素对象写出转置,加法,乘法的操作函数通过主函数调用实现在一个程序下进行矩阵的运算操作
2.数据结构设计抽象数据类型稀疏矩阵的定义如下ADTSparseMatrix{ 数据对象D={aij|i=12…m;j=
12..n;aij∈Elemsetm和n分别称为矩阵的行数和列数} 数据关系R={RowCol} Row={aijaij+1|1=i=m1=j=n-1}Col={aijai+1j|1=i=m-11=j=n}基本操作 CreateSMatrixM; 操作结果创建稀疏矩阵M DestroySMatrixM; 初始条件稀疏矩阵M存在操作结果销毁稀疏矩阵M PrintSMatrixM; 初始条件稀疏矩阵M存在操作结果输出稀疏矩阵M AddSMatrixM,N,Q; 初始条件稀疏矩阵M与N的行数和列数对应相等操作结果求稀疏矩阵的和Q=M+N MultSMatrixM,N,&Q; 初始条件稀疏矩阵M的列数等于N的行数操作结果求稀疏矩阵乘积Q=M*N TransposeSMatrixM,&T; 初始条件稀疏矩阵M存在操作结果求稀疏矩阵M的转置矩阵T }ADTSparseMatrix
3.软件结构设计
(1)主程序模块Voidmain(){初始化;do{接受命令;处理命令;}while(“命令”=“退出”);}
(2)稀疏矩阵模块{实现矩阵的相加boolAddSMatrix;实现矩阵的相乘boolMultSMatrix;实验矩阵的转置boolTransposeSMatrix;}
(3)十字链表模块{创建十字链表boolCreateSMatrix_OLCrossListM;输出十字链表boolOutPutSMatrix_OLCrossListT;}4主程序模块稀疏矩阵模块十字链表模块
三、详细设计
1.定义程序中所有用到的数据及其数据结构,及其基本操作的实现;typedefstruct{intij;inte;}Triple;//定义三元组的元素typedefstruct{Tripledata[MAXSIZE+1];intmunutu;}TSMatrix;//定义普通三元组对象typedefstruct{Tripledata[MAXSIZE+2];intrpos[MAXROW+1];intmunutu;}RLSMatrix;//定义带链接信息的三元组对象typedefstructOLNode{//定义十字链表元素intij;inte;structOLNode*right*down;//该非零元所在行表和列表的后继元素}OLNode*OLink;//定义十字链表元素typedefstruct{//定义十字链表对象结构体OLink*rhead*chead;intmunutu;//系数矩阵的行数,列数,和非零元素个数}CrossList;//定义十字链表对象结构体2.主函数intmain{intt;cout.fill*;coutsetw80*;cout.fill;coutsetw50***欢迎使用矩阵运算程序***endl;//输出头菜单cout.fill*;coutsetw80*;cout.fill;cout请选择要进行的操作endl;cout1:矩阵的转置endl;cout2:矩阵的加法endl;cout3:矩阵的乘法endl;cout4:退出程序endl;whilet{cout请输入您要进行的操作endl;cint;switcht{case1:TransposeSMatrix;//调用矩阵转置函数break;case2:AddSMatrix;//调用矩阵相加函数break;case3:MultSMatrix;//调用矩阵相乘函数break;case4:t=0;break;}}return0;}矩阵的转置函数boolTransposeSMatrix//求矩阵的转置矩阵{TSMatrixMT;//定义预转置的矩阵InPutTSMatrixM0;//输入矩阵intnum[MAXROW+1];intcpot[MAXROW+1];//构建辅助数组intqpt;T.tu=M.tu;T.mu=M.nu;T.nu=M.mu;ifT.tu{forintcol=1;col=M.nu;col++num[col]=0;fort=1;t=M.tu;t++++num[M.data[t].j];cpot
[1]=1;forinti=2;i=M.nu;i++cpot[i]=cpot[i-1]+num[i-1];//求出每一列中非零元素在三元组中出现的位置forp=1;p=M.tu;p++{intcol=M.data[p].j;q=cpot[col];T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;++cpot[col];}}cout输入矩阵的转置矩阵为endl;OutPutSMatrixT;returntrue;}boolCountRLSMatrixT{intnum[MAXROW+1];forintrow=1;row=T.mu;row++num[row]=0;forintcol=1;col=T.tu;col++++num[T.data[col].i];T.rpos
[1]=1;forinti=2;i=T.mu;i++T.rpos[i]=T.rpos[i-1]+num[i-1];//求取每一行中非零元素在三元组中出现的位置returntrue;}矩阵的乘法函数boolMultSMatrix//两个矩阵相乘{RLSMatrixMNQ;//构建三个带“链接信息”的三元组表示的数组InPutTSMatrixM1;//用普通三元组形式输入数组InPutTSMatrixN1;CountM;CountN;cout输入的两矩阵的乘矩阵为endl;ifM.nu!=N.mureturnfalse;Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;//Q初始化intctemp[MAXROW+1];//辅助数组intarowtppbrowtqccol;ifM.tu*N.tu//Q是非零矩阵{forarow=1;arow=M.mu;arow++{///memsetctemp0N.nu;forintx=1;x=N.nu;x++//当前行各元素累加器清零ctemp[x]=0;Q.rpos[arow]=Q.tu+1;//当前行的首个非零元素在三元组中的位置为此行前所有非零元素+1ifarowM.mutp=M.rpos[arow+1];elsetp=M.tu+1;forp=M.rpos[arow];ptp;p++//对当前行每个非零元素进行操作{brow=M.data[p].j;//在N中找到i值也操作元素的j值相等的行ifbrowN.mut=N.rpos[brow+1];elset=N.tu+1;forq=N.rpos[brow];qt;q++//对找出的行当每个非零元素进行操作{ccol=N.data[q].j;ctemp[ccol]+=M.data[p].e*N.data[q].e;//将乘得到对应值放在相应的元素累加器里面}}forccol=1;ccol=Q.nu;ccol++//对已经求出的累加器中的值压缩到Q中ifctemp[ccol]{if++Q.tuMAXSIZEreturnfalse;Q.data[Q.tu].e=ctemp[ccol];Q.data[Q.tu].i=arow;Q.data[Q.tu].j=ccol;}}}OutPutSMatrixQ;returntrue;}矩阵的加法函数boolAddSMatrix//矩阵的加法{CrossListMN;//创建两个十字链表对象,并初始化CreateSMatrix_OLM;CreateSMatrix_OLN;cout输入的两矩阵的和矩阵为endl;OLinkpapbprehl[MAXROW+1];//定义辅助指针,pa,pb分别为MN当前比较的元素,pre为pa的前驱元素forintx=1;x=M.nu;x++hl[x]=M.chead[x];forintk=1;k=M.mu;k++//对M的每一行进行操作{pa=M.rhead[k];pb=N.rhead[k];pre=NULL;whilepb//把N中此行的每个元素取出{OLinkp;if!p=OLinkmallocsizeofOLNodeexit0;//开辟新节点,存储N中取出的元素p-e=pb-e;p-i=pb-i;p-j=pb-j;ifNULL==pa||pa-jpb-j//当M此行已经检查完或者pb因该放在pa前面{ifNULL==preM.rhead[p-i]=p;elsepre-right=p;p-right=pa;pre=p;ifNULL==M.chead[p-j]//进行列插入{M.chead[p-j]=p;p-down=NULL;}else{p-down=hl[p-j]-down;hl[p-j]-down=p;}hl[p-j]=p;pb=pb-right;}elseifNULL!=papa-jpb-j//如果此时的pb元素因该放在pa后面,则取以后的pa再来比较{pre=pa;pa=pa-right;}elseifpa-j==pb-j//如果pa,pb位于同一个位置上,则将值相加{pa-e+=pb-e;if!pa-e{//如果相加后的和为0,则删除此节点,同时改变此元素坐在行,列的前驱元素的相应值ifNULL==pre//修改行前驱元素值M.rhead[pa-i]=pa-right;elsepre-right=pa-right;p=pa;pa=pa-right;ifM.chead[p-j]==pM.chead[p-j]=hl[p-j]=p-down;//修改列前驱元素值elsehl[p-j]-down=p-down;freep;pb=pb-right;}else{pa=pa-right;pb=pb-right;}}}}OutPutSMatrix_OLM;returntrue;}创建十字链表boolCreateSMatrix_OLCrossListM//创建十字链表{intxym;cout请输入矩阵的行,列,及非零元素个数endl;cinM.muM.nuM.tu;if!M.rhead=OLink*mallocM.mu+1*sizeofOLinkexit0;if!M.chead=OLink*mallocM.nu+1*sizeofOLinkexit0;forx=0;x=M.mu;x++M.rhead[x]=NULL;//初始化各行,列头指针,分别为NULLforx=0;x=M.nu;x++M.chead[x]=NULL;cout请按三元组的格式输入数组endl;forinti=1;i=M.tu;i++{cinxym;//按任意顺序输入非零元,(普通三元组形式输入)OLinkpq;if!p=OLinkmallocsizeofOLNodeexit0;//开辟新节点,用来存储输入的新元素p-i=x;p-j=y;p-e=m;ifM.rhead[x]==NULL||M.rhead[x]-jy{p-right=M.rhead[x];M.rhead[x]=p;}else{forq=M.rhead[x];q-rightq-right-jy;q=q-right;//查找节点在行表中的插入位置p-right=q-right;q-right=p;//完成行插入}ifM.chead[y]==NULL||M.chead[y]-ix{p-down=M.chead[y];M.chead[y]=p;}else{forq=M.chead[y];q-downq-down-ix;q=q-down;//查找节点在列表中的插入位置p-down=q-down;q-down=p;//完成列插入}}returntrue;}十字链表的输出boolOutPutSMatrix_OLCrossListT//输出十字链表,用普通数组形式输出{forinti=1;i=T.mu;i++{OLinkp=T.rhead[i];forintj=1;j=T.nu;j++{ifpj==p-j{coutsetw3p-e;p=p-right;}elsecoutsetw30;}coutendl;}returntrue;}
3.主要函数的程序流程图,实现设计中主程序和其他子模块的算法,以流程图的形式表示矩阵的相加流程图矩阵的相乘流程图#0;开始CrossListMN;CreateSMatrix_OLM;CreateSMatrix_OLN;对应位置相加输出结果结束开始RLSMatrixMNQ;InPutTSMatrixM1;InPutTSMatrixN1;intctemp[MAXROW+1];intarowtppbrowtqccol;Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;实现矩阵的相乘结束矩阵转置的流程图主函数流程图#0;#0;#0;开始TSMatrixMT;InPutTSMatrixM0;intnum[MAXROW+1];intcpot[MAXROW+1];T.tu=M.tu;T.mu=M.nu;T.nu=M.mu;T.tu实现转置OutPutSMatrixT结束是否开始输出界面inti;输入iiTransposeSMatrix;AddSMatrix;MultSMatrix;结束
4.画出函数之间的调用关系图MainAddSMatrixTransposeSMatrixMultSMatrixCreateSMatrix_OLInPutTSMatrixOutPutSMatrixInPutTSMatrixOutPutSMatrix_OL
4、调试分析
1.实际完成的情况说明(完成的功能,支持的数据类型等);完成了稀疏矩阵的建立,初始化及输出值的操作实现三元组,十字链表下的稀疏矩阵的加法,乘法以及转置运算
2.程序的性能分析,包括时空分析;能应对一般小的错误输入,如果复杂则自动退出程序
3.上机过程中出现的问题及其解决方案;
1.起始有错误设定的变量名相同经检查,改正2.一些逻辑错误经讨论改正运行出现部分语法错误修正
4.程序中可以改进的地方说明;程序在运行中一旦出现矩阵数据格式错误如输入汉字,则程序自动退出需要重新启动更新程序对更多错误输入情况的分析能力
5.程序中可以扩充的功能及设计实现假想对退出操作的扩充在主菜单下,用户输入4回车选择退出程序是,询问是否真的退出系统,如果是,则即退出系统,否则显示……continue……并且返回主菜单为了方便由于误按导致程序退出在退出时可以增加一段感谢使用本程序的结束语
五、测试结果系统运行主界面输入需要执行的操作1矩阵的转置输入需要执行的操作2矩阵的加法输入需要执行的操作3矩阵的乘法输入错误操作时需要重新选择退出操作
六、用户手册
1.本程序执行文件为crosslist.exe2.进入本系统之后,随即显示系统主菜单界面用户可在该界面下输入各子菜单前对应的数字并按回车,执行相应子菜单命令3.执行操作时,按要求输入数字彼此之间用空格隔开4.执行加法运算时,输入的两个矩阵的行必须相同,列数也必须相同这是基本的矩阵运算常识
5.执行乘法运算时,第一个矩阵的行数和第二个矩阵的列数相同
6.当输入错误时请尝试退出程序重新运行请尽量遵守矩阵运算的规则输入有效的运算
七、体会与自我评价 我选的上机题目是实现三元组,十字链表下的转置,乘法,加法运算对这个题目,我觉得有点难,因为我们数据结构这一部分并没有讲,可是选题必须是每人选择一个不许选重有点无奈吧,当作是考验了各种资料收集,各种代码整合各种错误虽然上机的时间只有短短两个星期,但从中学到了不少知识数据结构可以说是计算机里一门基础课程,对于以后的学习尤为重要所以我们一定要把基础学扎实,这两周的上机帮我们重新巩固基础知识,提高了我们专业的动手实践能力在实践的过程中我们应当有良好的规划,每天完成一小部分尽量减少操作的盲目性,提高我们学习的效率有个总体的大纲来逐步实现我也曾经犯过这种错误每个函数都做出来部分结果都没做完所以计划很重要在实验中我们要培养自己独立的思考能力和解决问题的能力培养这种能力主要看我们对待这次实验的态度我们要把它当作以后工作时接的项目一样认真对待积极的朝着更好地一面发展不断的完善程序不能马马虎虎随便应付一下通过这次实验我也认识到了数据结构这门课程的重要性,以及C语言功能的强大它可以令计算机执行各种你想要的操作当然前提是你的技术水平使我深刻的认识到要学好数据结构这门课程,为了以后打好坚实的基础提高自己的动手实践能力,把所学的理论知识和实践相结合就像古人云,纸上得来终觉浅,得知此事要躬行为了以后的计算机道路不断的提高自身的专业素养奋斗也希望在今后的学习生活中向老师学到更多的知识不断的充实自己努力改正自己的坏毛病,做个奋发向上的大学生源代码#includeiostream#includeiomanipusingnamespacestd;constintMAXSIZE=100;//定义非零元素的对多个数constintMAXROW=10;//定义数组的行数的最大值typedefstruct{intij;inte;}Triple;//定义三元组的元素typedefstruct{Tripledata[MAXSIZE+1];intmunutu;}TSMatrix;//定义普通三元组对象typedefstruct{Tripledata[MAXSIZE+2];intrpos[MAXROW+1];intmunutu;}RLSMatrix;//定义带链接信息的三元组对象typedefstructOLNode{//定义十字链表元素intij;inte;structOLNode*right*down;//该非零元所在行表和列表的后继元素}OLNode*OLink;//定义十字链表元素typedefstruct{//定义十字链表对象结构体OLink*rhead*chead;intmunutu;//系数矩阵的行数,列数,和非零元素个数}CrossList;//定义十字链表对象结构体templateclassPboolInPutTSMatrixPTinty{//输入矩阵,按三元组格式输入cout输入矩阵的行,列和非零元素个数:endl;cinT.muT.nuT.tu;cout请输出非零元素的位置和值:endl;forintk=1;k=T.tu;k++cinT.data[k].iT.data[k].jT.data[k].e;returntrue;}templateclassPboolOutPutSMatrixPT{intmnk=1;form=0;mT.mu;m++{forn=0;nT.nu;n++{ifT.data[k].i-1==mT.data[k].j-1==n{cout.width4;coutT.data[k++].e;}else{cout.width4;cout0;}}coutendl;}returntrue;}//输出矩阵,按标准格式输出boolTransposeSMatrix//求矩阵的转置矩阵{TSMatrixMT;//定义预转置的矩阵InPutTSMatrixM0;//输入矩阵intnum[MAXROW+1];intcpot[MAXROW+1];//构建辅助数组intqpt;T.tu=M.tu;T.mu=M.nu;T.nu=M.mu;ifT.tu{forintcol=1;col=M.nu;col++num[col]=0;fort=1;t=M.tu;t++++num[M.data[t].j];cpot
[1]=1;forinti=2;i=M.nu;i++cpot[i]=cpot[i-1]+num[i-1];//求出每一列中非零元素在三元组中出现的位置forp=1;p=M.tu;p++{intcol=M.data[p].j;q=cpot[col];T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;++cpot[col];}}cout输入矩阵的转置矩阵为endl;OutPutSMatrixT;returntrue;}boolCountRLSMatrixT{intnum[MAXROW+1];forintrow=1;row=T.mu;row++num[row]=0;forintcol=1;col=T.tu;col++++num[T.data[col].i];T.rpos
[1]=1;forinti=2;i=T.mu;i++T.rpos[i]=T.rpos[i-1]+num[i-1];//求取每一行中非零元素在三元组中出现的位置returntrue;}boolMultSMatrix//两个矩阵相乘{RLSMatrixMNQ;//构建三个带“链接信息”的三元组表示的数组InPutTSMatrixM1;//用普通三元组形式输入数组InPutTSMatrixN1;CountM;CountN;cout输入的两矩阵的乘矩阵为endl;ifM.nu!=N.mureturnfalse;Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;//Q初始化intctemp[MAXROW+1];//辅助数组intarowtppbrowtqccol;ifM.tu*N.tu//Q是非零矩阵{forarow=1;arow=M.mu;arow++{///memsetctemp0N.nu;forintx=1;x=N.nu;x++//当前行各元素累加器清零ctemp[x]=0;Q.rpos[arow]=Q.tu+1;//当前行的首个非零元素在三元组中的位置为此行前所有非零元素+1ifarowM.mutp=M.rpos[arow+1];elsetp=M.tu+1;forp=M.rpos[arow];ptp;p++//对当前行每个非零元素进行操作{brow=M.data[p].j;//在N中找到i值也操作元素的j值相等的行ifbrowN.mut=N.rpos[brow+1];elset=N.tu+1;forq=N.rpos[brow];qt;q++//对找出的行当每个非零元素进行操作{ccol=N.data[q].j;ctemp[ccol]+=M.data[p].e*N.data[q].e;//将乘得到对应值放在相应的元素累加器里面}}forccol=1;ccol=Q.nu;ccol++//对已经求出的累加器中的值压缩到Q中ifctemp[ccol]{if++Q.tuMAXSIZEreturnfalse;Q.data[Q.tu].e=ctemp[ccol];Q.data[Q.tu].i=arow;Q.data[Q.tu].j=ccol;}}}OutPutSMatrixQ;returntrue;}boolCreateSMatrix_OLCrossListM//创建十字链表{intxym;cout请输入矩阵的行,列,及非零元素个数endl;cinM.muM.nuM.tu;if!M.rhead=OLink*mallocM.mu+1*sizeofOLinkexit0;if!M.chead=OLink*mallocM.nu+1*sizeofOLinkexit0;forx=0;x=M.mu;x++M.rhead[x]=NULL;//初始化各行,列头指针,分别为NULLforx=0;x=M.nu;x++M.chead[x]=NULL;cout请按三元组的格式输入数组endl;forinti=1;i=M.tu;i++{cinxym;//按任意顺序输入非零元,(普通三元组形式输入)OLinkpq;if!p=OLinkmallocsizeofOLNodeexit0;//开辟新节点,用来存储输入的新元素p-i=x;p-j=y;p-e=m;ifM.rhead[x]==NULL||M.rhead[x]-jy{p-right=M.rhead[x];M.rhead[x]=p;}else{forq=M.rhead[x];q-rightq-right-jy;q=q-right;//查找节点在行表中的插入位置p-right=q-right;q-right=p;//完成行插入}ifM.chead[y]==NULL||M.chead[y]-ix{p-down=M.chead[y];M.chead[y]=p;}else{forq=M.chead[y];q-downq-down-ix;q=q-down;//查找节点在列表中的插入位置p-down=q-down;q-down=p;//完成列插入}}returntrue;}boolOutPutSMatrix_OLCrossListT//输出十字链表,用普通数组形式输出{forinti=1;i=T.mu;i++{OLinkp=T.rhead[i];forintj=1;j=T.nu;j++{ifpj==p-j{coutsetw3p-e;p=p-right;}elsecoutsetw30;}coutendl;}returntrue;}boolAddSMatrix//矩阵的加法{CrossListMN;//创建两个十字链表对象,并初始化CreateSMatrix_OLM;CreateSMatrix_OLN;cout输入的两矩阵的和矩阵为endl;OLinkpapbprehl[MAXROW+1];//定义辅助指针,pa,pb分别为MN当前比较的元素,pre为pa的前驱元素forintx=1;x=M.nu;x++hl[x]=M.chead[x];forintk=1;k=M.mu;k++//对M的每一行进行操作{pa=M.rhead[k];pb=N.rhead[k];pre=NULL;whilepb//把N中此行的每个元素取出{OLinkp;if!p=OLinkmallocsizeofOLNodeexit0;//开辟新节点,存储N中取出的元素p-e=pb-e;p-i=pb-i;p-j=pb-j;ifNULL==pa||pa-jpb-j//当M此行已经检查完或者pb因该放在pa前面{ifNULL==preM.rhead[p-i]=p;elsepre-right=p;p-right=pa;pre=p;ifNULL==M.chead[p-j]//进行列插入{M.chead[p-j]=p;p-down=NULL;}else{p-down=hl[p-j]-down;hl[p-j]-down=p;}hl[p-j]=p;pb=pb-right;}elseifNULL!=papa-jpb-j//如果此时的pb元素因该放在pa后面,则取以后的pa再来比较{pre=pa;pa=pa-right;}elseifpa-j==pb-j//如果pa,pb位于同一个位置上,则将值相加{pa-e+=pb-e;if!pa-e{//如果相加后的和为0,则删除此节点,同时改变此元素坐在行,列的前驱元素的相应值ifNULL==pre//修改行前驱元素值M.rhead[pa-i]=pa-right;elsepre-right=pa-right;p=pa;pa=pa-right;ifM.chead[p-j]==pM.chead[p-j]=hl[p-j]=p-down;//修改列前驱元素值elsehl[p-j]-down=p-down;freep;pb=pb-right;}else{pa=pa-right;pb=pb-right;}}}}OutPutSMatrix_OLM;returntrue;}intmain{intt;cout.fill*;coutsetw80*;cout.fill;coutsetw50***欢迎使用矩阵运算程序***endl;//输出头菜单cout.fill*;coutsetw80*;cout.fill;cout请选择要进行的操作endl;cout1:矩阵的转置endl;cout2:矩阵的加法endl;cout3:矩阵的乘法endl;cout4:退出程序endl;whilet{cout请输入您要进行的操作endl;cint;switcht{case1:TransposeSMatrix;//调用矩阵转置函数break;case2:AddSMatrix;//调用矩阵相加函数break;case3:MultSMatrix;//调用矩阵相乘函数break;case4:t=0;break;}}return0;}。