稀疏矩阵基本操作试验报告

1、稀疏矩阵基本操作 实验报告一、实验内容稀疏矩阵的压缩储存结构，以及稀疏矩阵的三元组表表示方法下的转置、相加、相 乘等算法二、实验目的1. 熟悉数组、矩阵的定义和基本操作2. 熟悉稀疏矩阵的储存方式和基本运算3. 理解稀疏矩阵的三元组表类型定义，掌握稀疏矩阵的输入、输出和转置算法三、实验原理1. 使用三元组储存矩阵中的非零元素（三元组分别储存非零元素的行下标，列下标和 元素值）。除了三元组表本身，储存一个稀疏矩阵还需要额外的三个变量，分别储 存矩阵的非零元个数，矩阵的行数和矩阵的列数。2. 稀疏矩阵的创建算法：第一步： 根据矩阵创建一个二维数组，表示原始矩阵第二步： 取出二维数组中的元素（从第一

2、个元素开始取） ，判断取出元素是否为非 零元素，如果为非零元素，把该非零元素的数值以及行下标和列下表储存到三元数 组表里，否则取出下一个元素，重复该步骤。第三步： 重复第二步，知道二维数组中所有的元素已经取出。3. 稀疏矩阵倒置算法：第一步： 判断进行倒置的矩阵是否为空矩阵，如果是，则直接返回错误信息。第二步： 计算要倒置的矩阵每列非零元素的数量， 存入到 num 数组（其中 numi 代 表矩阵中第 i 列非零元素的个数） 。以及倒置后矩阵每行首非零元的位置， 存入 cpot 数组中 （其中 cpot 表示倒置后矩阵每行非零元的位置， 对应表示原矩阵每列中第一 个非零元的位置） 。第三步：

3、确定倒置后矩阵的行数和列数。第四步： 取出表示要导致矩阵中三元组表元素e, I, j（第一次取出第一个，依次取出下一个元素） ，从第二步 cpot 数组中确定该元素倒置后存放的位置（ cpotj ），把 该元素的行下标和列下标倒置以后放入新表的指定位置中。 cpotj 变量加一。 第五步： 重复第四步，直到三元组表中所有的元素都完成倒置。第六步： 把完成倒置运算的三元组表输出。4. 稀疏矩阵加法算法：第一步： 检查相加两个矩阵的行数和列数是否相同，如果相同，则进入第二步，否 则输出错误信息。第二步： 定义变量 i 和 j，用于控制三元组表的遍历。第三步： 比较变量矩阵 M 中第 i个元素和矩阵

4、 N中第 j 个元素，如果两个元素是同 一行元素，如果不是则进入第四步，如果是，再继续比较两个元素是否为同一列元 素，如果是，把两个元素值相加，放到三元组表中；否则把列下表小的元素依次放 到三元组表中。进入第五步第四步： 如果矩阵 M 中第 i个元素的行下标大于矩阵 N中第 j 个元素的行下标，则 把矩阵 N 中第 j 个元素所在行的所有非零元素添加到三元组表中； 如果矩阵 M 中第 i 个元素的行下标小于矩阵 N 中第 j 个元素的下标，则把 M 中第 i 个元素所在行的 所有非零元素依次添加到三元组表中。第五步： 重复第三步，直到矩阵 M 和矩阵 N 中所有元素都非零元素添加到三元组 表中

5、。第六步： 输出运算结果5. 稀疏矩阵乘法算法：第一步： 检查矩阵 M 和矩阵 N 能否参与乘法运算（即矩阵 M 的列数等于矩阵 N 的 行数），如果两个矩阵可以参与乘法运算，进入下一步，否则输出错误信息第二步： 检查两个矩阵相乘以后是否为零矩阵，如果相乘结果是零矩阵，直接返回 一个零矩阵。第三步： 分别计算矩阵 M 和矩阵 N 中每行非零元的个数（分别存放到 num_m 和 num_n 数组中），并计算出每行首非零元的位置 （分别存放到 cpot_m 和 cpot_n 中）。 第四步： 依次取矩阵 M 中的非零元 （第一次取出矩阵 M 中的第一个非零元） ，求出 该非零元所在行和所在列乘积的

6、和，然后把值放到结果三元组表的特定位置。第五步： 重复第四步，直到矩阵 M 中所有非零元都已经参与运算。第六步： 输出结果四、程序流程图五、 实验结果5.1 程序主菜单5.2 稀疏矩阵三元组的创建和倒置5.3 稀疏矩阵的加法运算并以三元组输出结果5.4 稀疏矩阵的乘法运算并以矩阵方式输出结果六、操作说明1.在创建稀疏矩阵的时候，可以每次输入一个数据，也可以一次输入多个数据，程序会自动根据输入元素的个数对矩阵数据进行填充2.每次矩阵运算失败时（无论是输入的矩阵不符合矩阵运算的条件，参与运算其中一 个矩阵为空矩阵，或者分配不到临时空间） ，程序都会返回到主菜单。输入的数据 都会被清空。七、 附录：

7、代码#include #include #include #define MAXSIZE 1000#define OK 0#define MALLOC_FAIL -1矩阵的创建和转置 n );printf( 2. 矩阵的加法运算并以三元组输出结果 n);printf( 3. 矩阵的乘法运算并以矩阵输出结果 n );printf( n );printf( Q. 退出程序 n );printf( n );printf( 请输入选项： );scanf(%c, &ch);switch (ch)case 1 :system(cls );M = TSMatrix_CreateFromInput();if

8、(M != NULL)printf( nn 以三元组输出稀疏矩阵： n ); TSMatrix_PrintTriple(M);printf( n 倒置后稀疏矩阵的三元组输出： n ); TSMatrix_FastTranspose(*M, T); TSMatrix_PrintTriple(T);system(pause );elseprintf( 创建矩阵过程发生错误 ); system(pause );break;case 2 : system(cls );M = TSMatrix_CreateFromInput();N = TSMatrix_CreateFromInput();if (M

9、= NULL | N = NULL)printf( 创建矩阵过程中发生错误！ n); system(pause );break;info = TSMatrix_Add(*M, *N, T);if (info = MATRIX_NOT_MATCH)printf( 这两个矩阵不能运算呢！else if (info = OK)printf( n 运算结果： n );TSMatrix_PrintTriple(T);system(pause);break;case 3 :system(cls );M = TSMatrix_CreateFromInput();N = TSMatrix_CreateFrom

10、Input();if (M = NULL | N = NULL)printf( 创建矩阵过程中发生错误！ n); system(pause );break;info = TSMatrix_Multply(*M, *N, T);if (info = MATRIX_NOT_MATCH)printf( 这两个矩阵不能运算呢！ n ); n );else if (info = OK)printf( n 运算结果： n ); TSMartix_PrintMatrix(T);system(pause);break;case q :caseQ:exit(0);return 0;= *(a + i * col

11、 + j);P-dataP-num.row = i + 1;P-dataP-num.col = j + 1;ow, M-datai.col, M -datai.e); printf( =n);ol+;ol;T-datat.col = i.row;T-datat.row = i.col;T-datat.e = i.e;+cpoti.col;ow = j.row)ol = j.col)Q-datak.row = i.row;Q-datak.col = i.col; Q-datak.e = i.e + j.e; Q-num+;i+;j+; k+;ol j.col)Q-datak.row = j.ro

12、w;Q-datak.col = j.col;Q-datak.e = j.e; Q-num+;j+;k+;ol datak.row = i.row;Q-datak.col = i.col;Q-datak.e = i.e; Q-num+;i+;k+;ow j.row)Q-datak.row = j.row;Q-datak.col = j.col;Q-datak.e = j.e; Q-num+;k+;j+;ow datak.row = i.row;Q-datak.col = i.col;Q-datak.e = i.e;Q-num+;i+; k+;ow = i.row;Q-datak.col = i.

13、col;Q-datak.e = i.e;Q-num+;i+;k+;while (j datak.row = j.row;Q-datak.col = j.col;Q-datak.e = j.e;Q-num+;j+;k+;return OK;ow+;for (i = 0; i ; i+) num_ni.row+;cpot_m1 = cpot_n1 = 0;for (i = 2; i = ; i+)cpot_mi = cpot_mi - 1 + num_mi - 1;for (i = 2; i dataQ-num.row = ri;Q-dataQ-num.col = rj;Q-dataQ-num.e

14、 = s; Q-num+;ow = (i / M -colnum) + 1) &M -datak.col = (i % M -colnum) + 1) printf( %3d, M -datak.e);k+;elseprintf( %3d, 0);if (i % M-colnum) + 1 = M -colnum) printf( n );TSMatrix *TSMatrix_CreateFromInput() int *a, i, j, k; TSMatrix *T;ResetCursor();printf( 请输入新创建的矩阵的行数和列数，分别输入并利用空格间开：);/ 输入的同时对数据的

15、有效性进行检查 while (2 != scanf(%d%d, &i, &j) printf( 无效输入，请重新输入！ n );/ 分配临时储存输入数据的空间a = (int *)malloc(i * j * sizeof(int );/ 如果分配失败，则返回一个空指针 if (a = NULL)return NULL;/ 开始从键盘中读入元素for (k = 0; k i * j; k+) ResetCursor();printf( 请从键盘输入第 %d 行第 %d 列元素： , (k / j) + 1, (k % j) + 1);while (1 != scanf(%d , (a + k) printf( 无效输入，请重新输入！ n);T = TSMatrix_Create(a, i, j);/ 释放用于临时储存输入的空间 free(a);r