对称矩阵压缩算法的实现

数据结构课程设计设计说明书对称矩阵压缩算法的实现学生姓名学号班级成绩指导教师数学与计算机科学学院2015年1月2日课程设计任务书2014—2015学年第一学期专业：网络工程学号：姓名：课程设计名称：数据结构课程设计设计题目：对称矩阵压缩算法的实现完成期限：自2014年12月22日至2015年1月2日共2周设计内容及要求:矩阵是一个在科学计算与工程问题中常见的数学对象，在程序设计中这种数学对象常常采用二维数组来存储，然而，有些矩阵具有某些特殊性，如对称矩阵，若用数组存储对称矩阵其空间代价较高，为了降低对称矩阵存储代价，常常采用一维数组只存储对称矩阵中的对角线及其以上或以下元素值，此过程需要进行二维数组(矩阵)下标到一维数组下标的存储变换。请用C/C++语言编写一个程序实现对称矩阵的一维数组压缩存储。设计过程以及写作要求如下：（1）要针对本题目，认真研究所设计的内容，用简明扼要的语言描述课题，给出课题的基本内容及要求；（2）根据数据结构的相关知识给出实现对任意矩阵的输入、对称性的判断、对称矩阵压缩存储的转换，及对转换后的一维数组元素以数学形式打印输出原矩阵的算法基本策略及思路；（3）给出较为详尽数据结构与算法，算法可以用流程图、伪代码等描述手段进行描述；（4）给出一个完整的算法实现的C/C++程序，算法中的各子算法要力求用函数来实现；（5）对编写的程序要进行详尽的测试分析；（6）对本课题的设计工作要进行一个完整深刻的总结。最终设计成果形式为：1、设计软件一套；2、撰写一份课程设计说明书一份，打印并装订成册。指导教师（签字）：教研室主任（签字）：批准日期：年月日数据结构课程设计评阅书题目对称矩阵压缩算法的实现学生姓名学号指导教师评语及成绩成绩：教师签名：年月日教研室意见总成绩：室主任签名：年月日摘要本课程设计是以vc++语言编程软件功能和相关数据结构的知识实现的，借助VisualC++6.0工具实现对称矩阵压缩算法功能的源代码。将矩阵以二维数组的形式存放，通过对称矩阵的压缩存储，从而达到节省存储空间的目的。关键词：VC++；对称矩阵；压缩存储；节省空间目录1课题描述...................................................................12设计要求...................................................................22.1设计要求.............................................................22.2各模块程序的伪码算法.................................................22.2各模块之间的调用关系图...............................................23模块内的核心算法及流程图...................................................33.1构建任意矩阵.........................................................33.1.1构建矩阵代码...................................................43.2判断矩阵是否对称.....................................................43.2.1判断矩阵是否对称代码...........................................63.3对对称矩阵进行压缩存储...............................................63.3.1对对称矩阵进行压缩存储代码.....................................83.4将存储后的矩阵按照数学形式输出.......................................83.4.1将存储后的矩阵按照数学形式输出的代码..........................104详细代码..................................................................115程序测试..................................................................165.1合法输入............................................................165.1.1菜单..........................................................165.1.2构建任意矩阵..................................................165.1.3成功构建矩阵对其进行判断是否为对称矩阵........................175.1.4对对称矩阵进行压缩存储........................................185.1.5按照数学形式输出所压缩的矩阵..................................195.1.6退出程序......................................................205.2非法输入............................................................205.2.1非法操作菜单..................................................205.2.2n值的非法输入................................................21总结.......................................................................22参考资料....................................................................2311课题描述矩阵是很多科学与工程计算问题中研究的数学对象。在此，人们感兴趣的不是矩阵本身，而是如何存储矩阵的元，从而使矩阵的各种运算能有效的进行。通常，用高级语言编制程序时，都是用二维数组来存储矩阵元。有的程序设计语言中还提供了各种矩阵运算，用户使用时都很方便，然而，在数值分析中经常出现一些阶数很高的矩阵，同时在矩阵中有许多值相同的元素或者是零元素。有时为了节省存储空间，可以对这类矩阵进行压缩存储。压缩矩阵：为多个值相同的元止分配一个存储空间；对零元不分配空间。开发工具：VisualC++6.022设计要求2.1设计要求本次课程设计采用结构化程序设计方法，从整体到模块、逐步细化，模块化设计、结构化编码的算法只适合特殊矩阵中的对称矩阵，面对一般矩阵，不进行压缩存储。存储时采用的顺序存储结构主要为数组，包括一维数组和二维数组。程序中定义了一个结构体Arrays,其成员为两个数组，具体设计过程如下:2.2各模块程序的伪码算法（1）构建矩阵：CreatMatrix(Array&s);操作结果：创建任意n*n矩阵。（2）判断矩阵是否对称：JudgeMatrix(Array&s);初始条件：矩阵M存在。操作结果：判断M是否为对称矩阵，若不是，则重新构建，最终得到对称矩阵。（3）压缩存储：CompMatrix(Array&s);初始条件：矩阵M为对称矩阵。操作结果：将M压缩存储到一维数组中。（4）输出所压缩的对称矩阵：OutputMatrix(Array&s);初始条件：矩阵M已被压缩存储到一维数组中。操作结果：将M按照数学形式输出。2.2各模块之间的调用关系图各模块之间的调用关系如图2.1所示。mainCreatMatrixJudgeMatrixCompMatrixOutputMatrixCreatMatrix图2.1各模块之间的调用关系33模块内的核心算法及流程图3.1构建任意矩阵在构建任意n*n矩阵这个模块中，利用了二维数组来接收所构建矩阵的元。CreatMatrix()函数：在构建矩阵时，首先要得到n值，将n值带入构建矩阵中，而输入部分用for循环控制输入格式及元素个数，输入前已规定建立任意矩阵并且元素个数为n*n个，接收时以二维数组的形式来存储从键盘输入的任意元素。输出所构建的矩阵时仍用for循环来输出。输入流程图如图3.1所示，输出流程图如图3.2所示，其中n为行下表或列下标。开始开始输入n值i=1行下标初始化为1n是非零自然数N判断非法输入n0或者n为字符判断i值与Yi=n行下标输入矩阵系统提示Nn值的关系Yi=1行下标初始化为1j=1列下标初始化为1Ni=n判断i值与行下标n值的关系Yj=n判断j值j=1列下标初始化为1N与列下标n值的关系Yj=n判断j值与列下标输出元素NYn值的关系s.M[i][j]存入元素j++j++i++i++结束结束图3.1输入流程图图3.2输出流程图43.1.1构建矩阵代码intCreatMatrix(Array&s)//构建任意矩阵{inti,j;printf(\t请输入您需要构建n阶矩阵中的n值\n);scanf(%d,&n);if(n=0){fflush(stdin);printf(\tn值为非法输入，请您重新输入n值，n0\n);scanf(%d,&n);}fflush(stdin);printf(\t请输入数组中各元素，输入时请注意：s.M[i][j]=s.M[j][i]\n);for(i=1;i=n;i++){for(j=1;j=n;j++)scanf(%d,&s.M[i][j]);}printf(\t\t您构建的矩阵为：\n);printf(\n);for(i=1;i=n;i++){for(j=1;j=n;j++)printf(\t%2d,s.M[i][j]);printf(\n);}returnok;}3.2判断矩阵是否对称由于矩阵的压缩只针对对称矩阵，因此在创建任意矩阵后要判断是否符合压缩要求。JudgeMatrix()函数：函数包括两个小部分，判断部分和判断结果输出部分。在对称矩阵中，M[i][j]=M[j][i]为判断矩阵是否对称的依据,因此，要判断第一步输入的矩阵是否是对称矩阵，就是要判断这一条件是否成立，如果成立，则程序结束，若不成立，则调用函数CreatMatrix重新输入，构建矩阵并再次判断，直到输入的矩阵为对称矩阵结束。判断流程图如图3.3所示，判断结果流程图如图3.4所示。5开始开始i=1行下标初始化为1调用判断函数Ni=n判断i值与行下得到k值标n值的关系Yk==0j=1列下标初始N化为1YN对称矩阵构建的不j=n判断j值与构建成功是对称矩阵列下标n值Y的关系调用CreatMatrixs.M[i][j]!=s.M[j][i]函数沿对称线元素不对称矩阵构建成功NYk++结束j++图3.4判断结果流程图i++结束图3.3判断流程图63.2.1判断矩阵是否对称代码intJudgeMatrix(Arrays)//判断矩阵是否为对称矩阵{inti,j,k;k=0;for(i=1;i=n;i++)for(j=1;j=n;j++){if(s.M[i][j]!=s.M[j][i])k++;}printf(\t\t判断得到不相等元素的对数k=%d,k);printf(\n);if(k==0){printf(\n);printf(\t\tM[i][j]==M[j][i]\n);printf(\n\t\t对称矩阵构建正确!请您选择其他服务!\n);}else