C语言设有一段电文由字符集{A.B,C.D.EF.G,H}组成,各字符在电文中出现的次数集为{5,20,7,8,14,23,3,11},设计各个字符的哈夫曼编码,并译码。
时间: 2023-08-01 07:09:54 浏览: 306
首先,我们需要构建哈夫曼树。按照出现次数从小到大排序,每次选取出现次数最小的两个字符,构建一棵新的树,其权值为这两个字符的权值之和。重复这个过程,直到只剩下一棵树。
| 字符 | 出现次数 |
|------|----------|
| A | 5 |
| B | 20 |
| C | 7 |
| D | 8 |
| E | 14 |
| F | 23 |
| G | 3 |
| H | 11 |
将上表按照出现次数从小到大排序,得到:
| 字符 | 出现次数 |
|------|----------|
| G | 3 |
| A | 5 |
| C | 7 |
| D | 8 |
| H | 11 |
| E | 14 |
| B | 20 |
| F | 23 |
第一步,选取出现次数最小的两个字符 G 和 A,构建一棵新的树,其权值为 3+5=8。
| 字符 | 出现次数 | 编码 |
|------|----------|------|
| G | 3 | 00 |
| A | 5 | 01 |
第二步,选取出现次数最小的两个字符 G-A 和 C,构建一棵新的树,其权值为 8+7=15。
| 字符 | 出现次数 | 编码 |
|------|----------|------|
| G | 3 | 00 |
| A | 5 | 01 |
| C | 7 | 10 |
第三步,选取出现次数最小的两个字符 D 和 H,构建一棵新的树,其权值为 8+11=19。
| 字符 | 出现次数 | 编码 |
|------|----------|------|
| G | 3 | 00 |
| A | 5 | 01 |
| C | 7 | 10 |
| D | 8 | 110 |
| H | 11 | 111 |
第四步,选取出现次数最小的两个字符 G-A-C 和 D-H,构建一棵新的树,其权值为 15+19=34。
| 字符 | 出现次数 | 编码 |
|------|----------|------|
| G | 3 | 00 |
| A | 5 | 01 |
| C | 7 | 10 |
| D | 8 | 110 |
| H | 11 | 111 |
| GAC | 15 | 001 |
| DH | 19 | 011 |
第五步,选取出现次数最小的两个字符 G-A-C 和 E,构建一棵新的树,其权值为 15+14=29。
| 字符 | 出现次数 | 编码 |
|------|----------|------|
| G | 3 | 00 |
| A | 5 | 01 |
| C | 7 | 10 |
| D | 8 | 110 |
| H | 11 | 111 |
| GAC | 15 | 001 |
| E | 14 | 100 |
| DH | 19 | 011 |
最终,选取出现次数最小的两个字符 G-A-C-E 和 D-H,构建一棵新的树,其权值为 29+19=48。
| 字符 | 出现次数 | 编码 |
|--------|----------|------|
| G | 3 | 00 |
| A | 5 | 01 |
| C | 7 | 10 |
| D | 8 | 110 |
| H | 11 | 111 |
| GAC | 15 | 001 |
| E | 14 | 100 |
| DH | 19 | 011 |
| GACE | 29 | 1010 |
| B | 20 | 1011 |
| FG | 23 | 111 |
现在我们得到了每个字符的哈夫曼编码,接下来可以用这个编码来对电文进行编码和解码。
编码过程:
| 字符 | 出现次数 | 编码 |
|------|----------|------|
| A | 5 | 01 |
| B | 20 | 1011 |
| C | 7 | 10 |
| D | 8 | 110 |
| E | 14 | 100 |
| F | 23 | 111 |
| G | 3 | 00 |
| H | 11 | 111 |
电文为:BFAFFFGEDBEFBCFFACEEFDCBDA
将每个字符用上表中的编码替换,得到编码后的电文:
1011 111 100 111 111 00 100 111 110 1010 111 100 1011 1011 111 100 10 100 100 100 100 1011 100 10 111 111 10 1010
解码过程:
从根节点开始,对于每个 0,走左子树;对于每个 1,走右子树。当到达叶子节点时,输出对应的字符并回到根节点继续解码。
编码后的电文为:1011 111 100 111 111 00 100 111 110 1010 111 100 1011 1011 111 100 10 100 100 100 100 1011 100 10 111 111 10 1010
从根节点开始,第一个字符是 1,走右子树,到达 GACE 节点,第二个字符是 0,走左子树,到达 G 节点,输出 G。回到根节点,第三个字符是 1,走右子树,到达 FG 节点,第四个字符是 1,走右子树,到达 F 节点,输出 F。继续解码,最终得到解码后的电文:BFAFFFGEDBEFBCFFACEEFDCBDA。
阅读全文
相关推荐




