[Data Structure] Sparse Matrix, Symmetric Matrix

Sparse matrix

in matrix, if the number of elements with a value of 0 is far more than the number of non-zero elements , The matrix is ​​called a sparse matrix

 #include #include#include using namespace std;templatestruct Triple{ T _value; size_t _row; size_t _col; Triple(T& value,size_t row,size_t col) :_value( value) ,_row(row) ,_col(col) ());templateclass SparseMatrix{public: SparseMatrix(T* a=0,size_t m=0,size_t n=0,const T& invalid=0) :_m(m) ,_n(n) ,_invalid(invalid) {for(size_t i=0;i(a[i*n+j],i,j ));}}}} ~SparseMatrix() {} void Display() {size_t index=0; for (int i=0;i<_m;++i) {for (int j=0;j<_n; ++j) {if(index<_matrixs.size() &&_matrixs[index]._row==i &&_matrixs[index]._col==j) {cout<<_matrixs[index]._value<<" "; ++ index;} else {cout<<_invalid<<" ";} //cout< Transport() {SparseMatrix Ts; Ts ._m=_n; Ts._n=_m; Ts._invalid=_invalid; for (int i=0;i<_n;++i) {size_t index=0; while (index<_matrixs.size()) {if (_matrixs[index]._col==i) {Ts._matrixs.push_back(Triple(_matrixs[index]._value,i,_matrixs[index]._row));} ++index;}} return Ts ; }private: vector> _matrixs; T _invalid;//illegal value int _m;//row int _n;//column};void test(){ int arr[4][4]= {{ 1,0,0,0}, {2,3,0,0}, {4,5,6,0}, {7,8,9,10} }; int arr2[4][4]= { {1,0,0,0}, {0,3, 0,0}, {4,0,0,0}, {0,0,9,10} }; SparseMatrix sm((int*)arr,4,4,0); cout<<"original Matrix "< sm1=sm.Transport(); cout<<"Transpose matrix"< s((int *)arr2,4,4,0); cout<<"original matrix"< sm2=s.Transport(); cout<<"transpose matrix"<< endl; sm2.Display();}

Symmetric matrix

elements are on the main diagonalis an equal matrix corresponding to the symmetry axis

#include #includeusing namespace std;templateclass SymmetricMatrix{public: SymmetricMatrix(T* matrix ,size_t n) :_matrix (new T[n*(n+1)/2]) ,_size(n*(n+1)/2) ,_n(n) {for(size_t i=0;i=j) {_matrix[i*(i+1)/2+j]=matrix[i*n+j];}} }} T& Access(size_t i,size_t j) {if(i<=j) swap(i,j); return _matrix[i*(i+1)/2+j];} void Print() {for ( size_t i=0;i<_n;i++) {for (size_t j=0;j<_n;j++) {cout< smx((int*)arr,6); smx.Print();}

Test function

#include "SparseMatrix.h"#include "SymmetricMatrix.h"int main( ){ test(); test2(); system( "pause"); return 0;}