特殊矩阵的压缩存储

《数据结构》课程设计报告书题目：特殊矩阵的压缩存储算法的实现系别：计算机科学与技术学号：111096135学生姓名：徐光辉指导教师：刘双红完成日期：2012年6月5日目录1需求分析................................................................12概要设计................................................................13详细设计.................................................................13.1详细设计思想.......................................................13.2核心代码...........................................................24调试分析................................................................65测试结果................................................................66总结....................................................................8指导教师评语..............................................................911需求分析问题描述：对于特殊矩阵可以通过压缩存储减少存储空间。基本要求：1.针对多种特殊矩阵进行压缩存储，并能显示压缩后的相关地址和值。2.输入在原来特殊矩阵中的地址，要求能从压缩后的矩阵中读出相应的值。2概要设计程序流程图如下：图2.1程序流程图3详细设计3.1详细设计思想特殊矩阵：值相同元素或者零元素分布有一定规律的矩阵称为特殊矩阵例:对称矩阵、上（下）三角矩阵都是特殊矩阵。图3.1特殊矩阵特殊矩阵压缩存储(以对称矩阵为例)开始选择矩阵类型输入矩阵元素结束输入1012对称矩阵是满足下面条件的n阶矩阵:aij=aji1=i,j=n图3.2k=0123456n(n+1)/2-1对称矩阵元素可以只存储下三角部分，共需n(n+1)/2个单元的空间(三角矩阵的存储方式类似）。以一维数组sa[0..n(n+1)/2-1]作为n阶对称矩阵A的存储结构A中任意一元素aij与它的存储位置sa[k]之间关系：图3.3k=0123456n(n+1)/2-13.2核心代码#includestdio.h#includestdlib.hstaticshangsanjiao(intn){inti,j,k,z,g;intL[100][100],SA[100];printf(请输入您要压缩矩阵的行列数\n);scanf(%d,&n);printf(请输入您的矩阵内元素：\n);for(i=1;in+1;i++)for(j=1;jn+1;j++){scanf(%d,&L[i][j]);if(i=j)k=j*(j-1)/2+i-1;else3k=n*(n+1)/2;SA[k]=L[i][j];}printf(您输入的矩阵为：\n);for(i=1;in+1;i++){for(j=1;jn+1;j++)printf(%d,L[i][j]);printf(\n);}printf(压缩存储后：\n);for(k=0;kn*(n+1)/2+1;k++)printf(%d%d\n,k,SA[k]);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,SA[k]);z=1;printf(继续请输入'100'退出输入'000'。\n);scanf(%d,&z);}break;}}staticduichen(intn){inti,j,k,z,g;intL[100][100],SA[100];printf(请输入您要压缩矩阵的行列数\n);scanf(%d,&n);printf(请输入您的矩阵内元素：\n);for(i=1;in+1;i++)for(j=1;jn+1;j++){scanf(%d,&L[i][j]);if(i=j)k=i*(i-1)/2+j-1;else4k=j*(j-1)/2+i-1;SA[k]=L[i][j];}printf(您输入的矩阵为：\n);for(i=1;in+1;i++){for(j=1;jn+1;j++)printf(%d,L[i][j]);printf(\n);}printf(压缩存储后：\n);for(k=0;kn*(n+1)/2;k++)printf(%d%d\n,k,SA[k]);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=i*(i-1)/2+j-1;elsek=j*(j-1)/2+i-1;printf(该地址的值为：\n);printf(%d\n,SA[k]);z=1;printf(继续请输入'100'退出输入'000'。\n);scanf(%d,&z);}break;}}staticxiasanjiao(intn){inti,j,k,z,g;intL[100][100],SA[100];printf(请输入您要压缩矩阵的行列数\n);scanf(%d,&n);printf(请输入您的矩阵内元素：\n);for(i=1;in+1;i++)for(j=1;jn+1;j++){scanf(%d,&L[i][j]);if(i=j)k=i*(i-1)/2+j-1;else5k=n*(n+1)/2;SA[k]=L[i][j];}printf(您输入的矩阵为：\n);for(i=1;in+1;i++){for(j=1;jn+1;j++)printf(%d,L[i][j]);printf(\n);}printf(压缩存储后：\n);for(k=0;kn*(n+1)/2+1;k++)printf(%d%d\n,k,SA[k]);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=i*(i-1)/2+j-1;elsek=n*(n+1)/2;printf(该地址的值为：\n);printf(%d\n,SA[k]);z=1;printf(继续请输入'100'退出输入'000'。\n);scanf(%d,&z);}break;}}intmain(){intn,d;intm;for(d=0;d100;d++){printf(请选择您要存储的特殊矩阵类型：\n);printf(1:对称矩阵2:上三角矩阵3:下三角矩阵\n);printf(退出请输入’101‘\n);scanf(%d,&m);if(m==1){duichen(n);}elseif(m==2)6{shangsanjiao(n);}elseif(m==3){xiasanjiao(n);}elseif(m==101)break;elseprintf(对不起您输入的选号错误。\n);}}4调试分析主要遇到以下几个问题：1.代码语法错误。2。函数调用错误。3.c++软件使用不熟练。5测试结果图5.1选择矩阵类型图5.2对称矩阵7图5.3下三角矩阵5.4上三角矩阵86总结经过一周的奋斗，这次数据结构的课程设计终于做完了。通过这次设计我们也着实又感受了一次编程的乐趣，从中也学到了不少知识。感受最深的一点是：以前用编程，只是注重如何编写函数能够完成所需要的功能，似乎没有明确的战术，只是凭单纯的意识和简单的语句来堆砌出一段程序。现在编程感觉完全不同了。在编写一个程序之前，先对这个课程设计进行了一下分析，将每个要求都花了一下算法流程图，使得自己的思路更加的清晰了。然后进行编程，不断的在电脑上调试程序，终于完成了此次的课程设计。另外，我还体会到深刻理解数据结构的重要性。只有真正理解这样定义数据类型的好处，才能用好这样一种数据结构。了解典型数据结构的性质是非常有用的，它往往是编写程序的关键。通过这次课程设计逐渐提高了自己的程序设计和调试能力，我以前对算法一直很害怕，总是看不明白究竟这程序中间的过程是怎么进行的。在这次实验中我终于克服了这一障碍，一遍遍在心中自己默默的走，终于弄明白了，真的是功夫不负有心人啊！这次试验也让我看到了自己的不足，还是不太用模板类。还有许多关于C语言的一些比较具体的东西还不太懂，需要进一步了解。这次试验还让我意识到只有不断的在电脑上调试程序，自己的水平才能得到提高。我会继续我们的兴趣编写程序的，相信在越来越多的尝试之后，自己会不断进步和提高。9指导教师评语程序成绩：报告成绩：综合成绩：指导教师姓名：批改日期：年月日