BBCAADDDCCACACAC对以上asc码字符串写出利用贪心算法实现哈夫曼编码的过程
时间: 2024-06-09 15:05:30 浏览: 10
首先,我们需要统计每个字符出现的频率,得到如下表:
| 字符 | 频率 |
|------|------|
| A | 2 |
| B | 2 |
| C | 5 |
| D | 4 |
接下来,我们将频率从小到大排序,得到:
| 字符 | 频率 |
|------|------|
| A | 2 |
| B | 2 |
| D | 4 |
| C | 5 |
然后,我们将频率最小的两个字符合并成一个新的节点,它们的权值为它们频率的和。如图所示,我们将 A 和 B 合并成一个新节点 1,它的权值为 4。
```
(A,2) (B,2)
\ /
\ /
\ /
(1,4)
```
再次排序,得到:
| 字符 | 频率 |
|------|------|
| D | 4 |
| 1 | 4 |
| C | 5 |
合并权值最小的两个节点,得到新的节点 2,它的权值为 8。
```
(1,4) (D,4)
\ /
\ /
\ /
(2,8)
|
|
(C,5)
```
排序后得到:
| 字符 | 频率 |
|------|------|
| 2 | 8 |
| C | 5 |
合并节点 2 和 C,得到根节点,它的权值为 13。
```
(2,8)
/ \
/ \
/ \
(C,5) (D,4)
```
接下来,我们分别给左边和右边的节点赋值 0 和 1,得到哈夫曼编码:
| 字符 | 频率 | 编码 |
|------|------|------|
| A | 2 | 00 |
| B | 2 | 01 |
| C | 5 | 1 |
| D | 4 | 10 |
最终,将字符串 BBCAADDDCCACACAC 转换为哈夫曼编码为 01001000010111111100101010。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)