C++實現稀疏矩陣的壓縮存儲

什麼是稀疏矩陣呢，就是在M*N的矩陣中，有效值的個數遠小於無效值的個數，並且這些數據的分佈沒有規律。在壓縮存儲稀疏矩陣的時候我們只存儲極少數的有效數據。我們在這裡使用三元組存儲每一個有效數據，三元組按原矩陣中的位置，以行優先級先後次序依次存放。下面我們來看一下代碼實現。

1. #include
2. #include
3. #include
4. usingnamespace std;
5. template
6. class SparseMatrix
7. {
8. //三元組
9. template
10. struct Trituple
11. {
12. Trituple()//給一個默認構造函數
13. {}
14. Trituple(size_t row, size_t col, const T& data)
15. :_row(row)
16. ,_col(col)
17. ,_data(data)
18. {}
19. size_t _row;
20. size_t _col;
21. T _data;
22. };
23. public:
24. //稀疏矩陣的壓縮存儲
25. SparseMatrix()
26. {}
27. SparseMatrix(int* arr, size_t row, size_t col, const T& invalid)
28. :_row(row)
29. ,_col(col)
30. ,_invalid(invalid)
31. {
32. for(int i = 0; i < row; i++)
33. {
34. for(int j = 0; j < col; ++j)
35. {
36. if(arr[i*col+j] != invalid)//將有效值存儲在一個一維數組中
37. _sm.push_back(Trituple(i,j,arr[i*col+j]));//將三元組的無名對象push進去
38. }
39. }
40. }
41. //訪問稀疏矩陣中row行col中的元素
42. T& Acess(int row, int col)
43. {
44. //1、
45. /*for(int idx = 0; idx < _sm.size(); idx++)//遍歷一遍
46. {
47. if(_sm[idx]._row == row && _sm[idx]._col == col)//當前行列與我們要訪問那個元素行列相同時返回這個有效值
48. return _sm[idx]._data;
49. }
50. return _invalid;*///否則返回無效值
51. //2、
52. vector>::iterator it = _sm.begin();//定義一個迭代器,指向起始位置
53. while(it != _sm.end())//未到最後一個元素時
54. {
55. if(it->_row == row && it->_col == col)//行列相等輸出值
56. return it->_data;
57. ++it;//迭代器向後移動
58. }
59. return _invalid;
60. }
61. //還原稀疏矩陣
62. template
63. friend ostream& operator<& s)//重載<<
64. {
65. size_t idex = 0;
66. for(size_t i = 0; i < s._row; i++)
67. {
68. for(size_t j = 0; j < s._col; j++)
69. {
70. if(idex < s._sm.size()/*防止數組越界*/ && s._sm[idex]._row == i && s._sm[idex]._col == j)
71. {
72. _cout<
73. ++idex;
74. }
75. else
76. _cout<
77. }
78. _cout<
79. }
80. return _cout;
81. }
82. //實現稀疏矩陣的逆置 時間複雜度O(M*N)(M為元素個數N為矩陣列數)
83. SparseMatrix Transport()
84. {
85. SparseMatrix
    sm;
86. sm._row = _col;
87. sm._col = _row;
88. sm._invalid = _invalid;
89. for(size_t i = 0; i < _col; i++)
90. {
91. vector>::iterator it = _sm.begin();
92. while(it != _sm.end())
93. {
94. if(it->_col == i)//從原矩陣第0列開始，將每列中的有效值依次放入新的稀疏矩陣
95. sm._sm.push_back(Trituple (i, it->_row, it->_data));
96. ++it;
97. }
98. }
99. return sm;
100. }
101. //實現稀疏矩陣的快速轉置 時間複雜度O(N)+O(M)
102. SparseMatrix FastTransport()
103. {
104. SparseMatrix sm;
105. sm._col = _row;
106. sm._row = _col;
107. sm._invalid = _invalid;
108. sm._sm.resize(_sm.size());//開闢空間
109. //1、統計原矩陣中每一列有多少個有效元素
110. int* pCount = newint[_col];//開闢原矩陣中列個數的空間
111. memset(pCount, 0, _col*sizeof(pCount[0]));
112. for(int i = 0; i < _sm.size(); i++)
113. pCount[_sm[i]._col]++;
114. //2、原矩陣每一列在新矩陣中的起始位值
115. int* pAddr = newint[_col];
116. memset(pAddr, 0, _col*sizeof(pAddr[0]));
117. for(int i = 1/*從1開始，第一個位置起始為0已經放入*/; i < _sm.size(); i++)
118. {
119. pAddr[i] = pAddr[i - 1] + pCount[i - 1];//前一個起始位值+前一列有效元素個數
120. }
121. //3、放置元素到新空間
122. for(int i = 0; i < _sm.size(); i++)
123. {
124. int& addr = pAddr[_sm[i]._col];
125. sm._sm[addr] = Trituple(_sm[i]._col,_sm[i]._row,_sm[i]._data);
126. addr++;
127. }
128. return sm;
129. }
130. //實現稀疏矩陣的加法操作1
131. /*SparseMatrix operator+(const SparseMatrix& sp)
132. {
133. int i = 0, j = 0, k = 0;
134. T v;
135. SparseMatrix s;
136. if(this->_col != sp._col || this->_row != sp._row)
137. exit(1);
138. s._row = sp._row;
139. s._col = sp._col;
140. s._invalid = sp._invalid;
141. while(i < this->_sm.size() && j < sp._sm.size())
142. {
143. if(this->_sm[i]._row == sp._sm[j]._row)
144. {
145. if(this->_sm[i]._col < sp._sm[j]._col)
146. {
147. s._sm.push_back(Trituple(this->_sm[i]._row, this->_sm[i]._col, this->_sm[i]._data));
148. i++;
149. k++;
150. }
151. else if(this->_sm[i]._col > sp._sm[j]._col)
152. {
153. s._sm.push_back(Trituple(sp._sm[j]._row, sp._sm[j]._col, sp._sm[j]._data));
154. j++;
155. k++;
156. }
157. else
158. {
159. v = this->_sm[i]._data + sp._sm[j]._data;
160. if(v)
161. {
162. s._sm.push_back(Trituple(sp._sm[j]._row, sp._sm[j]._col, v));
163. k++;
164. }
165. i++;
166. j++;
167. }
168. }
169. else if(this->_sm[i]._row < sp._sm[j]._row)
170. {
171. s._sm.push_back(Trituple(this->_sm[i]._row, this->_sm[i]._col, this->_sm[i]._data));
172. i++;
173. k++;
174. }
175. else
176. {
177. s._sm.push_back(Trituple(sp._sm[j]._row, sp._sm[j]._col, sp._sm[j]._data));
178. j++;
179. k++;
180. }
181. }
182. return s;
183. }*/
184. //實現稀疏矩陣的加法操作2
185. SparseMatrix operator+(const SparseMatrix& sp)
186. {
187. assert(_row == sp._row && _col == sp._col);//檢測兩個相加的矩陣行列是否相等
188. SparseMatrix ret;
189. ret._row = _row;
190. ret._col = _col;
191. ret._invalid = _invalid;
192. int iLidx = 0, iRidx = 0;//定義兩個索引
193. while(iLidx < _sm.size() && iRidx < sp._sm.size())
194. {
195. size_t AddrLeft = _sm[iLidx]._row*_col+_sm[iLidx]._col;//左邊矩陣的起始位值
196. size_t AddrRight = sp._sm[iRidx]._row*sp._col+sp._sm[iRidx]._col;//右邊矩陣起始位值
197. if(AddrLeft < AddrRight)//左
198. {
199. ret._sm.push_back(Trituple(_sm[iLidx]._row, _sm[iLidx]._col, _sm[iLidx]._data));
200. iLidx++;
201. }
202. elseif(AddrLeft > AddrRight)
203. {
204. ret._sm.push_back(Trituple
     (sp._sm[iRidx]._row, sp._sm[iRidx]._col, sp._sm[iRidx]._data));
205. iRidx++;
206. }
207. else//當左邊等於右邊判斷相加後和是否為0，不為0放入
208. {
209. Trituple temp(_sm[iLidx]);
210. temp._data += sp._sm[iRidx]._data;
211. if(temp._data)
212. {
213. ret._sm.push_back(temp);
214. iLidx++;
215. iRidx++;
216. }
217. }
218. }
219. while(iLidx < _sm.size())//左邊還有剩餘則放入剩餘元素
220. {
221. ret._sm.push_back(Trituple(_sm[iLidx]._row, _sm[iLidx]._col, _sm[iLidx]._data));
222. iLidx++;
223. }
224. while(iRidx < sp._sm.size())
225. {
226. ret._sm.push_back(Trituple(sp._sm[iRidx]._row, sp._sm[iRidx]._col, sp._sm[iRidx]._data));
227. iRidx++;
228. }
229. return ret;
230. }
231. private:
232. size_t _row;
233. size_t _col;
234. vector> _sm;
235. T _invalid;//無效值
236. };
237. int main()
238. {
239. int arr[6][5] = {
240. {1,0,3,0,5},
241. {0,0,0,0,0},
242. {0,0,0,0,0},
243. {1,0,3,0,5},
244. {0,0,0,0,0},
245. {0,0,0,0,0}};
246. int arr1[6][5] = {
247. {1,0,3,0,5},
248. {0,0,0,0,0},
249. {0,0,2,4,0},
250. {1,0,3,0,5},
251. {0,0,0,1,0},
252. {0,0,0,0,1}};
253. SparseMatrix<int> s((int*)arr,6,5,0);
254. SparseMatrix<int> s1((int*)arr1,6,5,0);
255. cout<
256. cout<
257. cout<
258. cout<
259. cout<
260. cout<
261. cout<
262. cout<
263. cout<
264. cout<
265. cout<
266. cout<
267. system("pause");
268. return 0;
269. }

運行結果截圖：

在上面的代碼中用到C++模板、標準庫中vector容器，以及迭代器實現了一些基本的操作，如訪問稀疏矩陣中某個元素，輸出稀疏矩陣、稀疏矩陣的轉置以及快速轉置還有兩個稀疏矩陣的加法。

快速轉置操作的基本思路是：

（1）統計原矩陣中每一列有多少個有效元素；

（2）原矩陣中每一列在新矩陣中的起始地址；

（3）放置元素到新空間中。

還需注意的是，在我們打印這個稀疏矩陣時雖然也可以直接調用訪問元素的Acess接口，但是每次進去之後都得遍歷一遍，時間複雜度較高，所以我們不採取這種辦法，而是比較當前行列的值，若相等輸出有效元素，不等則輸出無效元素0。

閱讀更多 成都朗沃教育 的文章

關鍵字: 存儲 稀疏 技術