实验三哈夫曼编码.doc

北京邮电大学信息与通信工程学院

数据结构实验报告

1．实验要求

1 实验目的
掌握二叉树基本操作的实现方法
了解赫夫曼树的思想和相关概念
学习使用二叉树解决实际问题的能力
利用二叉树结构实现赫夫曼编/解码器。
基本要求：
1、 初始化(Init)： 能够对输入的任意长度的字符串 s 进行统计， 统计每个字符的频度，
并建立赫夫曼树
2、 建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字符的
编码输出。
3、 编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输
出。
4、 译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出
译码结果。
5、 打印(Print)：以直观的方式打印赫夫曼树（选作）
6、 计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压
缩效果。

第1页

北京邮电大学信息与通信工程学院

测试数据：
I love data Structure, I love Computer。I will try my best to study data Structure.

2. 程序分析

2.1 存储结构

用二叉树的结构建立哈夫曼树，每个节点的结构是
struct HNode
{
int weight; int parent;
int lch; int rch;
string code;
char data;
};
weight parent lch rch code data

哈夫曼树的特点：只有度为 2 的结点和叶子结点，所以具有 n 个叶子结点的哈夫曼树的结点
总数为 2n-1
顺序存储结构： 设置一个的 HTree[2*n-1]数组
2.2 关键算法分析

建立哈夫曼树 编码 解码

关键算法一：初始化
伪代码：
1.将存字符串权值的数组 a 赋 0 值，字符种类 n 赋 0 值
2.获取输入字符串
3.遍历输入的字符串，若某个字符出现一次，则在 a[i]++，i 为该字符 ascii 码
4.遍历 a 数组，在 a[i]有值的地方给 HTree[i].weight 赋值为 a[i],HTree[i].data 赋值为 ascii 码
为 i 的字符
源代码:
void Huffman::Init() //初始化
{
for(int m=0;m<256;++m)
a[m]=0;
cout<<"请输入想要编码的字符"<<endl;

第2页

北京邮电大学信息与通信工程学院

getline(cin,str);
n=0;
cout<<"各字符权值为："<<endl;
for(int i = 0;i!=str.size();++i)
++a[str[i]];
for(int i=0;i<256;++i)
if(a[i]!=0)
{

cout<<char(i)<<" "<<a[i]<<endl;n++;}
HTree=new HNode[2*n-1];

int j = 0;//j!=n;++j)

for(int k=0;k<256;++k)
{
if(a[k]!=0)
{
HTree[j].weight=a[k]; HTree[j].data=char(k);

j++;
}

}

}
时间复杂度：
若输入的字符串长度为 n，则时间复杂度为 O(n)

关键算法二：编码：
思想（不等长编码）
使用频率高的字符，编码长度短； 使用频率低的字符，编码长度长；
利用不等长编码，可以使报文总长度较短，这也是文件压缩技术的核心。
1．取当前结点=叶结点
2．取当前结点的父结点
2.1 如果叶结点是左孩子，编码 0
否则，编码 1
2.2 当前结点=父结点
反复执行，直到当前结点是根结点。
生成哈夫曼编码

第3页