哈夫曼树的课程设计报告

1、数据结构与算法课程设计报告书题目哈夫曼编码/译码器班级：学号：姓名：田欢 指导教师：龚丹周期：2011-12-19 至 2011-12-23成绩：1_SI年月日来源：网络转载、课程设计的目的与要求(一) 课程设计目的与任务(参考已发文档自行编辑，但不少于100 字)设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。利用哈夫曼树编码问题基本原理的应用， 撑握对树的不同存储结构的定义和算法描述。学会构造哈夫曼树和哈夫 曼编码等主要算法。(二) 题目要求1) 将权值数据存放在数据文件(文件名为data.txt,位于执行程序的当 前目录中)2) 分别采用动态和静态存储

2、结构3) 初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫 曼树；4) 编码：利用建好的哈夫曼树生成哈夫曼编码；5) 输出编码；6) 设字符集及频度如下表：字符空格 ABCDEFGHIJKLM频度 1866413223210321154757153220字符 NOPQRSTUVWXYZ频度 5763151485180238181161二、设计正文1系统分析(1) 定义一个变量名为HTNode!勺结构体，用该结构体中的chardata、intweight、intparent 、intlchild、intrchild分别表示哈夫曼树中每个结点的权值、权重、双亲结点、左孩子、右孩子，再定义

3、 一个HTNode类型的数组ht30存放哈夫曼树；另外定义一个变量名为 HCode勺结构体，采用HCode类型变量的cdstartcdn存放当前结点的哈夫曼编码、最后定义一个 HCode类型的数组hcd30的数组用于存 放当前叶子结点hti的哈夫曼编码。(2) 编写CodeInput(n,ht) 函数并在函数中设置一个 for(i=0;n;+)循环，首先输入n个字符，再利用函数中的for(i=0;n;+)循环实现对这n个字符的权值的输入。(3) 编写CreateHT(ht,n)函数来构造一棵哈夫曼树，首先用一个for(i=0;2* n-1;+)循环将所有 2n-1 个结点的 pare nt、l

4、child 、rchild域均置初值为-1 ;再用一个for(i=n;2*n-1;+)循环来构造哈夫曼树，在该循环中首先令lnode和rnode为最小权值的两个结点位置且其域值 均为-1，再用一个for(k=0;=i-1;k+)循环在数组ht30中寻找权值最小的两个结点并且只能在尚未构造二叉树的结点中查找，由于只能在尚 未构造二叉树的结点中查找，因此在for(k=0;k=i-1;k+)循环中加入一个if(htk.pare nt=-1)语句来判断结点In ode和rnode是否已经在二叉树中，如果结点In ode和rnode在二叉树中，则结点In ode和rnode 的parent的值为其双亲结

5、点在数组ht30中的序号就不会为-1 了，在 查找到htlnode和htrnode后将他们作为hti的左右子树， ht In ode和htrnode的双亲结点置为hti，且 hti.weight=htl node.weight+htrnode.weight。如此处理下去，直到所2n-1个结点处理完毕。(4) 编写CreateHCode(ht,hcd,n)函数来求哈夫曼编码，由于求哈夫曼编码只需求叶子结点的哈夫曼编码。对于当前叶子结点hti，首先将对应的哈夫曼编码hcdi的start域值置初值n，找其双亲结点 htf，若当前结点是双亲结点的左孩子结点，则在hcdi的cd数组中添加0,若当前结点是

6、双亲的右孩子结点，则在hcdi的cd数组中添加 1，将start域减1。再对双亲结点进行同样的操作，直到无双亲结点为 止，最后让start指向哈夫曼编码最开始字符。因此在函数中设置一个 for(i=0;in;i+)循环，在循环中设置一个while(f!=-1) 循环语句来判断循环是否到了根结点，再在while(f!=-1)中设置一个if(htf.lchild=c)语句来判断该处理左孩子结点还是该处理右孩子结点。最后用这个for(i=0;in;i+)循环来根据哈夫曼树求出哈夫曼编码。(5) 最后编写 CodeOutput(n,hcd)函数，首先利用 for(i=0;in;i+)循环和for(j=

7、hcdi.start;j=n;j+)循环来实现所有字符的哈夫曼编码的输出；再利用for(i=0;in;i+)循环和for(j=hcdi.start;j=n;j+)循环来实现每个字符的序号和哈夫曼编码的输出。2功能详细描述及框图I(1)主函数流程图如图2.1来源：网络转载开始seanf( %d”,&htt.we1 rInti;11In tl,f,c;i=0Jk.i+hc.start=n ;c=i;multiplex结束图2.1主函数流程图I r-Hc.start+;i+图2.2哈夫曼编码算法流程图(2) 哈夫曼编码算法流程图，如图2.2(3) 构造树函数流程图，如图2.3图2.3构造树函数流程图

8、3、数据结构设计3. 1抽象数据类型定义(1) 树的抽象数据类型定义3. 2模块划分本程序包括三个模块：(1) 主程序模块voidmai n()初始化；构造哈夫曼树；求哈夫曼编码；哈夫曼编码输出；(2) 哈夫曼模块实现哈夫曼树的抽象数据类型(3) 求哈夫曼编码模块实现求哈夫曼编码算法的数据类型4、主要功能逻辑过程和实现算法4. 1数据类型的定义(1) 哈夫曼树类型typedefstruct构造树chardata;/ 结点权值 in tweight;/权重in tpare nt;双亲结点in tlchild;/左孩子in trchild;/右孩子HTNode;HTNodeht30;(2) 求哈夫

9、曼编码类型typedefstructcharcd30;/存放当前结点的哈弗曼编码in tstart;/cdstartcd n存放哈弗曼码HCode;HCodehcd30;4. 2主要模块的算法描述(1) 主函数in tma in()intn;prin tf(请输入要输入的字符数量n:);/读入字符的个数while(sca nf(%d,&n), n!=-1)初始化printf( 请输入n个字符和n个权值n);Codelnput(n,ht);输入数据函数，将读入n个字符和权重CreateHT(ht, n);构造哈弗曼树CreateHCode(ht,hcd, n);哈弗曼编码算法CodeOutput

10、( n,hcd);打印哈弗曼编码将打印出编码，和每一个字符的编码return。；(2) 构造哈夫曼树voidCreateHT(HTNodeht,i ntn)构造一棵哈夫曼树in ti,k ,lno de,r no de;in tmi n1,mi n2;for(i=0;i2*n-1;i+)所有结点的相关域置初值-1hti.pare nt=hti.lchild=hti.rchild=-1;for(i=n;i2* n-1;i+)构造哈弗曼树min仁min2=32767;/lnode和rnode为最小权值的两个结点位置Ino de=r no de=-1;for(k=0;k=i-1;k+)在ht中查找权

11、值的最小的两个结点if(htk.pare nt=-1)只在未构造的二叉树结点中查找if(htk.weightmi n1)min 2=mi n1;rno de=l no de;min 1=htk.weight; Ino de=k;elseif(htk.weightmi n2)mi n2=htk.weight;rnode=k;ht Ino de.pare nt=i;htr no de.pare nt=i; hti.weight=ht Ino de.weight+htr no de.weight; hti.lchild=l node;hti.rchild=rnode;/ht为双亲结点(3) 利用哈夫

12、曼编码算法哈夫曼编码 voidCreateHCode(HTNodeht,HCodehcd,i ntn)in ti,f,c;HCodehc;for(i=0;i n;i+)根据哈弗曼树求哈弗曼编码hc.start=n ;c=i;f=hti.pare nt;while(f!=-1)循环知道树的根结点if(htf.lchild=c)hc.cdhc.start-=O;处理左孩子结点elsehc.cdhc.start-=1;处理右孩子结点c=f;f=htf.pare nt;hc.start+;/start指向哈弗曼编码最开始的位置hcdi=hc;5、界面设计6、系统测试测试数据及结果如下：对应的哈夫曼树如

13、图6.1 o图6.1构造哈夫曼树及哈夫曼编三、 小组成员分工说明码独立完成四、课程设计总结或结论1课程设计过程中出现的技术难点和解决方法：1.1技术难点。（1）输入的字符个数不确定，可跟据情况输入。（2）哈夫曼树的类型。（3）哈夫曼编码类型。（4）构造哈夫曼树算法。（5）计算哈夫曼编码算法。1.2解决方法。（1）通过向老师虚心学习请教（2）和同学们细心交流，认真讨论。（3）上网参考，吸取别人的精华。2课程设计期间的主要收获：通过这次课程设计使我充分的理解了用哈夫曼树再编码问题中基本 原理的应用，知道了树的不同存储结构的定义和算法描述，同时也学会 了编写简单的哈夫曼编码问题的程序。虽然此次的程序不是很完备，但 是总体还是一个比较能体现数据结构知识点的程序，当然只是相对于我 这个学者来说。在刚开始编程的时候，我感到很茫然，无从下手。但是 困难是可以解决的，只要通过努力，向老师虚心学习请教，