概要：
项目简介：利用哈夫曼编码的方式对文件进行压缩，并且对压缩文件可以解压
开发环境：windows vs2013
项目概述：
1.压缩
a.读取文件，将每个字符，该字符出现的次数和权值构成哈夫曼树
b.哈夫曼树是利用小堆构成，字符出现次数少的节点指针存在堆顶，出现次数多的在堆底
c.每次取堆顶的两个数，再将两个数相加进堆，直到堆被取完，这时哈夫曼树也建成
d.从哈夫曼树中获取哈夫曼编码，然后再根据整个字符数组来获取出现了得字符的编码
e.获取编码后每次凑满8位就将编码串写入到压缩文件（value处理编码1与它即可，0只移动位）
f.写好配置文件，统计每个字符及其出现次数，并以“字符+','+次数”的形式保存到配置文件中
2.解压
a.读取配置文件，统计所有字符的个数
b.构建哈夫曼树，读解压缩文件，将所读到的编码字符的这个节点所所含的字符写入到解压缩文件中，知道将压缩文件读完
c.压缩解压缩完全完成，进行小文件大文件的测试
实例代码：
?
|
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
|
#pragma once
#include<vector>
template<class T>
struct Less
{
bool operator()(const T& l, const T& r) const
{
return l < r;
}
};
template<class T>
struct Greater
{
bool operator()(const T& l, const T& r) const
{
return l > r;
}
};
template<class T, class Compare>
class Heap
{
public:
Heap()
{}
Heap(T* array, size_t n) //建堆
{
_array.reserve(n);
for (size_t i = 0; i < n; i++)
{
_array.push_back(array[i]);
}
for (int i = (_array.size() - 2) >> 1; i >= 0; --i)
{
_AdjustDown(i);
}
}
const T& Top()const
{
return _array[0];
}
void Push(const T& x)
{
_array.push_back(x);
_AdjustUp(_array.size() - 1);
}
size_t Size()
{
return _array.size();
}
void Pop()
{
assert(_array.size() > 0);
swap(_array[0], _array[_array.size() - 1]);
_array.pop_back();
_AdjustDown(0);
}
bool Empty()
{
return _array.size() == 0;
}
void Print()
{
for (size_t i = 0; i < _array.size(); ++i)
{
cout << _array[i] << " ";
}
cout << endl;
}
protected:
void _AdjustUp(int child) //上调
{
Compare ComFunc;
int parent = (child - 1) >> 1;
while (child)
{
if (ComFunc(_array[child], _array[parent]))
{
swap(_array[child], _array[parent]);
child = parent;
parent = (child - 1) >> 1;
}
else
{
break;
}
}
}
void _AdjustDown(int root) //下调
{
Compare ComFunc;
int parent = root;
int child = root * 2 + 1;
while (child < _array.size())
{
if (child + 1 < _array.size() && ComFunc(_array[child + 1], _array[child]))
{
++child;
}
if (ComFunc(_array[child], _array[parent]))
{
swap(_array[child], _array[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
protected:
vector<T> _array;
};
void TestHeap()
{
int a[] = { 10, 11, 13, 12, 16, 18, 15, 17, 14, 19 };
//Heap<int> heap(a, sizeof(a) / sizeof(a[0]));
//Heap<int, Less<int>> heap(a, sizeof(a) / sizeof(a[0]));
Heap<int, Greater<int>> heap(a, sizeof(a) / sizeof(a[0]));
heap.Print();
heap.Push(25);
heap.Print();
heap.Pop();
heap.Print();
}
|
?
|
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
|