杨应安课程设计文档.doc

红河学院工学院课程设计报告告专业：计算机科学与技术年级：2011级学号：201101030219姓名： 杨应安成绩：课程设计目录 课程名称：数据结构与算法 设计任务：特殊矩阵的压缩存储算法的实现 任务名称特殊矩阵的压缩存储算法的实现班级2011级指导教师许海成地点红河学院成绩学年2012-2013开始日期2012-12-7结束日期2012-12-25组员一人独立完成设计目的及要求：目的： （1）进一步加深特殊矩阵压缩，存储、定义的理解，并能够掌握特殊矩阵的压缩存储算，以及它在程序中的使用方法。（2）掌握软件设计的基本内容和设计方法，并能培养进行规范化软件设计能力。要求: （1）首先要分析题目，查阅相关资料。 （2）清晰的设计出整个程序的思路。 （3）按要求编写程序。 （4）写出运行结果，并分析结果。问题描述及基本要求：问题描述： 对于特殊矩阵可以通过压缩存储减少存储空间。基本要求： 1.针对多种特殊矩阵进行压缩存储，并能显示压缩后的相关地址和值； 2.输入在原来特殊矩阵中的地址，要求能从压缩后的矩阵中读出相应的值；程序功能模块:矩阵压缩存储系统功能模块，如图所示。主要由输入矩阵阶数、输入矩阵、显示矩阵、输入地址、读出相应的值、退出系统六部分组成。其中，输入矩阵阶数主要由用户输入矩阵阶数；输入矩阵主要输入矩阵；显示矩阵由系统显示矩阵；输入地址用来输入矩阵元素的地址；读出相应的值由系统读出；退出系统用来退出整个系统。输入矩阵阶数输入矩阵显示矩阵输入地址读出相应的值退出系统 将矩阵的阶数输入信息库 将矩阵按格式输入信息库 系统显示出相应矩阵 将矩阵中元素的地址输入信息库 显示出相应的值 退出压缩存储系统矩阵的压缩存储主要功能函数介绍:a) Menu-list函数：输出矩阵压缩存储系统菜单b) duichen函数：输入对称矩阵，实现压缩存储c) shangsanjiao函数：输入上三角矩阵，实现压缩存储d) xiasanjiao函数：输入下三角矩阵，实现压缩存储e) main函数：函数调用以及结束程序 功能模块详细设计:特殊矩阵：值相同元素或者零元素分布有一定规律的矩阵称为特殊矩阵 例:对称矩阵、 上（下）三角矩阵都是特殊矩阵特殊矩阵压缩存储(以对称矩阵为例)对称矩阵是满足下面条件的n 阶矩阵: aij= aji 1= i,j= nk= 0 1 2 3 4 5 6 n(n+1)/2-1 对称矩阵元素可以只存储下三角部分，共需 n(n+1)/2 个单元的空间( 三角矩阵的存储方式类似） 以一维数组sa0.n(n+1)/2-1作为n 阶对称矩阵A的存储结构A中任意一元素 aij与它的存储位置 sak 之间关系：k= 0 1 2 3 4 5 6 n(n+1)/2-1 核心代码： static shangsanjiao(int n)int i,j,k,z,g;int L100100,SA100;printf(请输入您要压缩矩阵的行列数n);scanf(%d,&n);printf(请输入您的矩阵内元素：n);for(i=1;in+1;i+)for(j=1;jn+1;j+)scanf(%d,&Lij);if(i=j)k=j*(j-1)/2+i-1;elsek=n*(n+1)/2;SAk=Lij;printf(您输入的矩阵为：n);for(i=1;in+1;i+)for(j=1;jn+1;j+)printf(%d ,Lij);printf(n);printf(压缩存储后：n);for(k=0;kn*(n+1)/2+1;k+)printf(%d %dn,k,SAk);printf(若要读取矩阵的值请输入100退出输入000。n);scanf(%d,&z);for(g=0;g1000;g+)while(z=100)printf(请您输入未压缩时所在行数:n);scanf(%d,&i);printf(请您输入未压缩时所在列数:n);scanf(%d,&j);if(i=j)k=j*(j-1)/2+i-1;elsek=n*(n+1)/2;printf(该地址的值为：n);printf(%d n,SAk);z=1;printf(继续请输入100退出输入000。n);scanf(%d,&z);break;static duichen(int n)int i,j,k,z,g;int L100100,SA100;printf(请输入您要压缩矩阵的行列数n);scanf(%d,&n);printf(请输入您的矩阵内元素：n);for(i=1;in+1;i+)for(j=1;j=j)k=i*(i-1)/2+j-1;elsek=j*(j-1)/2+i-1;SAk=Lij;printf(您输入的矩阵为：n);for(i=1;in+1;i+)for(j=1;jn+1;j+)printf(%d ,Lij);printf(n);printf(压缩存储后：n);for(k=0;kn*(n+1)/2;k+)printf(%d %dn,k,SAk);printf(若要读取矩阵的值请输入100退出输入000。n);scanf(%d,&z);for(g=0;g=j)k=i*(i-1)/2+j-1;elsek=j*(j-1)/2+i-1;printf(该地址的值为：n);printf(%d n,SAk);z=1;printf(继续请输入100退出输入000。n);scanf(%d,&z);break;static xiasanjiao(int n)int i,j,k,z,g;int L100100,SA100;printf(请输入您要压缩矩阵的行列数n);scanf(%d,&n);printf(请输入您的矩阵内元素：n);for(i=1;in+1;i+)for(j=1;j=j)k=i*(i-1)/2+j-1;elsek=n*(n+1)/2;SAk=Lij;printf(您输入的矩阵为：n);for(i=1;in+1;i+)for(j=1;jn+1;j+)printf(%d ,Lij);printf(n);printf(压缩存储后：n);for(k=0;kn*(n+1)/2+1;k+)printf(%d %dn,k,SAk);printf(若要读取矩阵的值请输入100退出输入000。n);scanf(%d,&z);for(g=0;g=j)k=i*(i-1)/2+j-1;elsek=n*(n+1)/2;printf(该地址的值为：n);printf(%d n,SAk);z=1;printf(继续请输入100退出输入000。n);scanf(%d,&z);break;int main()int n,d;int m;for(d=0;d100;d+)printf(请选择您要存储的特殊矩阵类型：n); printf(1:对称矩阵 2:上三角矩阵 3:下三角矩阵n);printf(退出请输入101n);scanf(%d,&m);if(m=1) duichen(n);else if(m=2) shangsanjiao(n);else if(m=3) xiasanjiao(n);else if(m=101) break;else printf(对不起您输入的选号错误。n);运行结果：对称矩阵的压缩及读取：上三角矩阵和下三角矩阵的压缩及读取：总结：经过一周的奋斗，这次数据结构的课程设计终于做完了。通过这次设计我感受到了一次编程的乐趣，从中也学到了不少知识。感受最深的一点是：以前用编程，只是注重如何编写函数能够完成所需要的功能，似乎没有明确的战术，只是凭单纯的意识和简单的语句来堆砌出一段程序。现在编程感觉完全不同了。在编写一个程序之前，先对这个课程设计进行了一下分析，将每个要求都花了一下算法流程图，使得自己的思路更加的清晰了 。 然后进行编程，不断的在电脑上调试程序，终于完成了此次的课程设计。另外，我还体会到深刻理解数据结构的重要性。只有真正理解这样定义数据类型的好处，才能用好这样一种数据结构。了解典型数据结构的性质是非常有用的，它往往是编写程序的关键。通过这次课程设计逐渐提高了自己的程序设计和调试能力，我以前对算法一直很害怕，总是看不明白究竟这程序中间的过程是怎么进行的。在这次