《稀疏矩阵基本操作技巧实验报告.doc》由会员分享，可在线阅读，更多相关《稀疏矩阵基本操作技巧实验报告.doc（29页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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个元素和矩阵N中第j个元素，如果两个元素是同一行元素，如果不是则进入第四步，如果是，再继续比较两个
4、元素是否为同一列元素，如果是，把两个元素值相加，放到三元组表中；否则把列下表小的元素依次放到三元组表中。进入第五步第四步：如果矩阵M中第i个元素的行下标大于矩阵N中第j个元素的行下标，则把矩阵N中第j个元素所在行的所有非零元素添加到三元组表中；如果矩阵M中第i个元素的行下标小于矩阵N中第j个元素的下标，则把M中第i个元素所在行的所有非零元素依次添加到三元组表中。第五步：重复第三步，直到矩阵M和矩阵N中所有元素都非零元素添加到三元组表中。第六步：输出运算结果5. 稀疏矩阵乘法算法：第一步：检查矩阵M和矩阵N能否参与乘法运算（即矩阵M的列数等于矩阵N的行数），如果两个矩阵可以参与乘法运算，进入下一
5、步，否则输出错误信息第二步：检查两个矩阵相乘以后是否为零矩阵，如果相乘结果是零矩阵，直接返回一个零矩阵。第三步：分别计算矩阵M和矩阵N中每行非零元的个数（分别存放到num_m和num_n数组中），并计算出每行首非零元的位置（分别存放到cpot_m和cpot_n中）。第四步：依次取矩阵M中的非零元（第一次取出矩阵M中的第一个非零元），求出该非零元所在行和所在列乘积的和，然后把值放到结果三元组表的特定位置。第五步：重复第四步，直到矩阵M中所有非零元都已经参与运算。第六步：输出结果四、 程序流程图五、 实验结果5.1 程序主菜单5.2 稀疏矩阵三元组的创建和倒置5.3 稀疏矩阵的加法运算并以三元组输
6、出结果5.4 稀疏矩阵的乘法运算并以矩阵方式输出结果六、 操作说明1. 在创建稀疏矩阵的时候，可以每次输入一个数据，也可以一次输入多个数据，程序会自动根据输入元素的个数对矩阵数据进行填充2. 每次矩阵运算失败时（无论是输入的矩阵不符合矩阵运算的条件，参与运算其中一个矩阵为空矩阵，或者分配不到临时空间），程序都会返回到主菜单。输入的数据都会被清空。七、 附录：代码#include #include #include #define MAXSIZE 1000#define OK 0#define MALLOC_FAIL -1/ 表示分配空间时发生错误#define EMPTY_MATRIX -2/
7、 表示正尝试对一个空矩阵进行运算操作#define MATRIX_NOT_MATCH -3/ 表示尝试对不符合运算条件的矩阵进行运算操作（例如非相同行数列数矩阵相加）/* - 结构体声明部分 - */typedef structint row;/ 非零元的行下标int col;/ 非零元的列下标int e;/ 非零元的值 Triple;typedef structTriple *data;/ 非零元素的元素表int rownum;/ 矩阵的行数int colnum;/ 矩阵的列数int num;/ 矩阵非零元的个数 TSMatrix, *PTSMatrix;/* - 函数声明部分 - */ 初
8、始化稀疏矩阵结构int TSMatrix_Init(TSMatrix *M);/ 以三元组的方式输出稀疏矩阵void TSMatrix_PrintTriple(TSMatrix *M);/ 以矩阵的方式输出稀疏矩阵void TSMartix_PrintMatrix(TSMatrix *M);/ 从一个二维数组（普通矩阵）创建一个稀疏矩阵TSMatrix *TSMatrix_Create(int *a, int row, int col);/ 从键盘录入数据创建一个稀疏矩阵TSMatrix *TSMatrix_CreateFromInput();/ 求稀疏矩阵 M 的转置矩阵 Tint TSMa
9、trix_FastTranspose(TSMatrix M, TSMatrix *T);/ 如果稀疏矩阵 M 和 N 的行数的列数相同，计算 Q = M + Nint TSMatrix_Add(TSMatrix M, TSMatrix N, TSMatrix *Q);/ 如果稀疏矩阵 M 的列数等于 N 的行数，计算 Q = M x N;int TSMatrix_Multply(TSMatrix M, TSMatrix N, TSMatrix *Q);/ 把光标位置移动到该行行首void ResetCursor();/* - 程序主函数 - */int main(void)int info;c
10、har ch;/ 从一个二维数组创建一个系数矩阵TSMatrix *M;TSMatrix *N;/ 用来接收运算结果的空间TSMatrix *T = (TSMatrix *)malloc(sizeof(TSMatrix);while (1)fflush(stdin);system(cls);printf( 稀疏矩阵基本操作演示 n);printf(1. 矩阵的创建和转置n);printf(2. 矩阵的加法运算并以三元组输出结果n);printf(3. 矩阵的乘法运算并以矩阵输出结果n);printf(n);printf(Q. 退出程序n);printf(n);printf( 请输入选项：);s
11、canf(%c, &ch);switch (ch)case 1:system(cls);M = TSMatrix_CreateFromInput();if (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 = TSMat
12、rix_CreateFromInput();N = TSMatrix_CreateFromInput();if (M = NULL | N = NULL)printf(创建矩阵过程中发生错误！n);system(pause);break;info = TSMatrix_Add(*M, *N, T);if (info = MATRIX_NOT_MATCH)printf(这两个矩阵不能运算呢！ n);else if (info = OK)printf(n运算结果：n);TSMatrix_PrintTriple(T);system(pause);break;case 3:system(cls);M
13、= TSMatrix_CreateFromInput();N = TSMatrix_CreateFromInput();if (M = NULL | N = NULL)printf(创建矩阵过程中发生错误！n);system(pause);break;info = TSMatrix_Multply(*M, *N, T);if (info = MATRIX_NOT_MATCH)printf(这两个矩阵不能运算呢！ n);else if (info = OK)printf(n运算结果：n);TSMartix_PrintMatrix(T);system(pause);break;case q:cas
14、e Q:exit(0);return 0;/ 初始化稀疏矩阵结构int TSMatrix_Init(TSMatrix *M)M-data = (Triple *)malloc(MAXSIZE * sizeof(Triple);if (!M-data)return MALLOC_FAIL;M-num = 0;M-colnum = 0;M-rownum = 0;return OK;/ 从一个二维数组创建一个稀疏矩阵TSMatrix *TSMatrix_Create(int *a, int row, int col)int i, j;TSMatrix *P = (TSMatrix *)malloc(
15、sizeof(TSMatrix);TSMatrix_Init(P);/ 设置稀疏矩阵的行数和列数P-rownum = row;P-colnum = col;for (i = 0; i row; i+)for (j = 0; j dataP-num.e = *(a + i * col + j);P-dataP-num.row = i + 1;P-dataP-num.col = j + 1;/ 把稀疏矩阵中的非零元个数加一P-num+;return P;/ 以三元组的方式输出稀疏矩阵void TSMatrix_PrintTriple(TSMatrix *M)int i;if (0 = M-num)
16、printf(稀疏矩阵为空！n);return;printf( i j v n);printf(=n);for (i = 0; i num; i+)printf(%3d %3d %3dn, M-datai.row, M-datai.col, M-datai.e);printf(=n);/ 求稀疏矩阵 M 的转置矩阵 Tint TSMatrix_FastTranspose(TSMatrix M, TSMatrix *T)int *num, *cpot, i, t;/ 如果矩阵 M 为空矩阵，返回错误信息if (M.num = 0)return EMPTY_MATRIX;/ 分配临时的工作空间nu
17、m = (int *)malloc(M.colnum + 1) * sizeof(int);cpot = (int *)malloc(M.colnum + 1) * sizeof(int);/ 如果临时的工作空间分配不成功if (num = NULL | cpot = NULL)return MALLOC_FAIL;/ 初始化临时工作空间（把 num 数组用 0 填充）for (i = 1; i = M.rownum; i+)numi = 0;/ 统计倒置后每行的元素数量（即统计倒置前矩阵每列元素的数量）for (i = 1; i = M.num; i+)numM.datai - 1.col+
18、;/ 设置 T 矩阵每行首个非零元的位置cpot1 = 0;for (i = 2; i num = M.num;T-colnum = M.rownum;T-rownum = M.colnum;/ 对 M 矩阵中每个非零元素进行转置操作for (i = 0; i datat.col = M.datai.row;T-datat.row = M.datai.col;T-datat.e = M.datai.e;+cpotM.datai.col;/ 转置完成后释放临时工作空间free(num);free(cpot);return OK;/ 如果稀疏矩阵 M 和 N 的行数的列数相同，计算 Q = M +
19、 Nint TSMatrix_Add(TSMatrix M, TSMatrix N, TSMatrix *Q)int i = 0, j = 0, k = 0;if (M.colnum != N.colnum | M.rownum != N.rownum)return MATRIX_NOT_MATCH;/ 填充结果矩阵信息TSMatrix_Init(Q);Q-colnum = M.colnum;Q-rownum = M.rownum;Q-num = 0;while (i M.num & j datak.row = M.datai.row;Q-datak.col = M.datai.col;Q-d
20、atak.e = M.datai.e + N.dataj.e;Q-num+;i+;j+;k+;/ 如果 i 指向元素的列下标大于 j 指向元素的列下标/ 把下标小（j 指向的元素）的放入到 Q 矩阵中else if (M.datai.col N.dataj.col)Q-datak.row = N.dataj.row;Q-datak.col = N.dataj.col;Q-datak.e = N.dataj.e;Q-num+;j+;k+;/ 如果 i 指向元素的列下标小于 j 指向元素的列下标/ 把下标小（i 指向的元素）的放入到 Q 矩阵中else if (M.datai.col datak.
21、row = M.datai.row;Q-datak.col = M.datai.col;Q-datak.e = M.datai.e;Q-num+;i+;k+;/ 如果 i 指向的元素行下标大于 j 指向元素的行下标else if (M.datai.row N.dataj.row)Q-datak.row = N.dataj.row;Q-datak.col = N.dataj.col;Q-datak.e = N.dataj.e;Q-num+;k+;j+;/ 如果 i 指向元素行下标小于 j 指向元素的行下标else if (M.datai.row datak.row = M.datai.row;Q
22、-datak.col = M.datai.col;Q-datak.e = M.datai.e;Q-num+;i+;k+;/ 如果还有剩余元素，按顺序把元素添加到结果矩阵中while (i datak.row = M.datai.row;Q-datak.col = M.datai.col;Q-datak.e = M.datai.e;Q-num+;i+;k+;while (j datak.row = N.dataj.row;Q-datak.col = N.dataj.col;Q-datak.e = N.dataj.e;Q-num+;j+;k+;return OK;/ 如果稀疏矩阵 M 的列数等于
23、N 的行数，计算 Q = M x N;int TSMatrix_Multply(TSMatrix M, TSMatrix N, TSMatrix *Q)int *num_m, *cpot_m, *num_n, *cpot_n, i, j, k, s, col;int a, ri, rj;/ 如果两个矩阵不满足矩阵相乘的条件，返回错误信息if (M.colnum != N.rownum)return MATRIX_NOT_MATCH;/ 分配临时空间num_m = (int *)malloc(M.rownum + 1) * sizeof(int);cpot_m = (int *)malloc(M
24、.rownum + 1) * sizeof(int);num_n = (int *)malloc(N.rownum + 1) * sizeof(int);cpot_n = (int *)malloc(N.rownum + 1) * sizeof(int);/ 填充结果矩阵的信息TSMatrix_Init(Q);Q-rownum = M.rownum;Q-colnum = N.colnum;Q-num = 0;/ 如果相乘为零矩阵，直接返回if (0 = M.num * N.num)return OK;/ 初始化临时空间for (i = 1; i = M.colnum; i+)num_mi =
25、0;for (i = 1; i = N.colnum; i+)num_ni = 0;/ 计算矩阵每行非零元元素的数量for (i = 0; i M.num; i+)num_mM.datai.row+;for (i = 0; i N.num; i+)num_nN.datai.row+;cpot_m1 = cpot_n1 = 0;for (i = 2; i = M.rownum; i+)cpot_mi = cpot_mi - 1 + num_mi - 1;for (i = 2; i = N.rownum; i+)cpot_ni = cpot_ni - 1 + num_ni - 1;/ 计算过程fo
26、r (i = 1; i = M.rownum; i+)/ 表示相乘结果在矩阵中的行下标ri = i;for (j = cpot_mi; j cpot_mi + num_mi; j+)/ 初始化累加器s = 0;/ 表示相乘结果在矩阵中的列下标rj = M.dataj.col;/ 获得第 i 行首个非零元素的位置k = cpot_mi;/ 对该行的每个元素进行相乘操作并累加while (k - cpot_mi num_mi)col = M.datak.col;a = cpot_ncol;/ 如果 a 指向元素仍然属于第 a 元素/ 遍历，找到符合条件的元素相乘，并把相乘结果累加到累加器中whil
27、e (a - cpot_ncol dataQ-num.row = ri;Q-dataQ-num.col = rj;Q-dataQ-num.e = s;Q-num+;/ 处理完成后释放临时空间free(num_m);free(cpot_m);free(num_n);free(cpot_n);return OK;/ 以矩阵的方式输出稀疏矩阵void TSMartix_PrintMatrix(TSMatrix *M)int count, i, k;/ 求出原矩阵的元素个数count = M-colnum * M-rownum;k = 0;for (i = 0; i datak.row = (i /
28、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(请输入新创建的矩阵的行数和列数，分别输入并利用空格间开：);/ 输入的同时对数据的有效性进行检查while (2 != scanf(%d%d, &i, &
29、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,
30、j);/ 释放用于临时储存输入的空间free(a);return T;/ 把光标位置移动到该行行首void ResetCursor()HANDLE hOut;COORD cTarget;CONSOLE_SCREEN_BUFFER_INFO info;int y = 0;hOut = GetStdHandle(STD_OUTPUT_HANDLE);GetConsoleScreenBufferInfo(hOut, &info);y = info.dwCursorPosition.Y;cTarget.X = 0;cTarget.Y = y;SetConsoleCursorPosition(hOut, cTarget);