稀疏矩阵的乘法实现.doc

武汉理工大学《数据结构》课程设计说明书 PAGE 4 学 号： 0120610680422 课 程 设 计 题 目 稀疏矩阵的乘法实现 学 院 计算机科学与技术学院 专 业 软件工程专业 班 级 软件0604班 姓 名 指导教师 2008 年 7 月 11 日 课程设计任务书 学生姓名： 专业班级： 软件0604班 指导教师： 工作单位：计算机科学与技术学院 题 目: 稀疏矩阵的乘法实现 初始条件： 理论：学习了《数据结构》课程，掌握了基本的数据结构和常用的算法； 实践：计算机技术系实验室提供计算机及软件开发环境。 要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求） 1、系统应具备的功能： （1）设计稀疏矩阵的存储结构 （2）实现稀疏矩阵的乘法 （3）输出运算结果 2、数据结构设计； 3、主要算法设计； 4、编程及上机实现； 5、撰写课程设计报告，包括： （1）设计题目； （2）摘要和关键词（中文和英文）； （3）正文，包括引言、需求分析、数据结构设计、算法设计、程序实现及测试、不足之处、设计体会等； （4）结束语； （5）参考文献。 时间安排： 2008年7月7日－11日 （第20周） 7月7日 查阅资料 7月8日 系统设计，数据结构设计，算法设计 7月9日 -10日 编程并上机调试 7月11日 撰写报告 7月12日 验收程序，提交设计报告书。 指导教师签名： 2008年7月7日 系主任（或责任教师）签名： 2008年7月7日 稀疏矩阵的乘法实现 计算机学院软件工程系 钟安原 摘要：本程序主要设计稀疏矩的存储方式及实现稀疏矩阵的相关运算，包括加法与乘法运算。稀疏矩阵的存储使用三元组，对于输入的两个多项式能够计算出二者的加运算与乘运算，并将结果以矩阵的形式输出出来，对于错误的输入系统进行报。 关键字：压缩存储 、稀疏矩阵、 重载 Abstract:This programe mainly aimed at the storage and the related operation of sparse matrix.The storage structure is tripe form,for any two inputed matrix,the system will decide whther they are sparse matrix,cacualte their addition and multiplication，print the result。If there is any mistake in the input,the system will inform us about it. Keywords:compressed storage、sparse matrix、overload 引言 随着信息技术的发展，数据的压缩存储也越来越重要 数据压缩是通过减少计算机中所存储数据或者通信传播中数据的冗余度，达到增大数据密度，最终使数据的存储空间减少的技术。 　　数据压缩在文件存储和分布式系统领域有着十分广泛的应用。数据压缩也代表着尺寸媒介容量的增大和网络带宽的扩展。 　　数据压缩就是将字符串的一种表示方式转换为另一种表示方式，新的表示方式包含相同的信息量，但是长度比原来的方式尽可能的短。 其实在如今存储器容量急剧增大的同时，我们似乎已经忘记了“空间不够用”的概念，想想自己大学时用的奔腾，才1G的硬盘，16MB的内存，那时候，对于压缩这个东西简直是喜欢的不得了，有时就希望一种算法能把1G大的文件夹压缩成几十兆（有点在做梦），当看到IBM 10G硬盘出现的时候，简直就觉得大的不得了了，可是后来随着软件规模的越来越大（这和微软绝对有关系），“那么大”的硬盘也变得杯水车薪，好在硬盘技术的发展非常快，能够满足我们日益膨胀的存储欲望。 不过个人领域似乎还体现不出压缩算法的威力，其实在一些空间计算等领域，好的压缩算法是非常重要的，要知道这些领域在1分钟内所产生的数据量就会以G记，如果没有压缩算法，再多的硬盘也不够用。 二维数组（即矩阵）是常见的数据结构类型，在自然科学与社会科学中都有很广泛的应用，矩阵也是数学中的一个重要概念。通常，用高级语言编制程序时，都是用二维数组来存储矩阵元。然而在数值分析中经常出现一些结束很高的矩阵，用二维数组存储一个矩阵需要的空间是n2级，需要很大的空间开销，同时在矩阵中有很多值相同的元素或者是零元素。有时为