参考《数据结构(C语言版)》- 严蔚敏 吴伟民 - 清华大学出版社
稀疏矩阵的结构定义
typedef struct {int i, j; //该非零元的行下标和列下标ElemType e; //非零元对应的值}Triple;typedef struct {Triple data[MAX_SIZE]; //非零元三元组表intrpos[MAX_RC];//各行第一个非0元的位置表intmu, nu, tu; //矩阵的行数，列数，非零元个数}RTSMatrix;
稀疏矩阵初始化
void Init_Matrix(RTSMatrix &M, int i){int x, y, z;int M_row = 0; int M_col = 0;M.tu = 0;printf("请按行,列,数据的形式输入，输入-1时结束输入\n");for (int i = 0; ; i++){scanf_s("%d,%d,%d", &x, &y, &z);if (x == -1 || y == -1)break;M.data[i].i = x; M.data[i].j = y; M.data[i].e = z;M.tu++;if (M_row < x)M_row = x;if (M_col < y)M_col = y;}M.mu = M_row;M.nu = M_col;printf("\n第%d个矩阵为\n", i);Show_Matrix_1(M);}
计算每行第一个非零元所在位置
void non_zero_elements(RTSMatrix &M){int num[100];//num[]保存每一行的非零元素个数 cpot[]保存每行元素起始地址for (int i = 0; i < M.mu; i++)num[i] = 0;//对num初始化for (int j = 0; j < M.tu; j++)num[M.data[j].i - 1]++;//计算每一行非零元素的个数,因为矩阵从第一行开始，而data数组从0开始，要-1M.rpos[0] = 0;//起始为0for (int k = 1; k < M.mu; k++)M.rpos[k] = M.rpos[k - 1] + num[k - 1];}
快速乘法
void FastMultSMatrix(RTSMatrix A, RTSMatrix B, RTSMatrix &C){if (A.nu != B.mu)//前矩阵列数要等于后矩阵行数return;C.mu = A.mu; //结果矩阵的行数为前矩阵行数C.nu = B.nu;//结果矩阵的列数为后矩阵列数C.tu = 0;//结果矩阵初始化int ctemp[MAX_SIZE];//累加器int arow, brow, t, tp, ccol;non_zero_elements(A);//计算每行第一个非0元的位置non_zero_elements(B);if (A.tu * B.tu != 0){//相乘矩阵非0for (arow = 0; arow < A.mu; arow++){//从第一行开始，直至最后一行for (int i = 0; i <= A.nu; i++)ctemp[i] = 0;//累加器清0C.rpos[arow] = C.tu;//第一个非0元位置为0if (arow < A.mu - 1)//获得A的该行非0元数tp = A.rpos[arow + 1];elsetp = A.tu;for (int j = A.rpos[arow]; j < tp; j++) {//对A的该行的每一个非0数，取其列标，与B的列标行的每一个数相乘brow = A.data[j].j;//取列标if (brow < B.mu)//取B的列标行的非0数t = B.rpos[brow];elset = B.tu;for (int k = B.rpos[brow - 1]; k < t; k++) {//对B的列标行的每一个非0元ccol = B.data[k].j;ctemp[ccol] += A.data[j].e * B.data[k].e;}}for (ccol = 1; ccol <= C.nu; ccol++)//将累加器的结果按次序复制到结果数组if (ctemp[ccol]) {C.tu++;if (C.tu > MAX_SIZE)return;C.data[C.tu - 1].i = arow + 1;C.data[C.tu - 1].j = ccol;C.data[C.tu - 1].e = ctemp[ccol];}}}printf("结果为\n");Show_Matrix_1(C);}
按矩阵形式输出稀疏矩阵
void Show_Matrix_1(RTSMatrix T) {int data[100] = { 0 };for (int i = 0; i < T.tu; i++)//在指定位置存放非0元，其余位置都为0data[(T.data[i].i - 1) * T.nu + T.data[i].j - 1] = T.data[i].e;for (int j = 0; j < T.mu * T.nu; j++) {printf("%5d", data[j]);if ((j + 1) % T.nu == 0)printf("\n");}printf("\n");}
按三元组形式输出稀疏矩阵
void Show_Matrix_2(RTSMatrix T){printf("\n三元表为\n");for (int t = 0; t < T.tu; t++)printf("%4d %4d %4d\n", T.data[t].i, T.data[t].j, T.data[t].e);printf("\n");}
测试集
矩阵A:1 2 00 2 00 0 3矩阵B:1 0 02 2 00 0 3
整体代码
#include<stdio.h>#include<stdlib.h>#define MAX_SIZE 1000#define MAX_RC 1000#define ElemType inttypedef struct {int i, j; //该非零元的行下标和列下标ElemType e; //非零元对应的值}Triple;typedef struct {Triple data[MAX_SIZE]; //非零元三元组表intrpos[MAX_RC];//各行第一个非0元的位置表intmu, nu, tu; //矩阵的行数，列数，非零元个数}RTSMatrix;void Show_Matrix_1(RTSMatrix T) {int data[100] = { 0 };for (int i = 0; i < T.tu; i++)data[(T.data[i].i - 1) * T.nu + T.data[i].j - 1] = T.data[i].e;for (int j = 0; j < T.mu * T.nu; j++) {printf("%5d", data[j]);if ((j + 1) % T.nu == 0)printf("\n");}printf("\n");}void Show_Matrix_2(RTSMatrix T){printf("\n三元表为\n");for (int t = 0; t < T.tu; t++)printf("%4d %4d %4d\n", T.data[t].i, T.data[t].j, T.data[t].e);printf("\n");}void Init_Matrix(RTSMatrix &M, int i){int x, y, z;int M_row = 0; int M_col = 0;M.tu = 0;printf("请按行,列,数据的形式输入，输入-1时结束输入\n");for (int i = 0; ; i++){scanf_s("%d,%d,%d", &x, &y, &z);if (x == -1 || y == -1)break;M.data[i].i = x; M.data[i].j = y; M.data[i].e = z;M.tu++;if (M_row < x)M_row = x;if (M_col < y)M_col = y;}M.mu = M_row;M.nu = M_col;printf("\n第%d个矩阵为\n", i);Show_Matrix_1(M);}void non_zero_elements(RTSMatrix &M){int num[100];//num[]保存每一行的非零元素个数 cpot[]保存每行元素起始地址for (int i = 0; i < M.mu; i++)num[i] = 0;//对num初始化for (int j = 0; j < M.tu; j++)num[M.data[j].i - 1]++;//计算每一行非零元素的个数,因为矩阵从第一行开始，而data数组从0开始，要-1M.rpos[0] = 0;//起始为0for (int k = 1; k < M.mu; k++)M.rpos[k] = M.rpos[k - 1] + num[k - 1];}void FastMultSMatrix(RTSMatrix A, RTSMatrix B, RTSMatrix &C){if (A.nu != B.mu)//前矩阵列数要等于后矩阵行数return;C.mu = A.mu; //结果矩阵的行数为前矩阵行数C.nu = B.nu;//结果矩阵的列数为后矩阵列数C.tu = 0;//结果矩阵初始化int ctemp[MAX_SIZE];//累加器int arow, brow, t, tp, ccol;non_zero_elements(A);//计算每行第一个非0元的位置non_zero_elements(B);if (A.tu * B.tu != 0){//相乘矩阵非0for (arow = 0; arow < A.mu; arow++){//从第一行开始，直至最后一行for (int i = 0; i <= A.nu; i++)ctemp[i] = 0;//累加器清0C.rpos[arow] = C.tu;//第一个非0元位置为0if (arow < A.mu - 1)//获得A的该行非0元数tp = A.rpos[arow + 1];elsetp = A.tu;for (int j = A.rpos[arow]; j < tp; j++) {//对A的该行的每一个非0数，取其列标，与B的列标行的每一个数相乘brow = A.data[j].j;//取列标if (brow < B.mu)//取B的列标行的非0数t = B.rpos[brow];elset = B.tu;for (int k = B.rpos[brow - 1]; k < t; k++) {//对B的列标行的每一个非0元ccol = B.data[k].j;ctemp[ccol] += A.data[j].e * B.data[k].e;}}for (ccol = 1; ccol <= C.nu; ccol++)//将累加器的结果按次序复制到结果数组if (ctemp[ccol]) {C.tu++;if (C.tu > MAX_SIZE)return;C.data[C.tu - 1].i = arow + 1;C.data[C.tu - 1].j = ccol;C.data[C.tu - 1].e = ctemp[ccol];}}}printf("结果为\n");Show_Matrix_1(C);}void main() {RTSMatrix A;RTSMatrix B;RTSMatrix C;Init_Matrix(A, 1);Init_Matrix(B, 2);FastMultSMatrix(A, B, C);system("pause");}
