东莞理工学院城市学院
《数据结构》课程设计
题 目： 二叉排序树
专 业： 计算机科学与技术（本） 年 级：2010级 计算机科学与技术 专业（1）班 个人姓名： 何振江 指导教师： 张娟 老师
时 间： 2010至2011第二学期第18周 地 点： 实验楼615机房
东莞理工学院城市学院计算机与信息科学系制
2011年 6月
实习报告的内容
一、 问题描述。
本次课程设计中我们小组要做的题目如下： 题目十七: 稀疏矩阵运算
1. 矩阵的转置运算是变换元素的位置，把位于（i，j）的元素换到（j，i）位置上，
也就是说。把元素的行和列对换。分别调用voie transmit(Spmatrix a,Spmatrix *b)和void fasttran(Spatrix a,Spmatrix *b)的完成。
2. 若稀疏矩阵采用三元组表示，请写出求两个具有相同行列数的稀疏矩阵相加的
算法。
由于任务模块化如下：
1.输入函数 2.界面的设计 3.初始化函数
4.转置函数voie transmit(Spmatrix a,Spmatrix *b)和void fasttran(Spatrix a,Spmatrix *b) 5加法函数 6减法函数 7.整合并调试。 问题描述：假设以顺序存储结构来表示三元组表，则得到稀疏矩阵的一种压缩存储方式，即三元组顺序表。在矩阵足够稀疏的情况下，对存储空间的需求量比通常的方法少得多。矩阵越大，越稀疏，其优越性越明显。
二、 设计。 设计思想：
（1） 存储结构。
本系统采用三元组结构类型（triples）存储稀疏矩阵的具体信息。其中：全部结点的信息用三元组结构数组存储；每个三元组数组里面包含行下标（row），列下标(colum)和对应的数值(value)，它们是整型数据。全部的信息用结构体包含了（tri），包括数组结点（matrix[]）和总共的行数（row_size）,列数（colum_size）以及非零元素的个数(non_zero_amount)。 结点结构如下：
#define ElemType int typedef struct {
int row, colum; //非零元的行下标(row)和列下标(colum) ElemType value; //非零元的值(value)
}Triple; //结构体(Triple) typedef struct {
Triple data[MAXSIZE+1]; //结构体(Triple)的变量
int row_size, colum_size, non_zero_amount; //矩阵的行
(row_size)列(colum_size)非零个数(non_zero_amount) }TSMatrix; //结构体(TSMatrix)
（2） 主要算法基本思想。
本系统除了要完成稀疏矩阵的初始化功能外还设置了4个子功能菜单。稀疏矩阵的初始化由函数creat_matrix( )实现。依据读入的行数和列数以及非零元素的个数，分别初始化每个非零元素的信息。4个子功能的设计描述如下。 1. 创建函数void Creat(TSMatrix &M) 2. 稀疏矩阵的加法：
此功能由函数add_matrix( )实现，该功能用到插入排序，将第二个矩阵的值插入到第一个，最后排序。当用户选择该功能，系统之前初始化要进行加法的加数矩阵的信息。然后检测这两个矩阵是否符合矩阵相加的规则，如果符合，进行加法。否则重新输入第二个矩阵来保证两个矩阵可以相加。最后输出结果。 3. 转置函数transmat(TSMatrix a,TSMatrix *b)
该算法使用了一个二重循环语句。外循环来控制扫描的次数，每执行完一次循环体，矩阵N相当于排好了一行；内循环则用来控制扫描a.data的第1~non_zero_amount个，判断每个元素在该轮中是否需要转换。
4. 转置函数Fasttran(TSMatrix M,TSMatrix *T)通过标记num[]和pot[]，使得每次装置后的元素不连续存放。直接放到b中的相应位置上，这样既可以避免元素移动，又只需对a.data扫描一次。
5. 减法函数void minus_matrix(TSMatrix one,TSMatrix two, TSMatrix &three); 减法函数比加法函数多一个判断是否相减后的值为0，如果为0，则data里的数据往前移动。
6. 初始化函数ChuSH(TSMatrix a,TSMatrix *b)
通过这个行数使得稀疏矩阵按照行和列的顺序存放。
7. 退出函数（即退出稀疏矩阵的应用系统，由exit(1)函数实现.）
设计表示：
（1） 函数声明和规格说明。
void Creat(TSMatrix &M); //创建一个矩阵
void chush(TSMatrix a,TSMatrix *b); //初始化稀疏矩阵(进行顺序排列)
void add_matrix(TSMatrix one,TSMatrix two, TSMatrix &three);/ /加法函数one+two=three
void minus_matrix(TSMatrix one,TSMatrix two, TSMatrix &three); //减法函数 void print_matrix(TSMatrix T); //输出函数
void transmat(TSMatrix a,TSMatrix *b); //transmat转置函数 void Fasttran(TSMatrix M,TSMatrix *T); //Fasttran转置函数 void Destory_SMatrix(TSMatrix &M);
（2） 每个函数所调用和被调用的函数，以及调用关系图。
main() 创建 加法 Creat 转置transmat 转置Fasttran 减法 退出 Chush add_matrix transmat Fasttran Minus_matrix Exit Destory_SMatrix print_matrix
实现注释：
（１） 所有操作均以建立好一个稀疏矩阵为基础；
（２） 非零元素的个数不能超过100个，如果想改大一点，可以到源代码中修改
MAXSIZE的值。
（３） 程序中将矩阵数据域定义为ElemType类型，用户可以改变ElemType的值从
而改变数据域的类型；
（４） 矩阵可以随用户输入。通过输入总共的行数（row_size）,列数（colum_size）
以及非零元素的个数(non_zero_amount)来创建想要的矩阵，用户行数、列数和非零元素的个数不可以小于零否则重新输入，再输入行下标（row），列下标(colum)和对应的数值(value)，行下标与列下标必须不大于总行数和总列数，否则重新输入。
三、 调试报告。
我使用了两种算法来实现稀疏矩阵的转置，两个算法的区别不是很大，但深入了解了函数后就会发现，两个的时间复杂度相差比较大，后者的实现效率比较高，前者因为每次都要重新比较，所以时间上占用的比较多！
时间复杂度分析： 1、 时间分析
Transmit算法：因算法的主要工作是在col和p的二重循环中完成的，故算法的执行时间为O(n*t)。当非零元素个数non_zero_amount的数量级为m*n是，其执行时间变为O（m*n*n）。这比直接用二维数组表示矩阵的转置算法的时间量级O（m*n）要差。
Fanttran算法：算法的执行时间为O（n+t）。在non_zero_amount和m*n等量级时，该算法的执行时间上升到O（m*n）,但在non_zero_amount Transmit算法：分析这个算法，除少数附加空间，它所需要的存储量仅为两 个三元组表A,B所需要的空间。因此，当非零元素个数non_zero_amount Fanttran算法：此算法比Transmit算法多用了两个辅助数组。 3、 缺点与优点分析 加减算法通过一层一层的判断后插入，中间还加入了一些移动，所以对于这两个算法时间复杂度方面比较大，但通过了层次分明的判断后，代码的可读性也比较好，虽然比较长，但看懂后很好理解！ 四、 系统环境（源代码和运行结果）抓图。 源代码： 结果： 界面（上）选择1加法的时候（下） 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构课程设计报告模板在线全文阅读。
相关推荐：