数据结构课设-赫夫曼树讲解

1、塔里木大学信息工程学院课程设计目录 前言1正文21课程设计目的及意义21.1课程设计目的21.2课程设计的意义22设计方案论证22.1 问题描述22.1.1赫夫曼树的基本概念22.1.2赫夫曼树的应用32.1.3哈夫曼树在数据编码中的应用42.2 数据结构设计52.3.1功能模块图62.3.2功能模块图思路设计72.4 详细设计82.4.2 算法设计102.5设计程序133 课程设计运行结果与分析16设计总结17参考文献18 前言数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系的操作的学科。它是介于数学、计算机硬件之间的一门计算机专业的核心课程，是计算机

2、程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高我们的思维能力，促进我们综合应用能力和专业素质的提高。随着计算机的普遍应用与日益发展，其应用早已不局限于简单的数值运算，而涉及到问题的分析、数据结构框架的设计以及设计最短路线等复杂的非数值处理和操作。 算法与数据结构的学习就是为以后利用计算机资源高效地开发非数值处理的计算机程序打下坚实的理论、方法和技术基础。算法与数据结构旨在分析研究计算机加工的数据对象的特性，以便选择适当的数据结构和存储结构，从而

3、使建立在其上的解决问题的算法达到最优。数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。 数据结构主要介绍一些最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程

4、，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学习数据结构是为了将实际问题中所涉及的对象在计算机中 此次课程设计通过对赫夫曼树的概念、构造算法的理解，进行建立赫夫曼树从而掌握赫夫曼树，同时了解赫夫曼树在解决实际问题中的重要地位。本文采用了数组和结构体结合的存储方式，通过对二叉树结点以及带权路径长度等的学习和探究，通过建立最优二叉树函数，实现了赫夫曼树的建立和输出的功能。正文1课程设计目的及意义 1.1课程设计目的 (1)掌握算法的编写方法。(2)掌握C语言的算法转换成C程序并上机调试的基本方法。(3)根据建立好的函数输入二叉树，

5、对其输入的字符出现的频率作为权值输出其相对应的赫夫曼树。 1.2课程设计的意义通过熟练使用c+语言编写程序，解决实际问题；了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；练习树和赫夫曼树的有关操作，和各个算法程序，理解赫夫曼树的构造与应用，熟悉赫夫曼树的基本操作，掌握赫夫曼树的实现以及实际应用。 2设计方案论证2.1 问题描述2.1.1赫夫曼树的基本概念相关概念：路径：从树中一个结点到另一个结点所经过的分支序列或者说结点序列。路径长度：路径上面的

6、分支个数。树的路径长度：从树根到每一个结点的路径长度之和。结点的权值：在某些应用中，树中结点往往要和一定的数值联系起来，那么这个数值通常称为该结点的权值，简称权。结点的带权路径长度：该结点到根结点的路径长度与该结点上权的乘积。树的带权路径长度：树中所有叶子结点的带权路径长度之和。最优二叉树（哈夫曼树）：给定n个权值w1,w2,wn，试构造一棵有n个叶子结点的二叉树，每个叶子结点带权为wi。构造出来的二叉树的形态可以有多个，我们把其中带权路径长度WPL最小的二叉树称作最优二叉树或者哈夫曼树。按照结构体来存放树的结点的权值，双亲、左孩子、右孩子。通过建立赫夫曼树函数输入二叉树，并输出其赫夫曼树各节

7、点编码。哈夫曼算法的语言描述根据给定的n个权值w1,w2,wn构成n棵二叉树的集合F=T1,T2,Tn,其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树为空。在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。在F中删除这两棵树，同时将新得到的二叉树加入F中。重复和，直到F只含一棵树为止。这棵树便是哈夫曼树。2.1.2赫夫曼树的应用哈夫曼树的应用十分广泛，在不同的应用中，对叶子结点的权和带权路径长度有不同的解释。哈夫曼树的应用之一是用于优化判断过程，利用哈夫曼树得到最佳判定算法。例如，将百分制转换成五级制的算法

8、。显然，此算法很简单，只需利用if语句描述即可。if ( x60)score=不及格;else if ( x70) score=及格;else if ( x80)score=中;else if ( x90)score=良;elsescore=优;如果学生规模很大，该算法需反复多次执行，就应该考虑算法执行的时间问题。在实际应用中，学生的成绩呈正态分布，大部分在7089分之间，优秀和不及格的概率较小。假设不及格、及格、中、良、优的百分比为5、12%、40%、35%、8%，则上述算法80%以上的成绩需要进行三次或三次以上的比较才能得到结果。若以这些百分比值5,12,40,35,8为权值，使用哈夫曼算

9、法来构造一棵判定树，则得到判定过程，可使多数成绩经过较少的比较即可得到结果。但由于每个判定框都有两次比较，将两次比较分开，得到判定树，按此判定树构造程序，显然可以大大减少比较次数。2.1.3哈夫曼树在数据编码中的应用在数据通信中，需要将传送的文字转换成二进制的字符串，用0，1码的不同排列来表示字符。例如，需传送的报文为“AFTER DATA EAR ARE ART AREA”，这里用到的字符集为“A，E，R，T，F，D”，各字母出现的次数为8，4，5，3，1，1。现要求为这些字母设计编码。要区别6个字母，最简单的二进制编码方式是等长编码，固定采用3位二进制，可分别用000、001、010、01

10、1、100、101对“A，E，R，T，F，D”进行编码发送，当对方接收报文时再按照三位一分进行译码。显然编码的长度取决报文中不同字符的个数。若报文中可能出现26个不同字符，则固定编码长度为5。然而，传送报文时总是希望总长度尽可能短。在实际应用中，各个字符的出现频度或使用次数是不相同的，如A、B、C的使用频率远远高于X、Y、Z，自然会想到设计编码时，让使用频率高的用短码，使用频率低的用长码，以优化整个报文编码。但这样长短不等的编码又会产生一个新问题，即如何解译成原文？除非设计时能够保证任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀，符合此要求的编码称为前缀编码。为使不等长编码为前缀编

11、码，可用字符集中的每个字符作为叶子结点生成一棵编码二叉树，为了获得传送报文的最短长度，可将每个字符的出现频率作为字符结点的权值赋予该结点上，求出此树的最小带权路径长度就等于求出了传送报文的最短长度。因此，求传送报文的最短长度问题转化为求由字符集中的所有字符作为叶子结点，由字符出现频率作为其权值所产生的哈夫曼树的问题。利用哈夫曼树来设计二进制的前缀编码，既满足前缀编码的条件，又保证报文编码总长最短。我们用上述各字母出现的次数8，4，5，3，1，1作为权构造哈夫曼树，如图6.36所示。约定左分支表示字符“0”，右分支表示字符“1”，则可以从根结点到叶子结点的路径的分支上的字符组成的字符串作为该叶子

12、对应字符的编码。可以证明，如此得到的必为二进制前缀编码，而且是一种最优前缀编码。我们称这样的树为哈夫曼编码树，由此得到的编码称为哈夫曼编码。本例中字母A、E、R、T、F、D的哈夫曼编码分别为11、00、01、011、0100、0101。可以看出，出现次数较多的字母A、E、R，具有最短的编码，长度均为2；而出现次数最少的字母F、D，具有最长的编码，长度均为4。报文的最短传送长度为：6 L=WPL=S(wklk)=42+52+82+33+14+14=51 k=1若采用等长编码，报文的传送长度为 L=83+43+53+33+13+13=66显然，哈夫曼编码比等长编码所得到的报文长度要短得多。哈夫曼编

13、码是最优前缀编码。一个任意长度的编码序列可被唯一地翻译为一个字符序列（单词）。依次取出编码序列中的0或1，从哈夫曼编码树的根结点开始寻找一条路径。若为0，则沿着左分支向下走；若为1，则沿着右分支向下走。每到达一个叶子外结点时，就译出一个相应的字符，然后再回到哈夫曼树的根结点处，依次译出余下的字符，最后得到一个单词。2.2 数据结构设计 通过建立一个赫夫曼树的简易程序，可以实现建立最优二叉树函数，并且可以建立函数输入二叉树，并输出其赫夫曼树。此程序是线性链表式存储结构，这种存储结构便于数据的插入和删除，同时还节约存储空间。各种编码方式(1)定长编码根据出现的字符种数进行编码(2)变长编码采取这种

14、变长编码方式，需要遵循一个原则，即每一个字符的编码都不应该是另一个字符编码的前缀。否则就会出现二义性。一个可用的编码必须满足每个字符的编码不能是其他编码的前缀。也可以看出，每一个可用的编码都可以转化成二叉树的形式，这样编码理论便可以与二叉树的一些性质结合起来，就可以应用二叉树的理论知识来解决编码问题。那么总的编码长度为：WPL=w1*L1+w2*L2+w3*L3+w4*L4可以看出，该公式与哈夫曼树满足的公式一模一样，那么我们可以采取构造哈夫曼树的方式来求编码的长度。对哈夫曼树进行编码，每一个结点的左分支上面标0，右分支上面标1,从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点

15、所代表字符的编码。假设有n个权值w1，w2，wn，每个权值赋给一个叶子，可以构造出多棵含n个叶子结点的二叉树。其中，必存在一棵其带权路径长度WPL取最小值的二叉树，称为最优二叉树。因为构造这种树的算法最早是哈夫曼1952年提出来的，所以被称为哈夫曼树(Huffman Tree)。如何构造哈夫曼树？D.A.Huffman 最早研究出一个带有一般规律的构造算法，俗称哈夫曼算法，其基本思想是让权值最大的叶子离根最近。构造方法如下：(1) 由给定的n个权值w1, w2, , wn，构造n棵扩充二叉树的集合F = T1, T2, , Tn，其中每棵扩充二叉树中均只含一个带权值wi的根结点,其左、右子树均

16、为空；(2) 重复下列步骤，直到F中只含一棵树为止：j 在F中选取其根结点的权值为最小的两棵扩充二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;k 从F中删去这两棵树，同时加入刚生成的新树；(3) 按上述步骤得到的二叉树就是哈夫曼树。2.3 设计思路及算法设计 2.3.1功能模块图 赫夫曼树的建立查找最小的两个权统计字符出现的频率构造赫夫曼树并输出图1功能模块图2.3.2功能模块图思路设计设需要编码的字符集合为d1,d2,dn,各个字符在电文中出现的次数集合为w1,w2,wn，以d1,d2,dn作为叶结点，以w1,w2,wn作为各叶结

17、点的权值构造一棵二叉树，规定赫夫曼树中的左分支为0，右分支为1，则从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码。这样的代码总长度最短的不等长编码称为赫夫曼编码。赫夫曼算法：根据给定的n个权值w1，w2，w3，wn构成n棵二叉树的集合F=T1，T2，T3，Tn，其中每棵二叉树Ti中只有一个带权为Wi的根结点，其左右树均空。在F中选取两棵根结点的 权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为期左、右子树上根结点的权值之和。在F中删除这棵树，同时将新得到的二叉树加入F中。重复(2)和(3)的过程，直到F只含一棵树为止。这棵树便是哈夫曼树

18、。设给定的权值集合为5，4，7，2，构造哈夫曼树的过程如图6.34 所示。首先构造每棵树只有一个结点的森林，如图2(a)所示；然后每次选择两个根结点权值最小的二叉树，以它们为左、右子树构造新的二叉树，步骤参看图2(b)，(c)和(d)，最后得到一棵扩充二叉树 图2 哈夫曼树的构造过程2.4 详细设计2.4.1 程序流程图 开 始创建一个空的赫夫曼树判断PHt是否为空输入m判断m是否比1大找两个最小权的无父结点的结点构造新的二叉树得到新的结点NYY输入外部结点个数及权值所有结点生成树得到赫夫曼树编码输出结束N图3 流程图2.4.2 算法设计(1)建立最优二叉树函数由于赫夫曼树种没有度为的结点（这

19、类又称严格的（strict）(或正则的)二叉树），则一颗有n个叶子结点的赫夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中。如何选定结点结构？由于在构成赫夫曼树之后，为求编码需要从叶子结点出发走一条从叶子到根的路径；而为译码需要从根出发走一条从根到叶子的路径。则对每个节点而言，既需知双亲的信息，又需知孩子结点的信息。由此：二叉树的存储结构：#define MAXINT 2147483647 #define MAXNUM 50 /* 数组w中最多容纳的元素个数，注意 m=MAXNUM */ #define MAXNODE 100 /* 哈夫曼树中的最大结点数，注意 2*m-1M

20、AXNODE */ struct HtNode /* 哈夫曼树结点的结构 */ int ww; int parent,llink,rlink; ; (2)赫夫曼树的构造算法根据给定的n个权值w1，w2，w3，wn构成n棵二叉树的集合F=T1，T2，T3，Tn，其中每棵二叉树Ti中只有一个带权为Wi的根结点，其左右树均空。在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。在F中删除这棵树，同时将新得到的二叉树加入F中。重复操作直到所有结点生成树。PHtTree huffman(int m, int *w) PHtTre

21、e pht; int i, j, x1, x2, m1, m2; pht = (PHtTree)malloc(sizeof(struct HtTree); /* 创建空哈夫曼树 */ if (pht = NULL) printf(Out of space! n); return pht; for (i = 0; i hti.llink = -1; pht-hti.rlink = -1; pht-hti.parent = -1; if (i hti.ww = wi; else pht-hti.ww = -1; for ( i = 0; i m-1; i+) /* 每循环一次构造一个内部结点 */

22、 m1 = MAXINT; m2 = MAXINT;/* 相关变量赋初值 */ x1 = -1; x2 = -1; for (j= 0; j htj.ww htj.parent = -1) m2 = m1; x2 = x1; m1= pht-htj.ww; x1 = j; else if (pht-htj.ww htj.parent = -1) m2 = pht-htj.ww; x2 = j; pht-htx1.parent = m+i; /* 构造一个内部结点 */ pht-htx2.parent = m+i; pht-htm+i.ww = m1+m2; pht-htm+i.llink =

23、x1; pht-htm+i.rlink = x2; pht-root = m+i; return pht; (3)字符的赫夫曼编码的算法向量HT的前n个分量表示叶子结点，最后一个分量表示根结点。各字符的编码长度不等，所以按实际长度分配空间。求每个字符的赫夫曼编码是从叶子到根的逆向处理。也可以从根出发遍历整棵赫夫曼树，求得各叶子结点所表示的字符的赫夫曼编码。算法如下：int main() int m = 0, j = 0, i = 0, parent = 0; int* w; PHtTree pht; printf(please input m = );/*输入外部结点个数*/ scanf(%d

24、, &m); if (m 1) printf(m is not reasonable!n); return 1; w = (int *)malloc(sizeof(int)*m); if (w = NULL) printf(overflow!n); return 1; printf(please input the %d numbers：n,m);/*输入权值*/ for (j= 0; j m; j+) scanf(%d, w+j); pht = huffman(m, w); for (j = 0; j hti.parent != -1) parent = pht-hti.parent; if

25、 (pht-htparent.llink = i) printf(0); else printf(1); i = parent; printf(n); return 0; (4)查找权值最小的两个结点的函数选择二叉树的根结点，使达最小构造次优二叉树的算法，首先标价所有结点，依次编号，判断结点的权值的大小，将所判断的结点赋值给一个变量，然运用比较算法，选择权值较小的一个结点，赋值给的变量不变，另一个变量释放其所赋的值。应用循环语句进行新的赋值，继续比较，直到所有结点比较完毕。s1 、s2所有值就是全职最小的两个结点。依此算法比较完全部的结点由此构成一颗赫夫曼树。算法如下:void Select(

26、HuffmanTree HT, int n, int &s1, int &s2)unsigned int weight;int i;s1=0; s2=0; weight=100;for(i=1;iweight)continue;else weight=HTi.weight; s1=i;HTs1.parent=s1;/暂时改写HTs1.parent的值 weight=100;for(i=1;iweight) continue; else weight=HTi.weight; s2=i;2.5设计程序#include #include #define MAXINT 2147483647#defin

27、e MAXNUM 50#define MAXNODE 100struct HtNode int ww; int parent,llink,rlink; ; struct HtTree int root; struct HtNode htMAXNODE; ; typedef struct HtTree *PHtTree; PHtTree huffman(int m, int *w) PHtTree pht; int i, j, x1, x2, m1, m2; pht = (PHtTree)malloc(sizeof(struct HtTree); if (pht = NULL) printf(O

28、ut of space! n); return pht; for (i = 0; i hti.llink = -1; pht-hti.rlink = -1; pht-hti.parent = -1; if (i hti.ww = wi; else pht-hti.ww = -1; for ( i = 0; i m-1; i+) m1 =MAXINT; m2 =MAXINT; x1 =-1; x2 =-1; for (j = 0; jhtj.ww htj.parent = -1) m2 = m1; x2 = x1; m1 = pht-htj.ww; x1 = j; else if (pht-ht

29、j.ww htj.parent = -1) m2 = pht-htj.ww; x2 = j; pht-htx1.parent = m+i; pht-htx2.parent = m+i; pht-htm+i.ww = m1+m2; pht-htm+i.llink = x1; pht-htm+i.rlink = x2; pht-root = m+i; return pht; int main() int m = 0, j = 0, i = 0, parent = 0; int* w; PHtTree pht; printf(please input m = ); scanf(%d,&m); if

30、(m 1) printf(m is not reasonable!n); return 1; w = (int *)malloc(sizeof(int)*m); if (w = NULL) printf(overflow!n); return 1; printf(please input the %d numbers：n,m); for (j = 0; j m; j+) scanf(%d, w+j); pht = huffman(m, w); for (j = 0; j hti.parent != -1) parent = pht-hti.parent; if (pht-htparent.llink = i) printf(0); else printf(1); i = parent; printf(n); return 0;3 课程设计运行结果与分