事实上是看到了脚本之家的代码，感觉其写的很清楚很简洁。
C++稀疏矩阵的各种基本运算并实现加法乘法
我主要是在上面添加了些备注和解释，方便大家理解。
过两天我把基于这个大神的稀疏矩阵类实现也贴在下面。
以下是添加了备注解释的代码
#include <iostream> #include<malloc.h> #include<cstdio> using namespace std; #define M 4 #define N 4 #define MaxSize 100 //三元组定义 typedef struct { int r; int c; int d;//元素值 } TupNode; //三元组顺序表定义 //总共有多少行，多少列 //里面含有多少个元素 typedef struct { int rows;//标准矩阵总共有多少行 int cols;//标准矩阵总共有多少列 int nums;//总共有几个非零值 TupNode data[MaxSize]; } TSMatrix; //将一个矩阵转为稀疏矩阵t void CreatMat(TSMatrix& t, int A[M][N]) { t.rows = M; t.cols = N; t.nums = 0; for (int i = 0; i < M; i++) for (int j = 0; j < N; j++) if (A[i][j] != 0) {//如果这个元素不是0，就把它读入系数矩阵 t.data[t.nums].r = i; t.data[t.nums].c = j; t.data[t.nums].d = A[i][j]; t.nums++;//每读入一个元素，nums+1 } } //函数功能：赋值。令t[i,j]处的值等于x bool Value(TSMatrix& t, int x, int i, int j) { int k = 0, k1; if (i >= t.rows || j >= t.cols) return false; while (k<t.nums && i>t.data[k].r)k++; while (k<t.nums && i == t.data[k].r && j>t.data[k].c)k++; if (t.data[k].r == i && t.data[k].c == j) t.data[k].d = x; else { for (k1 = t.nums - 1; k1 >= k; k1--) { t.data[k1 + 1].r = t.data[k].r; t.data[k1 + 1].c = t.data[k].c; t.data[k1 + 1].d = t.data[k].d; } t.data[k].r = i; t.data[k].c = j; t.data[k].d = x; t.nums++; } return true; } //函数功能：令x=矩阵t[i,j]处的值 //相当于取出矩阵t[i,j]处的值 bool Assign(TSMatrix t, int& x, int i, int j) { int k = 0; if (i >= t.rows || j >= t.cols) return false; while (k<t.nums && i>t.data[k].r)k++; while (k<t.nums && i == t.data[k].r && j>t.data[k].c)k++; if (t.data[k].r == i && t.data[k].c == j) x = t.data[k].d; else x = 0; return true; } //函数功能：将稀疏矩阵打印 void DispMat(TSMatrix t) { if (t.nums <= 0) return; printf("\t%d\t%d\t%d\n", t.rows, t.cols, t.nums); printf("\t-----------------\n"); for (int i = 0; i < t.nums; i++) printf("\t%d\t%d\t%d\n", t.data[i].r, t.data[i].c, t.data[i].d); } //将稀疏矩阵t转置为稀疏矩阵tb void TranMat(TSMatrix t, TSMatrix& tb) { int i, j, k = 0; tb.rows = t.cols; //t的行数变为tb的列数 tb.cols = t.rows; //t的列数变为tb的行数 tb.nums = t.nums; //t的非零值和tb的非零值相同 if (t.nums != 0) //如果该矩阵有非0值 { //这是很慢的算法了 //按列来扫是因为转置矩阵相当于按行来添加的元素 for (i = 0; i < t.cols; i++) //按列来扫 for (j = 0; j < t.nums; j++) if (t.data[j].c == i) //如果该元素的行数等于现在的行数 { tb.data[k].r = t.data[j].c; tb.data[k].c = t.data[j].r; tb.data[k].d = t.data[j].d; k++; } } } //两个稀疏矩阵相加 //a矩阵与b矩阵相加得到c bool MatAdd(TSMatrix a, TSMatrix b, TSMatrix& c) { int i = 0, j = 0, k = 0; int v; //两个矩阵行列不相同则无法相加 if (a.rows != b.rows || a.cols != b.cols) return false; //初始化矩阵c c.rows = a.rows; c.cols = a.cols; //i和j和k的初始值都为0 while (i < a.nums && j < b.nums) { if (a.data[i].r == b.data[j].r)//先控制行相等 {//行相等了才能再判断列是不是相等 //如果a的i元素的列小于b的j元素的列 if (a.data[i].c < b.data[j].c) { //c[k]元素就等于a的[i] //第一遍k=0其实就是c的第一个元素 c.data[k].r = a.data[i].r; c.data[k].c = a.data[i].c; c.data[k].d = a.data[i].d; k++; i++;//a.data[i++] } else if (a.data[i].c > b.data[j].c) { //此是c的第[k]个元素等于b的第[j]个元素 c.data[k].r = b.data[j].r; c.data[k].c = b.data[j].c; c.data[k].d = b.data[j].d; k++; j++;//b.data[j++] } else//如果行相等的前提下列也相等 { //保存的value值相加 v = a.data[i].d + b.data[j].d; if (v != 0) { c.data[k].r = a.data[i].r; c.data[k].c = a.data[i].c; c.data[k].d = v; k++; } i++; j++; } } //如果行不相等，a[i]的行小于b[j]的行 //那c的下一个元素就填上a[i](方便从小到大顺序存储) else if (a.data[i].r < b.data[j].r) { c.data[k].r = a.data[i].r; c.data[k].c = a.data[i].c; c.data[k].d = a.data[i].d; k++; i++; } //如果行不相等，a[i]的行大于b[j]的行 else { c.data[k].r = b.data[j].r; c.data[k].c = b.data[j].c; c.data[k].d = b.data[j].d; k++; j++; } c.nums = k; } return true; } //返回矩阵c低i行第j列的值 int getvalue(TSMatrix c, int i, int j) { int k = 0; //遍历稀疏矩阵里的值 while (k < c.nums && (c.data[k].r != i || c.data[k].c != j)) k++; if (k < c.nums) return (c.data[k].d); else//稀疏矩阵，如果没有找到当然就返回0 return (0); } //稀疏矩阵相乘 //由矩阵乘法规则可知 //C(i,j) = A(i,1)*B(1,j)+A(i,2)*B(2,j)+....+A(i,n)*B(n,j) //即C(i,j)为A的第i行与B的第j列非零元素乘积之和。 bool MatMul(TSMatrix a, TSMatrix b, TSMatrix& c) { int i, j, k, p = 0; int s;//s用来累加相乘的值 //a乘b，如果a的行数与b的列数不相等，则两个矩阵无法相乘 if (a.cols != b.rows) return false;//返回执行错误 for (i = 0; i < a.rows; i++) for (j = 0; j < b.cols; j++) { s = 0; //这一步用getvalue函数很聪明，因为getvalue对没有值的数据会返回0 for (k = 0; k < a.cols; k++) s += getvalue(a, i, k) * getvalue(b, k, j); //如果算出来的结果不为0，就添加到稀疏矩阵c中 if (s != 0) { c.data[p].r = i; c.data[p].c = j; c.data[p].d = s; p++; } } //乘完后，c的行数等于a的行数，c的列数等于a的列数 c.rows = a.rows; c.cols = b.cols; //c里面总共有p个有值的数 c.nums = p; return true;//返回执行正确 } int main() { int a1[N][N] = { {1,0,3,0},{0,1,0,0},{0,0,1,0},{0,0,1,1} }; int b1[M][M] = { {3,0,0,0},{0,4,0,0},{0,0,1,0},{0,0,0,2} }; TSMatrix a, b, c; CreatMat(a, a1); CreatMat(b, b1); printf("a的三元组:\n"); DispMat(a); printf("b的三元组:\n"); DispMat(b); printf("a转置为c\n"); TranMat(a, c); printf("c的三元组\n"); DispMat(c); printf("c=a+b\n"); MatAdd(a, b, c); printf("c的三元组：\n"); DispMat(c); printf("c=a*b\n"); MatMul(a, b, c); printf("c的三元组:\n"); DispMat(c); return 0; }