哈夫曼树的课程设计报告.docx
《哈夫曼树的课程设计报告.docx》由会员分享，可在线阅读，更多相关《哈夫曼树的课程设计报告.docx（12页珍藏版）》请在冰点文库上搜索。
哈夫曼树的课程设计报告
数据结构与算法
课程设计报告书
题目：
哈夫曼编码/译码器
班级：
11091211
学号：
1109121105
姓名：
田欢
指导教师：
龚丹
周期：
2011-12-19至2011-12-23
成绩：
年月日
一、课程设计的目的与要求
（一）课程设计目的与任务（参考已发文档自行编辑，但不少于100字）
设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。
利用哈夫曼树编码问题基本原理的应用，撑握对树的不同存储结构的定义和算法描述。
学会构造哈夫曼树和哈夫曼编码等主要算法。
（二）题目要求
1） 将权值数据存放在数据文件（文件名为data.txt，位于执行程序的当前目录中）
2） 分别采用动态和静态存储结构
3） 初始化：
键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；
4） 编码：
利用建好的哈夫曼树生成哈夫曼编码；
5） 输出编码；
6） 设字符集及频度如下表：
字符空格ABCDEFGHIJKLM
频度1866413223210321154757153220
字符NOPQRSTUVWXYZ
频度5763151485180238181161
二、设计正文
1系统分析
（1）定义一个变量名为HTNode的结构体，用该结构体中的chardata、intweight、intparent、intlchild、intrchild分别表示哈夫曼树中每个结点的权值、权重、双亲结点、左孩子、右孩子，再定义一个HTNode类型的数组ht[30]存放哈夫曼树；另外定义一个变量名为HCode的结构体，采用HCode类型变量的cd[start]~cd[n]存放当前结点的哈夫曼编码、最后定义一个HCode类型的数组hcd[30]的数组用于存放当前叶子结点ht[i]的哈夫曼编码。
（2）编写CodeInput（n,ht）函数并在函数中设置一个for（i=0;n;++）循环，首先输入n个字符，再利用函数中的for（i=0;（3）编写CreateHT（ht,n）函数来构造一棵哈夫曼树，首先用一个for（i=0;<2*n-1;++）循环将所有2n-1个结点的parent、lchild、rchild域均置初值为-1；再用一个for（i=n;<2*n-1;++）循环来构造哈夫曼树，在该循环中首先令lnode和rnode为最小权值的两个结点位置且其域值均为-1，再用一个for（k=0;<=i-1;k++）循环在数组ht[30]中寻找权值最小的两个结点并且只能在尚未构造二叉树的结点中查找，由于只能在尚未构造二叉树的结点中查找，因此在for（k=0;k<=i-1;k++）循环中加入一个if（ht[k].parent==-1）语句来判断结点lnode和rnode是否已经在二叉树中，如果结点lnode和rnode在二叉树中，则结点lnode和rnode的parent的值为其双亲结点在数组ht[30]中的序号就不会为-1了，在查找到ht[lnode]和ht[rnode]后将他们作为ht[i]的左右子树，ht[lnode]和ht[rnode]的双亲结点置为ht[i]，且ht[i].weight=ht[lnode].weight+ht[rnode].weight。
如此处理下去，直到所2n-1个结点处理完毕。
（4）编写CreateHCode（ht,hcd,n）函数来求哈夫曼编码，由于求哈夫曼编码只需求叶子结点的哈夫曼编码。
对于当前叶子结点ht[i]，首先将对应的哈夫曼编码hcd[i]的start域值置初值n，找其双亲结点ht[f]，若当前结点是双亲结点的左孩子结点，则在hcd[i]的cd数组中添加0，若当前结点是双亲的右孩子结点，则在hcd[i]的cd数组中添加1，将start域减1。
再对双亲结点进行同样的操作，直到无双亲结点为止，最后让start指向哈夫曼编码最开始字符。
因此在函数中设置一个for（i=0;i=-1）循环语句来判断循环是否到了根结点，再在while（f!
=-1）中设置一个if（ht[f].lchild==c）语句来判断该处理左孩子结点还是该处理右孩子结点。
最后用这个for（i=0;i（5）最后编写CodeOutput（n,hcd）函数，首先利用for（i=0;i2功能详细描述及框图
（1）主函数流程图如图2.1
（2）哈夫曼编码算法流程图，如图2.2
（3）构造树函数流程图，如图2.3
3、数据结构设计
3．1抽象数据类型定义
（1）树的抽象数据类型定义
3．2模块划分
本程序包括三个模块：
（1）主程序模块
voidmain（）
{
初始化；
构造哈夫曼树；
求哈夫曼编码；
哈夫曼编码输出；
}
（2）哈夫曼模块——实现哈夫曼树的抽象数据类型
（3）求哈夫曼编码模块——实现求哈夫曼编码算法的数据类型
4、主要功能逻辑过程和实现算法
4．1数据类型的定义
（1）哈夫曼树类型
typedefstruct{//构造树
chardata;//结点权值
intweight;//权重
intparent;//双亲结点
intlchild;//左孩子
intrchild;//右孩子
}HTNode;
HTNodeht[30];
（2）求哈夫曼编码类型
typedefstruct{
charcd[30];//存放当前结点的哈弗曼编码
intstart;//cd[start]~cd[n]存放哈弗曼码
}HCode;
HCodehcd[30];
4．2主要模块的算法描述
（1）主函数
intmain（）
{
intn;
printf（"请输入要输入的字符数量n:
"）;//读入字符的个数
while（scanf（"%d",&n）,n!
=-1）{//初始化
printf（"请输入n个字符和n个权值\n"）;
CodeInput（n,ht）;//输入数据函数，将读入n个字符和权重
CreateHT（ht,n）;//构造哈弗曼树
CreateHCode（ht,hcd,n）;//哈弗曼编码算法
CodeOutput（n,hcd）;}//打印哈弗曼编码将打印出编码，和每一个字符的编码
return0;
（2）构造哈夫曼树
voidCreateHT（HTNodeht[],intn）//构造一棵哈夫曼树
{
inti,k,lnode,rnode;
intmin1,min2;
for（i=0;i<2*n-1;i++）//所有结点的相关域置初值-1
ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
for（i=n;i<2*n-1;i++）//构造哈弗曼树
{
min1=min2=32767;//lnode和rnode为最小权值的两个结点位置
lnode=rnode=-1;
for（k=0;k<=i-1;k++）//在ht[]中查找权值的最小的两个结点
if（ht[k].parent==-1）//只在未构造的二叉树结点中查找
{
if（ht[k].weight{
min2=min1;rnode=lnode;
min1=ht[k].weight;lnode=k;
}
elseif（ht[k].weight{
min2=ht[k].weight;rnode=k;}
}
ht[lnode].parent=i;ht[rnode].parent=i;
ht[i].weight=ht[lnode].weight+ht[rnode].weight;
ht[i].lchild=lnode;ht[i].rchild=rnode;//ht[]为双亲结点
}
}
（3）利用哈夫曼编码算法哈夫曼编码
voidCreateHCode（HTNodeht[],HCodehcd[],intn）
{
inti,f,c;
HCodehc;
for（i=0;i{
hc.start=n;c=i;
f=ht[i].parent;
while（f!
=-1）//循环知道树的根结点
{
if（ht[f].lchild==c）
hc.cd[hc.start--]='0';//处理左孩子结点
else
hc.cd[hc.start--]='1';//处理右孩子结点
c=f;f=ht[f].parent;
}
hc.start++;//start指向哈弗曼编码最开始的位置
hcd[i]=hc;
}
}
5、界面设计
6、系统测试
测试数据及结果如下：
结果分析：
首先确定要输入的字符数量n为8，然后分别输入这8个字符和这8个字符的权值，且输入的这8个字符分别为B、C、D、E、F、G、H、I而这8个字符对应的权值分别为13、22、32、103、21、15、47、57。
其次根据输出的结果可知：
所有字符的哈夫曼为0010110010001111110000011。
其中序号0表示字符B，其哈夫曼编码为0010；序号1表示字符C，其哈夫曼编码为110；序号2表示字符D，其哈夫曼编码为010；序号3表示字符E，其哈夫曼编码为0011；序号4表示字符F，其哈夫曼编码为111；序号5表示字符G，其哈夫曼编码为10；序号6表示字符H，其哈夫曼编码为000；序号7表字符I，其哈夫曼编码为011，这个8个字符对应的哈夫曼树如图6.1。
0
4F
1C
6H
3E
1
0
1
0
1
0
1
0
7I
2D
0
1
1
0B
5G
0
1
图6.1构造哈夫曼树及哈夫曼编码
三、小组成员分工说明
独立完成
四、课程设计总结或结论
1课程设计过程中出现的技术难点和解决方法：
1.1技术难点。
（1）输入的字符个数不确定，可跟据情况输入。
（2）哈夫曼树的类型。
（3）哈夫曼编码类型。
（4）构造哈夫曼树算法。
（5）计算哈夫曼编码算法。
1.2解决方法。
（1）通过向老师虚心学习请教.
（2）和同学们细心交流，认真讨论。
（3）上网参考，吸取别人的精华。
2课程设计期间的主要收获：
通过这次课程设计使我充分的理解了用哈夫曼树再编码问题中基本原理的应用，知道了树的不同存储结构的定义和算法描述，同时也学会了编写简单的哈夫曼编码问题的程序。
虽然此次的程序不是很完备，但是总体还是一个比较能体现数据结构知识点的程序，当然只是相对于我这个学者来说。
在刚开始编程的时候，我感到很茫然，无从下手。
但是困难是可以解决的，只要通过努力，向老师虚心学习请教，再难的题目也可以自己动手完成。
通过这次的数据结构课程设计，我也深刻了解到这门学问的博大精深，要积极进取，不断学习，不断积累知识。
同时也认识到自己的不足和缺点，做什么事都需要细心和耐心，并坚持下去，这样才有一个比较满意的成果。
在此我非常感谢的是我的指导老师，感谢老师的细心认真的辅导，让我对数据结构这门课程有了更深刻的认识，同时我还要感谢帮助过我的同学，没有他们的帮助我不肯能完成这样顺利，谢谢！
升级会员 