什么是稀疏矩陣呢，就是在M*N的矩陣中，有效值的個數遠小于無效值的個數，并且這些數據的分布沒有規律。在壓縮存儲稀疏矩陣的時候我們只存儲極少數的有效數據。我們在這里使用三元組存儲每一個有效數據，三元組按原矩陣中的位置，以行優先級先后次序依次存放。下面我們來看一下代碼實現。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
|
#include<iostream> #include<vector> #include<assert.h> using namespace std; template<class T> class SparseMatrix { //三元組 template<class T> struct Trituple { Trituple()//給一個默認構造函數 {} Trituple(size_t row, size_t col, const T& data) :_row(row) ,_col(col) ,_data(data) {} size_t _row; size_t _col; T _data; }; public: //稀疏矩陣的壓縮存儲 SparseMatrix() {} SparseMatrix(int* arr, size_t row, size_t col, const T& invalid) :_row(row) ,_col(col) ,_invalid(invalid) { for(int i = 0; i < row; i++) { for(int j = 0; j < col; ++j) { if(arr[i*col+j] != invalid)//將有效值存儲在一個一維數組中 _sm.push_back(Trituple<T>(i,j,arr[i*col+j]));//將三元組的無名對象push進去 } } } //訪問稀疏矩陣中row行col中的元素 T& Acess(int row, int col) { //1、 /*for(int idx = 0; idx < _sm.size(); idx++)//遍歷一遍 { if(_sm[idx]._row == row && _sm[idx]._col == col)//當前行列與我們要訪問那個元素行列相同時返回這個有效值 return _sm[idx]._data; } return _invalid;*/ //否則返回無效值 //2、 vector<Trituple<T>>::iterator it = _sm.begin();//定義一個迭代器,指向起始位置 while(it != _sm.end())//未到最后一個元素時 { if(it->_row == row && it->_col == col)//行列相等輸出值 return it->_data; ++it;//迭代器向后移動 } return _invalid; } //還原稀疏矩陣 template<typename T> friend ostream& operator<<(ostream& _cout, SparseMatrix<T>& s)//重載<< { size_t idex = 0; for(size_t i = 0; i < s._row; i++) { for(size_t j = 0; j < s._col; j++) { if(idex < s._sm.size()/*防止數組越界*/ && s._sm[idex]._row == i && s._sm[idex]._col == j) { _cout<<s._sm[idex]._data<<" "; ++idex; } else _cout<<s._invalid<<" "; } _cout<<endl; } return _cout; } //實現稀疏矩陣的逆置 時間復雜度O(M*N)(M為元素個數N為矩陣列數) SparseMatrix<T> Transport() { SparseMatrix<T> sm; sm._row = _col; sm._col = _row; sm._invalid = _invalid; for(size_t i = 0; i < _col; i++) { vector<Trituple<T>>::iterator it = _sm.begin(); while(it != _sm.end()) { if(it->_col == i)//從原矩陣第0列開始，將每列中的有效值依次放入新的稀疏矩陣 sm._sm.push_back(Trituple<T> (i, it->_row, it->_data)); ++it; } } return sm; } //實現稀疏矩陣的快速轉置 時間復雜度O(N)+O(M) SparseMatrix<T> FastTransport() { SparseMatrix<T> sm; sm._col = _row; sm._row = _col; sm._invalid = _invalid; sm._sm.resize(_sm.size());//開辟空間 //1、統計原矩陣中每一列有多少個有效元素 int* pCount = new int[_col];//開辟原矩陣中列個數的空間 memset(pCount, 0, _col*sizeof(pCount[0])); for(int i = 0; i < _sm.size(); i++) pCount[_sm[i]._col]++; //2、原矩陣每一列在新矩陣中的起始位值 int* pAddr = new int[_col]; memset(pAddr, 0, _col*sizeof(pAddr[0])); for(int i = 1/*從1開始，第一個位置起始為0已經放入*/; i < _sm.size(); i++) { pAddr[i] = pAddr[i - 1] + pCount[i - 1];//前一個起始位值+前一列有效元素個數 } //3、放置元素到新空間 for(int i = 0; i < _sm.size(); i++) { int& addr = pAddr[_sm[i]._col]; sm._sm[addr] = Trituple<T>(_sm[i]._col,_sm[i]._row,_sm[i]._data); addr++; } return sm; } //實現稀疏矩陣的加法操作1 /*SparseMatrix<T> operator+(const SparseMatrix<T>& sp) { int i = 0, j = 0, k = 0; T v; SparseMatrix<T> s; if(this->_col != sp._col || this->_row != sp._row) exit(1); s._row = sp._row; s._col = sp._col; s._invalid = sp._invalid; while(i < this->_sm.size() && j < sp._sm.size()) { if(this->_sm[i]._row == sp._sm[j]._row) { if(this->_sm[i]._col < sp._sm[j]._col) { s._sm.push_back(Trituple<T>(this->_sm[i]._row, this->_sm[i]._col, this->_sm[i]._data)); i++; k++; } else if(this->_sm[i]._col > sp._sm[j]._col) { s._sm.push_back(Trituple<T>(sp._sm[j]._row, sp._sm[j]._col, sp._sm[j]._data)); j++; k++; } else { v = this->_sm[i]._data + sp._sm[j]._data; if(v) { s._sm.push_back(Trituple<T>(sp._sm[j]._row, sp._sm[j]._col, v)); k++; } i++; j++; } } else if(this->_sm[i]._row < sp._sm[j]._row) { s._sm.push_back(Trituple<T>(this->_sm[i]._row, this->_sm[i]._col, this->_sm[i]._data)); i++; k++; } else { s._sm.push_back(Trituple<T>(sp._sm[j]._row, sp._sm[j]._col, sp._sm[j]._data)); j++; k++; } } return s; }*/ //實現稀疏矩陣的加法操作2 SparseMatrix<T> operator+(const SparseMatrix<T>& sp) { assert(_row == sp._row && _col == sp._col);//檢測兩個相加的矩陣行列是否相等 SparseMatrix<T> ret; ret._row = _row; ret._col = _col; ret._invalid = _invalid; int iLidx = 0, iRidx = 0;//定義兩個索引 while(iLidx < _sm.size() && iRidx < sp._sm.size()) { size_t AddrLeft = _sm[iLidx]._row*_col+_sm[iLidx]._col;//左邊矩陣的起始位值 size_t AddrRight = sp._sm[iRidx]._row*sp._col+sp._sm[iRidx]._col;//右邊矩陣起始位值 if(AddrLeft < AddrRight)//左<右，將左邊有效值放入和矩陣中，左邊的索引加加 { ret._sm.push_back(Trituple<T>(_sm[iLidx]._row, _sm[iLidx]._col, _sm[iLidx]._data)); iLidx++; } else if(AddrLeft > AddrRight) { ret._sm.push_back(Trituple<T>(sp._sm[iRidx]._row, sp._sm[iRidx]._col, sp._sm[iRidx]._data)); iRidx++; } else//當左邊等于右邊判斷相加后和是否為0，不為0放入 { Trituple<T> temp(_sm[iLidx]); temp._data += sp._sm[iRidx]._data; if(temp._data) { ret._sm.push_back(temp); iLidx++; iRidx++; } } } while(iLidx < _sm.size())//左邊還有剩余則放入剩余元素 { ret._sm.push_back(Trituple<T>(_sm[iLidx]._row, _sm[iLidx]._col, _sm[iLidx]._data)); iLidx++; } while(iRidx < sp._sm.size()) { ret._sm.push_back(Trituple<T>(sp._sm[iRidx]._row, sp._sm[iRidx]._col, sp._sm[iRidx]._data)); iRidx++; } return ret; } private: size_t _row; size_t _col; vector<Trituple<T>> _sm; T _invalid;//無效值 }; int main() { int arr[6][5] = { {1,0,3,0,5}, {0,0,0,0,0}, {0,0,0,0,0}, {1,0,3,0,5}, {0,0,0,0,0}, {0,0,0,0,0}}; int arr1[6][5] = { {1,0,3,0,5}, {0,0,0,0,0}, {0,0,2,4,0}, {1,0,3,0,5}, {0,0,0,1,0}, {0,0,0,0,1}}; SparseMatrix<int> s((int*)arr,6,5,0); SparseMatrix<int> s1((int*)arr1,6,5,0); cout<<"訪問三行四列元素"<<endl; cout<<s.Acess(3,4)<<endl; cout<<s<<endl; cout<<"快速轉置"<<endl; cout<<s.FastTransport(); cout<<endl; cout<<"矩陣s："<<endl; cout<<s<<endl; cout<<"矩陣s1："<<endl; cout<<s1<<endl; cout<<"s+s1求和："<<endl; cout<<s1+s<<endl; system("pause"); return 0; } |
運行結果截圖：
在上面的代碼中用到C++模板、標準庫中vector容器，以及迭代器實現了一些基本的操作，如訪問稀疏矩陣中某個元素，輸出稀疏矩陣、稀疏矩陣的轉置以及快速轉置還有兩個稀疏矩陣的加法。
快速轉置操作的基本思路是：
（1）統計原矩陣中每一列有多少個有效元素；
（2）原矩陣中每一列在新矩陣中的起始地址；
（3）放置元素到新空間中。
還需注意的是，在我們打印這個稀疏矩陣時雖然也可以直接調用訪問元素的Acess接口，但是每次進去之后都得遍歷一遍，時間復雜度較高，所以我們不采取這種辦法，而是比較當前行列的值，若相等輸出有效元素，不等則輸出無效元素0。
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。
原文鏈接：http://blog.csdn.net/z517602658/article/details/70500188?utm_source=tuicool&utm_medium=referral
