矩陣的存儲及轉置算法

1、矩陣的存儲及轉置算法本文要點：1. 對稱矩陣與稀疏矩陣2兩種矩陣的壓縮存儲3.代碼實現兩種矩陣對稱矩陣 <SymmetryMatrix>1. 對稱矩陣也是一種特殊矩陣， 滿足Aij = Aji(設矩陣為A,且有0<=i<N-1 && 0<=j<N-1),這種矩陣以對角線分割為上三角和下三角，關于對角線對稱的元素相等。2. 對稱矩陣的壓縮存儲如果把矩陣中的每個元素都存儲起來，那么就會顯得浪費空間， 因為每兩個關于對角線對稱的元素相等，因此就可以將矩陣壓縮存儲到一個數組Array中，即：將對稱的兩個元素存一份，對角線上的元素都存儲起來，也就是說只

2、存儲上三角或下三角， 那么存儲的元素的總個 數就為n(n +1)/2個，這樣，當n特別大的時候，也就最有效。壓縮存儲的數組與矩陣之間滿足：Arrayi*(i+1)/2+j = Martixij(下三角存儲i>=j)3. 代碼實現cppview pla in copy1. template <class T>2. class SymmetryMatrix3. 4. public :5. SymmetryMatrix( const T* a, size_t n)6. :_matrix(new Tn*(n+1)/2)7. ,_size( n*( n+1)/2)8.,_n(n)9.1

3、0.size._t in dex - 0; /表示一維數組的下標11.for(size_t i=0; i<n; +i)12.13.for ( size_t j=0; j<n; +j)14.15.if (i >= j) /存儲下三角16.17._matrixi ndex+ = ai* n+j;18./in dex+;19.20.else21.con ti nue ;5.26.T& Access(size_t row, size_t col)/訪問數據27.28.if (row < col)29.30.std:swap(row,col);31.3

4、2.retur n_matrixrow*(row+1)/2+col;33.34.35.void Display()36.37.for ( size_t i=0; i<_n; i+)38.39.for ( size_t j=0; j<_n; j+)40.41.cout<<Access(i,j)<<""42.43.cout<<e ndl;44.45.46.protected :47.T* _matrix; /壓縮存儲的一維數組48.size_t _size; /可存儲的大小49.size_t _n;/行列的大小50. ;稀疏矩陣

5、<SparseMatrix>1. 稀疏矩陣中，有效數據（非0）的數量遠小于非法數據的個數（0為非法數據）2. 稀疏矩陣的存儲也是壓縮存儲的，但與對稱矩陣不同的地方有兩點：（1 ）稀疏矩陣的壓縮存儲只存儲有效值；（2）稀疏矩陣存儲以行優(yōu)先的順序存儲在三元組中，表示為：row,col,value ， row和col分別表示該有效值的行和列。一、存儲及輸出存儲的方法類似于對稱矩陣的存儲，但要將行和列也進行存儲；輸出的時候多考慮表示數組的下標會不會越界cppview pla in copy1./數據的存儲2.SpareMatrix( const T* a, size_t row, size

6、_tcol, const T& in valid)3.:_rowSize(row)4.，colSize(col)5.，in valid(i nvalid)6.7.for ( size_t i=0; i<row; i+)8.9.for ( size_t j=0; j<col; j+)10.11.if (ai*col+j != in valid) /有效值12.13.Triple<T> t(i,j,ai*col+j);14.t._value = ai*col+j;15.t._row = i;16.t._col = j;17._martix.push_back(t);

7、18.II輸出void Display。size_t in dex = 0;for ( size_t i=0; i<_rowSize; +i)for ( size_t j=0; j<_colSize; +j)if (index < _martix.size()&& i = _martixi ndex._row&& j = _martixi ndex._col)cout<<_martixi ndex._value<<""+i ndex;elsecout<<0<<"&qu

8、ot;cout<<e ndl;cout<<e ndl;3.44.45.般轉置算法轉置前：10 2 0 30 0 0 0 04 0 0 5 06 0 0 0 0轉置后:三元組的巔序：|1 2 3 4 5 &10 4 60 0 0 02 0 0 00 0 5 03 0 0 01 4 6 2 5 3從上圖我們可以看出：矩陣轉置后，三元組中的順序也發(fā)生了改變。因此要得到矩陣置后的矩陣TM，我們只需將三元組的順序改變就好了。轉置

9、的三步:a. 將矩陣的行列交換b. 將每個三元組中的行、列交換c.將原矩陣三元組的順序重排得到新的三元組cpp view pla in copy1. SpareMatrix<T> Tran sport() /矩陣的轉置2. 3. SpareMatrix<T> TSMartix;4. TSMartix._rowSize = _colSize;交換行列5. TSMartix._colSize = _rowSize;6. TSMartix._i nvalid = _in valid;7. TSMartix._artix.reserve(_martix.size();8.9.f

10、or ( size_t col=0; col<_colSize; +col) /以列優(yōu)先進行查找10.11.for ( size_tindex=0; index<_martix.size(); +index)12.13.if (_martixindex._col = col)14.15.Triple<T> tmp(_martixi ndex._col,_martixi ndex._row,_martixi ndex._value);16.TSMartix._marwww.sha nxiwa ng. nettix.push_back(tmp)17.18.轉養(yǎng)后二10 4

11、60 0 0 02 0 0 00 0 5 03 0 0 0三元組的順序；count:1 2 3 4 5 600 億 j- .：；、30111三元組的順序：H 4 6 2 3列I 02 03 20 32 40count: 30111start： 03356start: 03345519. 20. return TSMartix;21. 這樣算法即使可以得到結果，但是效率高不高呢？！算算時間復雜度0（矩陣的列數*有效數值的個數），如果這個矩陣是 500*500呢？！顯然效率就會特別低了。 因此，我們就需要一種轉置算法來提高效率。三、快速轉置（假設原矩陣為M，轉置后得到的矩陣為 FSTM）我們按照普

12、通轉置的算法，將M的三元組的次序進行轉置，并將每次轉置后的數據能直接放到FSTM三元組正確的位置。但這種算法的前提是： 需要預先知道 M每行的有效值個數, 將M中第一個有效數放到正確位置后，并記下該位置，以后對M的三元組中的每個數進行轉置時，都可以直接放到正確的位置。引入兩個量count和start， count記錄每行的有效數據的個數start表示每行第一個數的起始位置轉置前:10203000004005060000分析上圖我們可以得到：start =上一行的起始位置+上一行的有效數個數時間復雜度：O（2*有效值的個數+列數）代碼實現：cppview pla in copyC1.SpareM

13、atrix<T> FastTra nsport()2.3.SpareMatrix<T> FSTMartix;4.FSTMartix._rowSize = _colSize;交換行列5.FSTMartix._colSize = _rowSize;6.FSTMartix._i nvalid =n valid;7.FSTMartix._martix.resize(_martix.size();8.9.int * count =new int _colSize;10.memset(cou nt,0,_martix.size()*sizeof (int );11.int * st

14、art =new int _colSize;12.memset(start,0,_martix.size()*sizeof (int );13.14./統(tǒng)計每列的有效值個數15.for ( size_t i=0; i<_martix.size(); +i)16.17.coun t_martixi._col+;18.19.20./計算每一列的起始位置21.for ( size_t j=1; j<_colSize; +j)22.23.startj = startj-1 + coun tj-1;每一列起始位置-上一列起始位置+上一列有效數個數24.25.26./ 轉置27.for ( s

15、ize_tindex=0; index<_martix.size(); +index)28.29.size_t tmp = _martixi ndex._col;/取到原三元組中每個數的列30.FSTMartix._martixstarttmp._col = _martixi ndex._row;31.FSTMartix._martixstarttmp._row =_martixi ndex._col;32.FSTMartix._martixstarttmp._value=_martixi ndex._value;33.+starttmp; /start指針要向后移位34.35.retu

16、rn FSTMartix;36.稀疏矩陣代碼的整體實現:cppview plain copy1.template <class T>2.struct Triple3.4.Triple(size_t row,size_t col, const T& value = T()5.:_row(row)6.，col(col)7.，value(value)8.9.Triple()10.11.12.size_t _row; /行13.size_t _col; /列14.T _value;/有效值15.;16.17.t emplate <class T>18.class Spa

17、reMatrix19.20.public :21.SpareMatrix()22.:_martix(NULL)23.，rowSize(O)24.，colSize(O)25.,_i nvalid(T()26.27./數據的存儲28.SpareMatrix(const T* a, size_t row, size_tcol, const T& in valid)29.:_rowSize(row)30.,_colSize(col)31.,_i nvalid(i nvalid)32.33.for (size_t i=0; i<row; i+)34.35.for ( size_t j=0;

18、 j<col; j+)36.37.if (ai*col+j != in valid) /有效值38.39.Triple<T> t(i,j,ai*col+j);40.t._value = ai*col+j;41.t._row = i;42.t._col = j;43._martix.push_back(t);7.48./輸出49.void Display()50.51.size_tin dex = 0;52.for ( size_t i=0; i<_rowSize; +i)53.54.for ( size_t j=0; j<_colSize; +

19、j)55.56.if (index < _martix.size()57.&& i = _martixindex._row58.&& j = _martixi ndex._col)59.60.cout<<_martixi ndex._value<<""61.+in dex;62.63.else64.65.cout<<0<<""66.67.68.cout<<e ndl;69.70.cout<<e ndl;71.72.SpareMatrix<T

20、> Tran sport() /矩陣的轉置73.74.SpareMatrix<T> TSMartix;75.TSMartix._rowSize = _colSize;交換行列76.TSMartix._colSize = _rowSize;77.TSMartix._i nvalid = _in valid;78.TSMartix._martix.reserve(_martix.size();79.80.for ( size_t col=0; col<_colSize; +col)/以列優(yōu)先進行查找81.82.for ( size_tindex=0; index<_m

21、artix.size(); +i ndex)83.84.if (_martixindex._col =col)85.86.Triple<T> tmp(_martixindex._col,_martixindex._row,_martixi ndex._value);87.TSMartix._martix.push_back(tmp);1.return TSMartix;92.93.94.SpareMatrix<T> FastTra nsport()95.96.SpareMatrix<T> FSTMartix;97.FSTMartix._rowSize = _colSize;交換行列98.FSTMartix._colSize = _rowSize;99.FSTMartix._i nvalid =n valid;100.FSTMartix._martix.resize(_martix.size();101.102.int * count =new int _colSize;103.memset(cou nt,0,_martix.size()*sizeof(int );104.int * start =new int _colSize;105.memset(start,0,_martix.siz