数据结构课程设计
设计说明书
稀疏矩阵相关操作的实现
学生姓名 学班成
号 级 绩
指导教师
数学与计算机科学学院 2012 年 3 月 2 日
数据结构课程设计评阅书
题 目 学生姓名 指导教师评语及成绩 稀疏矩阵相关操作的实现 学号 成绩： 教师签名： 年 月 日 答辩教师评语及成绩 成绩： 教师签名： 年 月 日 教研室意见 总成绩： 室主任签名： 年 月 日 注：指导教师成绩60%，答辩成绩40%，总成绩合成后按五级制记入。
课程设计任务书
2011—2012学年第二学期
专业： __________________ 学号： __________ 姓名： _______ 课程设计名称： 数据结构课程设计 设 计 题 目： 稀疏矩阵相关操作的实现
完 成 期 限：自 ____ 年 _ 月 __ 日至 ____ 年 _月 _ 日共 _ 周 设计内容：
用C/C++编写程序实现稀疏矩阵创建、销毁、输出、复制、求和、求差、求乘积和转置等相关操作(详见数据结构教材P96)，并进行算法分析。 设计要求:
1）问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？ 确定问题的输入数据集合。
2）逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的功能说明），各个主要模块的算法，并画出模块之间的调用关系图；
3）详细设计：定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作做出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架；
4）程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚；
5）程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果；
6）结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析；
7）编写课程设计报告；
以上要求中前三个阶段的任务完成后，先将设计说明数的草稿交指导老师面审，审查合格后方可进入后续阶段的工作。设计工作结束后，经指导老师验收合格后将设计说明书打印装订，并进行答辩。
指导教师（签字）： 教研室主任（签字）： 批准日期： 2012年2月 20 日
摘 要
矩阵是很多科学与工程计算问题中研究的数学对象，通常用高级语言编制程序时，都是用二维数组来存储矩阵元的，有的程序设计语言中还提供了各种矩阵运算，用户使用时都很方便，然而，在数值分析中经常出现一些阶数很高的矩阵，同时在矩阵中有许多值相同的元素或者是零元素，为了节省存储空间，可以对这类矩阵进行压缩存储。当值相同的元素或者零元素在矩阵中的分布有一定规律时，则称此类矩阵为特殊矩阵，反之称为稀疏矩阵。
这里设计了一个稀疏矩阵相关操作的软件，该软件具有简单的稀疏矩阵相关运算功能。本稀疏矩阵操作软件采用VC++作为软件开发环境，采用算数表达式处理算法来实现稀疏矩阵的加法、减法、乘法以及转置运算。操作简单，界面清晰，易于为用户所接受。
关键字：三元组、稀疏矩阵、数据结构
目 录
第一章 课题描述 ............................................................................................................................. 2
1.1 课程设计的目的 ······················· 2 1.2 问题描述 ·························· 2 1.3 基本要求 ·························· 2
第二章 问题分析和任务定义 ......................................................................................................... 3
2.1 结构设计 ·························· 3 2.2 算法思想 ·························· 3 第三章 逻辑设计 ............................................................................................................................. 4
3.1 模块划分·························· 4 3.2 函数调用图 ························· 4 3.3 流程图··························· 5 第四章 详细设计 ............................................................................................................................. 6
4.1 定义矩阵·························· 6 4.2 创建稀疏矩阵 ························ 6 4.3 求矩阵的转置 ························ 7 4.4 矩阵的相乘 ························· 7 4.5 矩阵的相加 ························· 9 第五章 程序编码 ........................................................................................................................... 13 第六章 程序调试与测试 ............................................................................................................... 22
6.1 运行该程序的操作平台 ···················· 22 6.2 错误分析 ·························· 22 第七章 结果分析 ........................................................................................................................... 23
7.1 程序运行结果 ························ 23 7.2 时间及空间复杂度分析 ···················· 25 第八章 总结 ................................................................................................................................... 26