前一篇讲了赫夫曼树可以得到最优的编码, 也说了给定叶子结点之后, 如何构造出一棵赫夫曼树, 但是还没有说赫夫曼树是如何跟编码联系起来的.
一. 赫夫曼树与编码的关系
当我们要对一系列字符进行编码, 首先根据字符出现的频率构造一棵赫夫曼树, 然后规定: 从根结点开始, 往左走一步编码添加一个 1, 往右走编码添加一个 0, 一直到叶子结点.
将每个叶子结点都进行这样的操作, 就得到了它们对应的编码.
(此处并没有证明为什么赫夫曼树编码是最优的, 因为我看不懂文档上面说的.)
二. 赫夫曼树编码的算法
直觉上应该是从上往下, 将 0 或 1 拼凑起来, 但是貌似先中后序遍历和层次遍历都没办法依次遍历到每个叶子结点(至少我是不知道.)
所以赫夫曼树编码的算法是从叶子结点开始的, 往上走求出赫夫曼编码的.
(没办法从根节点按顺序的走到叶子结点, 但是通过赫夫曼树的前 N 个元素, 我们可以直接访问到叶子结点, 而且通过找双亲, 肯定能够走回根节点的, 这样就得到了完整的编码)
两个点:
从下往上得到的是倒过来的编码, 如何得到正确的编码呢?
实际的代码中, 添加一个 0 或 1 都是在末尾添加, 这样到最后得到的其实是正确的编码.怎么知道当前结点是左分支还是右分支?
在赫夫曼树中, 可以访问到双亲结点, 看看当前结点是否等于双亲结点的左孩子, 是的话就是左分支, 反之是右分支.
三. 赫夫曼树编码代码
1 | //通过编码之后, 每个字符得到其对应编码, 这些编码是 0 和 1 组成的字符串. |
四. 完整代码
有一部分来自上一篇的代码, 为了与文档上的结果一致, 做出了一些修改.
逻辑上面说了, 只不过细节还有些需要注意的地方, 比如字符串的内部指针, 以及挑选最小的两个元素.
(还有很多可以优化的地方.)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
typedef char * HuffmanCode[N+1];/*存放编码的结果*/
typedef struct
{
int weight;
int parent;
int LChild;
int RChild;
}HuffmanTree[M+1]; /*HuffmanTree 是一个结构体数组类型, 0 号单元不用.*/
void select(HuffmanTree ht, int n, int * s1, int * s2);
void CrtHuffmanTree(HuffmanTree ht, int w[], int n);
void ScanW(int w[], int * n);
void PrintHuffmanTree(HuffmanTree ht, int n);
void CrtHuffmanCode(HuffmanTree ht, HuffmanCode hc, int n);
void PrintHuffmanCode(HuffmanCode hc, int n);
int main()
{
HuffmanTree ht;
HuffmanCode hc;
int w[N], n;
ScanW(w, &n);
CrtHuffmanTree(ht, w, n);
PrintHuffmanTree(ht, n);
CrtHuffmanCode(ht, hc, n);
PrintHuffmanCode(hc, n);
return 0;
}
//输出赫夫曼树
void PrintHuffmanTree(HuffmanTree ht, int n)
{
int i;
printf("赫夫曼树如下: \n");
for(i=1; i<2*n; i++)
{
printf("权重: %2d, 双亲: %2d, 左子树: %2d, 右子树 %2d .\n", ht[i].weight, ht[i].parent, ht[i].LChild, ht[i].RChild);
}
}
//输入个数和权重
void ScanW(int w[], int *n)
{
int i;
printf("请输入叶子结点的个数: \n");
scanf("%d", n);
printf("请输入各结点的权重: \n");
for(i=0; i<(*n); i++)
{
scanf("%d", &w[i]);
}
}
//选出最小的两个数
void select(HuffmanTree ht, int n, int * s1, int * s2)
{
/*
这个函数是为了找出 ht[1]~ht[n] 中 parent 等于 0, 而且最小的两个数, 同时保证 s1 小于 s2.
思路: s2 等于第一个 parent 为 0 的数的下标, s1 等于第二个 parent 为 0 的下标, s1 往后找最小的数, s2 也往后找最小的数.
这样就保证了 s2 和 s1 不会是同一个数. 最后保证 s1 对应的值 小于 s2对应的值.
*/
int i, first, second, min;
*s1 = 0;
*s2 = 0;
for(i=1; i<=n; i++)
{
if(ht[i].parent != 0)
{
continue;
}
else
{
first = i;
break;
}
}
*s2 = first; /*确保它们不会指向同一个元素*/
for(i=first+1; i<=n; i++)
{
if(ht[i].parent != 0)
{
continue;
}
else
{
second = i;
break;
}
}
*s1 = second;
for(i=second+1; i<=n; i++)
{
if(ht[i].parent != 0)
{
continue;
}
else
{
if(ht[i].weight <= ht[*s1].weight)
{
*s1 = i;
}
}
}
for(i=first+1; i<=n; i++)
{
if(ht[i].parent != 0 || i == (*s1))
{
continue;
}
else
{
if(ht[i].weight <= ht[*s2].weight)
{
*s2 = i;
}
}
}
/*判断的是 ht[*s1].weight 和 ht[*s2].weight, 而不是 s1 和 s2*/
if(ht[*s1].weight > ht[*s2].weight)
{
min = *s1;
*s1 = *s2;
*s2 = min;
}
/*此处是为了跟文档上面的编码结果一致*/
if(ht[*s1].LChild==0 && ht[*s2].LChild!=0)
{
min = *s1;
*s1 = *s2;
*s2 = min;
}
/*两个 if 保证了赫夫曼树中, 左子树小于右子树, 同时叶子结点在右子树(除最底层)*/
printf("本次选出: %d %d\n", ht[*s1].weight, ht[*s2].weight);
}
//构造赫夫曼树
void CrtHuffmanTree(HuffmanTree ht, int w[], int n)
{
int i, s1, s2;
/*构造赫夫曼树 ht[M+1], w[] 存放 n 个权值. */
for(i=1; i<=n; i++)
{
/*1~n 号单元存放叶子结点, 初始化*/
ht[i].weight = w[i-1];
ht[i].parent = 0;
ht[i].LChild = 0;
ht[i].RChild = 0;
}
for(i=n+1; i<2*n; i++)
{
/*n+1~2*n-1 号单元存放非叶子结点, 初始化*/
ht[i].weight = 0;
ht[i].parent = 0;
ht[i].LChild = 0;
ht[i].RChild = 0;
}
//开始创建赫夫曼树
for(i=n+1; i<2*n; i++)
{
//从 ht[1]~ht[i-1] 中选两个 parent 为 0 而且权值最小的两个数, 赋给 s1, s2
select(ht, i-1, &s1, &s2);
ht[i].weight = ht[s1].weight + ht[s2].weight;
ht[i].LChild = s1;
ht[i].RChild = s2;
ht[s1].parent = i;
ht[s2].parent = i;
}/*赫夫曼树建立完毕*/
}
//对赫夫曼树编码
void CrtHuffmanCode(HuffmanTree ht, HuffmanCode hc, int n)
{
//传入赫夫曼树, 存储赫夫曼编码的数组, 需要编码的个数
int i, c, p, start;
char * cd;/*cd 作为临时指针, 指向编码过程中得到的字符串*/
cd = (char *)malloc((n+1)*sizeof(char));/*光有一个指针只能存一个地址, 字符串都没地方放, 所以需要动态分配一块内存存放字符串(n 个字符是有备无患的意思吗???)*/
cd[n] = '\0';/*最后一位添加一个字符串结束标志*/
for(i=1; i<=n; i++)
{
/*从赫夫曼树第一个元素开始(1-n 存储的是叶子结点), c 指向当前结点, p 指向双亲结点*/
c = i;
p = ht[i].parent;
start = n;/*start 是 cd 指向的数组的内部指针*/
while(p!=0)/*只要当前结点不是根节点(只有根节点的双亲为 0), 就一直循环*/
{
start--;
if(ht[p].LChild == c)/*如果双亲的左孩子指向当前结点, 说明往左走走到当前结点.(c 是一个数组下标)*/
{
cd[start] = '1';
}
else
{
cd[start] = '0';
}
/*向上移动*/
c = p;
p = ht[p].parent;
}
/*得到某个叶子结点的编码之后, 为其指针分配内存空间(长度根据实际情况决定)*/
hc[i] = (char *)malloc((n+1-start)*sizeof(char));
strcpy(hc[i], &cd[start]);/*取 start 位置的字符的指针, 通过 strcpy 复制*/
}
}
void PrintHuffmanCode(HuffmanCode hc, int n)
{
printf("赫夫曼编码: \n");
int i;
for(i=1; i<=n; i++)
{
printf("%s\n", hc[i]);
}
}