霍夫曼树与霍夫曼编码.doc

实验五霍夫曼树与霍夫曼编码
实验目的
掌握霍夫曼树的概念
掌握霍夫曼树的构造过程;
掌握霍夫曼树编码;
掌握霍夫曼树译码。
实验内容与要求
本实验要求对输入的一串电文字符实现霍夫曼编码,再对霍夫曼编码生成的代码串进行译码,输出电文字符串。具体要求:
建立霍夫曼树;
霍夫曼编码的生成;
霍夫曼译码。
实验编程指导
1)霍夫曼树的建立
由霍夫曼树的定义可知,含有n个叶子结点的霍夫曼树中共有2n-1个结点,而且霍
夫曼中没有度为1的分支结点。我们可以用一个大小为2n-1的一维数组来存储霍夫曼树中的结点。霍夫曼树的参考存储结构描述如下:
#define n 100
#define m 2*n-1
typedef struct
{ int weight;
char ch;
int parent,lchild,rchild;
}HTNode;
typedef HTNode HuffmanTree[m];
要实现霍夫曼树,首先要实现HT[1…n]中选择parent为-1且权值最小的两个根结点的选择算法;另外,还要有一个实现统计输入电文字符串中各种字符出现的频率以及字符的种类的算法,假设电文中仅含有大写字母。霍夫曼树的建立主要包括以下三个部分:
选择parent为-1且权值最小的两个根结点的算法;
统计字符串中字符的种类以及各种字符的个数的算法;
构造霍夫曼树。
2)霍夫曼编码
要求电文的霍夫曼编码,必须先定义霍夫曼编码的类型。参考的定义如下:
typedef struct{
char ch; //存放编码的字符
char bits[n+1]; // 存放编码位串
int start; //编码起始位置
} CodeNode;
该部分主要包括如下内容:
霍夫曼编码:根据霍夫曼树求霍夫曼编码表;
建立正文的编码文件:将要编码的字符串中的字符逐一与预先生成的霍夫曼树保存的字符编码对照表进行比较,找到之后,将该字符的编码写入代码文件,直至所有的字符处理完毕为止。功能:输入任意一个字符串(要求其中的字符在原始字符串中出现过),能够进行霍夫曼编码。
3) 霍夫曼译码
读取编码,并与原生成的霍夫曼编码表比较,遇到相等时,即取出其对应的字符存入一个新串中。
注意:具体编解码算法可以参考讲义。以上为参考实验方案,不局限于此方案。
实验报告要求
分组方式:按小组方式进行,2个人为1组,选1名为组长,负责计划整个题目的进展,要求分工明确,任务详实。
实验报告要求以word文件形式发到老师邮箱。内容包括:
(1)报告封面包括实验名称、班级、姓名、学号以及实验完成日期。
(2)各程序模块名称及功能说明。并绘制出主要功能函数的程序流程图。
(3)个人小结。包括实验难点分析、进一步的工作、个人希望等。
(4)完整的程序清单。
完成日期:2012—4—30
各模块名称以及功能说明:
int Init( HTNode ht[])函数:初始化函数,通过读取输入的信息,统计哪一些字符出现过,并且统计出现次数来确定权值,最后存入ht[]中。
void select(HTNode ht[],int q,int *p1,int *p2)函数:选出包含新增结点在内的权值最小的两个结点,p1为最小的结点的下标,p2为次小的结点的下标。
void huffman_setup(HTNode ht[],int s)函数:霍夫曼树的建立函数,在所有的叶子结点数组之后依次增加新增结点,其权值依次增加,每一个新的结点的权值为当前结点中权值最小的两个结点权值之和,并建立相应的双亲关系。
void huffman_show(CodeNode hc[],HTNode ht[],int s)函数:给每个输入的信息元素按照权值编01码,其基本原理是按照已经建立的霍夫曼树从最后一个元素(跟结点)开始,根据子树是否满足左右子树的条件来判断0还是1编码。
void huffman_code(CodeNode hc[])函数:根据人为输入的字母信息进行比对编码,得到相应的01码。
void huffman_read(HTNode ht[],int s)函数:根据人为输入的01码,从跟结点开始往下查找得到并输出对应的字母信息。
主要功能函数的程序流程图:
int Init( HTNode ht[])函数
进入函数
初始化各个元素信息
读取元素
N
统计各个元素的出现次数
为‘!’
Y
把统计的结果给ht[]赋值
返回元素的个数
void select(HTNode ht[],int q,int *p1,int *p2)函数
进入函数
N
树中继续查找
双亲非零
Y
后项后移