哈夫曼树及其应用

1、EAST CHINA INSTITUTE OF TECHNOLOGY* * * *课程设计报告题目：哈夫曼树及其应用学生姓名:何昆学 号：201120180418班 级：1121804指导教师：张军2013年1月10日目录一、需求分析说明31课程设计目的32.课程设计题目 33 程序功能及需求说明3二、总体设计41. 哈夫曼树建立42 哈夫曼编码43 哈夫曼译码4三、详细设计51. 算法设计52. 类设计5四、实现部分6五、程序测试97 > 总结 10一、需求分析说明1、课程设计目的本课程设讣的U的考察学生对常见数据结构及相关算法的综合应用能力，达 到理论与实际应用相结合，使同学们能够根

2、据数据对象的特性，学会数据组织的 方法，解决实际问题中数据的合理存储表示，并根据相应的存储结构设讣效率较 高的算法实现对问题的求解；通过此次课程设讣进一步培养学生良好的程序设计 技巧和分析问题解决问题的能力。2、课程设计题哈夫曼树及其应用(1) .设计L1的：熟悉树的各种存储结构及其特点及掌握建立哈夫曼树和哈夫曼编 码的方法及带权路径长度的计算。(2) .设计内容：欲发一封内容为AABBCAB(共长100字符,其中:A、B、C、 D、E、F分别有7、9、12、22、23、27个)的电报报文，实现哈夫曼编码 和译码。(3) .设计要求：分析系统需求。建立哈夫曼树。进行哈夫曼编码，并求出平均编码长

3、度。译码，对编码好的内容进行译码。3、程序功能及需求说明功能：编码，编码长度，译码要实现编码译码等功能，必须先建立一个哈夫曼树，编码长度、译码乂通过编码 求得。这里通过分别创建结点类(tree)和编码类(codetype),子函数有哈夫 曼树建立(creathuffmantree ),哈夫曼编码(arrangecode ),哈夫曼译码 (transcode),最后通过主函数调用执行。二、总体设计1 哈夫曼树建立A7B-9C-12D-22E-23F-272哈夫曼树编码（路径往左为0,往右为1）7的编码：1110 9的编码：1111 12的编码：1 1 022的编码：0023的编码：0 127的编

4、码：1 0带权路径长度：WPL=7*4+9*4+12*3+22*2+23*2+27*2=244平均编码长度为：4+5+5+6+6+7=333 哈夫曼树译码假设发送的电报报文为:1110110111110000110则译码成原文为：7 12 9 27 22 23 27即 “ACBFDEF”三、详细设计(1) .建立哈夫曼树的算法：左义各廿点类型英中应包含两类数据一是权值域weight：- 是指针域而指针域中应该包括指向左右孩子和指向双亲的指针这里分别用lchild、rdhild和 parent来表示，在实际构造中由于是叶子节点来构造新的根节点苴构造过程中仅与叶子节点 的权重有关而与其数据域无关所

5、以构造过程中不用考虑苴数值域，并且在链表中从叶子开始 存放，让后不断的将两颗最小权值的子树合并为一颗权值为英和的较大的子树，逐步生成各 自内部节点直到树根。(2) .哈夫曼编码的算法：将建立的哈夫曼树从每个叶子廿点开始沿着双亲域回到根节点， 每走一步进行编码得到一位编码值；由于每个叶子节点的哈夫曼编码是从根i'j点到相应的叶 子的路径的各个分支的代码组成的0和1序列，所以先得到了低位编码后得到髙位编码因此 可用一维数组从后向前来存放各位编码值，并用start来记录编码的起始位苣。(3) .哈夫曼译码的算法：通过哈夫曼编码所得到的0和1序列路径，判断是左结点还是右 结点的路径，从而译码得

6、到权值内容。(4) .将建立的哈夫曼树、实现哈夫曼编码、哈夫曼译码都左义成子函数的形式，然后在主 函数中调用它们。两个类:class treepublic:int weight;int parent;int lch jch;void creathuffmantree();class codetypepublic:int bitsn+l;int start;void arrangecode();void transcode();codetype coden+l;tree hftreem+l;四、实现部分（核心代码）第一步：建立哈夫曼树void tree:creathuffmantree()int

7、 i, j, pl, p2;int si,s2;for (i=l;i<=m;i+) hftreeEi parent=0; hftreeilch二0; hftreei rch二0; hftreei weight=0;，z«endl;、B、C、cout«zz哈夫曼树及其应用cout«"输入电报报文内容AABBCAB(共长100字符,其中: D、E、F 分别有 7、9、12、22、23、27 个)：，z«endl;cout«"请分别输入A B C D E F的权值：”； for(i=l;i<=n;i+)cin»

8、;hftreei weight;for (i=n+l; i<=m; i+) /进行 nT 次合并pl二p2=0;/pl、p2分别指向两个权值最小的值的位置 si二s2=32767;/sl、s2代表两个最小权值 for (j二 1; j<=i-l; j+) /选两个最小值if (hftree j. parent0)/该权值还没有被选中if(hftreej weightsl)s2=sl;sl=hftreej weight;p2二pl;pl二 j;elseif(hftreej. weights2)s2=hftreej weight; P2二 j;/以下为合并hftreepl parent

9、二i;hftreep2 parent二i;hftreeilch二pl;hftreei rch二p2;hftreei weight=hftreepl weight+hftreep2 weight;cout«z/哈夫曼树建立成功！ "<Xendl;cout«""endl;for (i=l; i二m; i+)/输出合并后的结果cout«，z 权值:z，<<hftreei. weight«，z ""双亲结点： ，z«hftreei. parent«，z "«

10、;"左孩子："hftreei. lch«""右孩子: "<<hftreei. rch«endl;第二步：对权值进行编码同时并求出带权路径长度 void codetype: :arrangecodeOcodetype cd;int c, p;for (int i二l;iE;i+)cd. start=n+l;c=i;p=hftreei parent;while(p!=0)cd. start一一；if(hftreeplch二二c)cd. bitsEcd start=0;elsecd. bitsEcd. start二1;

11、c 二p；p二hftreep parent;codei二cd;for(i=l;i<=n;i+)int wpl=hftreei.weight:int ave;cout«endl; cout«"+«endl; cout<<z，编码："<<endl;cout<</，权值，<<hftreei. weight«，z"<"编码为："；for(int j二codei start;j<=n;j+)cout«codei bits j «&

12、quot;"wpl=hftreei. weight*(7-codei. bitsj);/求带权路径长度 ave二wpl/j;/平均编码长度cout«z/ 带权路径长度为："wpl«endl;cout«，z平均编码长度为:，z«ave;第三步：对编码进行译码void codetype:transcode()int i=m;char word;cout«endl;cout«""<endl;cout«z/进行译码："endl;cout«请输入信封内容的编码：&quo

13、t;；cin»word;cout«"(A二7、B二9、012、D二22、E二23、F二27) "endl;cout"译码成功！ "endl;cout«endl;cout«""<endl;cout«译码为：“；while (word" 0311 (word= f )/译码,向左为0,向右为1得到相应的 根结点权值if (word=，O')i=hftreei. lch;elsei=hftreei rch;if(hftreei. lch=O)cout«hft

14、reei weigh;i=m;cin>>word;五、程序测试哈夫曼树建立（通过分别输入A、B、C、D、E、F权值）:用:A 应中 其其 W一长一it八-z273 C : /成 、n±2别曼 i八負 谙哈i.子t:f =予t:蚩刊齐一子子葫聲脣孩孩孩孩一liks右云右右右右0 3 4 6 9- 0 ® 0 1i.子一骑予/-:一奎刊2?:lilli0 u 1 1 0 8 9 918111 7 7 冷矗疊饕«« =口 =口>二，二亍!:£亍>7*,二->!:"二定 誓亲亲亲亲亲亲亲亲对 亠II双双饕双發线

15、223768550 79122212451编码（对权值生成的哈夫曼树进行编码，向左为0,向右为1,并对所得编码进行带权路径 长度和平均编码长度运算）：0带权路径长度为：28<-+ + + + 4-4 + + + + + *- + + + + 4-4 + + +1蒂权K径长度为；36< + + + + +4+ + + + +4-+ + + + + 4 + + +带权路径长度为，？6十 * +十 * + 十 *帶权路径长度为：44t-r1-r t-r1-带权路径长度为：46带权路径长度为：54餐B-9功进请Kfi铎译码（通过输入已生成的编码，反推出结点所在位置的权值）:1110110111110000110、E-23s F-27>降码为：?12927222327六、总结实验心得这次实验最大遗憾是没有把二义树很好的显示出来，对于本程序的主要部分， 哈夫曼树的生成和哈夫曼码的编译，没有任何的创新，无论是算法还是基本框架 都是套用课本上的经典算法，时间复杂度都为0(112).51外在创建哈夫曼树时选择 两个权值的结点的效率不是太高。每次都要先找到最大的权值，然后再进行比较, 经过两次循环找到两个最小的权值，这一个函数的时间复杂度比创建，编码，