壓縮存儲稀疏矩陣的非零元素，存儲非零元素的行號，列號，值。用一個三元式(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; } ~~~