数据结构——稀疏矩阵 完整代码

/*** *TSMatrix.cpp - 稀疏矩阵基本操作的实现 * *班级： * *姓名：刘士龙 * *学号： * ****/ #include <stdio.h> #include <stdlib.h> #include <malloc.h> #include <memory.h> #include <assert.h> #include "TSMatrix.h" /*------------------------------------------------------------ 操作目的： 初始化稀疏矩阵 初始条件： 无 操作结果： 构造空稀疏矩阵 函数参数： TSMatrix *M 待初始化的稀疏矩阵 返回值： bool 操作是否成功 ------------------------------------------------------------*/ bool InitSMatrix(TSMatrix *M) { for (int i=0; i<=MAXSIZE; i++) //置三元组顺序表各项元素为0 M->data[i].e = 0; M->tu = 0; //初始化时非零元个数为0 return true; } /*------------------------------------------------------------ 操作目的： 创建稀疏矩阵 初始条件： 稀疏矩阵已经存在 操作结果： 构造稀疏矩阵 函数参数： TSMatrix *M 待创建的稀疏矩阵 返回值： bool 操作是否成功 参考提示： 按照三元组的方式提示用户输入稀疏矩阵的所有非零元素 ------------------------------------------------------------*/ bool CreateSMatrix(TSMatrix *M) { printf("请输入稀疏矩阵的行数、列数和非零元个数:\n"); scanf("%d%d%d", &M->mu, &M->nu, &M->tu); if (M->mu < 2 || M->nu < 2 || M->tu <= 0 || M->tu > MAXSIZE || M->tu > M->mu*M->nu) return false; printf("请以三元组形式(i,j,e)输入稀疏矩阵的非零元信息:\n"); for (int k=1; k<=M->tu; k++) { scanf("%d%d%d",&M->data[k].i, &M->data[k].j, &M->data[k].e); } return true; } /*------------------------------------------------------------ 操作目的： 销毁稀疏矩阵 初始条件： 稀疏矩阵已存在 操作结果： 销毁稀疏矩阵 函数参数： TSMatrix *M 待销毁的三元组顺序表 返回值： 无 ------------------------------------------------------------*/ void DestroySMatrix(TSMatrix *M) { // Do Nothing } /*------------------------------------------------------------ 操作目的： 打印稀疏矩阵 初始条件： 稀疏矩阵已存在 操作结果： 按照矩阵的数学形式打印稀疏矩阵M 函数参数： TSMatrix M 待打印稀疏矩阵 返回值： 无 参考提示： 矩阵A(3×5)的打印样式，如下： 0 0 0 0 0 0 0 0 1 0 2 0 0 0 0 ------------------------------------------------------------*/ void PrintSMatrix(TSMatrix M) { int k = 1; for (int i=1; i<=M.mu; i++) { for (int j=1; j<=M.nu; j++) { if (M.data[k].i == i && M.data[k].j ==j) { printf("%d\t",M.data[k].e); k++; } else printf("%d\t",0); } //for printf("\n"); } } /*------------------------------------------------------------ 操作目的： 拷贝稀疏矩阵 初始条件： 稀疏矩阵src已存在 操作结果： 由稀疏矩阵src复制得到稀疏矩阵dst 函数参数： TSMatrix src 原始稀疏矩阵src TSMatrix *dst 目标稀疏矩阵src 返回值： 无 ------------------------------------------------------------*/ void CopySMatrix(TSMatrix *dst, TSMatrix src) { for (int i=1; i<=src.tu; i++) { dst->data[i] = src.data[i]; } dst->mu = src.mu; dst->nu = src.nu; dst->tu = src.tu; } /*------------------------------------------------------------ 操作目的： 稀疏矩阵求和 初始条件： 稀疏矩阵M,N和Q存在,且M和N的行列数相同 操作结果： 返回稀疏矩阵的和Q = M + N 函数参数： TSMatrix M 稀疏矩阵M TSMatrix N 稀疏矩阵N TSMatrix *Q 稀疏矩阵Q 返回值： 无 ------------------------------------------------------------*/ bool AddSMatrix(TSMatrix M, TSMatrix N, TSMatrix *Q) { printf("AddSMatrix\n"); if (M.mu != N.mu || M.nu != N.nu) return false; //求和要求两个矩阵行列数相等 int pm = 1, pn = 1, q = 1; while (pm <= M.tu && pn <= N.tu) { if (M.data[pm].i < N.data[pn].i) //比较行下标大小，插入M Q->data[q++] = M.data[pm++]; else if (M.data[pm].i > N.data[pn].i) //比较行下标大小，插入N Q->data[q++] = N.data[pn++]; else { if (M.data[pm].j < N.data[pn].j) //比较列下标大小，插入M Q->data[q++] = M.data[pm++]; else if (M.data[pm].j > N.data[pn].j) //比较列下标大小，插入N Q->data[q++] = N.data[pn++]; else //行下标、列下标均相等 { Q->data[q].e = M.data[pm].e + N.data[pn].e; if (Q->data[q].e != 0) //和不为0 { Q->data[q].i = M.data[pm].i; Q->data[q].j = M.data[pm].j; q++; pm++; pn++; } else { pm++; pn++; } //if-else(和不为0) } //if-else } //if-else } //while while (pm <= M.tu) //插入剩下M的元素 Q->data[q++] = M.data[pm++]; while (pn <= N.tu) //插入剩下N的元素 Q->data[q++] = N.data[pn++]; Q->mu = M.mu; Q->nu = M.nu; Q->tu = q; return true; } //O(m+n) /*------------------------------------------------------------ 操作目的： 稀疏矩阵相减 初始条件： 稀疏矩阵M,N和Q存在 操作结果： 返回稀疏矩阵的差Q = M - N 函数参数： TSMatrix M 稀疏矩阵M TSMatrix N 稀疏矩阵N TSMatrix *Q 稀疏矩阵Q 返回值： 无 ------------------------------------------------------------*/ bool SubSMatrix(TSMatrix M, TSMatrix N, TSMatrix *Q) { if (M.mu != N.mu || M.nu != N.nu) return false; for (int ni=1; ni<=N.tu; ni++) //转化N为-N N.data[ni].e *= -1; printf("-N = \n"); PrintSMatrix(N); AddSMatrix(M, N, Q); return true; } //O(m+n) /*------------------------------------------------------------ 操作目的： 稀疏矩阵相乘 初始条件： 稀疏矩阵M,N和Q存在,且M，N满足相乘条件 操作结果： 返回稀疏矩阵的积Q = M × N 函数参数： TSMatrix M 稀疏矩阵M TSMatrix N 稀疏矩阵N TSMatrix *Q 稀疏矩阵Q 返回值： 无 ------------------------------------------------------------*/ //以矩阵M的每一行创建一个一维数组 void create_row_array(TSMatrix M, int i, ElemType *Mrow_tmp_array) { //求矩阵的每一列的一个数值 for (int j = 1; j <= M.nu; ++j) { int pm = 1; bool flag = false; while (pm <= M.tu) { //当前元素行标与所求行的行标相等 if (M.data[pm].i == i) { //当前元素列标与所求行的元素的列标相等 if (M.data[pm].j == j) { Mrow_tmp_array[j-1] = M.data[pm].e; flag = true; break; } } //if ++pm; } //while //三元组重不存在下标为i、j的元素 if (flag == false) Mrow_tmp_array[j-1] = 0; } //for } bool MultSMatrix(TSMatrix M, TSMatrix N, TSMatrix *Q) { if (M.nu != N.mu) return false; //建立三个临时矩阵 ElemType **Mtmp = (ElemType **)malloc(sizeof(ElemType*)*M.mu); for (int i=0; i<M.mu; ++i) Mtmp[i] = (ElemType *)malloc(sizeof(ElemType)*M.nu); ElemType **Ntmp = (ElemType **)malloc(sizeof(ElemType*)*N.mu); for (int i=0; i<N.mu; ++i) Ntmp[i] = (ElemType *)malloc(sizeof(ElemType)*N.nu); ElemType **Qtmp = (ElemType **)malloc(sizeof(ElemType*)*M.mu); for (int i=0; i<M.mu; ++i) Qtmp[i] = (ElemType *)malloc(sizeof(ElemType)*N.nu); //把稀疏矩阵M和N转化为普通矩阵 for (int i = 1; i <= M.mu; ++i) create_row_array(M, i, Mtmp[i-1]); for (int i = 1; i <= N.mu; ++i) create_row_array(N, i, Ntmp[i-1]); //普通矩阵乘积 for (int i=0; i<M.mu; ++i) { for (int j=0; j<N.nu; ++j) { Qtmp[i][j] = 0; for (int k=0; k<M.mu; ++k) Qtmp[i][j] += Mtmp[i][k] * Ntmp[k][j]; } } //把普通矩阵的乘积矩阵Qtmp转化为稀疏矩阵Q int pq = 1; for (int i = 0; i < M.mu; ++i) { for (int j = 0; j < N.nu; ++j) { if (Qtmp[i][j] != 0) { Q->data[pq].i = i+1; Q->data[pq].j = j+1; Q->data[pq].e = Qtmp[i][j]; pq++; } } } //为Q的行号、列号、非零元个数赋值 Q->mu = M.mu; Q->nu = N.nu; Q->tu = pq; //释放分配的临时空间 for (int i=0; i<M.mu; ++i) { free(Mtmp[i]); free(Qtmp[i]); } for (int i=0; i<N.mu; ++i) { free(Ntmp[i]); } free(Mtmp); free(Ntmp); free(Qtmp); return true; } /*------------------------------------------------------------ 操作目的： 稀疏矩阵转置 初始条件： 稀疏矩阵M和T存在 操作结果： 返回稀疏矩阵的转置 函数参数： TSMatrix M 稀疏矩阵M TSMatrix *T 稀疏矩阵T 返回值： 无 ------------------------------------------------------------*/ void TranSMatrix(TSMatri