综合训练 稀疏矩阵运算器

1、数据结构综 合 训 练 报 告理学院课程设计报告参考格式一、题目：稀疏矩阵运算器二、目的和要求：使学生掌握稀疏矩阵的存储方法及其运算。要求利用C+语言实现一个能实现稀疏矩阵简单运算的程序。具体要求如下：1、采用顺序存储方式。2、提供稀疏矩阵的输入功能。输入方式可以采用三元组方式，也可采用用户直接输入方式等。3、实现稀疏矩阵的转置功能。可以将用户输入的稀疏矩阵进行转置，并将转置后的稀疏矩阵显示到屏幕。4、稀疏矩阵的加法运算功能。提供用户连续输入两个稀疏矩阵的功能，并能将所求的两个稀疏矩阵的和显示出来。5、稀疏矩阵的乘法运算功能。提供用户连续输入两个稀疏矩阵的功能，并能将所求的两个稀疏矩阵的和显示

2、出来。6、稀疏矩阵输出要求输出为完整形式。三、概要设计：稀疏矩阵的顺序储存结构，就是对其相应的三元组线性表进行顺序存储。 每个非零元素的三元组用如下结构定义：struct Tripleint row ,col;ElemType val;其中，row和col用来分别存储元素的行号和列号，val用来存储元素值。 一个稀疏矩阵的顺序存储类型定义如下。struct SMatrixint m,n,t;Triple smmaxterms+1;其中，m、n和t分别用来存储稀疏矩阵的行数、列数和非零元素的个数，sm数组用来顺序存储每个三元组元素。稀疏矩阵的加法、减法、数乘和乘法模块调用了稀疏矩阵的初始化和输出

3、函数。四、算法描述：1.稀疏矩阵的输入（1）首先把形参m，n传递给稀疏矩阵的行数和列数，确定稀疏矩阵的规模。（2）定义整型变量row，col，val分别用来存储三元组的行号、列号和元素值，定义整型变量k表示第k个三元组元素，其中k初值为零。（3）定义一个while循环，k自加，然后把每次输入的row，col，val的值分别赋值给第k个三元组元素的行号、列号和元素值。（4）当输入完所有的三元组后，以输入特殊的三元组（0,0,0）结束整个输入过程，并且把k的值赋值给稀疏矩阵非零元素的个数。2.稀疏矩阵的输出（1）定义一个二重for循环来输出稀疏矩阵每一行，每一列的元素。（2）在二重for循环中再定

4、义一个for循环来判断每一个非零元素。（3）如果这个非零元素的行号和列号分别与这个二重循环的行数和列数相等，那么就输出这个非零元素的值。否则，就输出零。3.稀疏矩阵的快速转置方法（1）首先把稀疏矩阵的行数、列数和非零元素的个数m，n，t赋值给转置矩阵的列数、行数和非零元数的个数。（2）如果这个矩阵是零矩阵（即非零元素的个数为零的矩阵），那么转换完毕返回。否则，为num和pot向量动态分配存储空间。然后对num向量进行初始化，置每个分量为0.（3）第1遍扫描数组M.sm，统计出每一列（即转换后的每一行）非零元素的个数。（4）计算每一列（即转换后的每一行）的第1个非零元素在S.sm中存储位置。（5

5、）对M.sm进行第2遍扫描，把每个元素行、列值互换写入到S.sm的确定位置。（6）删除动态分配的数组，返回转置矩阵。4.稀疏矩阵的加法运算（方法1）（1）如果两个矩阵尺寸不同，就给出错误信息。（2）否则，把这两个稀疏矩阵线性表上下排列形成一个新的线性表。（3）做一个循环，把这个线性表中具有相同行号和相同列号的元素进行相加，并进行判断。（4）如果相加的结果不为零，那么就把行号、列号和这个值赋值给一个新线性表的三元组的行号、列号和元素值，并且非零元素个数自加。（5）最后，把原来矩阵的尺寸复制给这个新的线性表的规模。那么这个线性表即为所求，输出这个线性表。5.稀疏矩阵的加法运算（方法2）（1）如果两

6、个矩阵尺寸不同，就给出错误信息。（2）否则，定义一个while循环，一直循环到两个稀疏矩阵线性表中的某一个线性表扫描完毕。（3）判断两个线性表中的两个三元组的行号是否相等，如果不相等，就把行号较小的那个三元组传递给一个新的线性表，把较大的三元组在与另一个线性表的下一个三元组再进行比较。（4）如果行号相等的话，再判断两个三元组的列号是否相等。如果不相等，就把列号较小的那个三元组传递给那个新的线性表，把较大的三元组在与另一个线性表的下一个三元组再进行比较。（5）如果列号相等的话，就把两个三元组的元素值相加。（6）如果相加的值不为零，就把这个值赋值给新线性表的一个新的三元组的元素值。把三元组的行号和

7、列号也依次赋值给新三元组的行号和列号。（7）如果相加的值为零，就再比较两个线性表的下一个三元组。（8）当这个while循环循环完毕后，把另一个线性表的剩余元素依次传递给那个新的线性表。（9）这个新的线性表即为所求，输出这个新的稀疏矩阵。6.稀疏矩阵的减法运算（1）如果两个矩阵尺寸不同，就给出错误信息。（2）否则，把这两个稀疏矩阵线性表上下排列形成一个新的线性表。其中，把第二个线性表中的每一个三元组的元素值变为它的相反数。（3）做一个循环，把这个线性表中具有相同行号和相同列号的元素进行相加，并进行判断。（4）如果相加的结果不为零，那么就把行号、列号和这个值赋值给一个新线性表的三元组的行号、列号和

8、元素值，并且非零元素个数自加。（5）最后，把原来矩阵的尺寸复制给这个新的线性表的规模。那么这个线性表即为所求，输出这个线性表。7.稀疏矩阵的数乘运算（1）做一个循环，把每一个三元组的元素值乘以k再赋值给它本身。（2）输出这个线性表。8.稀疏矩阵的乘法运算（1）定义一个二重for循环，外层循环i从1循环到第一个矩阵的最大行数，里层循环c从1循环到第二个矩阵的最大列数。（2）在二重for循环里，再定义一个for循环，扫描第一个线性表中的所有元素，如果有三元组j的行号和二重for循环中的i相等，那么再定义一个for循环，扫描第二个线性表中的所有元素，判断是否有三元组a，使三元组a的行号和三元组j的列

9、号相同，且三元组a的列号和二重for循环中的c相同。（3）如果存在三元组a，那么就把三元组j的元素值和三元组a的元素值相乘再累加。（4）如果这个累加值不为零的话，就把二重for循环中的i、c和步骤（3）中的累加值分别赋值给一个新线性表中的新创建的三元组的行号、列号和元素值。（5）这个新的线性表即为所求，输出这个线性表。五、测试结果及分析：1.测试数据测试的数据如下图所示：经检验，输出的结果是正确的。2.时间复杂度分析（1）稀疏矩阵的快速转置方法O（n + t）（2）稀疏矩阵的加法运算（方法一）（M1.m * M1.n+1）*（M1.t + M2.t）（3）稀疏矩阵的加法运算（方法二）（M1.t

10、+M2.t）（4）稀疏矩阵的减法运算（M1.m * M1.n +1）*（M1.t + M2.t）（5）稀疏矩阵的数乘运算O（t）（6）稀疏矩阵的乘法运算M1.m * M2.n * M1.t * M2.t3.每个模块设计和调试时存在问题的思考前两个模块，即稀疏矩阵的加法和减法运算比较简单，但也因思路不够清晰而出现过错误，后来经过研究，例子分析，最后得出此算法。实现乘法运算是相对困难的，也是本次综合训练的难点，本组同学花了半天的时间思索，才想到了思路，经过几十次的调试分析，最后才能完成。虽然时间复杂度有点大，但我们付出了自己的汗水和心血。4.算法的改进设想我们组第一次做加法运算程序的时候，二重循环

11、是对稀疏矩阵的行数和列数而言的。所以，当稀疏矩阵的阶数很大时，这个算法的时间复杂度特别高。经过我们小组的反复讨论和分析后，对加法运算程序进行了改进，这个新的算法的循环是对稀疏矩阵的非零元素个数而言的。当稀疏矩阵的阶数很大时，其非零元素个数相对而言要小得多，所以这个算法的时间复杂度相对而言很小。改进思想：利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。六、心得体会和参考资料我们小组的稀疏矩阵运算器的设计和实现主要依赖于三元组线性表的顺序存储结构。在本次综合训练的过程中，使我们更加了解了数据的存储结构和程序调试的技巧，而且小组成员之间团结协作，互相帮助，每个人都有很大的收获。数据结构这门课最主要的内容在于算法思想，而程序编写次之。在编写程序时，如果算法思想是正确的，那么这个程序就已经成功了一多半。算法思想在数据结构中占有重要地位，所以，要想学好数据结构这门课程，平