稀疏矩阵基本操作 实验报告 一、 实验内容稀疏矩阵的压缩储存结构，以及稀疏矩阵的三元组表表达方法下的转置、相加、相乘等算法二、 实验目的1. 熟悉数组、矩阵的定义和基本操作2. 熟悉稀疏矩阵的储存方式和基本运算3. 理解稀疏矩阵的三元组表类型定义，掌握稀疏矩阵的输入、输出和转置算法三、 实验原理1. 使用三元组储存矩阵中的非零元素（三元组分别储存非零元素的行下标，列下标和元素值）除了三元组表自身，储存一个稀疏矩阵还需要额外的三个变量，分别储存矩阵的非零元个数，矩阵的行数和矩阵的列数2. 稀疏矩阵的创建算法：第一步：根据矩阵创建一个二维数组，表达原始矩阵第二步：取出二维数组中的元素（从第一个元素开始取），判断取出元素是否为非零元素，假如为非零元素，把该非零元素的数值以及行下标和列下表储存到三元数组表里，否则取出下一个元素，反复该环节第三步：反复第二步，知道二维数组中所有的元素已经取出3. 稀疏矩阵倒置算法：第一步：判断进行倒置的矩阵是否为空矩阵，假如是，则直接返回错误信息第二步：计算要倒置的矩阵每列非零元素的数量，存入到num数组（其中num[i] 代表矩阵中第i列非零元素的个数）以及倒置后矩阵每行首非零元的位置，存入cpot数组中（其中cpot表达倒置后矩阵每行非零元的位置，相应表达原矩阵每列中第一个非零元的位置）。
第三步：拟定倒置后矩阵的行数和列数第四步：取出表达要导致矩阵中三元组表元素 {e, I, j}（第一次取出第一个，依次取出下一个元素），从第二步cpot数组中拟定该元素倒置后存放的位置（cpot[j]），把该元素的行下标和列下标倒置以后放入新表的指定位置中cpot[j] 变量加一第五步：反复第四步，直到三元组表中所有的元素都完毕倒置第六步：把完毕倒置运算的三元组表输出4. 稀疏矩阵加法算法：第一步：检查相加两个矩阵的行数和列数是否相同，假如相同，则进入第二步，否则输犯错误信息第二步：定义变量i和j，用于控制三元组表的遍历第三步：比较变量矩阵M中第i个元素和矩阵N中第j个元素，假如两个元素是同一行元素，假如不是则进入第四步，假如是，再继续比较两个元素是否为同一列元素，假如是，把两个元素值相加，放到三元组表中；否则把列下表小的元素依次放到三元组表中进入第五步第四步：假如矩阵M中第i个元素的行下标大于矩阵N中第j个元素的行下标，则把矩阵N中第j个元素所在行的所有非零元素添加到三元组表中；假如矩阵M中第i个元素的行下标小于矩阵N中第j个元素的下标，则把M中第i个元素所在行的所有非零元素依次添加到三元组表中。
第五步：反复第三步，直到矩阵M和矩阵N中所有元素都非零元素添加到三元组表中第六步：输出运算结果5. 稀疏矩阵乘法算法：第一步：检查矩阵M和矩阵N能否参与乘法运算（即矩阵M的列数等于矩阵N的行数），假如两个矩阵可以参与乘法运算，进入下一步，否则输犯错误信息第二步：检查两个矩阵相乘以后是否为零矩阵，假如相乘结果是零矩阵，直接返回一个零矩阵第三步：分别计算矩阵M和矩阵N中每行非零元的个数（分别存放到num_m和num_n数组中），并计算出每行首非零元的位置（分别存放到cpot_m和cpot_n中）第四步：依次取矩阵M中的非零元（第一次取出矩阵M中的第一个非零元），求出该非零元所在行和所在列乘积的和，然后把值放到结果三元组表的特定位置第五步：反复第四步，直到矩阵M中所有非零元都已经参与运算第六步：输出结果四、 程序流程图五、 实验结果5.1 程序主菜单5.2 稀疏矩阵三元组的创建和倒置5.3 稀疏矩阵的加法运算并以三元组输出结果5.4 稀疏矩阵的乘法运算并以矩阵方式输出结果六、 操作说明1. 在创建稀疏矩阵的时候，可以每次输入一个数据，也可以一次输入多个数据，程序会自动根据输入元素的个数对矩阵数据进行填充2. 每次矩阵运算失败时（无论是输入的矩阵不符合矩阵运算的条件，参与运算其中一个矩阵为空矩阵，或者分派不到临时空间），程序都会返回到主菜单。
输入的数据都会被清空七、 附录：代码#include #include #include #define MAXSIZE 1000#define OK 0#define MALLOC_FAIL -1 // 表达分派空间时发生错误#define EMPTY_MATRIX -2 // 表达正尝试对一个空矩阵进行运算操作#define MATRIX_NOT_MATCH -3 // 表达尝试对不符合运算条件的矩阵进行运算操作（例如非相同行数列数矩阵相加）/* ----------- 结构体声明部分 ---------------- */typedef struct{ int row; // 非零元的行下标 int col; // 非零元的列下标 int e; // 非零元的值} Triple;typedef struct{ Triple *data; // 非零元素的元素表 int rownum; // 矩阵的行数 int colnum; // 矩阵的列数 int num; // 矩阵非零元的个数} TSMatrix, *PTSMatrix;/* ----------- 函数声明部分 ------------------ */// 初始化稀疏矩阵结构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 TSMatrix_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; char 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(" 请输入选项："); scanf("%c", &ch); switch (ch) { case '1': system("cls"); M = TSMatrix_CreateFromInput(); if (M != NULL) { printf("\n\n以三元组输出稀疏矩阵：\n"); TSMatrix_PrintTriple(M); printf("\n倒置后稀疏矩阵的三元组输出：\n"); TSMatrix_FastTranspose(*M, T); TSMatrix_PrintTriple(T); system("pause"); } else { printf("创建矩阵过程发生错误"); system("pause"); } break; case '2': system("cls"); M = TSMatrix_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 = 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': case '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(sizeof(TSMatrix)); TSMatrix_Init(P); // 设立稀疏矩阵的行数和列数 P->rownum = row; P->colnum = col; for (i = 0; i < row; i++) { for (j = 0; j < col; j++) { // 假如第 i+1 行第 i+1 列元素是非零元素 if (0 != *(a + i * col + j)) { // 把非零元的元素和位置信息保存到稀疏矩阵中 P->data[P->num].e = *(a + i * col + j); P->data[P->num].row = i + 1; P->data[P->num].col = j + 1; // 把稀疏矩阵中的非零元个数加一 P->num++; } } } return P;}// 以三元组的方式输出稀疏矩阵void TSMatrix_PrintTriple(TSMatrix *M){ int i; if (0 == M->num) { printf("稀疏矩阵为空！\n"); return; } printf(" i j v \n"); printf("===============\n"); for (i = 0; i < M->num; i++) { printf("%3d %3d %3d\n", M->data[i].row, M->data[i].col, M->data[i].e); } printf("===============\n");}// 求稀疏矩阵 M 的转置矩阵 Tint TSMatrix_FastTranspose(TSMatrix M, TSMatrix *T){ int *num, *cpot, i, t; // 假如矩阵 M 为空矩阵，返回错误信息 if (M.num == 0) return EMPTY_MATRIX; // 分派临时的工作空间 num = (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++) num[i] = 0; // 记录倒置后每行的元素数量（即记录倒置前矩阵每列元素的数量） for (i = 1; i <= M.num; i++) num[M.data[i - 1].col]++; // 设立 T 矩阵每行首个非零元的位置 cpot[1] = 0; for (i = 2; i <= M.colnum; i++) cpot[i] = cpot[i - 1] + num[i - 1]; // 把 T 矩阵的信息清空 TSMatrix_Init(T); // 把矩阵 M 的信息填充到 T 中。
// 矩阵倒置以后，T 的行数等于 M 的列数，T 的列数等于 M 的行数 T->num = M.num; T->colnum = M.rownum; T->rownum = M.colnum; // 对 M 矩阵中每个非零元素进行转置操作 for (i = 0; i < M.num; i++) { t = cpot[M.data[i].col]; T->data[t].col = M.data[i].row; T->data[t].row = M.data[i].col; T->data[t].e = M.data[i].e; ++cpot[M.data[i].col]; } // 转置完毕后释放临时工作空间 free(num); free(cpot); return OK;}// 假如稀疏矩阵 M 和 N 的行数的列数相同，计算 Q = M + 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 < N.num) { // 假如 i j 指向元素是同一行的元素 if (M.data[i].row == N.data[j].row) { // 假如 i 和 j 指向的元素指向的是同一个元素 if (M.data[i].col == N.data[j].col) { Q->data[k].row = M.data[i].row; Q->data[k].col = M.data[i].col; Q->data[k].e = M.data[i].e + N.data[j].e; Q->num++; i++; j++; k++; } // 假如 i 指向元素的列下标大于 j 指向元素的列下标 // 把下标小（j 指向的元素）的放入到 Q 矩阵中 else if (M.data[i].col > N.data[j].col) { Q->data[k].row = N.data[j].row; Q->data[k].col = N.data[j].col; Q->data[k].e = N.data[j].e; Q->num++; j++; k++; } // 假如 i 指向元素的列下标小于 j 指向元素的列下标 // 把下标小（i 指向的元素）的放入到 Q 矩阵中 else if (M.data[i].col < N.data[j].col) { Q->data[k].row = M.data[i].row; Q->data[k].col = M.data[i].col; Q->data[k].e = M.data[i].e; Q->num++; i++; k++; } } // 假如 i 指向的元素行下标大于 j 指向元素的行下标 else if (M.data[i].row > N.data[j].row) { Q->data[k].row = N.data[j].row; Q->data[k].col = N.data[j].col; Q->data[k].e = N.data[j].e; Q->num++; k++; j++; } // 假如 i 指向元素行下标小于 j 指向元素的行下标 else if (M.data[i].row < N.data[j].row) { Q->data[k].row = M.data[i].row; Q->data[k].col = M.data[i].col; Q->data[k].e = M.data[i].e; Q->num++; i++; k++; } } // 假如尚有剩余元素，按顺序把元素添加到结果矩阵中 while (i < M.num) { Q->data[k].row = M.data[i].row; Q->data[k].col = M.data[i].col; Q->data[k].e = M.data[i].e; Q->num++; i++; k++; } while (j < N.num) { Q->data[k].row = N.data[j].row; Q->data[k].col = N.data[j].col; Q->data[k].e = N.data[j].e; Q->num++; j++; k++; } return OK;}// 假如稀疏矩阵 M 的列数等于 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.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_m[i] = 0; for (i = 1; i <= N.colnum; i++) num_n[i] = 0; // 计算矩阵每行非零元元素的数量 for (i = 0; i < M.num; i++) num_m[M.data[i].row]++; for (i = 0; i < N.num; i++) num_n[N.data[i].row]++; cpot_m[1] = cpot_n[1] = 0; for (i = 2; i <= M.rownum; i++) cpot_m[i] = cpot_m[i - 1] + num_m[i - 1]; for (i = 2; i <= N.rownum; i++) cpot_n[i] = cpot_n[i - 1] + num_n[i - 1]; // 计算过程 for (i = 1; i <= M.rownum; i++) { // 表达相乘结果在矩阵中的行下标 ri = i; for (j = cpot_m[i]; j < cpot_m[i] + num_m[i]; j++) { // 初始化累加器 s = 0; // 表达相乘结果在矩阵中的列下标 rj = M.data[j].col; // 获得第 i 行首个非零元素的位置 k = cpot_m[i]; // 对该行的每个元素进行相乘操作并累加 while (k - cpot_m[i] < num_m[i]) { col = M.data[k].col; a = cpot_n[col]; // 假如 a 指向元素仍然属于第 a 元素 // 遍历，找到符合条件的元素相乘，并把相乘结果累加到累加器中 while (a - cpot_n[col] < num_n[col]) { if (N.data[a].row == M.data[j].col) { s = s + (M.data[j].e * N.data[a].e); } a++; } k++; } if (s != 0) { Q->data[Q->num].row = ri; Q->data[Q->num].col = rj; Q->data[Q->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 < count; i++) { // 假如发现相应位置的非零元 if (M->data[k].row == ((i / M->colnum) + 1) && M->data[k].col == ((i % M->colnum) + 1)) { printf("%3d", M->data[k].e); k++; } else { printf("%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, &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); 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);}。