《稀疏矩阵应用..docx》由会员分享，可在线阅读，更多相关《稀疏矩阵应用..docx（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、稀疏矩阵应用.稀疏矩阵应用课题简介1.1课题及要求稀疏矩阵应用限1人完成设计要求：实现三元组，十字链表下的稀疏矩阵的加、转、乘的实现。1稀疏矩阵的存储2稀疏矩阵加法3矩阵乘法4矩阵转置1.2课程任务分析本课程设计主要实如今三元组存储构造与十字链表存储构造下输入稀疏矩阵，并对稀疏矩阵进行转置，相加，相乘操作，最后输出运算后的结果。稀疏矩阵采用三元组和十字链表表示，并在两种不同的存储构造下，求两个具有一样行列数的稀疏矩阵A和B的相加矩阵C，并输出C；求出A的转置矩阵D，输出D；求两个稀疏矩阵A和B的相乘矩阵E，并输出E。1.3课程的意义其意义是让我们在学习完C、数据构造等课程基础上，把握多维数组的
2、逻辑构造和存储构造、把握稀疏矩阵的压缩存储及转置，相加，相乘等基本操作，并用不同的方法输出结果，进一步把握设计、实现较大系统的完好经过，包括系统分析、编码设计、系统集成、以及调试分析，熟练把握数据构造的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。程序分析2.1设计函数建立稀疏矩阵及初始化值和输出稀疏矩阵的值本模块要求设计函数建立稀疏矩阵并初始化，包括在三元组构造下和十字链表构造下。首先要定义两种不同的构造体类型，在创立稀疏矩阵时，需要设计两个不同的函数分别在三元组和十字链表下创立稀疏矩阵，在输入出现错误时，能够对错误进行判别处理，初始化稀疏矩阵都为空值，十分注意在十字链表下，对变
3、量进行动态的地址分配。在设计输出稀疏矩阵的值的函数时，也要针对两种不同的情况，分别编制函数，才能准确的输出稀疏矩阵。在对稀疏矩阵进行初始化及输出值时，均只输出非零元素的值和它所在的所在行及所在列。2.2构造函数进行稀疏矩阵的转置并输出结果本模块要求设计函数进行稀疏矩阵的转置并输出转置后的结果，由于对稀疏函数的转置只对一个矩阵进行操作，所以实现起来难度不是很大，函数也比拟容易编写。在编写函数时，要先定义一个相应的构造体变量用于存放转置后的矩阵，最后把此矩阵输出。2.3构造函数进行两个稀疏矩阵相加及相乘并输出最终的稀疏矩阵本模块要求设计相加和相乘函数对两个矩阵进行运算，并输出最终的稀疏矩阵，在进行
4、运算前，要对两个矩阵进行检查，看是不是一样类型的矩阵，由于两个矩阵相加要求两个矩阵一定是同一类型的矩阵，定义相应的矩阵类型用于存放两个矩阵相加相乘后的结果矩阵，这个结果矩阵的行数列数需要综合多方面情况来确定。这四个函数也是整个程序的难点，需要灵敏运用数组及指针的特点。2.4退出系统本模块要求设置选项能随时结束程序的运行，本程序中采用exit(0)函数。程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息之后，由用户在键盘上输入演示程序中需要的相关信息及命令。概要设计3.1主界面设计为了实如今两种存储构造下对稀疏矩阵的多种算法功能的管理，首先设计一含有多个菜单项的主控菜单子程序以链接
5、系统的各项子功能，方便用户交互式使用本系统。本系统主控菜单运行界面如图1所示。图1主界面图3.2存储构造设计本系统采用三元组构造和十字链表构造存储稀疏矩阵的详细信息。其中：在三元组中，所有元素的信息用数组表示，每个数组元素中包含有行下标(i)，列下标(j)和对应的数值(e)，它们是整型数据，全部的信息用在十字链表中，全部结点的信息用构造体TSMatrix包含，包括用数组TripledataMAXSIZE和总共的行数mu,列数nu以及非零元素的个数(tu)。在十字链表下，头结点为指针数组的十字链表存储；每个结点里面包含行下标(i)，列下标(j)和对应的数值(e)，它们是整型数据，还有两个指针(r
6、ight)、(down),属于OLNode构造体。全部的信息用构造体(crosslist)包含，包括指针数组(OLink*rhead和*chead和总共的行数mu,列数nu以及非零元素的个数(tu)。三元组构造体定义:typedefstructinti,j;inte;Triple;typedefstructTripledataMAXSIZE;intrposMAXSIZE+1;intnu,mu,tu;TSMatrix;十字链表构造体定义:typedefstructOLNodeinti,j;inte;structOLNode*right,*down;OLNode,*OLink;typedefstr
7、uctintmu,nu,tu;OLink*rhead,*chead;CrossList;3.3系统功能设计本系统除了要完成分别在三元组存储构造以及在十字链表下实现稀疏矩阵的初始化功能外还设置了4个子功能菜单。稀疏矩阵的建立及初始化在三元组存储构造下，由函数voidCreateSMatrix(TSMatrix&M)实现，在十字链表存储构造下，由函数voidCreateSMatix_OL(CrossList&M)根据读入的行数和列数以及非零元素的个数，分别设定每个非零元素的信息。4个子功能的设计描绘如下。1稀疏矩阵的转置：此功能在三元组存储构造下，由函数voidTransposeSMatrix(T
8、SMatrixM,TSMatrix&T)实现，在十字链表存储构造下，由函数voidTurnSMatrix_OL(CrossList&M)实现。当用户选择该功能，系统提示用户初始化一个矩阵，然后进行转置，最终输出结果。2稀疏矩阵的加法：此功能在三元组存储构造下，由函数voidAddTMatix(TSMatrixM,TSMatrixT,TSMatrix&S)实现，在十字链表存储构造下，由函数intSMatrix_ADD(CrossList*A,CrossList*B)实现。当用户选择该功能，系统即提示用户初始化要进行加法的两个矩阵的信息。然后进行加法，最后输出结果。3稀疏矩阵的乘法：此功能在三元组
9、存储构造下，由函数intMultSMatrix(TSMatrixM,TSMatrixN,TSMatrix&Q)实现。在十字链表存储构造下，由函数intMultSMatrix_OL(CrossListM,CrossListN,CrossList&Q)实现。当用户选择该功能，系统提示输入要进行相乘的两个矩阵的具体信息。然后进行相乘，最后得到结果。4退出：即退出稀疏矩阵的应用系统，由exit(0)函数实现。当用户选择该功能，则退出该稀疏矩阵的应用系统。调试分析4.1系统运行主界面系统运行主界面如图2所示：图2主界面图4.2各子功能测试运行结果以三元组为例1稀疏矩阵的创立及初始化：在主菜单下，用户输入
10、1回车，是用三元组创立稀疏矩阵，根据屏幕提示初始化一个稀疏矩阵，按enter键，运行结果如图3所示。图3三元组创立并初始化矩阵2稀疏矩阵的转置：用三元组创立稀疏矩阵后，用户输入1回车，便显示该矩阵的转置矩阵，运行结果如图4所示。图4三元组稀疏矩阵转置结果示意图3稀疏矩阵的相加：用三元组创立并初始化一个稀疏矩阵后，输入2回车，按屏幕提示输入第二个同类型的稀疏矩阵，按enter键，运行结果如图5所示。图5三元组稀疏矩阵相加结果示意图4稀疏矩阵的相乘：用三元组创立并初始化一个稀疏矩阵后，输入3回车，按屏幕提示输入第二个同类型的稀疏矩阵，按enter键，运行结果如图6所示。阵进行运算，是实现起来有很多
11、困难，主要包括：1、书上这种方面的东西不多，资料少，能够参考的东西不是很多；2、用十字链表进行运算比拟复杂，难度较大，需要对指针把握较好；3、在书写课程设计报告时，没有详细的模板，感觉无从下手。针对上述困难，我通过网络，图书馆找资料，借鉴别人的以往的优秀的课程设计报告，和同学们一起讨论，逐步地解决本人的问题。通过此次课程设计，使我对本学期学的（数据构造）有了更深的了解，也使本人的所学愈加牢固，并能够把更方面的知识综合起来运用。附录：程序源代码#include#include#defineMAXSIZE100intnum100;typedefstructOLNodeinti,j;inte;str
12、uctOLNode*right,*down;OLNode,*OLink;typedefstructintmu,nu,tu;OLink*rhead,*chead;CrossList;/十字链表构造体定义typedefstructinti,j;inte;Triple;typedefstructTripledataMAXSIZE;intrposMAXSIZE+1;intnu,mu,tu;TSMatrix;/三元组构造体定义；intCreateSMatix_OL(CrossList&M)inti,j,e;OLinkq;OLinkp;printf(请输入稀疏矩阵的行数，列数，非零元素的个数:);/矩阵行
13、数，列数下标均从开场；scanf(%d%d%d,&M.mu,&M.nu,M.rhead=(OLink*)malloc(M.mu+1)*sizeof(OLNode);/分配内存空间M.chead=(OLink*)malloc(M.nu+1)*sizeof(OLNode);/分配内存空间for(i=1;ifor(i=1;ii=i;p-j=j;p-e=e;if(M.rheadi=NULL|M.rheadi-jj)p-right=M.rheadi;M.rheadi=p;elseq=M.rheadi;while(q-right&q-right-jright;p-right=q-right;q-right
14、=p;if(M.cheadj=NULL|M.cheadj-ii)p-down=M.cheadj;M.cheadj=p;elseq=M.cheadj;while(q-down&q-down-idown;p-down=q-down;q-down=p;scanf(%d%d%d,&i,return1;/创立十字链表voidCreateSMatrix(TSMatrix&M)/采用三元组顺序表存储表示，创立稀疏矩阵Mprintf(请输入稀疏矩阵的行数、列数和非零元个数：);scanf(%d%d%d,&M.mu,&M.nu,if(M.muM.mu*M.nu)/判定行值、列值、元素个数能否合法printf(输
15、入有误！);for(inti=1;iT.nu=M.mu;/T矩阵存放转置后的矩阵T.mu=M.nu;T.tu=M.tu;intq=1;for(intcol=1;cola2)return1;elseif(a1if(b1T.mu?M.mu:T.mu;/对S矩阵的行数赋值S.nu=M.nuT.nu?M.nu:T.nu;/对S矩阵的列数赋值S.tu=0;intce;intq=1;intmcount=1,tcount=1;while(mcountT.datatcount.i或M.datamcount.jT.datatcount.jS.dataq.i=T.datatcount.i;S.dataq.j=T.
16、datatcount.j;/把第二个矩阵的行数i，列数j赋值给S矩阵的行数i，列数jq+;tcount+;break;case0:ce=M.datamcount.e+T.datatcount.e;/其他情况下把两个矩阵的值相加if(ce)S.dataq.e=ce;S.dataq.i=M.datamcount.i;S.dataq.j=M.datamcount.j;q+;mcount+;tcount+;elsemcount+;break;while(mcountMAXSIZE)return1;Q.dataQ.tu.i=arow,Q.dataQ.tu.j=ccol,Q.dataQ.tu.e=ctem
17、pccol;return1;/三元组相乘voidShowTMatrix(TSMatrixM)for(intcol=1;colfor(intp=1;pi;p-i=p-j;p-j=row;q=p-right;p-right=p-down;p-down=q;/十字链表转置intSMatrix_ADD(CrossList*A,CrossList*B)OLNode*pa,*pb,*pre,*p,*cp100;/定义OLNode类型的变量inti,j,t;t=A-tu+B-tu;for(j=1;jnu;j+)cpj=A-cheadj;/将A矩阵的列表头指针赋给cp数组for(i=1;imu;i+)pa=A
18、-rheadi;pb=B-rheadi;/将A，B矩阵的行表头指针分别赋给pa，pbpre=NULL;while(pb)/当pb不等于零if(pa=NULL|pa-jpb-j)p=(OLink)malloc(sizeof(OLNode);/给p动态分配空间if(!pre)A-rheadi=p;elsepre-right=p;p-right=pa;pre=p;p-i=i;p-j=pb-j;p-e=pb-e;if(!A-cheadp-j)A-cheadp-j=cpp-j=p;p-down=NULL;/假如A-cheadp-j不等于零，则把p赋给它及cpp-jelsecpp-j-down=p;cpp-j=p;pb=pb-right;/否则把p赋给cpp-jelseif(pa-jj)pre=pa;pa=pa-right;elseif(pa-e+pb-e)t-;pa-e+=pb-e;