1.对称矩阵

特点： 关于对角线对称，Aij == Aji。 下面实现： ①对称矩阵的压缩存储 ②对称矩阵的访问 ③对称矩阵的还原

实现代码如下：

#define _CRT_SECURE_NO_WARNINGS 1 #include<iostream> using namespace std; //对称矩阵的压缩存储 template<class T> class SymmetricMatrix { public: SymmetricMatrix(T* array, size_t N) :_N(N) ,_a(NULL) { _a = new T[(N * (N + 1))>> 1]; for (size_t i = 0; i < N; ++i) { for (size_t j = 0; j < N; ++j) { if (i >= j)//表明是下三角数据时 { _a[(i * (i + 1))>>1 + j] = array[i * N + j]; } else { break; } } } } T& Access(size_t x, size_t y) { if (x < y)//如果访问上三角元素 { swap(x, y); } return _a[(x * (x + 1)) >> 1 + y]; } void DisPlay() { for (size_t i = 0; i < _N; ++i) { for (size_t j = 0; j < _N; ++j) { if (i >= j)//访问下三角元素 { cout<<Access(i, j)<<" "; } else { cout << Access(j, i) << " "; } } cout << endl; } cout << endl; } ~SymmetricMatrix() { if (_a) { delete[] _a; _a = NULL; } } private: T* _a; size_t _N; };

测试代码如下：

void Test() { int a[5][5] = { { 0, 1, 2, 3, 4 }, { 1, 0, 1, 2, 3 }, { 2, 1, 0, 1, 2 }, { 3, 2, 1, 0, 1 }, { 4, 3, 2, 1, 0 }, }; SymmetricMatrix<int> sm((int*)a, 5); cout << sm.Access(0, 3) << endl; cout << sm.Access(3, 0) << endl; sm.DisPlay(); } int main() { Test(); return 0; }

2.稀疏矩阵：

(1)稀疏矩阵的压缩存储：

所谓稀疏矩阵的压缩存储，其实就是将稀疏矩阵中的有效元素保存起来，但由于稀疏矩阵中有效元素的分布没有规律可寻，所以需要使用一个三元组来保存其位置（row、col）以及有效值。—>三元组最好使用结构体来存储。

因为不知道矩阵中究竟有多少个有效元素（即就是不知需要多少个结构体），那么就可以使用vector（动态增长型）来保存有效元素。

//三元组--->存储有效元素的位置及值 template<class T> struct Trituple { Trituple(size_t row, size_t col, const T& data) :_row(row) , _col(col) , _data(data) {} size_t _row; size_t _col; T _data; }; //稀疏矩阵的压缩存储 SparseMatrix(T* array, int row, int col,const T& invalid) :_row(row) , _col(col) ,_invalid(invalid) { for (int i = 0; i < row; ++i) { for (int j = 0; j < col; ++j) { if (array[i * col + j] != invalid) { _sm.push_back(Trituple<T>(i, j, array[i * col + j])); } } } }

(2)稀疏矩阵的转置：

稀疏矩阵的转置过程如下：

实现代码如下：

// 稀疏矩阵的转置 //时间复杂度：(稀疏矩阵的列*稀疏矩阵中有效元素的个数) SparseMatrix<T> Transprot() { SparseMatrix<T> sm; sm._row = _col; sm._col = _row; for (size_t index = 0; index < _col; ++index) { vector<Trituple<T> >::iterator it = _sm.begin(); while (it != _sm.end()) { if ( it->_col == index) { sm._sm.push_back(Trituple<T>(it->_col, it->_row, it->_data)); } it++; } } return sm; }

3.稀疏矩阵的快速转置：

稀疏矩阵的转置的时间复杂度：(稀疏矩阵的列N*稀疏矩阵中有效元素的个数)—-》时间复杂度较大，所以引出了快速转置

稀疏矩阵的快速转置的时间复杂度（2*有效元素的个数 + 稀疏矩阵的列）

快速转置的思想如下：

代码实现：

//快速转置 SparseMatrix<T,N,M> FastTransport(const size_t m,const size_t n) { SparseMatrix < T, N, M> sm;//转置后的压缩矩阵 sm._row = _col; sm._col = _row; sm._v.resize(_v.size());//为了保证后面可以直接访问vector中的数据（调用operator[]） //保存转置前的每列有效元素的个数,即就是转置后每行有效元素的个数 int rows[N] = {0}; size_t index = 0; while (index < _v.size()) { rows[_v[index]._col]++; index++; } //保存转置后的每行第一个有效元素在转置后的三元组数组中的下标 int starts[N] = { 0 }; for (size_t i = 1; i < _col; ++i) { starts[i] = starts[i - 1] + rows[i - 1]; } for (size_t i = 0; i < _v.size(); ++i) { int row = _v[i]._col;//转置前列的下标即是转置后行的下标 Triple<T> t; t._value = _v[i]._value; t._col = _v[i]._row; t._row = _v[i]._col; sm._v[starts[row]] = t; starts[row]++;//每次需要更新starts数组中的数据 } return sm; }

全部代码如下：

#define _CRT_SECURE_NO_WARNINGS 1 #include<iostream> using namespace std; #include<vector> //三元组 template<class T> struct Triple { Triple() {} Triple(T& data, size_t row, size_t col) :_value(data) , _row(row) , _col(col) {} T _value; size_t _row; size_t _col; }; template<class T,size_t M,size_t N> class SparseMatrix { public: SparseMatrix() {} //稀疏矩阵的压缩存储 SparseMatrix(T* array, const T& invalid) :_invalid(invalid) , _row(M) , _col(N) { for (size_t i = 0; i < _row; ++i) { for (size_t j = 0; j < _col; ++j) { if (array[i * N + j] != invalid) { Triple<T> t; t._value = array[i * N + j]; t._row = i; t._col = j; _v.push_back(t); } } } } //稀疏矩阵的还原 void Display() { int index = 0; for (size_t i = 0; i < _row; ++i) { for (size_t j = 0; j < _col; ++j) { if (index < _v.size() && _v[index]._row == i && _v[index]._col == j) { cout << _v[index]._value << " "; index++; } else { cout << _invalid << " "; } } cout << endl; } cout << endl; } //稀疏矩阵的转置 SparseMatrix<T,N,M> Transport() { SparseMatrix<T,N,M> _sm;//转置后的 _sm._invalid = _invalid; _sm._row = _col; _sm._col = _row; //按列查找（转置前的列优先即就是转置后的行优先） for (size_t i = 0; i < _col; ++i) { size_t index = 0; while (index < _v.size()) { if (_v[index]._col == i) { Triple<T> t; t._value = _v[index]._value; t._row = _v[index]._col; t._col = _v[index]._row; _sm._v.push_back(t); } index++; } } return _sm; } template<class T, size_t N, size_t M> friend class SparseMatrix; //快速转置 SparseMatrix<T,N,M> FastTransport(const size_t m,const size_t n) { SparseMatrix < T, N, M> _sm;//转置后的压缩矩阵 _sm._row = _col; _sm._col = _row; _sm._v.resize(_v.size());//为了保证后面可以直接访问vector中的数据（使用operator[]） //保存转置前的每列有效元素的个数,即就是转置后每行有效元素的个数 int rows[N] = {0}; size_t index = 0; while (index < _v.size()) { rows[_v[index]._col]++; index++; } //保存转置后的每行第一个有效元素在转置后的三元组数组中的下标 int starts[N] = { 0 }; for (size_t i = 1; i < _col; ++i) { starts[i] = starts[i - 1] + rows[i - 1]; } for (size_t i = 0; i < _v.size(); ++i) { int row = _v[i]._col;//转置前列的下标即是转置后行的下标 Triple<T> t; t._value = _v[i]._value; t._col = _v[i]._row; t._row = _v[i]._col; _sm._v[starts[row]] = t; starts[row]++;//每次需要更新starts数组中的数据 } return _sm; } private: vector<Triple<T> > _v; T _invalid; size_t _row; size_t _col; };

测试代码如下：

void Test() { int array[6][5] = { { 1, 0, 3, 0, 5 }, { 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0 }, { 1, 0, 3, 0, 5 }, { 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0 }, }; SparseMatrix<int,6,5> sm((int*)array, 0); sm.Display(); SparseMatrix<int,5,6> sm2 = sm.FastTransport(5,6); sm2.Display(); } int main() { Test(); return 0; }

由于能力有限，又是刚开始学习数据结构，难免会有思考的不正确或是不完善的地方，欢迎大家批评指正。。。