什么是稀疏矩阵呢，就是在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
