本文要点：
1.对称矩阵与稀疏矩阵
2.两种矩阵的压缩存储
3.代码实现两种矩阵
对称矩阵<SymmetryMatrix>
1.对称矩阵也是一种特殊矩阵，满足Aij = Aji(设矩阵为A,且有0<=i<N-1 && 0<=j<N-1),这种矩阵以对角线分割为上三角和下三角，关于对角线对称的元素相等。
2.对称矩阵的压缩存储
如果把矩阵中的每个元素都存储起来，那么就会显得浪费空间，因为每两个关于对角线对称的元素相等，因此就可以将矩阵压缩存储到一个数组Array中，即：将对称的两个元素存一份，对角线上的元素都存储起来，也就是说只存储上三角或下三角，那么存储的元素的总个数就为n(n+1)/2个，这样，当n特别大的时候，也就最有效。
压缩存储的数组与矩阵之间满足：Array[i*(i+1)/2+j] = Martix[i][j](下三角存储i>=j)
3.代码实现
template<class T>
class SymmetryMatrix
{
public:
SymmetryMatrix(const T* a,size_t n)
:_matrix(new T[n*(n+1)/2])
,_size(n*(n+1)/2)
,_n(n)
{
size_t index = 0; //表示一维数组的下标
for (size_t i=0; i<n; ++i)
{
for (size_t j=0; j<n; ++j)
{
if (i >= j) //存储下三角
{
_matrix[index++] = a[i*n+j];
//index++;
}
else
continue;
}
}
}
T& Access(size_t row,size_t col) //访问数据
{
if (row < col)
{
std::swap(row,col);
}
return _matrix[row*(row+1)/2+col];
}
void Display()
{
for (size_t i=0; i<_n; i++)
{
for (size_t j=0; j<_n; j++)
{
cout<<Access(i,j)<<" ";
}
cout<<endl;
}
}
protected:
T* _matrix; //压缩存储的一维数组
size_t _size; //可存储的大小
size_t _n; //行列的大小
};稀疏矩阵<SparseMatrix>
1.稀疏矩阵中，有效数据（非0）的数量远小于非法数据的个数（0为非法数据）
2.稀疏矩阵的存储也是压缩存储的，但与对称矩阵不同的地方有两点：
（1）稀疏矩阵的压缩存储只存储有效值；
（2）稀疏矩阵存储以行优先的顺序存储在三元组中，表示为：{row,col,value}，row和col分别表示该有效值的行和列。
一、存储及输出
存储的方法类似于对称矩阵的存储，但要将行和列也进行存储；
输出的时候多考虑表示数组的下标会不会越界
//数据的存储
SpareMatrix(const T* a,size_t row,size_t col,const T& invalid)
:_rowSize(row)
,_colSize(col)
,_invalid(invalid)
{
for(size_t i=0; i<row; i++)
{
for (size_t j=0; j<col; j++)
{
if (a[i*col+j] != invalid) //有效值
{
Triple<T> t(i,j,a[i*col+j]);
t._value = a[i*col+j];
t._row = i;
t._col = j;
_martix.push_back(t);
}
}
}
}
//输出
void Display()
{
size_t index = 0;
for (size_t i=0; i<_rowSize; ++i)
{
for (size_t j=0; j<_colSize; ++j)
{
if (index < _martix.size()
&& i == _martix[index]._row
&& j == _martix[index]._col)
{
cout<<_martix[index]._value<<" ";
++index;
}
else
{
cout<<0<<" ";
}
}
cout<<endl;
}
cout<<endl;
}
从上图我们可以看出：矩阵转置后，三元组中的顺序也发生了改变。因此要得到矩阵M转置后的矩阵TM，我们只需将三元组的顺序改变就好了。转置的三步：
a.将矩阵的行列交换
b.将每个三元组中的行、列交换
c.将原矩阵三元组的顺序重排得到新的三元组
SpareMatrix<T> Transport() //矩阵的转置
{
SpareMatrix<T> TSMartix;
TSMartix._rowSize = _colSize;//交换行列
TSMartix._colSize = _rowSize;
TSMartix._invalid = _invalid;
TSMartix._martix.reserve(_martix.size());
for (size_t col=0; col<_colSize; ++col) //以列优先进行查找
{
for (size_t index=0; index<_martix.size(); ++index)
{
if (_martix[index]._col == col)
{
Triple<T> tmp(_martix[index]._col,_martix[index]._row,_martix[index]._value);
TSMartix._martix.push_back(tmp);
}
}
}
return TSMartix;
}
这样算法即使可以得到结果，但是效率高不高呢？！算算时间复杂度--------
O(矩阵的列数*有效数值的个数)，如果这个矩阵是500*500呢？！显然效率就会特别低了。因此，我们就需要一种转置算法来提高效率。
三、快速转置
（假设原矩阵为M，转置后得到的矩阵为FSTM）
我们按照普通转置的算法，将M的三元组的次序进行转置，并将每次转置后的数据能直接放到FSTM三元组正确的位置。但这种算法的前提是：需要预先知道M每行的有效值个数，将M中第一个有效数放到正确位置后，并记下该位置，以后对M的三元组中的每个数进行转置时，都可以直接放到正确的位置。
引入两个量count和start，count-----记录每行的有效数据的个数
start-------表示每行第一个数的起始位置
分析上图我们可以得到：start = 上一行的起始位置 + 上一行的有效数个数
时间复杂度：O(2*有效值的个数+列数)
代码实现：
SpareMatrix<T> FastTransport()
{
SpareMatrix<T> FSTMartix;
FSTMartix._rowSize = _colSize;//交换行列
FSTMartix._colSize = _rowSize;
FSTMartix._invalid = _invalid;
FSTMartix._martix.resize(_martix.size());
int* count = new int[_colSize];
memset(count,0,_martix.size()*sizeof(int));
int* start = new int[_colSize];
memset(start,0,_martix.size()*sizeof(int));
//统计每列的有效值个数
for (size_t i=0; i<_martix.size(); ++i)
{
count[_martix[i]._col]++;
}
//计算每一列的起始位置
for (size_t j=1; j<_colSize; ++j)
{
start[j] = start[j-1] + count[j-1];//每一列起始位置=上一列起始位置+上一列有效数个数
}
//转置
for (size_t index=0; index<_martix.size(); ++index)
{
size_t tmp = _martix[index]._col; //取到原三元组中每个数的列
FSTMartix._martix[start[tmp]]._col = _martix[index]._row;
FSTMartix._martix[start[tmp]]._row = _martix[index]._col;
FSTMartix._martix[start[tmp]]._value = _martix[index]._value;
++start[tmp]; //start指针要向后移位
}
return FSTMartix;
}
template<class T>
struct Triple
{
Triple(size_t row,size_t col,const T& value = T())
:_row(row)
,_col(col)
,_value(value)
{}
Triple()
{}
size_t _row; //行
size_t _col; //列
T _value; //有效值
};
template<class T>
class SpareMatrix
{
public:
SpareMatrix()
:_martix(NULL)
,_rowSize(0)
,_colSize(0)
,_invalid(T())
{}
//数据的存储
SpareMatrix(const T* a,size_t row,size_t col,const T& invalid)
:_rowSize(row)
,_colSize(col)
,_invalid(invalid)
{
for(size_t i=0; i<row; i++)
{
for (size_t j=0; j<col; j++)
{
if (a[i*col+j] != invalid) //有效值
{
Triple<T> t(i,j,a[i*col+j]);
t._value = a[i*col+j];
t._row = i;
t._col = j;
_martix.push_back(t);
}
}
}
}
//输出
void Display()
{
size_t index = 0;
for (size_t i=0; i<_rowSize; ++i)
{
for (size_t j=0; j<_colSize; ++j)
{
if (index < _martix.size()
&& i == _martix[index]._row
&& j == _martix[index]._col)
{
cout<<_martix[index]._value<<" ";
++index;
}
else
{
cout<<0<<" ";
}
}
cout<<endl;
}
cout<<endl;
}
SpareMatrix<T> Transport() //矩阵的转置
{
SpareMatrix<T> TSMartix;
TSMartix._rowSize = _colSize;//交换行列
TSMartix._colSize = _rowSize;
TSMartix._invalid = _invalid;
TSMartix._martix.reserve(_martix.size());
for (size_t col=0; col<_colSize; ++col) //以列优先进行查找
{
for (size_t index=0; index<_martix.size(); ++index)
{
if (_martix[index]._col == col)
{
Triple<T> tmp(_martix[index]._col,_martix[index]._row,_martix[index]._value);
TSMartix._martix.push_back(tmp);
}
}
}
return TSMartix;
}
SpareMatrix<T> FastTransport()
{
SpareMatrix<T> FSTMartix;
FSTMartix._rowSize = _colSize;//交换行列
FSTMartix._colSize = _rowSize;
FSTMartix._invalid = _invalid;
FSTMartix._martix.resize(_martix.size());
int* count = new int[_colSize];
memset(count,0,_martix.size()*sizeof(int));
int* start = new int[_colSize];
memset(start,0,_martix.size()*sizeof(int));
//统计每列的有效值个数
for (size_t i=0; i<_martix.size(); ++i)
{
count[_martix[i]._col]++;
}
//计算每一列的起始位置
for (size_t j=1; j<_colSize; ++j)
{
start[j] = start[j-1] + count[j-1];//每一列起始位置=上一列起始位置+上一列有效数个数
}
//转置
for (size_t index=0; index<_martix.size(); ++index)
{
size_t tmp = _martix[index]._col; //取到原三元组中每个数的列
FSTMartix._martix[start[tmp]]._col = _martix[index]._row;
FSTMartix._martix[start[tmp]]._row = _martix[index]._col;
FSTMartix._martix[start[tmp]]._value = _martix[index]._value;
++start[tmp]; //start指针要向后移位
}
return FSTMartix;
}
protected:
vector<Triple<T>> _martix;
size_t _rowSize;
size_t _colSize;
T _invalid; //非法值
};