矩陣的存儲及轉置算法分析解析

1、矩陣的存儲及轉置算法本文要點：.對稱矩陣與稀疏矩陣.兩種矩陣的壓縮存儲.代碼實現(xiàn)兩種矩陣對稱矢巨陣.對稱矩陣也是一種特殊矩陣，滿足Aij=Aji(設矩陣為A,且有0=iN-1&0=j=j).代碼實現(xiàn)cppviewplaincopytemplateclassSymmetryMatrixpublic:SymmetryMatrix(constT*a,size_tn):_matrix(newTn*(n+1)/2),_size(n*(n+1)/2),_n(n)size_tindex=0;/表示一維數(shù)組的下標for(size_ti=0;i=j)/存儲下三角訪問數(shù)據(jù)_matrixindex+=ai*n+j;

2、/index+;elsecontinue;T&Access(size_trow,size_tcol)/if(rowcol)std:swap(row,col);return_matrixrow*(row+1)/2+col;voidDisplay。for(size_ti=0;i_n;i+)for(size_tj=0;j_n;j+)coutAccess(i,j);coutendl;protected:T*_matrix;/壓縮存儲的一維數(shù)組49.size_t_n;/行列的大小50.；稀疏失I陣.稀疏矩陣中，有效數(shù)據(jù)(非0)的數(shù)量遠小于非法數(shù)據(jù)的個數(shù)(0為非法數(shù)據(jù)).稀疏矩陣的存儲也是壓縮存儲的，但與

3、對稱矩陣不同的地方有兩點：(1)稀疏矩陣的壓縮存儲只存儲有效值；(2)稀疏矩陣存儲以行優(yōu)先的順序存儲在三元組中，表示為：row,col,value,row和col分別表示該有效值的行和列。一、存儲及輸出存儲的方法類似于對稱矩陣的存儲，但要將行和列也進行存儲；輸出的時候多考慮表示數(shù)組的下標會不會越界cppviewplaincopy/數(shù)據(jù)的存儲SpareMatrix(constT*a,size_trow,size_tcol,constT&invalid):_rowSize(row)，colSize(col),_invalid(invalid)for(size_ti=0;irow;i+) TOC o

4、 1-5 h z for(size_tj=0;jcol;j+)if(ai*col+j!=invalid)/有效值Triplet(i,j,ai*col+j);t._value=ai*col+j;t._row=i;t._col=j;_martix.push_back(t);19./輸出voidDisplay。size_tindex=0;for(size_ti=0;i_rowSize;+i)for(size_tj=0;j_colSize;+j)if(index_martix.size()&i=_martixindex._row&j=_martixindex._col)cout_martixindex

5、._value;+index;elsecout0;coutendl;coutendl;般轉置算法轉置前：10203000004005060000轉置后;10 4 60 0 0 00 0 00 0 5 00 0 01 4 6 2 5 3三元組的期序：|1 2 3 4 5目從上圖我們可以看出：矩陣轉置后，三元組中的順序也發(fā)生了改變。因此要得到矩陣置后的矩陣TM,我們只需將三元組的順序改變就好了。轉置的三步:a.將矩陣的行列交換b.將每個三元組中的行、列交換c.將原矩陣三元組的順序重排得到新的三元組cppviewplaincopySpareMatrixTransport。/矩陣的轉置SpareMat

6、rixTSMartix;TSMartix._rowSize=_colSize;/交換行列TSMartix._colSize=_rowSize;TSMartix._invalid=_invalid;TSMartix._artix.reserve(_martix.size();for(size_tcol=0;col_colSize;+col)/以列優(yōu)先進行查找 TOC o 1-5 h z for(size_tindex=0;index_martix.size();+index)if(_martixindex._col=col)Tripletmp(_martixindex._col,_martixi

7、ndex._row,_martixindex._value);TSMartix._tix.push_back(tmp);returnTSMartix;這樣算法即使可以得到結果，但是效率高不高呢？！算算時間復雜度0（矩陣的列數(shù)*有效數(shù)值的個數(shù)），如果這個矩陣是500*500呢？！顯然效率就會特別低了。因此，我們就需要一種轉置算法來提高效率。三、快速轉置（假設原矩陣為M,轉置后得到的矩陣為FSTM）我們按照普通轉置的算法，將M的三元組的次序進行轉置，并將每次轉置后的數(shù)據(jù)能直接放到FSTM三元組正確的位置。但這種算法的前提是：需要預先知道M每行的有效值個數(shù),將M中第一個有效數(shù)放到正確位置后，并記下該

8、位置，以后對M的三元組中的每個數(shù)進行轉置時，都可以直接放到正確的位置。引入兩個量count和start,count記錄每行的有效數(shù)據(jù)的個數(shù)start表示每行第一個數(shù)的起始位置轉置前:10203000004005060000三元組的順序：12 3 4 5 600 Q2 04 20 23 30count： 30111轉置后二10 4 60 0 0 02 0 0 00 0 5 03 0 0 0三元組的順序：|1 4 6 2 5/I 02 03 20 32 40count: 3 0 1 1 1start： 03356start； 033455分析上圖我們可以得到：start=上一行的起始位置+上一行的

9、有效數(shù)個數(shù)時間復雜度：O（2*有效值的個數(shù)+列數(shù)）代碼實現(xiàn)：cppviewplaincopyCSpareMatrixFastTransport()SpareMatrixFSTMartix;FSTMartix._rowSize=_colSize;FSTMartix._colSize=_rowSize;FSTMartix._invalid=_invalid;FSTMartix._martix.resize(_martix.size();int*count=newint_colSize;memset(count,0,_martix.size()*int*start=newint_colSize;me

10、mset(start,0,_martix.size()*/統(tǒng)計每列的有效值個數(shù)for(size_ti=0;i_martix.size();+i)count_martixi._col+;/計算每一列的起始位置for(size_tj=1;j_colSize;+j)startj=startj-1+countj-1;起始位置+上一列有效數(shù)個數(shù)交換行列sizeof(int);sizeof(int);每一列起始位置=上一列/轉置for(size_tindex=0;index_martix.size();+index)size_ttmp=_martixindex._col;/的列FSTMartix._mar

11、tixstarttmp._col=_martixindex._row;取到原三元組中每個數(shù)FSTMartix._martixstarttmp._row=_martixindex._col;FSTMartix._martixstarttmp._value=_martixindex._value;+starttmp;/start指針要向后移位returnFSTMartix;稀疏矩陣代碼的整體實現(xiàn)：cppviewplaincopytemplatestructTripleTriple(size_trow,size_tcol,constT&value=T():_row(row)，col(col)，val

12、ue(value)Triple()12.size_t_row;/行13.size_t_col;/列14.T_value;/后效值;templateclassSpareMatrixpublic:SpareMatrix():_martix(NULL),_rowSize(0)，colSize(0),_invalid(T()/數(shù)據(jù)的存儲SpareMatrix(constT*a,size_trow,size_tcol,constT&invalid):_rowSize(row)，colSize(col),_invalid(invalid)for(size_ti=0;irow;i+)for(size_tj=

13、0;jcol;j+)if(ai*col+j!=invalid)/有效值Triplet(i,j,ai*col+j);t._value=ai*col+j;t._row=i;t._col=j;_martix.push_back(t);/輸出voidDisplay。size_tindex=0;for(size_ti=0;i_rowSize;+i)54.for(size_tj=0;j_colSize;+j)if(index_martix.size()&i=_martixindex._row&j=_martixindex._col)cout_martixindex._value+index;else TO

14、C o 1-5 h z cout0;coutendl;coutendl;SpareMatrixTransports/矩陣的轉置SpareMatrixTSMartix;TSMartix._rowSize=_colSize;/交換行列TSMartix._colSize=_rowSize;TSMartix._invalid=_invalid;TSMartix._martix.reserve(_martix.size();for(size_tcol=0;col_colSize;+col)/以列優(yōu)先進行查找for(size_tindex=0;index_martix.size();+index)if(_

15、martixindex._col=col)85.86.87.Tripletmp(_martixindex._col,_martixindex._row,_martixindex._value);1.return TSMartix;92.93.94.SpareMatrix FastTransport()95.96.SpareMatrix FSTMartix;97.FSTMartix._rowSize = _colSize;交換行列98.FSTMartix._colSize = _rowSize;99.FSTMartix._invalid = _invalid;100.FSTM

16、artix._martix.resize(_martix.size();101.102.int * count = new int _colSize;103.memset(count,0,_martix.size()*sizeof(int);104.int * start = new int _colSize;105.memset(start,0,_martix.size()*sizeof(int);106.107./統(tǒng)計每列的有效值個數(shù)108.for ( size_t i=0; i_martix.size(); +i)109.110.count_martixi._col+;111.112.113./計算每一列的起始位置TSMartix._martix.push_back(tmp);114.for(size_tj=1;j_colSize;+j)115.116.每一列起始位置=上startj=startj-1+countj-1;一列起始位置+上一列有效數(shù)個數(shù)/轉置for(size_tindex=0;index_martix.size();+index)size_ttmp=_martixindex._col;/取到原三元組中每個數(shù)的列