哈夫曼树的课程设计报告

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

2、个权值，建立哈夫曼树；4） 编码：利用建好的哈夫曼树生成哈夫曼编码；5） 输出编码；6） 设字符集及频度如下表：字符空格ABCDEFGHIJKLM频度1866413223210321154757153220字符NOPQRSTUVWXYZ频度5763151485180238181161二、设计正文1 系统分析（1）定义一个变量名为HTNode的结构体，用该结构体中的chardata、intweight、intparent、intlchild、intrchild分别表示哈夫曼树中每个结点的权值、权重、双亲结点、左孩子、右孩子，再定义一个HTNode类型的数组ht30存放哈夫曼树；另外定义一个变量名

3、为HCode的结构体，采用HCode类型变量的cdstart卜cdn存放当前结点的哈夫曼编码、最后定义一个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个结点的parent、lchild、rchild域均置初值为-1；再用一个for(i=n;<

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

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

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

7、的输出；再利用for(i=0;i<n;i+)循环和for(j=hcdi.start;j<=n;j+)循环来实现每个字符的序号和哈夫曼编码的输出。2 功能详细描述及框图(1)主函数流程图如图图主函数流程图图哈夫曼编码算法流程图(2)哈夫曼编码算法流程图，如图(3)构造树函数流程图，如图图构造树函数流程图3、数据结构设计3 1抽象数据类型定义（1）树的抽象数据类型定义4 2模块划分本程序包括三个模块：（ 1）主程序模块voidmain（）初始化；构造哈夫曼树；求哈夫曼编码；哈夫曼编码输出；（ 2）哈夫曼模块实现哈夫曼树的抽象数据类型（ 3）求哈夫曼编码模块实现求哈夫曼编码算法的数据类型

8、4、主要功能逻辑过程和实现算法41数据类型的定义（1）哈夫曼树类型typedefstructarent=hti.lchild=hti.rchild=-1;for（i=n;i<2*n-1;i+）arent=-1）eight<min1）min2=min1;rnode=lnode;min1=htk.weight;lnode=k;elseif(htk.weight<min2)min2=htk.weight;rnode=k;htlnode.parent=i;htrnode.parent=i;hti.weight=htlnode.weight+htrnode.weight;hti.lch

9、ild=lnode;hti.rchild=rnode;arent;while(f!=-1)child=c)='0'arent;+；r/：211Q5、喑夫曼Debu*哈夫曼.请前无要输X的字符裁量n：H请输入卜字符和n个权值bcdcFshi1322321B321154757所有字符的哈弗曼编后010B1BO1011111Q0Q0101101B8尸看0：61BB户三工二1001尸皆2：B11隹景3：辰序号4：1000序钻：阻骊庐叁61101序附.弼请掷请按T赳出请喻人一个字符或编配IB出 裘退 请请T 篇按 编兽。，.G八211。5g夫曼0加八哈夫I建物请摄请挖7；艮出klr请谕入

10、一个字符或编”rwj<5s any key tn contimie.雨饮;请输入一个字符或编码b3100编犯请茨译汩请技2请城送出;请植入一个字符或编码心本串里找不嘴藕»2请谕入一个字符或编码B02请谕入一个字符或编码MW1右(3)上网参考，吸取别人的精华。2课程设计期间的主要收获：通过这次课程设计使我充分的理解了用哈夫曼树再编码问题中基本原理的应用，知道了树的不同存储结构的定义和算法描述，同时也学会了编写简单的哈夫曼编码问题的程序。虽然此次的程序不是很完备，但是总体还是一个比较能体现数据结构知识点的程序，当然只是相对于我这个学者来说。在刚开始编程的时候，我感到很茫然，无从下手。但是困难是可以解决的，只要通过努力，向老师虚心学习请教，再难的题目也可以自己动手完成。通过这次的数据结构课程设计，我也深刻了解到