稀疏矩陣:M*N的矩陣,矩陣中有效值的個(gè)數(shù)遠(yuǎn)小于無效值的個(gè)數(shù),且這些數(shù)據(jù)的分布沒有規(guī)律
創(chuàng)新互聯(lián)建站專業(yè)為企業(yè)提供福海網(wǎng)站建設(shè)、福海做網(wǎng)站、福海網(wǎng)站設(shè)計(jì)、福海網(wǎng)站制作等企業(yè)網(wǎng)站建設(shè)、網(wǎng)頁(yè)設(shè)計(jì)與制作、福海企業(yè)網(wǎng)站模板建站服務(wù),10年福海做網(wǎng)站經(jīng)驗(yàn),不只是建網(wǎng)站,更提供有價(jià)值的思路和整體網(wǎng)絡(luò)服務(wù)。
如下圖所示:
一般情況下,我們會(huì)想到只要交換對(duì)應(yīng)的行和列,但是這種做法很浪費(fèi)時(shí)間和空間,所以我們可以利用三元組進(jìn)行存儲(chǔ),壓縮存儲(chǔ)極少數(shù)的有效數(shù)據(jù),使用{row,col,value}三元組存儲(chǔ)每一個(gè)有效數(shù)據(jù),三元組按原矩陣中的位置,以行優(yōu)先級(jí)先后順序依次存放。
#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() //逆轉(zhuǎn)矩陣 { //務(wù)必保持行優(yōu)先 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() //快速轉(zhuǎn)置 { 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; }; 測(cè)試代碼如下: 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 << "轉(zhuǎn)置之前:" << endl; d.display((int*)a, 6, 5, 0); cout << endl; cout << "轉(zhuǎn)置之后:" << endl; tmp.display((int*)a, 5, 6, 0); } int main() { test(); system("pause"); return 0; }
運(yùn)行結(jié)果如下:
網(wǎng)站標(biāo)題:稀疏矩陣的轉(zhuǎn)置
轉(zhuǎn)載來于:http://www.muchs.cn/article40/jiojeo.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供移動(dòng)網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì)公司、定制網(wǎng)站、網(wǎng)站收錄、軟件開發(fā)、標(biāo)簽優(yōu)化
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請(qǐng)盡快告知,我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如需處理請(qǐng)聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時(shí)需注明來源: 創(chuàng)新互聯(lián)