稀疏矩阵基本操作和转置.doc

PAGE 北京理工大学珠海学院 《数据结构》实验报告 题目：稀疏矩阵基本操作的实现和快速转置 所在学院： 计算机科学与技术学院 专业班级： 学 号： 学生姓名： _  目录 TOC \o 1-3 \h \z \u 1．前 言 1 2．概要设计 2 2.1 数据结构设计 2 2.2 算法设计 2 2.2.1 创建稀疏矩阵的算法 2 2.2.2 求稀疏矩阵的和的算法 3 2.2.3 销毁稀疏矩阵的算法 3 2.2.4 快速求稀疏矩阵的转置矩阵的算法 3 2.3 ADT描述 4 2.4 功能模块分析 5 3．详细设计 5 3.1 数据存储结构设计 5 3.2主要算法流程图（或算法伪代码） 6 4．软件测试 8 5．心得体会 9 参考文献 9 附 录 9 PAGE 15 1．前 言 “数据结构”是计算机专业一门重要的专业技术基础课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法；介绍了常用的多种查找和排序技术，并进行性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础，数据结构课程是计算机专业的一门核心的关键性课程。 《数据结构》课程是计算机科学与技术专业、软件工程专业等相关专业的一门专业基础课，学好数据结构课程，将为后续的专业课程，如数据库系统、操作系统、编译原理等，打下良好的知识基础，而且还为软件开发和程序设计提供了必要的技能训练。是一门理论性和实践性都很强的一门课程。它涉及在计算机中如何有效地表示数据，如何合理地组织数据和处理数据，还涉及初步的算法设计和算法性能分析。 C与C++语言程序设计和离散数学的基础都将影响到本课程的学习效果，同时《数据结构》也是一门自学起来比较困难的一门课程。所以学生在以学习过程中，应当在认真听取老师课堂讲解的基础上，充分运用辅导资料、网络教学资源、多媒体课件等进行深入学习理解和掌握，并利用实习机会进行上机操作，理解和巩固算法 2．概要设计 2.1 数据结构设计 本程序对三元组的实现采用的是通过建立一个存放数据元素及下标的数组来存放对应的元素，再定义矩阵的行数，列数，非零元数来实现数组的压缩存储。 struct Triple { int i,j; ElemType e; }; typedef struct { Triple data[MAX_SIZE+1]; int mu,nu,tu; }TSMatrix; 2.2 算法设计 2.2.1 创建稀疏矩阵的算法 （1）算法思想分析 输入矩阵的M.mu行数，M.nu列数，M.tu非零元个数。然后保存非零元对应的下标i,j，和数据元素，创建3元表。 （2）要点描述 if(T.i1||T.iM.mu||T.j1||T.jM.nu)，要判断所输入元素是否越界，若越界while循环返回重新输入。 （3）时间和空间复杂度分析 时间复杂度O（tu*k） 2.2.2 求稀疏矩阵的和的算法 （1）算法思想分析 判断栈顶是否为空，若为空，用realloc重新分配内存空间，若不为空增加栈顶元素。 （2）要点描述 每增加一个元素之后，栈顶要top++而不是top+1，因为栈顶是指的是即将存放元素的位置，所以加完元素后，栈顶也要加1。 （3）时间和空间复杂度分析 时间复杂度O（n） 2.2.3 销毁稀疏矩阵的算法 （1）算法思想分析 M.mu=M.nu=M.tu=0; 把行数，列数，非零元设为零即可。 （2）要点描述 （3）时间和空间复杂度分析 时间复杂度o(1) 2.2.4 快速求稀疏矩阵的转置矩阵的算法 （1）算法思想分析 通过num[col]表示矩阵M中第col列中非零元的个数，和cpot[col]表示首非零元的位置，通过for循环进行控制数组的行列互换，来进行转置。 （2）要点描述 在求num[col]和cpot[col]，num[col]实际是一个记数的，每次遇到一个该列的非零元则对应++ num[col]，来记住每列的非零元的个数。而cpot[col]则通过cpot[col]-1也就是前一行的非零元位置加num[col]对应的非零元个数而求得。 （3）时间和空间复杂度分析 时间复杂度O（n） 2.3 ADT描述 ADT