#include<iostream>
#include<vector>
#include<string>
using namespace std;
//
template<class T>
struct Triple
{
size_t _row;
size_t _col;
T _value;
};
template<class T>
class SparseMatrix
{
public:
SparseMatrix();
SparseMatrix(T* a,size_t row,size_t col,const T& invalid);
SparseMatrix(const SparseMatrix<T>& sm);
SparseMatrix<T>& operator=(const SparseMatrix<T>& sm);
~SparseMatrix();
void Display();
SparseMatrix& Transpose();
SparseMatrix& FastTranspose();
private:
vector<Triple<T>> _array;
size_t _rowSize;
size_t _colSize;
T _invalid;
};
template<class T>
SparseMatrix<T>::SparseMatrix()
:_rowSize(0)
,_colSize(0)
,_invalid(0)
{}
template<class T>
SparseMatrix<T>::SparseMatrix(T* a,size_t row,size_t col,const T& invalid)
:_rowSize(row)
,_colSize(col)
,_invalid(invalid)
{
for(size_t i=0;i<_rowSize;i++)
{
for(size_t j=0;j<_colSize;j++)
{
if(a[i*_colSize+j]!=_invalid)
{
Triple<T> t;
t._row=i;
t._col=j;
t._value=a[i*_colSize+j];
_array.push_back(t);
}
}
}
}
template<class T>
SparseMatrix<T>::SparseMatrix(const SparseMatrix<T>& sm)
:_rowSize(sm._rowSize)
,_colSize(sm._colSize)
,_invalid(sm._invalid)
{
for(size_t i=0;i<sm._array.size();i++)
{
_array.push_back(sm._array[i]);
}
}
template<class T>
SparseMatrix<T>& SparseMatrix<T>::operator=(const SparseMatrix<T>& sm)
{
_rowSize=sm._rowSize;
_colSize=sm._colSize;
_invalid=sm._invalid;
for(size_t i=0;i<_sm.array.size(;i++))
{
_array.push_back(sm._array[i]);
}
return *this;
}
template<class T>
SparseMatrix<T>::~SparseMatrix()
{}
template<class T>
void SparseMatrix<T>::Display()
{
size_t index=0;
for(size_t i=0;i<_rowSize;i++)
{
for(size_t j=0;j<_colSize;j++)
{
if(index<_array.size()&&(_array[index]._row==i)
&&(_array[index]._col==j))
{
cout<<_array[index]._value;
index++;
}
else
{
cout<<_invalid;
}
cout<<" ";
}
cout<<endl;
}
cout<<endl;
}
//
template<class T>
SparseMatrix<T>& SparseMatrix<T>::Transpose()
{
SparseMatrix<T> sm;
for(size_t i=0;i<_colSize;i++)
{
for(size_t index=0;index<_array.size();index++)
{
if(_array[index]._col==i)
{
Triple<T> t;
t._row=_array[index]._col;
t._col=_array[index]._row;
t._value=_array[index]._value;
sm._array.push_back(t);
}
}
}
swap(sm._array,_array);
swap(_rowSize,_colSize);
return *this;
}
//
template<class T>
SparseMatrix<T>& SparseMatrix<T>:: FastTranspose()
{
int* RowCounts=new int[_colSize];// //2 0 2 0 2
int* RowStart=new int[_colSize];// // new _colSize, // , 0 2 2 4 4
memset(RowCounts,0,sizeof(int)*_colSize);
// RowCounts
memset(RowStart,0,sizeof(int)*_colSize);
for(size_t index=0;index<_array.size();index++)
{
RowCounts[_array[index]._col]++;
}
// RowStart
RowStart[0]=0;
for(size_t index=1;index<_colSize;index++)
{
RowStart[index]= RowStart[index-1]+RowCounts[index-1];
}
RowStart[0]=0;
for(int index=0;index<_array.size();index++)
{
Triple<T> t;
t._row=_array[index]._col;
t._col=_array[index]._row;
t._value=_array[index]._value;
}
return *this;
}
void Test1()
{
int a[]={1,0,3,0,5,0,0,0,0,0,0,0,0,0,0,1,0,3,0,5,0,0,0,0,0,0,0,0,0,0,0,};
SparseMatrix<int> sm1(a,6,5,0);
sm1.Display();
SparseMatrix<int>sm2(sm1);
sm2.Display();
SparseMatrix<int>sm3=sm1;
sm3.Display();
}
void Test2()
{
int a[6][5]={
{1,0,3,0,5},
{0,0,0,0,0},
{0,0,0,0,0},
{1,0,3,0,5},
{0,0,0,0,0},
{0,0,0,0,0}
};
SparseMatrix<int> sm1(a[0],6,5,0);
sm1.Display();
SparseMatrix<int> sm2=sm1.Transpose();
sm2.Display();
SparseMatrix<int> sm3=sm1.FastTranspose();
sm3.Display();
}
int main()
{
//Test1();
Test2();
system("pause");
return 0;
}