您好,登录后才能下订单哦!
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
压缩存储值存储极少数的有效数据。使用{row,col,value}三元组存储每一个有效数据,三元组按原矩阵中的位置,以行优先级先后顺序依次存放。 #define _CRT_SECURE_NO_WARNINGS 1 #include <vector> #include<iostream> using namespace std; //三元组的定义 template<class T> struct Triple { T _value; size_t _row; size_t _col; Triple(const T& value = T(), size_t row = 0, size_t col = 0) :_value(value) , _row(row) , _col(col) {} }; template<class T> class SparseMatrix { public: //无参构造函数 SparseMatrix() :_colSize(0) , _rowSize(0) {} //矩阵的压缩 SparseMatrix(T* a, size_t m, size_t n, const T& invalid) :_rowSize(m) , _colSize(n) , _invalid(invalid) { for (size_t i = 0; i < m; ++i)//行遍历 { for (size_t j = 0; j < n; ++j)//列遍历 { if (a[i*n + j] != invalid) { _a.push_back(Triple<T>(a[i*n + j], i, j)); } } } } void Display()//打印 { size_t index = 0; for (size_t i = 0; i < _rowSize; ++i) { for (size_t j = 0; j < _colSize; ++j) { if (index < _a.size() && _a[index]._row == i && _a[index]._col == j) { cout << _a[index]._value << " "; ++index; } else { cout << _invalid << " "; } } cout << endl; } cout << endl; } SparseMatrix<T> Transport()//列转置 { SparseMatrix<T> tmp; tmp._colSize = _rowSize; tmp._rowSize = _colSize; tmp._invalid = _invalid; for (size_t i = 0; i < _colSize; ++i) { size_t index = 0; while (index < _a.size()) { if (_a[index]._col == i) { Triple<T> t; t._value = _a[index]._value; t._row = _a[index]._col; t._col = _a[index]._row; tmp._a.push_back(t); } ++index; } } return tmp; } SparseMatrix<T> FastTransport()//快速转置 { SparseMatrix<T> tmp; tmp._colSize = _rowSize; tmp._rowSize = _colSize; tmp._invalid = _invalid; int* rowCounts = new int[_colSize]; int* rowStart = new int[_colSize]; memset(rowCounts, 0, sizeof(int)*_colSize); memset(rowStart, 0, sizeof(int)*_colSize); size_t index = 0; while (index < _a.size()) { rowCounts[_a[index]._col]++; ++index; } rowStart[0] = 0; for (size_t i = 1; i < _colSize; ++i) { rowStart[i] = rowStart[i - 1] + rowCounts[i - 1]; } index = 0; tmp._a.resize(_a.size()); while (index < _a.size()) { size_t rowIndex = _a[index]._col; int& start = rowStart[rowIndex]; Triple<T> t; t._value = _a[index]._value; t._row = _a[index]._col; t._col = _a[index]._row; tmp._a[start++] = t; ++index; } return tmp; } protected: vector<Triple<T>> _a;//三元组类型的顺序表 size_t _rowSize;//行 size_t _colSize;//列 T _invalid;//非法值 }; void TestSparseMatrix() { int a[6][5] = { { 1, 0, 3, 0, 5 }, { 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0 }, { 2, 0, 4, 0, 6 }, { 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0 } }; SparseMatrix<int> sm1((int*)a, 6, 5, 0); sm1.Display(); SparseMatrix<int> sm2 = sm1.Transport(); sm2.Display(); SparseMatrix<int> sm3 = sm1.FastTransport(); sm3.Display(); } int main() { TestSparseMatrix(); getchar(); return 0; }
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。