对称矩阵压缩算法的实现

1、数据结构课程设计设计说明书对称矩阵压缩算法的实现学生姓名学号班级成绩指导教师数学与计算机科学学院2015年1月2日课程设计任务书20142015学年第一学期专业： 网络工程 学号： 姓名： 课程设计名称： 数据结构课程设计 设 计 题 目： 对称矩阵压缩算法的实现 完 成 期 限：自 2014 年 12 月 22 日至 2015 年 1 月 2 日共 2 周设计内容及要求:矩阵是一个在科学计算与工程问题中常见的数学对象，在程序设计中这种数学对象常常采用二维数组来存储，然而，有些矩阵具有某些特殊性，如对称矩阵，若用数组存储对称矩阵其空间代价较高，为了降低对称矩阵存储代价，常常采用一维数组只存储对

2、称矩阵中的对角线及其以上或以下元素值，此过程需要进行二维数组(矩阵)下标到一维数组下标的存储变换。请用C/C+语言编写一个程序实现对称矩阵的一维数组压缩存储。设计过程以及写作要求如下：（1）要针对本题目，认真研究所设计的内容，用简明扼要的语言描述课题，给出课题的基本内容及要求；（2）根据数据结构的相关知识给出实现对任意矩阵的输入、对称性的判断、对称矩阵压缩存储的转换，及对转换后的一维数组元素以数学形式打印输出原矩阵的算法基本策略及思路；（3）给出较为详尽数据结构与算法，算法可以用流程图、伪代码等描述手段进行描述；（4）给出一个完整的算法实现的C/C+程序，算法中的各子算法要力求用函数来实现；（

3、5）对编写的程序要进行详尽的测试分析；（6）对本课题的设计工作要进行一个完整深刻的总结。最终设计成果形式为：1、 设计软件一套；2、 撰写一份课程设计说明书一份，打印并装订成册。指导教师（签字）： 教研室主任（签字）： 批准日期： 年 月 日数据结构 课程设计评阅书题 目对称矩阵压缩算法的实现学生姓名学 号指导教师评语及成绩成 绩： 教师签名： 年 月 日教研室意见总成绩： 室主任签名： 年 月 日摘要本课程设计是以vc+语言编程软件功能和相关数据结构的知识实现的，借助Visual C+6.0工具实现对称矩阵压缩算法功能的源代码。将矩阵以二维数组的形式存放，通过对称矩阵的压缩存储，从而达到节省

4、存储空间的目的。 关键词：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 成功构建矩阵对其进行判断是

5、否为对称矩阵175.1.4 对对称矩阵进行压缩存储185.1.5 按照数学形式输出所压缩的矩阵195.1.6 退出程序205.2 非法输入205.2.1 非法操作菜单205.2.2 n值的非法输入21总结22参考资料23 1 课题描述矩阵是很多科学与工程计算问题中研究的数学对象。在此，人们感兴趣的不是矩阵本身，而是如何存储矩阵的元，从而使矩阵的各种运算能有效的进行。通常，用高级语言编制程序时，都是用二维数组来存储矩阵元。有的程序设计语言中还提供了各种矩阵运算，用户使用时都很方便，然而，在数值分析中经常出现一些阶数很高的矩阵，同时在矩阵中有许多值相同的元素或者是零元素。有时为了节省存储空间，可以

6、对这类矩阵进行压缩存储。压缩矩阵：为多个值相同的元止分配一个存储空间；对零元不分配空间。开发工具：Visual C+6.02 设计要求2.1设计要求本次课程设计采用结构化程序设计方法，从整体到模块、逐步细化，模块化设计、结构化编码的算法只适合特殊矩阵中的对称矩阵，面对一般矩阵，不进行压缩存储。存储时采用的顺序存储结构主要为数组，包括一维数组和二维数组。程序中定义了一个结构体Array s,其成员为两个数组，具体设计过程如下:2.2各模块程序的伪码算法（1）构建矩阵： CreatMatrix(Array &s); 操作结果：创建任意n*n矩阵。（2）判断矩阵是否对称： JudgeMatr

7、ix(Array &s); 初始条件：矩阵M存在。 操作结果：判断M是否为对称矩阵，若不是，则重新构建，最终得到对称矩阵。（3）压缩存储： CompMatrix(Array &s); 初始条件：矩阵M为对称矩阵。 操作结果：将M压缩存储到一维数组中。（4）输出所压缩的对称矩阵： OutputMatrix(Array &s); 初始条件：矩阵M已被压缩存储到一维数组中。 操作结果：将M按照数学形式输出。2.2各模块之间的调用关系图各模块之间的调用关系如图2.1所示。main CreatMatrix JudgeMatrix CompMatrix OutputMatrix C

8、reatMatrix图2.1 各模块之间的调用关系3 模块内的核心算法及流程图3.1构建任意矩阵在构建任意n*n矩阵这个模块中，利用了二维数组来接收所构建矩阵的元。CreatMatrix()函数：在构建矩阵时，首先要得到n值，将n值带入构建矩阵中，而输入部分用for循环控制输入格式及元素个数，输入前已规定建立任意矩阵并且元素个数为n*n个，接收时以二维数组的形式来存储从键盘输入的任意元素。输出所构建的矩阵时仍用for循环来输出。输入流程图如图3.1所示，输出流程图如图3.2所示，其中n为行下表或列下标。 开始 开始 输入n值 i=1 行下标初始化为1 n是非零自然数 N 判断非法输入 n<

9、;0或者n为字符 判断i值与 Y i<=n 行下标 输入矩阵 系统提示 N n值的关系 Y i=1 行下标初始化为1 j=1 列下标初始化为1 N i<=n 判断i值与行下标n值的关系 Y j<=n 判断 j值 j=1 列下标初始化为1 N 与列下标 n值的关系 Y j<=n 判断j值与列下标 输出元素 NY n值的关系 s.Mij 存入元素 j+ j+ i+ i+ 结束 结束 图3.1输入流程图 图3.2输出流程图3.1.1构建矩阵代码int CreatMatrix(Array &s)/构建任意矩阵int i,j;printf("t请输入您需要构建n

10、阶矩阵中的n值n");scanf("%d",&n);if(n<=0)fflush(stdin);printf("tn值为非法输入，请您重新输入n值，n>0n");scanf("%d",&n);fflush(stdin);printf("t请输入数组中各元素，输入时请注意：s.Mij=s.Mjin");for(i=1;i<=n;i+)for(j=1;j<=n;j+)scanf("%d",&s.Mij);printf("tt您构建的

11、矩阵为：n");printf("n");for(i=1;i<=n;i+)for(j=1;j<=n;j+)printf("t%2d",s.Mij); printf("n");return ok;3.2判断矩阵是否对称由于矩阵的压缩只针对对称矩阵，因此在创建任意矩阵后要判断是否符合压缩要求。JudgeMatrix()函数：函数包括两个小部分，判断部分和判断结果输出部分。在对称矩阵中，Mij=Mji为判断矩阵是否对称的依据,因此，要判断第一步输入的矩阵是否是对称矩阵，就是要判断这一条件是否成立，如果成立，则程序结束，若

12、不成立，则调用函数CreatMatrix重新输入，构建矩阵并再次判断，直到输入的矩阵为对称矩阵结束。判断流程图如图3.3所示，判断结果流程图如图3.4所示。 开始 开始 i=1 行下标初始化为1 调用判断 函数 N i<=n 判断i值与行下 得到k值 标n值的关系 Y k=0 j=1 列下标初始 N 化为1 Y N 对称矩阵 构建的不j<=n 判断j值与 构建成功 是对称矩阵 列下标n值 Y 的关系 调用 CreatMatrix s.Mij!=s.Mji 函数 沿对称线元素不对称 矩阵构建成功N Y k+ 结束j+ 图3.4 判断结果流程图 i+ 结束 图3.3 判断流程图3.2.

13、1判断矩阵是否对称代码int JudgeMatrix(Array s)/判断矩阵是否为对称矩阵int i,j,k;k=0;for(i=1;i<=n;i+)for(j=1;j<=n;j+)if(s.Mij!=s.Mji)k+;printf("tt判断得到不相等元素的对数k=%d",k);printf("n");if(k=0)printf("n");printf("ttMij=Mjin");printf("ntt对称矩阵构建正确!请您选择其他服务!n");elseprintf("

14、;n");printf("tt您构建的矩阵不是对称矩阵");return 1;return 0;3.3 对对称矩阵进行压缩存储当判断得到对称矩阵后，便可对其进行压缩存储，将一维数组作为对称矩阵的存储结构从而实现存储过程。CompMatrix()函数：此函数功能是对对称矩阵进行压缩存储，即就是将二维数组压缩存储到一维数组中，压缩存储的元素为下三角元，再将压缩后的数组元素进行输出。压缩部分：通过赋值语句s.mk=s.Mij,将矩阵进行压缩存储。压缩流程图如图3.5所示，输出流程图如图3.6所示 开始 开始 i=1,k=0 初始化行下标i=1, 压缩时元素个数k一维数组

15、下标k=0 N i<=n 判断行下标 k<n*(n+1)/2 i值与 N值的 下三角元素个数 Y 关系 N 初始化 Y j=1 列下标j 输出压缩后矩阵元素s.Mk N j<=i 列下标 与行下标 Y 的比较 结束 s.mk=s.Mij 图3.6 输出流程图 下三角元素赋值给 s.mk k+j+i+ 结束 图3.5 压缩流程图3.3.1 对对称矩阵进行压缩存储代码int CompMatrix(Array &s)/对对称矩阵进行压缩存储int i,j,k=0;for(i=1;i<=n;i+)for(j=1;j<=i;j+)s.mk=s.Mij;k+;prin

16、tf("tt压缩后的矩阵存入一维数组后各元素为：n");printf("n");for(k=0;k<n*(n+1)/2;k+)printf("%2d",s.mk);return ok;3.4 将存储后的矩阵按照数学形式输出矩阵的数学形式即为一个二维数组，我们将矩阵进行压缩存储后，其原来的形式被改变，变为一维数组，而所存储的元素个数也少于原矩阵，因此需要编辑函数将矩阵按数学形式输出。OutputMatrix()函数：此函数的功能是：将压缩后的矩阵按照矩阵的数学形式输出，通过公式：当i>=j时，k=i*(i-1)/2+j-1;

17、当i<j时，k=j*(j-1)/2+i-1。赋值流程图如图3.7所示，输出流程图如图3.8所示。 开始 开始 i=1 初始化i=1i=1 初始化i=1 NN 判断i值与 i<=n 判断i值与 i<=n 行下标n值 行下标n值的的关系Y 关系Y j=1 初始化j=1 j=1 初始化 j=1 N 判断列下 判断列下标j j<=i 标j值 j<=n 与n值的 与行下标 大小关系 Y i值得大小Y k=i*(i-1)/2+j-1 输出矩阵 k=j*(j-1)/2+i-1 j+ s.Mij=s.mki+ j+ 结束 i+ 图3.8 输出流程图 结束 图3.7 赋值流程图 3

18、.4.1 将存储后的矩阵按照数学形式输出的代码int OutputMatrix(Array s)/按照数学形式输出矩阵int i,j,k=0;for(i=1;i<=n;i+)for(j=1;j<=n;j+)if(i>=j)k=i*(i-1)/2+j-1;s.Mij=s.mk;elsek=j*(j-1)/2+i-1;s.Mij=s.mk;printf("tt您压缩存储的矩阵按照数学形式输出为：n");printf("n");for(i=1;i<=n;i+)for(j=1;j<=n;j+)printf("t%2d&qu

19、ot;,s.Mij);printf("n");return ok;4 详细代码#include<stdio.h>#include<stdlib.h>#include<stdarg.h>#define OVERFLOW -2#define UNDERFLOW -1#define ok 1typedef structint M100100;int m100;Array;Array s;int n;int CreatMatrix(Array &s)/构建任意矩阵int i,j;/printf("tt请输入数组中各元素，输入时请

20、注意：s.Mij=s.Mjin");printf("t请输入您需要构建n阶矩阵中的n值n");scanf("%d",&n);if(n<=0)fflush(stdin);printf("tn值为非法输入，请您重新输入n值，n>0n");scanf("%d",&n);fflush(stdin);printf("t请输入数组中各元素，输入时请注意：s.Mij=s.Mjin");for(i=1;i<=n;i+)for(j=1;j<=n;j+)scanf(

21、"%d",&s.Mij);printf("tt您构建的矩阵为：n");printf("n");for(i=1;i<=n;i+)for(j=1;j<=n;j+)printf("t%2d",s.Mij);printf("n");return ok;int JudgeMatrix(Array s)/判断矩阵是否为对称矩阵int i,j,k;k=0;for(i=1;i<=n;i+)for(j=1;j<=n;j+)if(s.Mij!=s.Mji)k+;printf(&quo

22、t;tt判断得到不相等元素的对数k=%d",k);printf("n");if(k=0)printf("n");printf("ttMij=Mjin");printf("ntt对称矩阵构建正确!请您选择其他服务!n");elseprintf("n");printf("tt您构建的矩阵不是对称矩阵");return 1;return 0;int CompMatrix(Array &s)/对对称矩阵进行压缩存储int i,j,k=0;for(i=1;i<=

23、n;i+)for(j=1;j<=i;j+)s.mk=s.Mij;k+;printf("tt压缩后的矩阵存入一维数组后各元素为：n");printf("n");for(k=0;k<n*(n+1)/2;k+)printf("%2d",s.mk);return ok;int OutputMatrix(Array s)/按照数学形式输出矩阵int i,j,k=0;for(i=1;i<=n;i+)for(j=1;j<=n;j+)if(i>=j)k=i*(i-1)/2+j-1;s.Mij=s.mk;elsek=j*(

24、j-1)/2+i-1;s.Mij=s.mk;printf("tt您压缩存储的矩阵按照数学形式输出为：n");printf("n");for(i=1;i<=n;i+)for(j=1;j<=n;j+)printf("t%2d",s.Mij);printf("n");return ok;int menu_select() /菜单char c;doprintf("tt*n");printf("tt* 对称矩阵压缩算法的实现 *n");printf("tt* 1.

25、构建任意N*N个元素的矩阵 *n");printf("tt* 2.判断所建矩阵是否为对称矩阵 *n");printf("tt* 3.对对称矩阵进行压缩存储 *n");printf("tt* 4.按照数学形式输出所压缩的矩阵 *n");printf("tt* 5.退出程序 *n");printf("tt*n");printf("tt*请您输入选项1-5*n");fflush(stdin);c=getchar();while(c<'1'|c>

26、'5');return(c); /返回选择void main() /主函数char n='1'int m;for(;)switch(menu_select() )case '1':printf("n");printf("ttt<构建任意n*n个元素的矩阵>n");printf("n");CreatMatrix(s);printf("n");printf("tt您已经成功构建*任意*矩阵!请您选择其他服务!n");printf("

27、;n");printf("ttt");system("pause");break;case'2':printf("n");printf("ttt<判断矩阵是否为对称矩阵>n");printf("n");m=JudgeMatrix(s);printf("n");if(m=1)CreatMatrix(s);printf("n");printf("ttt");system("pause"

28、;);break;case'3':printf("n");printf("ttt<对对称矩阵进行压缩存储>n");printf("n");printf("tt只存储其下三角各元素：n");printf("n");CompMatrix(s);printf("n");printf("ttt");system("pause");break;case'4':printf("n");

29、printf("ttt<按照数学形式输出所压缩的矩阵>n");printf("n");OutputMatrix(s);printf("n");printf("ttt");system("pause");break;case'5':printf("n");printf("ttt祝您好运!n");printf("ttt");exit(0);5 程序测试5.1 合法输入5.1.1 菜单为了使程序界面能够美化，使用*

30、 *对其进行框圈，并且使用t使其跳到下一个制表位置，菜单的使用，使程序的操作简单明了，如图5.1所示。图5.1 菜单5.1.2构建任意矩阵在对矩阵进行构建时，先确定矩阵的阶数n，然后对矩阵中的元素进行录入，录入时用空格键区分两个数字，即使输入元素超过n*n个，也只取前n*n个元素，并将其以矩阵的形式输出，如图5.2所示。图5.2 构建任意矩阵5.1.3 成功构建矩阵对其进行判断是否为对称矩阵该矩阵是否为对称矩阵，是通过k值进行判断，对于上述矩阵，对角线为1、7、3、9、5；如若对称则s.Mij=s.Mji,但通过矩阵的输出，我们发现（6、2）（1、3）（6、4）（1、5）（2、8）（7、9）.

31、10组数据中，没有一组内的数据相同，则不相等的元素数为k=20.所以该矩阵不是对称矩阵。如图5.3所示图5.3 矩阵的对称判断(不对称矩阵)在矩阵输入时，必须是对称矩阵才可以进行第三步第四步操作，否则在判断对称矩阵不是对称矩阵之后，系统提示重新输入数据，在输入并对其判断为对称矩阵之后，该矩阵是对称矩阵，因为对角线为1、3、5、7、9；如若对称则s.Mij=s.Mji,通过矩阵的输出，我们发现（2,2）（3，3）（4,4）（4,4）（5,5）（6,6）.10组数据中，括号内的元素都相同，则不相等的元素数为k=0.所以该矩阵是对称矩阵，如图所示5.4。图5.4 矩阵的对称判断（对称矩阵）5.1.4 对对称矩阵进行压缩存储对对称矩阵进行压缩存储，其存储的元素为下三角（包括对角线）中的元，即1、2、3、3、4、5、4、5、6、7、5、6、7、8、9，存储元素的个数为k=n*(n+1)/2,