数据结构课程设计本课程设计已调试通过，请放心使用。请到：道客巴巴或豆丁网充值购买word版，省打字，直接修改即可，价格较便宜，在这里百度较贵！搜索：数据结构_哈夫曼树的构造及其应用_课程设计_实验报告
设计题目：哈夫曼树的构造及其应用
课题名称哈夫曼树的构造及其应用院系年级专业学号姓名成绩
课题设计目的与设计意义1、课题设计目的:(1)巩固构造哈夫曼树的算法。(2)设计算法实现哈夫曼树及哈夫曼编码的构造。2、课题设计意义：（1）通过设计此课程，让我对哈夫曼树有了更深的了解。（2）通过设计此课程，让我们对老师课上的讲述有了更深的理解，让所学有所思。（3）哈夫曼树的编译码具体应用在生活中，使我们明白了数据结构这一课程在实际生活中具有重要意义。指导教师：
年月日
目录第一章哈夫曼树的基本术语......................................................................................11．1路径和路径长度............................................................................................11.2树的带权路径长度...........................................................................................11．3哈夫曼树的定义............................................................................................1第二章哈夫曼树的构造..............................................................................................22.1哈夫曼树的构造...............................................................................................2第三章哈夫曼树的存储结构及哈夫曼算法的实现..................................................3
3.1哈夫曼树的存储结构.......................................................................................33.2哈夫曼算法的简要描述..................................................................................3第四章哈夫曼树的应用............................................................................................54.1哈夫曼编码.......................................................................................................54.2求哈夫曼编码的算法.......................................................................................54.21思想方法..................................................................................................54.22字符集编码的存储结构及其算法描述..................................................64.3哈夫曼树和编码程序实现：...........................................................................64.4程序运行结果：...............................................................................................9心得体会...............................................................................................................10
参考文献......................................................................................................................10
1
第一章哈夫曼树的基本术语1．1路径和路径长度在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。1.2结点的权及带权路径长度若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。1.2树的带权路径长度
树的带权路径长度(WeightedPathLengthofTree)：也称为树的代价，定义为树中所有叶结点的带权路径长度之和，通常记为：其中：n表示叶子结点的数目wi和li分别表示叶结点ki的权值和根到结点ki之间的路径长度。1．3哈夫曼树的定义在权为w
l，w2，…，wn的n个叶子所构成的所有二叉树中，带权路径长度最小(即代价最小)的二叉树称为最优二叉树或哈夫曼树。[例]给定4个叶子结点a，b，c和d，分别带权7，5，2和4。构造如下图所示的三棵二叉树(还有许多棵)，它们的带权路径长度分别为：(a)WPL=72+52+22+42=36(b)WPL=73+53+21+42=4(c)WPL=71+52+23+43=35其中(c)树的WPL最小，可以验证，它就是哈夫曼树。
2
第二章哈夫曼树的构造2.1哈夫曼树的构造(a)初始森林67524
(b)c与d合并1871171156652244
图1哈夫曼树的构造过程假设有n个权值，则构造出的哈夫曼树有n个叶子结点。n个权值分别设为w1,w2,…,wn,则哈夫曼树的构造规则为：(1)将w1,w2,…,wn看成是有n棵树的森林(每棵树仅有一个结点)；(2)在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；(3)从森林中删除选取的两棵树，并将新树加入森林；(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为我们所求得的哈夫曼树。下面给出哈夫曼树的构造过程，假设给定的叶子结点的权分别为1,5,7,3，则构造哈夫曼树过程如下图所示。从图中可知，n个权值构造哈夫曼树需n-1
次合并，每次合并，森林中的树数目减1，最后森林中只剩下一棵树，即为我们求得的哈夫曼树。
abcdabcd
abcdabcd
3
第三章哈夫曼树的存储结构及哈夫曼算法的实现3.1哈夫曼树的存储结构用一个大小为2n-1的向量来存储哈夫曼树中的结点，其存储结构为：#definen100//叶子数目#definem2n-1//树中结点总数typedefstruct{//结点类型floatweight;//权值，不妨设权值均大于零intlchild,rchild,parent;//左右孩子及双亲指针
}HTNode；typedefHTNodeHuffmanTree[m];//HuffmanTree是向量类型因为C语言数组的下界为0，故用-1表示空指针。树中某结点的lchild、rchild和parent不等于-1时，它们分别是该结点的左、右孩子和双亲结点在向量中的下标。这里设置parent域有两个作用：其一是使查找某结点的双亲变得简单；其二是可通过判定parent的值是否为-1来区分根与非根结点。3.2哈夫曼算法的简要描述在上述存储结构上实现的哈夫曼算法可大致描述为(设T的类型为HuffmanTree)：(1)初始化
将T[0．．m-1]中2n-1个结点里的三个指针均置为空(即置为-1)，权值置为0。(2)输人读人n个叶子的权值存于向量的前n个分量(即T[0．．n-1])中。它们是初始森林中n个孤立的根结点上的权值。(3)合并对森林中的树共进行n-1次合并，所产生的新结点依次放人向量T的第i个分量中(n≤i≤m-1)。每次合并分两步：①在当前森林T[0．．i-1]的所有结点中，选取权最小和次小的两个根结点[p1]和T[p2]作为合并对象，这里0≤p1，p2≤i-1。②将根为T[p1]和T[p2]的两棵树作为左右子树合并为一棵新的树，新树的根是新结点T[i]。具体操作：
4
将T[p1]和T[p2]的parent置为i，将T[i]的lchild和rchild分别置为p1和p2新结点T[i]的权值置为T[p1]和T[p2]的权值之和。注意：合并后T[pl]和T[p2]在当前森林中已不再是根，因为它们的双亲指针均已指向了T[i]，所以下一次合并时不会被选中为合并对象。
5
第四章哈夫曼树的应用4.1哈夫曼编码通信中，可以采用0,1的不同排列来表示不同的字符，称为二进制编码。而哈夫曼树在数据编码中的应用，是数据的最小冗余编码问题，它是数据压缩学的基础。若每个字符出现的频率相同，则可以采用等长的二进制编码，若频率不同，则可以采用不等长的二进编码，频率较大的采用位数较少的编码，频率较小的字符采用位数较多的编码，这样可以使字符的整体编码长度最小，这就是最小编码的问题。而哈夫曼编码就是一种不等长的二进制编码，且哈夫曼树是一种最优二叉树，它的编码也是一种最优编码，在哈夫曼树中，规定往左编码为0，
往右编码为1，则得到叶子结点编码为从根结点到叶子结点中所有路径中0和1的顺序排列。例如，给定权{1,5,7,3}，得到的哈夫曼树及编码见图6-32(假定权值就代表该字符名字)。1的哈夫曼编码1005的哈夫曼编码117的哈夫曼编码03的哈夫曼编码101
图6-31构造哈夫曼编码树4.2求哈夫曼编码的算法4.21思想方法给定字符集的哈夫曼树生成后，求哈夫曼编码的具体实现过程是：依次以叶子T[i](0≤i≤n-1)为出发点，向上回溯至根为止。上溯时走左分支则生成代码0，走右分支则生成代码1。注意：16794513
6
①由于生成的编码与要求的编码反序，将生成的代码先从后往前依次存放在一个临时向量中，并设一个指针start指示编码在该向量中的起始位置（start初始时指示向量的结束位置）。②当某字符编码完成时，从start处将编码复制到该字符相应的位串cd中即可。4.22字符集编码的存储结构及其算法描述typedefstruct{charcd[N];/存放哈夫曼码/intstart;}HCode;4.3哈夫曼树和编码程序实现：
//hfmTree.cpp:Definestheentrypointfortheconsoleapplication.//#include"stdio.h"#include#include#defineN4/叶子结点数/#defineM2N-1/树中结点总数/typedefstruct{chardata;/结点值/intweight;/权重/
intparent;/双亲结点/intlchild;/左孩子结点/intrchild;/右孩子结点/}HTNode;typedefstruct{charcd[N];/存放哈夫曼码/intstart;}HCode;voidCreateHT(HTNodeht[],intn){inti,k,lnode,rnode;
7
intmin1,min2;for(i=0;i<2n-1;i++)/所有结点的相关域置初值-1/{ht[i].parent=ht[i].lchild=ht[i].rchild=-1;}//n——2n-1节点的数据域置为，权值为-1，主要是为显示用，不影响生成哈夫曼树和编码for(i=n;i<2n-1;i++){ht[i].data='''';ht[i].weight=-1;
}printf("构建哈夫曼树，存储结构的初始情况：\n");printf("data\tweight\tparent\tlchild\trchild\n");for(i=0;i<2n-1;i++)printf("%c\t%d\t%d\t%d\t%d\n",ht[i].data,ht[i].weight,ht[i].parent,ht[i].lchild,ht[i].rchild);printf("\n");//显示结束for(i=n;i<2n-1;i++)/构造哈夫曼树/{min1=min2=32767;/lnode和rnode为最小权重的两个结点位置/
lnode=rnode=-1;for(k=0;k<=i-1;k++)if(ht[k].parent==-1)/只在尚未构造二叉树的结点中查找/{if(ht[k].weight
}}ht[i].data='''';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;
8
}}voidCreateHCode(HTNodeht[],HCodehcd[],intn){inti,f,c;HCodehc;for(i=0;i
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;}}voidDispHCode(HTNodeht[],HCodehcd[],intn){
inti,k;intsum=0,m=0,j;printf("输出哈夫曼编码:\n");/输出哈夫曼编码/for(i=0;i
m+=ht[i].weight;sum+=ht[i].weightj;printf("\n");}printf("\n平均长度=%g\n",1.0sum/m);}
9
intmain(){intn=4,i;charstr[]={''a'',''b'',''c'',''d''};intfnum[]={5,3,1,7};HTNodeht[M];HCodehcd[N];for(i=0;i
CreateHT(ht,n);printf("data\tweight\tparent\tlchild\trchild\n");for(i=0;i<2n-1;i++)printf("%c\t%d\t%d\t%d\t%d\n",ht[i].data,ht[i].weight,ht[i].parent,ht[i].lchild,ht[i].rchild);printf("\n");CreateHCode(ht,hcd,n);DispHCode(ht,hcd,n);return0;}4.4程序运行结果：
10
心得体会：通过这次的课程设计，让我对数据结构有了一个比较深刻的了解。课程设计非常锻炼人，每完成一个项目，不仅是知识体系的完善和知识的验证，更是编程技术的提升，当自己编的多了，就会开始摸索编程的捷径，想着用更高效的方法去完成一个个项目，就这样在一次次的锻炼中自己会慢慢的提高。参考文献[1]唐策善,李龙澍,黄刘生.数据结构-用C语言描述.高等教育出版社.1995[2]孙家启等.C语言程序设计教程.合肥工业大学出版社.2011[3]晋良颖等.数据结构.人民邮电出版社.2002
|
|
