哈夫曼编译码系统的设计与实现

《哈夫曼编译码系统的设计与实现》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、计算机与信息技术学院设计性实验报告专业：年级/班级：2011—2012学年第一学期课程名称数据结构指导教师木组成员学号姓名实验地点过街楼机房实验时间12月2日项日名称哈夫曼编/译码系统的设计与实现实验类型设计性一、实验1=1的理解哈夫曼树的特征及其应用；在对哈夫曼树进行理解的基础上，构造哈夫曼树，并用构造的哈夫曼树进行编码和译码；通过该实验，使学生对数据结构的应用有更深层次的理解。二、实验仪器或设备学院提供公共机房，1台/学生微型计算机。三、总体设计（设计原理、设计方案及流程等）设计原理：利用哈夫曼编码进行通信可以大大提高信道利用率

2、，缩短信息传输时间，降低传输成木。但是，这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码（解码）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个哈夫曼编/译码系统。设计方案及流程：1）初始化（Initialzation）o从数据文件DataFile.dat中读入字符及每个字符的权值，建立哈夫曼树HuffTree；2）编码（EnCoding）o用已建好的哈夫曼树，对文件ToBeTran.dat+的文本进行编码形成报文，将报文写在文件Code.txt

3、中；3）译码（Decoding）＜＞利用已建好的哈夫曼树,对文件CodeFile.dat中的代码进行解码形成原文，结果存入文件Textfile.txt中；4）输出（Output）:输tBDataFile.dat中出现的字符以及各字符出现的频度（或概率）；输出ToBeTran.dat及其报文Code.txt；输出CodeFile.dat及其原文Textfile.txt；要求：所设计的系统应能在程序执行的过程屮，根据实际情况（不同的输入）建立DataFile.dat^ToBeTran.dat和CodeFile.dat三个文件,以保证系统

4、的通用性。四、实验步骤（包括主要步骤、代码分析等）（1）完成程序的主框架设计，进行调试，验证其正确性。在给定一组具有确定权值的叶结点，可以构造出不同的带权二叉树。例如：给出4个叶结点，设具权值分别为1,3,5,7,我们可以构造出形状不同的多个二叉树。这些形状不同的二叉树的带权路径长度将各不相同。这五棵树的带权路径长度分別为：(a)WPL=IX2+3X2+5X2+7X2=32(b)WPL=IX3+3X3+5X2+7X1=29(c)WPL=1X2+3X3+5X3+7X1=33(d)WPL=7X3+5X3+3X2+1X1=43(e)WPL

5、=7X1+5X2+3X3+1X3=29由此可见，由相同权值的一组叶子结点所构成的二叉树有不同的形态和不同的带权路径长度，那么如何找到带权路径长度最小的二义树(即哈夫曼树)呢？根据哈夫曼树的定义，一棵二叉树要使其WPL值最小，必须使权值越人的叶结点越靠近根结点，而权值越小的叶结点越远离根结点。哈夫曼(a)(c)(b)(d)(e)(Haffman)依据这一特点提出了一种方法，这种方法的基本思想是：(1)根据给定的n个权值{wl,w2,wn},构造n棵二叉树的集合F={Tl,T2,…,Tn},具中每棵二义树中均只含一个带权值为wi的根结点

6、,其左、右子树为空树；(2)在F中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和；(3)从F中删去这两棵树，同时将新生成的二叉树加入F中；(4)重复第⑵和(3)两步，直至F中只含一棵树为止。例如：叶结点权值集合为W={1,3,5,7}的哈夫曼树的构造过程。第一步Q00O第二步OQo4Huffman算法实现：1)一棵有n个叶子结点的Huffman树有2n-l个结点2)采用顺序存储结构——一维结构数纽3)结点类型定义typedefstruct{in

7、tdata;intweight;intpa,lc,rc;}JN;(2)详细设计，进行调试，验证其正确性。算法如下：voidInitialzation(HuffmanTree&HT,HuffmanCode&HC,int*w」ntn,ElemType*d){//w存放n个字符的权值(均>0),构造哈弗曼书HT,并求出n个字符的哈弗曼编码HC。讦(n

8、(p=HT+l,i=l;i<=n;++i/++p,++w,++d){〃给相关变量赋值，p->weight=*w;p->lchild=0;p->rchild=0;p->parent=0;p->data=*d;}for(;i<=m;++i