矩阵的存储及转置算法
本文要点：
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.代码实现
[cpp] view plain copy
2.class SymmetryMatrix
3.{
4.public:
5. SymmetryMatrix(const T* a,size_t n)
6. :_matrix(new T[n*(n+1)/2])
7. ,_size(n*(n+1)/2)
8. ,_n(n)
9. {
10.size_t index = 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. _matrix[index++] = a[i*n+j];
18. //index++;
19. }
20.el
22. }
23. }
24. }
25.
26. T& Access(size_t row,size_t col) //访问数据
27. {
28.if (row < col)
29. {
30. std::swap(row,col);
31. }
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<<endl;
44. }
45. }
46.p rotected:
47. T* _matrix; //压缩存储的一维数组
48.size_t _size; //可存储的大小
49.size_t _n; //行列的大小
50.};
稀疏矩阵<SparMatrix>
1.稀疏矩阵中，有效数据（非0）的数量远小于非法数据的个数（0为非法数据）
2.稀疏矩阵的存储也是压缩存储的，但与对称矩阵不同的地方有两点：
（1）稀疏矩阵的压缩存储只存储有效值；
（2）稀疏矩阵存储以行优先的顺序存储在三元组中，表示为：{row,col,value}，row和col 分别表示该有效值的行和列。
一、存储及输出
存储的方法类似于对称矩阵的存储，但要将行和列也进行存储；
输出的时候多考虑表示数组的下标会不会越界
[cpp] view plain copy
1.//数据的存储
2.SpareMatrix(const T* a,size_t row,size_t col,const T& invalid)
3. :_rowSize(row)
4. ,_colSize(col)
5. ,_invalid(invalid)
6.{
7.for(size_t i=0; i<row; i++)
8. {
9.for (size_t j=0; j<col; j++)
10. {
11.if (a[i*col+j] != invalid) //有效值
12. {
13. Triple<T> t(i,j,a[i*col+j]);
14. t._value = a[i*col+j];
15. t._row = i;
16. t._col = j;
17. _martix.push_back(t);
18. }
19. }
20. }
21.}
22.//输出
23.v oid Display()
24.{
25.size_t index = 0;
26.for (size_t i=0; i<_rowSize; ++i)
27. {
28.for (size_t j=0; j<_colSize; ++j)
29. {
30.if (index < _martix.size()
31. && i == _martix[index]._row
32. && j == _martix[index]._col)
33. {
34. cout<<_martix[index]._value<<" ";
35. ++index;
36. }
37.el
38. {
39. cout<<0<<" ";
40. }
41. }
42. cout<<endl;
43. }
44. cout<<endl;
45.}
二、一般转置算法
从上图我们可以看出：矩阵转置后，三元组中的顺序也发生了改变。因此要得到矩阵M转置后的矩阵TM，我们只需将三元组的顺序改变就好了。转置的三步：
a.将矩阵的行列交换
b.将每个三元组中的行、列交换
c.将原矩阵三元组的顺序重排得到新的三元组
[cpp] view plain copy
1.SpareMatrix<T> Transport() //矩阵的转置
2.{
3. SpareMatrix<T> TSMartix;
4. TSMartix._rowSize = _colSize;//交换行列
5. TSMartix._colSize = _rowSize;
6. TSMartix._invalid = _invalid;
7. TSMartix._ve(_martix.size());
8.
9.for (size_t col=0; col<_colSize; ++col) //以列优先进行查找
10. {
11.for (size_t index=0; index<_martix.size(); ++index)
12. {
13.if (_martix[index]._col == col)
14. {
15. Triple<T> tmp(_martix[index]._col,_martix[index].
_row,_martix[index]._value);
16. TSMartix._ix.push_back(tmp)
;
17. }
18. }
