压缩存储稀疏矩阵的非零元素，存储非零元素的行号，列号，值。用一个三元式(row, col, value)唯一表示，可以按行排序或者列排 序，成为行三元组或列三元组。 实现代码： ~~~ #include "iostream" #include "cstdio" #include "cstring" #include "algorithm" using namespace std; template <class T> struct node { /* data */ int row, col; T value; }; template <class T> class SeqTriple { public: SeqTriple(int mSize); ~SeqTriple() { delete []trip; } void Add(const SeqTriple<T> &B, const SeqTriple<T> &C) const; void Mul(const SeqTriple<T> &B, const SeqTriple<T> &C) const; void Transpose(SeqTriple<T> &B); friend istream &operator >> (istream &in, const SeqTriple<T> &); friend ostream &operator << (ostream &out, const SeqTriple<T> &); /* data */ private: int maxSize, m, n, t; // 最大元素个数，稀疏矩阵的行数，列数以及非零元个数 node<T> *trip; }; ~~~ 下面重点分析三中转置稀疏的方法，转置A矩阵到B矩阵中。 1.将三元组A中所有元素的行，列交换后保存到B中，然后按B中的行号排序。时间复杂度：O(n*logn) 2.对三元组A扫描n遍(i = 0 ~ n -1)，每遍扫描t次(j = 0 ~ t - 1)。第I遍扫描时，找出A中列号col等于I第j行元素(可以是多个)，并将第j 行元素转置后存入B中的位置k。时间复杂度：O(n * t) 实现代码： ~~~ k = 0; for(int i = 0; i < n; ++i) for(int j = 0; j < t; ++j) if(A[j].col == i) { B[k].col = A[j].row; B[k].row = A[j].col; B[k++].value = A[j].value; } ~~~ 3.方法2只用了一个指针k，用来指示转置后元素在B中存放的位置，因此在B中必须按0 ~ n - 1的顺序存放，导致反复扫描A，效率不 高。方法3使用n个指针k[i](n是指针的列数)，指向稀疏矩阵M中的第i列的第一非零元素在转置后的三元组B中的存放位置。 稀疏矩阵M中下标0列的第1个非零元素也是转置后的矩阵中下标0行的第1个非零元素，他在转置后的三元组B中的位置一定是0， k[0] = 0。用num[0]表示M中下标0列的非零元素的个数，k[1]表示M中下标1列的第1个非零元素在B中的位置，k[1] = k[0] + num[0]。 可以得到以下式子： k[0] = 0                               i = 0 k[i] = k[i - 1] + num[i - 1]     1 <= i && i < n 时间复杂度：O(n + t) 实现代码： ~~~ template <class T> void SeqTriple<T>::Transpose(SeqTriple<T> &B) const // 将this转置赋给B { int *num = new T[n], *k = new int[n]; B.m = n, B.n = m, B.t = t; if(t > 0) { memset(num, 0, sizeof(num)); for(int i = 0; i < t; ++i) num[trip[i].col]++; k[0] = 0; for(int i = 0; i < n; ++i) k[i] = k[i - 1] + num[i - 1]; for(int i = 0; i < t; ++i) { // 扫描this对象的三元组表 int j = k[trip[i].col]; // 求this对象的第i项在B中的位置j B.trip[j].row = trip[i].col; // 将this对象的第i项转置到B中的位置j B.trip[j].col = trip[i].row; B.trip[j].value = trip[i].value; } } delete [] k; } ~~~