您好,登錄后才能下訂單哦!
壓縮存儲(chǔ)值存儲(chǔ)極少數(shù)的有效數(shù)據(jù)。使用{row,col,value}三元組存儲(chǔ)每一個(gè)有效數(shù)據(jù),三元組按原矩陣中的位置,以行優(yōu)先級(jí)先后順序依次存放。 #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: //無(wú)參構(gòu)造函數(shù) 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()//列轉(zhuǎn)置 { 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()//快速轉(zhuǎn)置 { 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;//三元組類(lèi)型的順序表 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; }
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。