11计本《数据结构课程设计报告》.doc

安徽省巢湖学院计算机与信息工程学院 课程设计报告 课程名称 《》 课题名称 专业班级 1工程*班 学 号 姓 名 联系方式 指导教师 完成日期: 年 月 日 目录 1 数据结构课程设计任务书 1 1.1 题目 1 1.2 要求 1 2 总体设计 1 2.1 功能模块设计 1 2.2 所有功能模块的流程图 1 3 详细设计 1 3.1 程序中所采用的数据结构及存储结构的说明 1 3.2 算法的设计思想 2 3.3 稀疏矩阵各种运算的性质变换 2 4 调试与测试： 2 4.1 调试方法与步骤： 2 4.2 测试结果的分析与讨论： 3 4.3 测试过程中遇到的主要问题及采取的解决措施： 3 5 时间复杂度的分析： 4 6 源程序清单和执行结果 4 7 总结 8 8 参考文献 8 1 数据结构课程设计任务书 1.1 题目 【示例】用三元组实现稀疏矩阵的转置、相加、相乘 1.2 要求 【示例】 （1）用creat函数创建三元组； （2）用print函数打印计算结果； （3）用add函数实现稀疏矩阵的相加运算； （4）用mult 函数实现稀疏矩阵的相乘运算； （5）用?Transm函数实现稀疏矩阵的转置运算； （6）用menu函数创建一个菜单 2 总体设计 2.1 功能模块设计 根据课程设计题目的功能要求，各个功能模块的组成框图如下： 【示例】 2.2 所有功能模块的流程图 【示例1】略 3 详细设计 模块功能说明：如函数功能、入口及出口参数说明，函数调用关系描述等； 【示例1】 3.1 程序中所采用的数据结构及存储结构的说明 以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方式——三元组顺序表。 //-----------稀疏矩阵的三元组顺序存储表示------------- #define MAXSIZE 100 /*假设非零元个数的最大值为20*/ typedef struct { int i,j; /*该非零元的行下标和列下标*/ int v; }Triple; typedef struct { Triple data[MAXSIZE+1]; /*非零元三元组表,data[0]未用*/ int mu,nu,tu; /*矩阵的行数,列数和非零元个数*/ }TSMastrix; 在此，data域中表示非零元得三元组是以行序为主序顺序排列的，这样有利于进行某些矩阵运算。 3.2 算法的设计思想 a) 相加运算 对于两个稀疏矩阵相加，即行与行，列与列相加 b）相乘运算 若设Q=M*N 其中M是m1*n1矩阵，N是m2*n2矩阵，只有当n1=m2时才可以相乘。 乘积矩阵Q中元素 Q（i，j）=∑M（i，k）*N（k，j） 1≤i≤m1，1≤j≤n2 在算法中，不论M（i，k）和 N（k，j）的值是否为零，都要进行一次乘法运算，而实际上，这两者有一个值为零时，其乘积也为零。因此，在对稀疏矩阵进行运算时，应免去这种无效操作，只需在M.data和N.data中找到相应的各对元素(即M.data中的j值和 N.data中的i值相等的各对元素)相乘即可。 ?c) 转置运算 对于一个m*n的矩阵M，它的转置矩阵T是一个n*m的矩阵，且T（i，j）=M（j，i）， 1≤i≤n，1≤j≤m。完成一个稀疏矩阵的转置分为三步： （1）将矩阵的行列值相互交换； （2）将每个三元组中的i和j相互调换； （3）重排三元组之间的次序便可实现矩阵的转置； 3.3 稀疏矩阵各种运算的性质变换 a)加法运算 两个稀疏矩阵的加和矩阵仍然是稀疏矩阵 b）乘法运算 两个稀疏矩阵的乘积矩阵不是稀疏矩阵 c）转置运算 一个稀疏矩阵的转置矩阵仍然是稀疏矩阵 4 调试与测试： 4.1 调试方法与步骤： 【示例1】简述测试步骤 第一步：测试矩阵加法： 过程（略） 第二步：测试矩阵乘法： 过程（略） 第三步：测试矩阵转置： 过程（略） 4.2 测试结果的分析与讨论： （测试要写出测试用例及每个用例结果的的截图） 4.3 测试过程中遇到的主要问题及采取的解决措施： （略） 5 时间复杂度的分析： a)加法运算 由于两矩阵行列相等，故时间复杂度为O（行*列） b）乘法运算 设M是m1*