稀疏矩阵的转置-创新互联
稀疏矩阵:M*N的矩阵,矩阵中有效值的个数远小于无效值的个数,且这些数据的分布没有规律
成都服务器托管,创新互联建站提供包括服务器租用、服务器机柜租用、带宽租用、云主机、机柜租用、主机租用托管、CDN网站加速、域名申请等业务的一体化完整服务。电话咨询:18980820575如下图所示:
一般情况下,我们会想到只要交换对应的行和列,但是这种做法很浪费时间和空间,所以我们可以利用三元组进行存储,压缩存储极少数的有效数据,使用{row,col,value}三元组存储每一个有效数据,三元组按原矩阵中的位置,以行优先级先后顺序依次存放。
#define _CRT_SECURE_NO_WARNINGS 1 #pragma once #include#include using namespace std; template struct Triple //定义三元组 { int _row; int _col; T _value; Triple(int row, int col, T& value) :_row(row) , _col(col) , _value(value) {} Triple() :_row(0) , _col(0) , _value(0) {} }; template class SparseMatrix { public: SparseMatrix(T* a, int m, int n, const T& invalid)//invalid为非法值 :_rowsize(m) , _colsize(n) , _invaild(invalid) { for (int i = 0; i < m; ++i) { for (int j = 0; j < n; j++) { if (a[i*n + j] != invalid) { Triple tmp(i, j, a[i*n + j]); _a.push_back(tmp); } } } } SparseMatrix(size_t rowsize, size_t colsize, T invaild) :_rowsize(rowsize), _colsize(colsize), _invaild(invaild) {} void display(T* a, int m, int n, const T& invalid) //打印稀疏矩阵 { int p = 0; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; j++) { if (p < _a.size() && _a[p]._row == i&&_a[p]._col == j) { cout << _a[p]._value << " "; p++; } else { cout << invalid << " "; } } cout << endl; } } SparseMatrix Transport() //逆转矩阵 { //务必保持行优先 SparseMatrix sm(_colsize, _rowsize, _invaild); for (size_t i = 0; i < _colsize; i++) { size_t index = 0; while (index < _a.size()) { if (_a[index]._col == i) { Triple mm; mm._col = _a[index]._row; mm._row = _a[index]._col; mm._value = _a[index]._value; sm._a.push_back(mm); } ++index; } } return sm; } SparseMatrix FastTransport() //快速转置 { SparseMatrix temp; temp._a.resize(_a.size()); int* rowcounts = new int[_col]; int* rowstarts = new int[_col]; memset(rowcounts, 0, sizeof((int)*_col)); memset(rowstarts, 0, sizeof((int)*_col)); size_t index = 0; while (index < _a.size()) { rowcounts[_a[index]._col]++; ++index; } rowstarts[0] = 0; for (size_t i = 0; i < _col; ++i) { rowstarts[i] = rowstarts[i - 1] + rowcounts[i - 1]; } while (index < _a.size()) { size_t& begin = rowstarts[_a[index]._col]; Triple tp; tp._row = _a[index]._col; tp._col = _a[index]._row; tp._value = _a[index]._value; tmp._a[rowstarts++] = tp; ++index; } delete[] _a; return tmp; } protected: size_t _rowsize; size_t _colsize; T _invaild; vector > _a; }; 测试代码如下: void test() { 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 d((int*)a, 6, 5, 0); SparseMatrix tmp = d.Transport(); cout << "转置之前:" << endl; d.display((int*)a, 6, 5, 0); cout << endl; cout << "转置之后:" << endl; tmp.display((int*)a, 5, 6, 0); } int main() { test(); system("pause"); return 0; }
运行结果如下:
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
新闻标题:稀疏矩阵的转置-创新互联
本文路径:http://scyanting.com/article/dpidhs.html