对称矩阵及稀疏矩阵的压缩存储
1.稀疏矩阵
对于那些零元素数目远远多于非零元素数目，并且非零元素的分布没有规律的矩阵称为稀疏矩阵（sparse）。
人们无法给出稀疏矩阵的确切定义，一般都只是凭个人的直觉来理解这个概念，即矩阵中非零元素的个数远远小于矩阵元素的总数，并且非零元素没有分布规律。
实现代码：
|
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
|
//稀疏矩阵及其压缩存储 #pragma once #include <vector> #include <iostream> using namespace std; template<class T> struct Triple { size_t _r; size_t _c; T _value; Triple(size_t row = 0, size_t col = 0, const T& value = T()) :_r(row) ,_c(col) ,_value(value) {} }; template <class T> class SparseMatrix { public: SparseMatrix() :_row(0) ,_col(0) ,_illegal(T()) {} SparseMatrix(T* arr, size_t row, size_t col, const T& illegal) :_row(row) ,_col(col) ,_illegal(illegal) { for(size_t i = 0; i<row; ++i) { for(size_t j = 0; j<col; ++j) { if(arr[i*col+j] != illegal) { Triple<T> t(i,j,arr[i*col+j]); _matrix.push_back(t); } } } } void Display() { vector<Triple<T> >::iterator iter; iter = _matrix.begin(); for(size_t i = 0; i<_row; ++i) { for(size_t j = 0; j<_col; ++j) { if(iter!=_matrix.end() &&iter->_r == i &&iter->_c == j) { cout << iter->_value <<" "; ++iter; } else { cout << _illegal <<" "; } } cout << endl; } cout << endl; } //普通转置(行优先存储) //列变行，从0列开始，将列数据一个一个放进转置矩阵 SparseMatrix<T> Transpose() { SparseMatrix<T> tm; tm._row = _col; tm._col = _row; tm._illegal = _illegal; tm._matrix.reserve(_matrix.size()); for(size_t i = 0; i<_col; ++i) { size_t index = 0; while(index < _matrix.size()) { if(_matrix[index]._c == i) { Triple<T> t(_matrix[index]._c, _matrix[index]._r, _matrix[index]._value); tm._matrix.push_back(t); } ++index; } } return tm; } SparseMatrix<T> FastTranspose() { SparseMatrix<T> tm; tm._row = _col; tm._col = _row; tm._illegal = _illegal; tm._matrix.resize(_matrix.size()); int* count = new int[_col];//记录每行的元素个数 memset(count, 0, sizeof(int)*_col); int* start = new int[_col];//转置矩阵中元素的位置 start[0] = 0; size_t index = 0; while(index < _matrix.size()) { count[_matrix[index]._c]++; ++index; } for(size_t i=1; i<_col; ++i) { start[i] = start[i-1] + count[i-1]; } index = 0; while(index < _matrix.size()) { Triple<T> t(_matrix[index]._c, _matrix[index]._r, _matrix[index]._value); tm._matrix[start[_matrix[index]._c]++] = t; //核心代码 ++index; } delete[] count; delete[] start; return tm; } protected: vector<Triple<T> > _matrix; size_t _row; size_t _col; T _illegal; }; |
2.对称矩阵
实现代码：
|
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
|
//对称矩阵及其压缩存储 #pragma once #include <iostream> using namespace std; template <class T> class SymmetricMatrix { public: SymmetricMatrix(T* arr, size_t n) :_n(n) ,_matrix(new T[n*(n+1)/2]) { size_t index = 0; for(size_t i = 0; i<n; ++i) { for(size_t j=0; j<n;++j) { if(i >= j) { _matrix[index] = arr[i*n+j]; ++index; } else { continue; } } } } void Display() { for(size_t i =0; i < _n; ++i) { for(size_t j = 0; j < _n; ++j) { /* if(i<j) { swap(i,j); cout<<_matrix[i*(i+1)/2+j]<<" "; swap(i,j); } else cout<<_matrix[i*(i+1)/2+j]<<" "; */ cout << Access(i,j) << " "; } cout << endl; } cout << endl; } T& Access(size_t row, size_t col) { if(row<col) { swap(row, col); } return _matrix[row*(row+1)/2+col]; } ~SymmetricMatrix() { if(_matrix != NULL) { delete[] _matrix; _matrix = NULL; } } protected: T* _matrix; size_t _n; //对称矩阵的行列大小 }; |
以上就是C++ 数据结构实现稀疏矩阵与对称矩阵，如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
原文链接：http://blog.csdn.net/xhfight/article/details/52843248
