通达学院

算法与数据结构程序设计

题 目： 哈夫曼编码和译码系统

专 业 学 生 姓 名 班 级 学 号 指 导 教 师 指 导 单 位 日 期

同学出勤率(满勤、较高、一般，较低)，学习态度(端正、教较端正、一般、较差)，程序设计基础（好、较好、一般、较差），演示程序(已经、没有)达到了基本要求，算法设计（好、较好、师一般），界面友好程度（好、较好、一般），答辩过程中回答问题（准确、较准确、错误率较高），撰写报告格式(规范、一般)、内评容（丰满、简单）、表述(清晰、一般、不清楚)，（圆满、较好、基本)完成了课题任务。 语 教师签名： 年 月 日 成绩评定 备注

一、题目要求： 题 目 ：哈夫曼编码和译码系统

基本要求： (1) 能输入字符集和各字符频度建立哈夫曼树； (2) 产生各字符的哈夫曼编码，并进行解码。 提高要求： (1) 能设计出简捷易操作的窗口界面； (2) 编码和译码存储在文件中。

二、需求分析： 2.1基本思想

根据,哈夫曼的定义,一棵二叉树要使其带权路径长度最小,必须使权值越大的叶子结点越靠近根结点,而权值越小的叶子结点越远离根结点.依据这个特点便提出了哈夫曼算法,其基本思想是:

(1) 初始化:由给定的n个权值{w1, w2,…, wn}构造n棵只有一个根结点的二叉树,从而得到一个二叉树集合F={ T1,T2,…,Tn};

(2) 选取与合并:在F中选取根结点的权值最小的两棵二叉树分别作为左、右子树构造一颗新的二叉树,这棵新二叉树的根结点的权值为其左、右子树根结点的权值之和;

(3) 删除与加入:在F中删除作为左、右子树的两棵二叉树,并将新建立的二叉树加入到F中;

(4) 重复(2)、(3)两步,当集合F中只剩下一棵二叉树时,这棵二叉树便是哈夫曼树.

2.2存储结构

在由哈夫曼算法构造的哈夫曼树中,非叶子结点的度均为2，根据二叉树的性质可知,具有n个叶子结点的哈夫曼树共有2n-1个结点,其中有n-1个非叶子结点,它们是在n-1次的合并过程中生成的.为了便于选取根结点权值最小的二叉树以及合并操作,设置一个数组HuffmanNode[2n-1]保存哈夫曼树中各结点的信息,数组元素的结点结构如图所示.

图 哈夫曼树的结点结构

其中:

weight parent lchild rchild inf