《哈夫曼树及其应用》PPT课件

第六章（续）哈夫曼树及其应用,设有10000个学生某门课程的考试成绩的分布如下表所示：,一、问题的提出,学生成绩数据分布情况表,*问题：现在要编写程序依次根据每个学生的成绩打印出该学生的成绩等级。,学生成绩数据分布情况表,方法1：,a60,打印bad“,yes,a70,no,打印pass,yes,a80,no,打印general,yes,a90,no,打印good,yes,打印excellent,no,5%的学生,15%的学生,40%的学生,30%的学生,10%的学生,共做31500次比较,读取一个学生成绩a,循环一万次,i=1,i=10000,N,结束,i=i+1,学生成绩数据分布情况表,方法2：,a80,打印bad,yes,a90,no,yes,no,a70,yes,no,a60,yes,no,打印“good,打印excellent,打印pass,打印general,5%的学生,15%的学生,40%的学生,30%的学生,10%的学生,读取一个学生成绩a,循环一万次,i=1,i=10000,N,结束,学生成绩数据分布情况表,方法2：,a80,打印bad,yes,a90,no,yes,no,a70,yes,no,a60,yes,no,打印“good,打印excellent,打印pass,打印general,5%的学生,15%的学生,40%的学生,30%的学生,10%的学生,共做22000次比较,读取一个学生成绩a,循环一万次,i=1,i=10000,N,结束,思考：如何找到一棵最优的判断树使得编写出来的程序的运行时间是最高效的？,1.哈夫曼树的有关概念,结点的路径长度：从根结点沿某条路径到某结点途中所经历的弧的条数称为该结点的路径长度。,二、哈夫曼树及其应用,树的路径长度：从根结点到每一个叶子结点的路径长度之和。,树的带权路径长度(WPL)：树中所有叶子结点的带权路径长度之和称为树的带权路径长度。,结点的带权路径长度：某结点的路径长度与该结点上的权值的乘积称为该结点的带权路径长度。,1.哈夫曼树的有关概念,二、哈夫曼树及其应用,实例：已知某二叉树的四个叶子结点a,b,c,d分别带权7，5，2，4，则可构造出有如下几种不同形式的二叉树：,a,a,a,7,7,7,b,5,b,5,c,2,d,4,c,2,d,4,b,5,c,2,d,4,树的带权路径长度为：WPL=2*7+2*5+2*2+2*4=36,树的带权路径长度为：WPL=2*4+3*7+3*5+1*2=46,树的带权路径长度为：WPL=1*7+2*5+3*2+3*4=35,1.哈夫曼树的有关概念,二、哈夫曼树及其应用,哈夫曼树的定义：设有n个叶子结点的二叉树，其第i个叶子结点的权值为wi(i=1,2,3,.n),且第i个叶子结点的路径长度为li,则使WPL=wi*li最小的二叉树称为“最优二叉树”或称为“哈夫曼树”。,i=1,n,n,2.哈夫曼树的求解过程,二、哈夫曼树及其应用,问题：,已知n个叶子的权值为w1,w2,.wn，构造一棵最优二叉树。,2.哈夫曼树的求解过程,二、哈夫曼树及其应用,方法：,步骤1:构造一个具有n棵二叉树的森林F=T1,T2,.,Tn，其中Ti是只有一个根结点且根结点的权值为wi的二叉树。,步骤2:在F中选取两棵其根结点的权值最小的二叉树，从F中删除这两棵树，并以这两棵二叉树为左右子树构造一棵新的二叉树添加到F中，该新的二叉树的根结点的权值为其左右孩子二叉树的根结点的权值之和。,步骤3:判断F中是否只有唯一的一棵二叉树。若是，则求解过程结束；否则，转步骤2。,2.哈夫曼树的求解过程,二、哈夫曼树及其应用,实例：已知有5个叶子结点的权值分别为：5,15,40,30,10；试画出一棵相应的哈夫曼树。,a,40,b,30,c,5,d,10,e,15,15,2.哈夫曼树的求解过程,二、哈夫曼树及其应用,实例：已知有5个叶子结点的权值分别为：5,15,40,30,10；试画出一棵相应的哈夫曼树。,a,40,b,30,c,5,d,10,e,15,15,2.哈夫曼树的求解过程,二、哈夫曼树及其应用,实例：已知有5个叶子结点的权值分别为：5,15,40,30,10；试画出一棵相应的哈夫曼树。,a,40,b,30,c,5,d,10,e,15,15,30,2.哈夫曼树的求解过程,二、哈夫曼树及其应用,实例：已知有5个叶子结点的权值分别为：5,15,40,30,10；试画出一棵相应的哈夫曼树。,a,40,b,30,c,5,d,10,e,15,15,30,60,2.哈夫曼树的求解过程,二、哈夫曼树及其应用,实例：已知有5个叶子结点的权值分别为：5,15,40,30,10；试画出一棵相应的哈夫曼树。,a,40,b,30,c,5,d,10,e,15,15,30,60,100,3.哈夫曼编码,二、哈夫曼树及其应用,等长编码：,以英文字符编码为例，一般英文字符编码是采用7位二进制数编码（ASCII码）。7位二进制数可以为27个不同的英文字符编码。,下面为讨论问题简单起见，假设被编码的字符集中只有4个（即22个）不同字符，故只要两位二进制数即可完成编码。,设这4个不同的字符为A，B，C，D，则可进行等长编码如下：,3.哈夫曼编码,二、哈夫曼树及其应用,等长编码：,设这4个不同的字符为A，B，C，D，则可进行等长编码如下：,3.哈夫曼编码,二、哈夫曼树及其应用,等长编码：,设这4个不同的字符为A，B，C，D，则可进行等长编码如下：,A:00B:01C:10D:11,则对于电文“ABACCDA”的二进制电码为：00010010101100总长为14位,译码时，两位一分进行译码，可唯一得到电文：ABACCDA。,3.哈夫曼编码,二、哈夫曼树及其应用,压缩编码：,即采用不等长的编码方案，将“高频字符”的编码设计得尽可能短一些，把最长的编码留给“低频字符”。,例如：对于刚才的4个字符的编码问题，可以按如下不等长编码方案进行编码：,A:0B:00C:1D:01,问题：译码时可能出现多意性，即译码不唯一：,则对于电文“ABACCDA”的二进制电码为：000011010总长为9位,3.哈夫曼编码,二、哈夫曼树及其应用,压缩编码：,例如：对于刚才的4个字符的编码问题，可以按如下不等长编码方案进行编码：,A:0B:00C:1D:01,问题：译码时可能出现多意性，即译码不唯一：,则对于电文“ABACCDA”的二进制电码为：000011010总长为9位,3.哈夫曼编码,二、哈夫曼树及其应用,压缩编码：,例如：对于刚才的4个字符的编码问题，可以按如下不等长编码方案进行编码：,A:0B:00C:1D:01,问题：译码时可能出现多意性，即译码不唯一。,则对于电文“ABACCDA”的二进制电码为：000011010总长为9位,如000011010中的前4个0的译码会有如下几种不同译码：,0000AAAA；0000ABA；0000BB,思考：如何解决这一问题？,问题的关键在于编码是否为无前缀编码。,3.哈夫曼编码,二、哈夫曼树及其应用,无前缀压缩编码（既哈夫曼编码）：,*思想：利用哈夫曼树设计出来的不等长的编码方案一定是无前缀的。,*方法：步骤1：将各字符按照其“出现频率”的统计数字安排一个“权值”并作为“叶子”，然后求出相应的哈夫曼树；步骤2：树中各结点到其左孩子的边上的权值设为0、到其右孩子的边上的权值设为1（即所谓左0右1）；步骤3：从根开始到“叶子”所经历的边上的数值的序列即为该“叶子”所对应的字符的编码。,三、实例,已知某通信用电文仅由A、B、C、D这4个字符构成，其出现的频率分别为：8、4、6、2，请给出它们的哈夫曼编码，要求写出相应的哈夫曼树。解：根据哈夫曼算法，求得哈夫曼树如下：,20,8,12,2,6,6,4,B,D,A,C,0,1,0,1,0,1,从根开始到叶子得各字符的哈夫曼编码如下：,A:0B:100C:11D:101,则对于电文“ABACCDA”的二进制电码为：0100011111010总长为13位,三、实例,补充内容：用一维数组存放单链表静态链表,A,0123456789,三、实例,补充内容：用一维数组存放单链表静态链表,A,0123456789,三、实例,补充内容：用一维数组存放单链表静态链表,A,0123456789,三、实例,补充内容：用一维数组存放单链表静态链表,A,0123456789,三、实例,补充内容：用一维数组存放单链表静态链表,A,0123456789,三、实例,补充内容：用一维数组存放单链表静态链表,A,0123456789,三、实例,补充内容：用一维数组存放单链表静态链表,A,0123456789,三、实例,补充内容：用一维数组存放单链表静态链表,A,0123456789,三、实例,补充内容：用一维数组存放单链表静态链表,A,0123456789,三、实例,补充内容：用一维数组存放单链表静态链表,A,0123456789,A,0123456789,在“孙”的前面插入一个“史”：,三、实例,补充内容：用一维数组存放单链表静态链表,A,0123456789,A,0123456789,在“孙”的前面插入一个“史”：,三、实例,补充内容：用一维数组存放单链表静态链表,A,0123456789,A,0123456789,在“孙”的前面插入一个“史”：,三、实例,补充内容：用一维数组存放单链表静态链表,A,0123456789,A,0123456789,在“孙”的前面插入一个“史”：,三、实例,补充内容：用一维数组存放单链表静态链表,A,0123456789,A,0123456789,在“孙”的前面插入一个“史”：,三、实例,补充内容：用一维数组存放单链表静态链表,A,0123456789,A,0123456789,在“孙”的前面插入一个“史”：,三、实例,补充内容：用一维数组存放单链表静态链表,A,0123456789,A,0123456789,在“孙”的前面插入一个“史”：,删除“周”时表的变化：,A,0123456789,三、实例,补充内容：用一维数组存放单链表静态链表,A,0123456789,A,0123456789,在“孙”的前面插入一个“史”：,删除“周”时表的变化：,A,0123456789,三、实例,补充内容：用一维数组存放单链表静态链表,A,0123456789,A,0123456789,在“孙”的前面插入一个“史”：,删除“周”时表的变化：,A,0123456789,三、实例,补充内容：用一维数组存放单链表静态链表,A,0123456789,A,0123456789,在“孙”的前面插入一个“史”：,删除“周”时表的变化：,A,0123456789,三、实例,补充内容：用一维数组存放单链表静态链表,A,0123456789,A,0123456789,在“孙”的前面插入一个“史”：,删除“周”时表的变化：,A,0123456789,总结：静态链表在插入和删除时一般不需要移动元素，仅需要修改指针即可。但在申请存储空间时需要一次性申请足够大的空间。,三、实例,补充内容：用一维数组存放单链表静态链表,A,0123456789,静态链表的结构类型定义：,#definedMAXSIZE1000/链表的最大尺寸TypedefstructStaticListNodeElemTypedata;/存放表中元素的值intnext;/指示后继元素的存放位置StaticListNode,StaticLinkListMAXSIZE;/定义一个数组,四、构造哈夫曼树并求n个字符的哈夫曼编码之程序,1.哈夫曼树的结点的物理结构：,TypedefstructHTNodeunsignedintweight;unsignedintparent,lchild,rchild;HTNode,*HuffmanTree;/该指针用以申请数组时作为数组名,2.结点物理结构的C语言定义：,例如：,a,7,b,5,c,2,d,4,6,11,18,1234567,HT,哈夫曼树HT的存储结构如下(HT为HuffmanTree类型)：,HT是一个HTNode类型的一维数组，用以存放m个结点元素(m=2n-1,其中n为叶子个数)；即采用静态二叉链表存放哈夫曼树；故HT可以用如下语句为其申请空间：HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);其中0号单元未用，从HT1开始存放树的结点,四、构造哈夫曼树并求n个字符的哈夫曼编码之程序,1.哈夫曼树的结点的物理结构：,typedefchar*HaffmanCode;/HaffmanCode是指向一个字符型数组的指针类型,3.用n个字符型数组存放n个叶子的哈夫曼编码,这n个字符数组的头指针HCi(1in)分别指向一个字符型数组的首地址，又构成一个指针类型的一维数组；,.,HC1,HC2,HCn,.,则n个字符串数组的头指针HCi(1in)可以如此定义：HC=(HuffmanCode)malloc(n+1)*sizeof(char*);HCi=(char*)malloc(编码长度+1)*sizeof(char);,四、构造哈夫曼树并求n个字符的哈夫曼编码之程序,4.构造哈夫曼树的程序之实现：,算法思想：,例如：,a,7,b,5,c,2,d,4,6,11,18,1234567,HT,其哈夫曼树HT的存储结构的初始情况如下：,针对第i个结点(n+1i2n-1,n=4为叶子结点的个数)，在1i-1号结点中为第i个结点寻找两个儿子结点(该两个儿子应该是i-1个节点中无父亲且权值最小的两个结点),四、构造哈夫曼树并求n个字符的哈夫曼编码之程序,4.构造哈夫曼树的程序之实现：,算法思想：,例如：,a,7,b,5,c,2,d,4,6,11,18,1234567,HT,其哈夫曼树HT的存储结构的初始情况如下：,针对第i个结点(n+1i2n-1,n=4为叶子结点的个数)，在1i-1号结点中为第i个结点寻找两个儿子结点(该两个儿子应该是i-1个节点中无父亲且权值最小的两个结点),四、构造哈夫曼树并求n个字符的哈夫曼编码之程序,4.构造哈夫曼树的程序之实现：,算法思想：,例如：,a,7,b,5,c,2,d,4,6,11,18,1234567,HT,其哈夫曼树HT的存储结构的初始情况如下：,针对第i个结点(n+1i2n-1,n=4为叶子结点的个数)，在1i-1号结点中为第i个结点寻找两个儿子结点(该两个儿子应该是i-1个节点中无父亲且权值最小的两个结点),四、构造哈夫曼树并求n个字符的哈夫曼编码之程序,4.构造哈夫曼树的程序之实现：,算法思想：,例如：,a,7,b,5,c,2,d,4,6,11,18,1234567,HT,其哈夫曼树HT的存储结构的初始情况如下：,针对第i个结点(n+1i2n-1,n=4为叶子结点的个数)，在1i-1号结点中为第i个结点寻找两个儿子结点(该两个儿子应该是i-1个节点中无父亲且权值最小的两个结点),四、构造哈夫曼树并求n个字符的哈夫曼编码之程序,4.构造哈夫曼树的程序之实现：,voidHu