c语言编程 根据给定的n企字符及其权值,设计各字符的哈夫曼编码。设有一段电文由字符集{A.B,C.D.EF.G,H}组成,各字符在电文中出现的次数集为{5,20,7,8,14,23,3,11},设计各个字符的哈夫曼编码,并译码。
时间: 2023-07-31 18:13:20 浏览: 73
根据哈夫曼编码的思想,出现次数越多的字符编码越短,出现次数越少的字符编码越长。首先,按照出现次数从小到大排序,以便于构建哈夫曼树。
1. 构建哈夫曼树
首先将字符集中的每个字符作为一个单独的节点,并将它们的出现次数作为权值。然后,每次从权值最小的两个节点中选出一个作为左子节点,一个作为右子节点,构建一个新的节点,其权值为左右子节点的权值之和。如此反复,直到所有节点都被合并成为一棵树,这就是哈夫曼树。
构建过程如下:
```
3 5 7 8 11 14 20 23
\ / \ / \ / \ / \ / \ / \ / \
AB C D E F G H
/ \
BCDEFGH
```
2. 根据哈夫曼树确定编码
从根节点出发,当向左走时编码加0,向右走时编码加1,当到达一个叶子节点时,就得到了该叶子节点对应的字符的哈夫曼编码。
编码过程如下:
```
3 5 7 8 11 14 20 23
\ / \ / \ / \ / \ / \ / \ / \
AB C D E F G H
/ \
BCDEFGH
A: 1111
B: 1110
C: 110
D: 101
E: 100
F: 01
G: 001
H: 000
```
3. 译码
根据编码表,将编码转化为对应的字符:
```
01001111001111110110011111110101011011110001101
```
按照编码表逐个匹配,得到原始电文:
```
FEFEDFECGFFABEFCGFEBFAGFHB
```
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)