您好,登錄后才能下訂單哦!
稀疏矩陣:M*N的矩陣,矩陣中有效值的個數遠小于無效值的個數,且這些數據的分布沒有規律
如下圖所示:
一般情況下,我們會想到只要交換對應的行和列,但是這種做法很浪費時間和空間,所以我們可以利用三元組進行存儲,壓縮存儲極少數的有效數據,使用{row,col,value}三元組存儲每一個有效數據,三元組按原矩陣中的位置,以行優先級先后順序依次存放。
#define _CRT_SECURE_NO_WARNINGS 1 #pragma once #include<vector> #include<iostream> using namespace std; template<class T> 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 T> 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<T> 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<T> Transport() //逆轉矩陣 { //務必保持行優先 SparseMatrix<T> 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<T> 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<T> FastTransport() //快速轉置 { SparseMatrix<T> 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<T> 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<Triple<T>> _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<int> d((int*)a, 6, 5, 0); SparseMatrix<int> 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; }
運行結果如下:
免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。