摘要:本文主要向大家介绍了C++语言程序设计的稀疏矩阵的压缩存储,通过具体的代码向大家展示,希望对大家学习C++语言程序设计有所帮助。
本文主要向大家介绍了C++语言程序设计的稀疏矩阵的压缩存储,通过具体的代码向大家展示,希望对大家学习C++语言程序设计有所帮助。
[cpp] view plain copy print? 1. #include <vector> 2. #include <iostream> 3. using namespace std; 4. template<class T> 5. class SparseMatrix 6. { 7. public: 8. // 稀疏矩阵的压缩存储 9. SparseMatrix(int* array, size_t row, size_t col, const T& invalid) 10. : _row(row) 11. , _col(col) 12. , _invalid(invalid) 13. { 14. for (size_t i = 0; i < row; ++i) 15. { 16. for (size_t j = 0; j < col; ++j) 17. { 18. if (array[i*col+j] != invalid) 19. { 20. Trituple<T> a(i, j, array[i*col + j]); 21. _sm.push_back(a); 22. } 23. } 24. } 25. } 26. 27. SparseMatrix() 28. {} 29. 30. // 访问稀疏矩阵中row行col中的元素 31. T& Access(int row, int col) 32. { 33. ////遍历数组两种方法 34. ////1.for循环 35. ////2.迭代器 36. //vector<Trituple<T>>::iterator it = _sm.begin(); 37. 38. //while (it != _sm.end()) 39. //{ 40. // if (it->_row == row&&it->_col == col) 41. // { 42. // return it->_data; 43. // } 44. // it++; 45. //} 46. //return _invalid; 47. for (size_t i = 0; i < _sm.size(); ++i) 48. { 49. if (_sm[i]._row == row&&_sm[i]._col == col) 50. { 51. return _sm[i]._data; 52. } 53. return _invalid; 54. } 55. } 56. 57. // 还原稀疏矩阵 58. template<class T> 59. friend ostream& operator<<(ostream& _cout, SparseMatrix<T>& s)//要申明为友元函数 60. { 61. int index = 0; 62. for (size_t i = 0; i < s._row; ++i) 63. { 64. for (size_t j = 0; j < s._col; ++j) 65. { 66. if (index<s._sm.size() && i == s._sm[index]._row&&j == s._sm[index]._col) 67. { 68. _cout << s._sm[index++]._data << " "; 69. } 70. else 71. { 72. _cout << s._invalid << " "; 73. } 74. } 75. _cout << endl; 76. } 77. return _cout; 78. } 79. 80. // 实现稀疏矩阵的逆置,并给出时间复杂度 81. //直接存储是有问题的,打印是按照行优先打印存储也要行优先存储 82. SparseMatrix<T> Transprot() 83. { 84. SparseMatrix<T> sm;//定义一个逆转后的结构体 85. sm._col = _row; 86. sm._row = _col; 87. sm._invalid = _invalid; 88. /*使用迭代器*/ 89. //for (int i = 0; i < _col; ++i) 90. //{ 91. // vector<Trituple<T>>::iterator it = _sm.begin(); 92. // while (it != _sm.end()) 93. // { 94. // if (i == it->_col) 95. // { 96. // sm._sm.push_back(Trituple<T>(it->_col, it->_row, it->_data)); 97. // } 98. // it++; 99. 100. // } 101. //} 102. //return sm; 103. //时间复杂度O(M*N) 104. for (size_t i = 0; i < _col; ++i) 105. { 106. size_t index = 0; 107. while (index < _sm.size()) 108. { 109. if (_sm[index]._col == i) 110. { 111. //三元组tmp存入满足下表i的元素 112. Trituple<T> tmp(_sm[index]._col, _sm[index]._row, _sm[index]._data); 113. sm._sm.push_back(tmp); 114. } 115. ++index;//此处要++index而不是index++ 116. } 117. 118. } 119. return sm; 120. } 121. 122. // 实现稀疏矩阵的快速逆置,并给出时间复杂度 123. SparseMatrix<T> FastTransprot() 124. { 125. SparseMatrix<T> sm;//定义一个逆转后的结构体 126. sm._col = _row; 127. sm._row = _col; 128. sm._invalid = _invalid; 129. sm._sm.reserve(_sm.size());//开辟有效元素个空间 130. 131. //1、统计原矩阵中每一列有多少个有效元素 132. int* pCount = new int[_col]; 133. memset(pCount, 0, _col*sizeof(pCount[0])); 134. for (int i = 1; i < _sm.size(); ++i) 135. { 136. pCount[_sm[i]._col]++; 137. } 138. 139. //2、原矩阵的每一列在新矩阵中的起始位置 140. int* pAddr = new int[_col]; 141. memset(pAddr, 0, _col*sizeof(pAddr[0])); 142. for (int j = 1; j < _col; ++j) 143. { 144. pAddr[j] = pAddr[j - 1] + pCount[j - 1]; 145. } 146. //3、放置元素到新的空间 147. for (int i = 0; i < _sm.size(); ++i) 148. { 149. //Trituple<T> t(_sm[i]._col, _sm[i]._row, _sm[i]._data); 150. //sm._sm[pAddr[_sm[i]._col]] = t; 151. //pAddr[_sm[i]._col] ++; 152. int & addr = pAddr[_sm[i]._col]; 153. sm._sm[addr] = Trituple<T>(_sm[i]._col, _sm[i]._row, _sm[i]._data); 154. addr++; 155. } 156. 157. return sm; 158. } 159. 160. // // 实现稀疏矩阵的加法操作 161. //SparseMatrix<T> operator+(const SparseMatrix<T>& sp); 162. 163. //三元组 164. template<class T> 165. struct Trituple 166. { 167. Trituple(size_t row, size_t col, const T& data) 168. : _row(row) 169. , _col(col) 170. , _data(data) 171. {} 172. 173. Trituple()//无参数构造函数 174. {} 175. 176. size_t _row; 177. size_t _col; 178. T _data; 179. }; 180. private: 181. vector<Trituple<T>> _sm; 182. size_t _row; 183. size_t _col; 184. T _invalid; 185. }; 186. void TestSparseMatrix() 187. { 188. int array[6][5] = 189. { 190. { 1, 0, 3, 0, 5 }, 191. { 0, 0, 0, 0, 0 }, 192. { 0, 0, 0, 0, 0 }, 193. { 2, 0, 4, 0, 6 }, 194. { 0, 0, 0, 0, 0 }, 195. { 0, 0, 0, 0, 0 } }; 196. SparseMatrix<int> sp((int*)array, sizeof(array) / sizeof(array[0]), sizeof(array[0]) / sizeof(array[0][0]), 0); 197. 198. cout << sp << endl; 199. cout << endl; 200. 201. SparseMatrix<int> sp1 = sp.Transprot(); 202. 203. cout << sp1 << endl; 204. 205. SparseMatrix<int> sp2 = sp.FastTransprot(); 206. 207. cout << sp2 << endl; 208. } 209. int main() 210. { 211. TestSparseMatrix(); 212. system("pause"); 213. return 0; 214. }
以上就介绍了C/C+的相关知识,希望对C/C+有兴趣的朋友有所帮助。了解更多内容,请关注职坐标编程语言C/C+频道!
您输入的评论内容中包含违禁敏感词
我知道了
请输入正确的手机号码
请输入正确的验证码
您今天的短信下发次数太多了,明天再试试吧!
我们会在第一时间安排职业规划师联系您!
您也可以联系我们的职业规划师咨询:
版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com,All Rights Reserved.
沪公网安备 31011502005948号