《实验四-赫夫曼》由会员分享，可在线阅读，更多相关《实验四-赫夫曼（15页珍藏版）》请在金锄头文库上搜索。
1、目 录1。概述11.问题描述12。现状分析13.系统分析14。1系统功能模块图25赫夫曼树的存储结构定义35。2赫夫曼算法及其实现3.3统计字符串中字符的种类以及各类字符的个数35.4赫夫曼编译码系统功能模块36。主要代码结构461定义赫夫曼编码类型如下6。2赫夫曼编码算法6建立正文的编码文件57。主要代码段分析671赫夫曼编码的结构定义67.2赫夫曼编码算法6.运行与测试7。1 测试数据及结果79。总结和心得8参考文献80.附:源代码9概述1。问题描述 利用赫夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间，降低传输成本.这要求在发送端通过一个编码系统对待传输数据预先编码,对于双工信
2、道(即可以双向传输信息的信道）,每端都需要一个完整的编码系统。2。现状分析在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，赫夫曼编码正是一种应用广泛且非常有效的数据压缩技术.赫夫曼编码是一种编码方式，以赫夫曼树即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。赫夫曼编码使用一张特殊的编码表将源字符(例如某文件中的一个符号）进行编码.赫夫曼编码的应用很广泛，利用赫夫曼树求得的用于通信的二进制编码称为赫夫曼编码。树中从根到每个叶子都有一条路径,对路径上的各分支约定：指向左子树的分支表示“”码，指向右子树的分支表示“1码,取
3、每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是赫夫曼编码。赫夫曼译码输入字符串可以把它编译成二进制代码，输入二进制代码时可以编译成字符串 赫夫曼编码是已被证明的一种有效的熵编码方式，在诸如文本、图像、视频压缩及通信、密码等信息压缩编码标准中被广泛使用。目前广泛应用的许多其他高效数据压缩算法。3.系统分析利用二叉树结构实现赫夫曼编解码器. 基本要求: 1、初始化：能够对输入的任意长度的字符串进行统计,统计每个字符的频度,并建立赫夫曼树.、 建立编码表（CreatTabe)：利用已经建好的赫夫曼树进行编码,并将每个字符的编码输出. 3、编码（oding):根据编码表对输入的
4、字符串进行编码，并将编码后的字符串输出。4、 译码（Dcoing)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。.概要设计系统功能模块图赫夫曼编译码器的主要功能是先建立赫夫曼树,然后利用建好的赫夫曼树生成赫夫曼编码后进行译码 。 在数据通信中，经常需要将传送的文字转换成由二进制字符0、1组成的二进制串,称之为编码。构造一棵赫夫曼树,规定赫夫曼树中的左分之代表0，右分支代表1，则从根节点到每个叶子节点所经过的路径分支组成的0和1的序列便为该节点对应字符的编码，称之为赫夫曼编码。 最简单的二进制编码方式是等长编码.若采用不等长编码,让出现频率高的字符具有较短的编码，让出现频率低
5、的字符具有较长的编码，这样可能缩短传送电文的总长度。赫夫曼树课用于构造使电文的编码总长最短的编码方案。赫夫曼编码 /译码器类型及相关变量的定义建立赫夫曼树生成赫夫曼文件赫夫曼译码4.1系统功能模块图5.详细设计5.赫夫曼树的存储结构定义#defn n 00/叶子结点数#deine m *-1赫夫曼树中结点总数yedef struct int weih；/权值 t lchild，rchild，aent；左右孩子及双亲指针HTNe；树中结点类型tyedf HTNodeHuffmanTreem1;/零号单元不用5。2赫夫曼算法及其实现根据给定的 个权值w1，w ,n, 构成n 棵二叉树的集F=T1,
6、T2 ，n， 其中每棵二叉树T 中只有一个带权为i的根结点，其左右子树均空.在F 中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树， 且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和.在F 中删除这两棵树, 同时将新得到的二叉树加入 中。重复和， 直到 只含一棵树为止, 这棵树便是赫夫曼树。 5.统计字符串中字符的种类以及各类字符的个数该算法的主要实现思想是:先定义一个含有6个元素的临时整型数组,用来存储各种字母出现的次数.因为大写字母与小写字母相差64位，所以在算法中我们可以使用字母减去64作为统计数组的下标对号入座。在统计和保存过程中,我们用一个循环来判断先前统计的
7、各类字符是否为零，若不为零，则将其存入一个数组对应得元素中,同时将其对应的字符也存入另一个数组元素中。5。赫夫曼编译码系统功能模块（ 1）赫夫曼建树模块 : 根据输入的字符和频率, 完成赫夫曼树的构造, 并根据赫夫曼树求赫夫曼编码。( 2)编码模块: 读取文本文件进行编码， 编码结果存入到新文件。（ 3)译码模块： 读取编码文件并解码， 打开存储编码的文件， 根据所读取的编码文件中的每字符，利用赫夫曼树进行解码.（ 4）输出模块: 将解码后的每个字母写入到一个新的文件中。6.主要代码结构.1定义赫夫曼编码类型如下dftrctchar c；/存放编码的字符char bitsn1;/存放编码的位置
8、int tart；/编码起始位置CodNode；typedef CdNodHufaCodn;6.赫夫曼编码算法oid HuffmanEcoing(HuffmaneHT,uffmanodHC)intc,p,i；char cdn;int str；cnum0；（i=1;=num;i+)stanum；c=i；wile（=HTc.parnt）0)-star=(Tplchil=） ？0:；c=；strcy(HCi。bits，cdstat）；HCi.ln=umtart;63建立正文的编码文件建立正文的编码文件的基本思想是：将要编码的字符串中的字符逐一与预先生成赫夫曼树是保存的字符编码对照表进行比较，找到之后
9、,对该字符的编码写入代码文件，直至所有的字符处理完为止。具体实现算法如下：vid oding(ffmanCode C,charstr) i,j；FLEp;p=ope(d”,w”)；hil（str）for（i=；i=um;+）i（H。ch=*str)fr(j=;jCi。e;+）utc（HCibi,p);brk;tr+；fclos（fp）;7。主要代码段分析赫夫曼编码可以用于通信技术，它的定义是树从根结点到每个叶子结点的路径上的各分支进行约定，指向左子树对的分支表示“”码,指向右子树的分支表示“1”码，取每条路径上的“0”或“1的序列作为和各个叶子对应的字符的编码，这就是赫夫曼编码。7。赫夫曼编码
10、的结构定义typedef ruchah；/存放编码的字符chabitn+1;/存放编码的位置insart；/编码起始位置CodeNoe；tpedef odeNd umanoden;赫夫曼编码算法id HufmnEncoig（HffmneHT,HuffanodHC)/根据赫夫曼树HT求赫夫曼编码Hintc,，i;/和分别指示HT中孩子和双亲的位置charcdn；/临时存放编码串int star；/指示编码在cd中起始位置cdnm=；/最后一位放上结束符for（;i=n;+)startnm;/起始位置=i;/从叶子结点HT开始上溯hl（p=HTc。paren）0)直至上溯到Hc是树根为止/若Hc是
11、p的左孩子,则生成0;否则生成代码dstrt=（Tp.lcld=c)?:1；c=p;trcp（HCibit，&dstr）；HCi。lnnumart;8.运行与测试8.测试数据及结果输入：NO MAN N OWO HINS AT NE，得出结果：9总结和心得通过这次课程设计,我们学习了很多在上课没懂的知识，并对求赫夫曼树及赫夫曼编码/译码的算法有了更加深刻的了解.更巩固了课堂中学习有关于赫夫曼编码的知识参考文献1 数据结构课程设计-苏仕华 等编著2 数据结构(C语言版）-严蔚敏 吴伟民编著3 C程序设计（第三版）-谭浩强 著0附：源代码#inlude stdioh#incud string。/（
12、1）类型及相关变量的定义/defn 100/ 叶子结点数define 2*n1/赫夫曼树中的结点总数typeftuct ar ch；r is9;/存放编码位串in le；/编码长度odeNde;typedef CodeoeHufmande+1;typdef stuc nt eigt；/权值int child，rcld，parent;/左右孩子及双亲指针HTNode；/树中的结点类型typedef HNodeHuffmane+1;/0号单元不可用itn；/字母类型的个数/（2)建立赫夫曼树的三个函数/voi sec(ufmnrT,int k，int *1，nt *s）/在H1k中选择paent为0且权值最小的两个根结点，其序号分别为S1和S i i,j;it in100；fo（i=;i=k;i)/查找s i（iwigtmn1 Ti.pret=0） j;mTiwegh; (1)j; mn1276； for(i1;i=k；i+)/查找s2,不和s1相同 f（T.gtmin1 &Ti.paren=0 & i！=(s1) =i; mi1Ti。weight； (s2）
