数据结构哈夫曼树的构造及其应用课程设计实验报告.doc

1、目 录第一章 哈夫曼树的基本术语111路径和路径长度11.2树的带权路径长度113哈夫曼树的定义1第二章 哈夫曼树的构造22.1哈夫曼树的构造2第三章 哈夫曼树的存储结构及哈夫曼算法的实现33.1哈夫曼树的存储结构33.2 哈夫曼算法的简要描述3第四章 哈夫曼树的应用54.1哈夫曼编码54.2求哈夫曼编码的算法54.21思想方法54.22字符集编码的存储结构及其算法描述64.3哈夫曼树和编码程序实现：64.4程序运行结果：9心得体会10参考文献1010 第一章 哈夫曼树的基本术语11路径和路径长度在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。通路中分支的数目称为路径长

2、度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。1.2结点的权及带权路径长度 若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。 1.2树的带权路径长度树的带权路径长度(Weighted Path Length of Tree)：也称为树的代价，定义为树中所有叶结点的带权路径长度之和，通常记为：其中：n表示叶子结点的数目wi和li分别表示叶结点ki的权值和根到结点ki之间的路径长度。13哈夫曼树的定义在权为wl，w2，wn的n个叶子所构成的所有二叉树中，带权路径长度最小(即代价最小)的

3、二叉树称为最优二叉树或哈夫曼树。例给定4个叶子结点a，b，c和d，分别带权7，5，2和4。构造如下图所示的三棵二叉树(还有许多棵)，它们的带权路径长度分别为：(a)WPL=7*2+5*2+2*2+4*2=36(b)WPL=7*3+5*3+2*1+4*2=4(c)WPL=7*1+5*2+2*3+4*3=35其中(c)树的WPL最小，可以验证，它就是哈夫曼树。 第二章 哈夫曼树的构造abcd2.1哈夫曼树的构造 (a)初始森林abcd 6 7 5 2 4 (b)c与d合并 abcdabcd 18 7 11 7 11 5 6 6 5 2 2 4 4 图1 哈夫曼树的构造过程 假设有n个权值，则构造出

4、的哈夫曼树有n个叶子结点。 n个权值分别设为 w1,w2,wn,则哈夫曼树的构造规则为：(1) 将w1,w2,wn看成是有n 棵树的森林(每棵树仅有一个结点)；(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；(3)从森林中删除选取的两棵树，并将新树加入森林；(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为我们所求得的哈夫曼树。下面给出哈夫曼树的构造过程，假设给定的叶子结点的权分别为1,5,7,3，则构造哈夫曼树过程如下图所示。从图中可知，n 个权值构造哈夫曼树需n-1次合并，每次合并，森林中的树数目减1，

5、最后森林中只剩下一棵树，即为我们求得的哈夫曼树。第三章 哈夫曼树的存储结构及哈夫曼算法的实现3.1哈夫曼树的存储结构用一个大小为2n-1的向量来存储哈夫曼树中的结点，其存储结构为：#define n 100 /叶子数目#define m 2*n-1/树中结点总数typedef struct /结点类型float weight; /权值，不妨设权值均大于零int lchild,rchild,parent; /左右孩子及双亲指针HTNode；typedef HTNode HuffmanTreem;/HuffmanTree是向量类型因为C语言数组的下界为0，故用-1表示空指针。树中某结点的lchil

6、d、rchild和parent不等于-1时，它们分别是该结点的左、右孩子和双亲结点在向量中的下标。这里设置parent域有两个作用：其一是使查找某结点的双亲变得简单；其二是可通过判定parent的值是否为-1来区分根与非根结点。3.2 哈夫曼算法的简要描述在上述存储结构上实现的哈夫曼算法可大致描述为(设T的类型为HuffmanTree)：(1)初始化将T0m-1中2n-1个结点里的三个指针均置为空(即置为-1)，权值置为0。(2)输人读人n个叶子的权值存于向量的前n个分量(即T0n-1)中。它们是初始森林中n个孤立的根结点上的权值。(3)合并对森林中的树共进行n-1次合并，所产生的新结点依次放

7、人向量T的第i个分量中(nim-1)。每次合并分两步：在当前森林T0i-1的所有结点中，选取权最小和次小的两个根结点p1和Tp2作为合并对象，这里0p1，p2i-1。 将根为Tp1和Tp2的两棵树作为左右子树合并为一棵新的树，新树的根是新结点Ti。具体操作：将Tp1和Tp2的parent置为i，将Ti的lchild和rchild分别置为p1和p2新结点Ti的权值置为Tp1和Tp2的权值之和。注意：合并后Tpl和Tp2在当前森林中已不再是根，因为它们的双亲指针均已指向了Ti，所以下一次合并时不会被选中为合并对象。第四章 哈夫曼树的应用4.1哈夫曼编码通信中，可以采用0,1的不同排列来表示不同的字

8、符，称为二进制编码。而哈夫曼树在数据编码中的应用，是数据的最小冗余编码问题，它是数据压缩学的基础。若每个字符出现的频率相同，则可以采用等长的二进制编码，若频率不同，则可以采用不等长的二进编码，频率较大的采用位数较少的编码，频率较小的字符采用位数较多的编码，这样可以使字符的整体编码长度最小，这就是最小编码的问题。 而哈夫曼编码就是一种不等长的二进制编码，且哈夫曼树是一种最优二叉树，它的编码也是一种最优编码，在哈夫曼树中，规定往左编码为0，往右编码为1，则得到叶子结点编码为从根结点到叶子结点中所有路径中0和1的顺序排列。例如，给定权1,5,7,3，得到的哈夫曼树及编码见图6-32 (假定权值就代表

9、该字符名字)。1666 1的哈夫曼编码 10097 5的哈夫曼编码 11 7的哈夫曼编码 04 3的哈夫曼编码 101531图6-31构造哈夫曼编码树4.2求哈夫曼编码的算法4.21思想方法给定字符集的哈夫曼树生成后，求哈夫曼编码的具体实现过程是：依次以叶子Ti(0in-1)为出发点，向上回溯至根为止。上溯时走左分支则生成代码0，走右分支则生成代码1。注意： 由于生成的编码与要求的编码反序，将生成的代码先从后往前依次存放在一个临时向量中，并设一个指针start指示编码在该向量中的起始位置（start初始时指示向量的结束位置）。 当某字符编码完成时，从start处将编码复制到该字符相应的位串cd

10、中即可。4.22字符集编码的存储结构及其算法描述typedef struct char cdN; /*存放哈夫曼码*/ int start; HCode;4.3哈夫曼树和编码程序实现：/ hfmTree.cpp : Defines the entry point for the console application./#include stdio.h#include #include #define N 4 /*叶子结点数*/#define M 2*N-1 /*树中结点总数*/typedef struct char data; /*结点值*/ int weight; /*权重*/ int p

11、arent; /*双亲结点*/ int lchild; /*左孩子结点*/ int rchild; /*右孩子结点*/ HTNode;typedef struct char cdN; /*存放哈夫曼码*/ int start; HCode;void CreateHT(HTNode ht,int n) int i,k,lnode,rnode; int min1,min2; for (i=0;i2*n-1;i+) /*所有结点的相关域置初值-1*/ hti.parent=hti.lchild=hti.rchild=-1; /n2*n-1节点的数据域置为*，权值为-1，主要是为显示用，不影响生成哈夫

12、曼树和编码 for (i=n;i2*n-1;i+) hti.data=*; hti.weight=-1; printf(构建哈夫曼树，存储结构的初始情况：n); printf(datatweighttparenttlchildtrchildn); for(i=0;i2*n-1;i+) printf(%ct%dt%dt%dt%dn,hti.data,hti.weight,hti.parent,hti.lchild,hti.rchild); printf(n);/显示结束 for (i=n;i2*n-1;i+) /*构造哈夫曼树*/ min1=min2=32767; /*lnode和rnode为最

13、小权重的两个结点位置*/ lnode=rnode=-1; for (k=0;k=i-1;k+) if (htk.parent=-1) /*只在尚未构造二叉树的结点中查找*/ if (htk.weightmin1) min2=min1;rnode=lnode; min1=htk.weight;lnode=k; else if (htk.weightmin2) min2=htk.weight;rnode=k; hti.data=*; htlnode.parent=i;htrnode.parent=i; hti.weight=htlnode.weight+htrnode.weight; hti.lc

14、hild=lnode;hti.rchild=rnode; void CreateHCode(HTNode ht,HCode hcd,int n) int i,f,c; HCode hc; for (i=0;in;i+) /*根据哈夫曼树求哈夫曼编码*/ hc.start=n-1;c=i; f=hti.parent; while (f!=-1) /*循序直到树根结点*/ if (htf.lchild=c) /*处理左孩子结点*/ hc.cdhc.start-=0; else /*处理右孩子结点*/ hc.cdhc.start-=1; c=f;f=htf.parent; hc.start+; /*

15、start指向哈夫曼编码最开始字符*/ hcdi=hc; void DispHCode(HTNode ht,HCode hcd,int n) int i,k; int sum=0,m=0,j; printf( 输出哈夫曼编码:n); /*输出哈夫曼编码*/ for (i=0;in;i+) j=0; printf( %c:t,hti.data); for (k=hcdi.start;kn;k+) printf(%c,hcdi.cdk); j+; m+=hti.weight; sum+=hti.weight*j; printf(n); printf(n 平均长度=%gn,1.0*sum/m);in

16、t main() int n=4,i; char str=a,b,c,d; int fnum=5,3,1,7; HTNode htM; HCode hcdN; for (i=0;in;i+) hti.data=stri; hti.weight=fnumi; CreateHT(ht,n); printf(datatweighttparenttlchildtrchildn); for(i=0;i2*n-1;i+)printf(%ct%dt%dt%dt%dn,hti.data,hti.weight,hti.parent,hti.lchild,hti.rchild); printf(n); CreateHCode(ht,hcd,n); DispHCode(ht,hcd,n); return 0;4.4程序运行结果：心得体会：通过这次的课程设计，让我对数据结构有了一个比较深刻的了解。课程设计非常锻炼人，每完成一个项目，不仅是知识体系的完善和知识的验证，更是编程技术的提升，当自己编的多了，就会开始摸索编程的捷径，想着用更高效的方法去完成一个个项目，就这样在一次次的锻炼中自己会慢慢的提高。参考文献1唐策善,李龙澍,黄刘生.数据结构-用C语言描述.高等教育出版社.19952孙家启等.C语言程序设计教程.合肥工业大学出版社.20113晋良颖等.数据结构.人民邮电出版社.2002