数据结构课程设计报告

东莞理工学院城市学院。

题目：二叉排序树

专业：计算机科学与技术（本）

年级：2010级计算机科学与技术专业（1）班。

个人姓名：何振江。

指导教师：张娟老师

时间： 2010至2011第二学期第18周

地点：实验楼615机房

东莞理工学院城市学院计算机与信息科学系制。

2023年 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相当于排好了一行；内循环则用来控制扫描的第1~non_zero_amount个，判断每个元素在该轮中是否需要转换。

4. 转置函数fasttran(tsmatrix m,tsmatrix *t)通过标记num和pot，使得每次装置后的元素不连续存放。直接放到b中的相应位置上，这样既可以避免元素移动，又只需对扫描一次。

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 *btransmat转置函数。

void fasttran(tsmatrix m,tsmatrix *tfasttran转置函数。

void destory_smatrix(tsmatrix &m);

2）每个函数所调用和被调用的函数，以及调用关系图。

实现注释：1）所有操作均以建立好一个稀疏矩阵为基础；

2）非零元素的个数不能超过100个，如果想改大一点，可以到源**中修改maxsize的值。

3）程序中将矩阵数据域定义为elemtype类型，用户可以改变elemtype的值从而改变数据域的类型；

4）矩阵可以随用户输入。通过输入总共的行数（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_amount2、空间分析。

transmit算法：分析这个算法，除少数附加空间，它所需要的存储量仅为两个三元组表a,b所需要的空间。因此，当非零元素个数non_zero_amountfanttran算法：

此算法比transmit算法多用了两个辅助数组。

3、缺点与优点分析。

加减算法通过一层一层的判断后插入，中间还加入了一些移动，所以对于这两个算法时间复杂度方面比较大，但通过了层次分明的判断后，**的可读性也比较好，虽然比较长，但看懂后很好理解！

四、系统环境（源**和运行结果）抓图。

源**：结果：

界面（上）选择1加法的时候（下）

选择4减法的时候（上）选择退出的时候（下）

选择退出的时候。

五、结果分析。

1. 界面，由以下函数实现：

printf("");

printf("\tn");

printf("\t稀疏矩阵的加、减、转、乘n");

printf("\tn");

printf("\t1、稀疏矩阵的加法n");

printf("\t2、稀疏矩阵的转置(transmat函数n");

printf("\t3、稀疏矩阵的转置(fasttran函数n");

printf("\t4、稀疏矩阵的减法n");

printf("\t5、退出该应用程序n");

printf("\tn");

printf("输入要进行的项目的编号：")

scanf("%d",&flag);

该函数由简单的输出函数完成。

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

其他用户还读了