数据结构
实
验
报
告
实验名称：____Huffman编码/解码器_____ 学生姓名：__________________
班级：__________________
班内序号：__________________
学号：__________________
日期：___________________
1．实验要求
利用二叉树结构实现哈夫曼编/解码器。
基本要求：
1.初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树
2.建立编码表(CreateTable)：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。
3.编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。
4.译码(Decoding)：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。
5.计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。
2. 程序分析
2.1 存储结构
静态三叉链表
2.2 程序流程(或程序结构、或类关系图等表明程序构成的内容，一般为流程图等)
2.2.1.流程图
2.2.1.伪代码
1.输入进行编码的字符串
2.遍历字符串，并为叶子节点权重赋值
3.依次对各字符进行哈弗曼编码，自下往上，若是双亲节点左孩子则编码前插入‘0’，若是双亲节点右孩子则编码钱插入‘1’。
4.显示各字符的哈弗曼编码。
5.对字符串进行编码，挨个遍历字符，找到相应的编码，复制到总的编码里，最后输出字符串的编码。
6.对字符串的哈弗曼码进行译码。自上往下，若是‘0’，则递归到左孩子，若是‘1’，则递归到右孩子，知道叶子节点，输出该叶子节点代表字符，再继续遍历。
7.分析内存占用情况。若用ASCII编码，每个字符占1个字节，即8bit，该情况下占用内存就是（字符长度）*8。若用哈弗曼编码，占用内存是各（字符频度）*（每个字符占用位数）之和。
2.3 关键算法分析
该程序关键算法即哈弗曼编码，语句如下：
void CHTree::huffmancode()
{
int i;
if(n<=1)return;
m=2*n-1;
for(i=1;i<=n;i++)//叶子节点的初始化
{ ht[i].parent=0;
ht[i].lchild=0;
ht[i].rchild=0;}
for(;i<=m;i++) //非叶子节点的初始化
{
ht[i].weight=0;
ht[i].parent=0;
ht[i].lchild=0;
ht[i].rchild=0;}
for(i=n+1;i<=m;++i)//构造哈夫曼树
{
s1=select(i-1);//函数在ht[1]到ht[i-1]中选择parent为0且weight最小的结点，并将结点序号返s，并将ht[s1].parent设为-1
s2=select(i-1);
ht[s1].parent=i;
ht[s2].parent=i;
ht[i].lchild=s1;
ht[i].rchild=s2;
ht[i].weight=ht[s1].weight+ht[s2].weight;
}
int c,f;
for(i=1;i<=n;++i) {
for(c=i,f=ht[i].parent;f!=0;c=f,f=ht[f].parent)//逆向求叶子结点的哈夫曼编码
if(ht[f].lchild==c){
str[i].insert(0,"0",0,1);} //在字符串str[i]的第0位置插入字符“0”
else{
str[i].insert(0,"1",0,1);} //在字符串str[i]的第0位置插入字符“1”
}
}
分析：这段语句实现的功能是根据统计出来的各字符的频度，建立哈弗曼。建立哈弗曼树的过程如程序所展示，每次选取权重最小且无双亲节点的节点组合，并将其权重之和赋给其双亲节点，加入到总结中进行下次判断。哈弗曼树建立完全以后，开始对各字符进行编码，从下往上，以叶子节点为起始点，若它是双亲节点的左孩子，其编码前插入‘0’，若是右孩子则插入‘1’。再判断双亲节点使其双亲节点的左孩子还是右孩子，以此类推直到根节点。依次对每个字符进行上述过程编码。
算法复杂度：
最好情况为只有根结点和叶子节点：O（n）
最坏情况为满二叉树情况：O（n*logn/2）
3.程序运行结果分析
首先，要求用户输入进行编码的字符串，遍历字符串，并为叶子节点权重赋值。然后，依次对各字符进行哈弗曼编码，自下往上，若是双亲节点左孩子则编码前插入‘0’，若是双亲节点右孩子则编码钱插入‘1’。屏幕上显示各字符的哈弗曼编码。接下来对字符串进行编码，挨个遍历字符，找到相应的编码，复制到总的编码里，最后输出字符串的编码。对字符串的哈弗曼码进行译码。自上往下，若是‘0’，则递归到左孩子，若是‘1’，则递归到右孩子，知道叶子节点，输出该叶子节点代表字符，再继续遍历。最后分析内存占用情况。若用ASCII 编码，每个字符占1个字节，即8bit，该情况下占用内存就是（字符长度）*8。若用哈弗曼编码，占用内存是各（字符频度）*（每个字符占用位数）之和。
3.总结
4.1实验的难点和关键点
本实验的难点和关键点是进行哈弗曼的编码与译码。编码之前先要遍历字符串，并统计各字符出现的频度。这里就要区分目前的字符是否出现过，若出现过则字符权重加一，若没有出现则在结构体数组的当前末尾添加该元素。统计完频度以后开始编码。根据哈弗曼树的特点，每次选取结点里权重最小，且双亲不为0的节点结合，依次添加直至根节点。编码过程是从下往上。对于某字符所在叶子节点，若是双亲节点左孩子则编码前插入‘0’，若是双亲节点右孩子则编码钱插入‘1’。直到双亲节点移动到根节点，所得到的编码即为该字符的编码。译码过程是编码的逆过程。依次读取哈弗曼码，自上往下，若是‘0’，则递归到左孩
