45.}
二、一般转置算法
从上图我们可以看出：
矩阵转置后，三元组中的顺序也发生了改变。
因此要得到矩阵M转置后的矩阵TM，我们只需将三元组的顺序改变就好了。
转置的三步：
a.将矩阵的行列交换
b.将每个三元组中的行、列交换
c.将原矩阵三元组的顺序重排得到新的三元组
[cpp] viewplain copy
1.SpareMatrix Transport（） //矩阵的转置
2.{
3. SpareMatrix TSMartix;
4. TSMartix._rowSize = _colSize;//交换行列
5. TSMartix._colSize = _rowSize;
6. TSMartix._invalid = _invalid;
7. TSMartix._artix.reserve（_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 tmp（_martix[index]._col,_martix[index]._row,_martix[index]._value）;
16. TSMartix._tix.push_back（tmp）;
17. }
18. }
19. }
20. return TSMartix;
21.}
这样算法即使可以得到结果，但是效率高不高呢？
！
算算时间复杂度--------
O（矩阵的列数*有效数值的个数），如果这个矩阵是500*500呢？
！
显然效率就会特别低了。
因此，我们就需要一种转置算法来提高效率。
三、快速转置
（假设原矩阵为M，转置后得到的矩阵为FSTM）
我们按照普通转置的算法，将M的三元组的次序进行转置，并将每次转置后的数据能直接放到FSTM三元组正确的位置。
但这种算法的前提是：
需要预先知道M每行的有效值个数，将M中第一个有效数放到正确位置后，并记下该位置，以后对M的三元组中的每个数进行转置时，都可以直接放到正确的位置。
引入两个量count和start，count-----记录每行的有效数据的个数
start-------表示每行第一个数的起始位置
分析上图我们可以得到：
start=上一行的起始位置+上一行的有效数个数
时间复杂度：
O（2*有效值的个数+列数）
代码实现：
[cpp] viewplain copy
1.SpareMatrix FastTransport（）
2.{
3. SpareMatrix FSTMartix;
4. FSTMartix._rowSize = _colSize;//交换行列
5. FSTMartix._colSize = _rowSize;
6. FSTMartix._invalid = _invalid;
7. FSTMartix._martix.resize（_martix.size（））;
8.
9. int* count = new int[_colSize];
10. memset（count,0,_martix.size（）*sizeof（int））;
11. int* start = new int[_colSize];
12. memset（start,0,_martix.size（）*sizeof（int））;
13.
14. //统计每列的有效值个数
15. for （size_t i=0; i<_martix.size（）; ++i）
16. {
17. count[_martix[i]._col]++;
18. }
19.
20. //计算每一列的起始位置
21. for （size_t j=1; j<_colSize; ++j）
22. {
23. start[j] = start[j-1] + count[j-1];//每一列起始位置=上一列起始位置+上一列有效数个数
24. }
25.
26. //转置
27. for （size_t index=0; index<_martix.size（）; ++index）
28. {
29. size_t tmp = _martix[index]._col; //取到原三元组中每个数的列
30. FSTMartix._martix[start[tmp]]._col = _martix[index]._row;
31. FSTMartix._martix[start[tmp]]._row = _martix[index]._col;
32. FSTMartix._martix[start[tmp]]._value = _martix[index]._value;
33. ++start[tmp]; //start指针要向后移位
34. }
35. return FSTMartix;
36.}
稀疏矩阵代码的整体实现：
[cpp] viewplain copy
1.template
2.struct Triple
3.{
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.template
18.class SpareMatrix
19.{
20.public:
21. SpareMatrix（）
22. :
_martix（NULL）
23. ,_rowSize（0）
24. ,_colSize（0）
25. ,_invalid（T（））
26. {}
27. //数据的存储
28. SpareMatrix（const T* a,size_t row,size_t col,const T& invalid）
29. :
_rowSize（row）
30. ,_colSize（col）
31. ,_invalid（invalid）
32. {
33. for（size_t i=0; i34. {
35. for （size_t j=0; j36. {
37. if （a[i*col+j] !
= invalid） //有效值
38. {
39. Triple t（i,j,a[i*col+j]）;
40. t._value = a[i*col+j];
41. t._row = i;
42. t._col = j;
43. _martix.push_back（t）;
44. }
45. }
46. }
47. }
48. //输出
49. void Display（）
50. {
51. size_t index = 0;
52. for （size_t i=0; i<_rowSize; ++i）
53. {
54. for （size_t j=0; j<_colSize; ++j）
55. {
56. if （index < _martix.size（）
57. && i == _martix[index]._row
58. && j == _martix[index]._col）
59. {
60. cout<<_martix[index]._value<<" ";
61. ++index;
62. }
63. else
64. {
65. cout<<0<<" ";
66. }
67. }
68. cout<69. }
70. cout<71. }
72. SpareMatrix Transport（） //矩阵的转置
73. {
74. SpareMatrix TSMartix;
75. TSMartix._rowSize = _colSize;//交换行列
76. TSMartix._colSize = _rowSize;
77. TSMartix._invalid = _invalid;
78. TSMartix._martix.reserve（_martix.size（））;
79.
80. for （size_t col=0; col<_colSize; ++col） //以列优先进行查找
81. {
82. for （size_t index=0; index<_martix.size（）; ++index）
83. {
84. if （_martix[index]._col == col）
85. {
86. Triple tmp（_martix[index]._col,_martix[index]._row,_martix[index]._value）;
87. TSMartix._martix.push_back（tmp）;
88. }
89. }
90. }
91. return TSMartix;
92. }
93.
94. SpareMatrix FastTransport（）
95. {
96. SpareMatrix FSTMartix;
97. FSTMartix._rowSize = _colSize;//交换行列
98. FSTMartix._colSize = _rowSize;
99. FSTMartix._invalid = _invalid;
100. FSTMartix._martix.resize（_martix.size（））;
101.
102. int* count = new int[_colSize];
103. memset（count,0,_martix.size（）*sizeof（int））;
104. int* start = new int[_colSize];
105. memset（start,0,_martix.size（）*sizeof（int））;
106.
107. //统计每列的有效值个数
108. for （size_t i=0; i<_martix.size（）; ++i）
109. {
110. count[_martix[i]._col]++;
111. }
112.
113. //计算每一列的起始位置
114. for （size_t j=1; j<_colSize; ++j）
115. {
116. start[j] = start[j-1] + count[j-1];//每一列起始位置=上一列起始位置+上一列有效数个数
117. }
118.
119. //转置
120. for （size
升级会员 