《c语言从入门到精通――第24章课件》由会员分享，可在线阅读，更多相关《c语言从入门到精通――第24章课件（18页珍藏版）》请在金锄头文库上搜索。
1、第24章哈夫曼编码的实现,问题描述 问题分析及实现 开发过程常见问题及解决,第24章哈夫曼编码的实现,问题描述 问题分析及实现 开发过程常见问题及解决,第24章哈夫曼编码的实现,问题描述 问题分析及实现 开发过程常见问题及解决,第24章哈夫曼编码的实现,问题描述 问题分析及实现 开发过程常见问题及解决,哈夫曼编码的实现,现实的信息生活中，需要存储的信息是越来越多。在通信行业中，为了提高通信的效率，各路济济的人才也是绞尽脑汁了。本章将讲解为了减小信息的编码及通信的编码，需要重新对信息进行编码的一种非常重要的编码算法。哈夫曼编码现已应用到了很多行业，那么如何实现哈夫曼编码呢？它又有什么优势呢？,2
2、4.1 问题描述,哈夫曼编码（Huffman Coding）是一种编码方式，是可变字长编码（VLC）的一种。 Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就称为Huffman编码。以哈夫曼树即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。 在本章，使用C语言实现一个Huffman编码的程序，可对预先定制的字符串及权重重新编码，打印每个字符串对应的编码。在数据通讯中，经常需要将传送的文字转换成由二进制字符0、1组成的二进制代码，称之为编码。如果在编码时考虑字符出现的频率，将重复出现次数较高的字符采用尽
3、可能短的编码，出现频率低的字符采用稍长的编码，构造一种不等长编码，则电文的代码就可能更短。因此，哈夫曼编码是一种用于构造使电文的编码总长最短的编码方案。,24.2 问题分析及实现,24.2.1 问题分析 24.2.2 问题实现 24.2.3 程序运行,24.2 问题分析及实现,由问题描述可知，我们要实现的是打印Huffman编码。在输入，处理，输出的环节中，要求的输入指的预先设定好的字符串及相应的权重，处理，就是Huffman树创建的过程，而输出，就是将最终处理后的结果打印出来。 Huffman编码，其中心目的就是为了使编码后的数据量比编码前的原始数据量有一个数量级的下降。换言之，就是为了压缩
4、。无论是它应用在通信行业，信息存储方面，都是为了这一目的。那么，怎么实现呢？在问题分析阶段，我们给出具体的更详细的讲解。,24.2.1 问题分析,Huffman的本质是压缩，那么压缩如何实现呢？采用哈夫曼（Huffman）树，也称最优二叉树建树，树建好后，就等于每个节点上的编码已经编好，只需要打印出来。那么还记得前几章讲到的如何建立一个最优二叉树吗？带权路径长度最小的二叉树就是Huffman树。所以求树的带权路径长度，就成为了关键。,24.2.2 问题实现,带权路径长度最小，就成了我们需要实现的目标。就是说，权重越大，离树的根部越近，这点相当于，一个单位的人员，权利越大，他的位置就离这个单位最
5、高领导的位置越近，相反，越无足轻重，则离领导岗位就越远。 给定字符集的哈夫曼树生成后，求哈夫曼编码的具体实现过程是：依次以叶子Ti为出发点，向上回溯至根为止。上溯时走左分支则生成代码0，走右分支则生成代码1。实现的代码如下。,24.2.2 问题实现,1. 采用结构体保存过程数据 通过定义两个结构体类型，分别记录二叉树的信息和编码的信息。代码如下（代码24-1.txt）,24.2.2 问题实现,01 #include 02 #include 03 #define Node 100 /*叶子结点数*/ 04 #define M 2*Node-1 /*树中结点总数*/ 05 typedef stru
6、ct 06 07 int parent; /*父结点*/ 08 int lchild; /*左子结点*/ 09 int rchild; /*右子结点*/ 10 char data10; /*结点值*/ 11 int weight; /*权重*/ 12 TreeNode; /*树结构体*/ 13 typedef struct 14 15 char cdNode; /*存放哈夫曼码*/ 16 int start; 17 Code; /*编码结构体*/,24.2.2 问题实现,2. 输出结果 将结果输出至屏幕，以循环打印的方式，调用标准输入输出函数printf，将结果回显。代码如下（代码24-2.t
7、xt）。,24.2.2 问题实现,01 void DispCode(TreeNode ht,Code hcd,int n) 02 03 int sum=0,m=0; 04 int i,j,k; 05 printf(哈夫曼编码:n); /*输出哈夫曼编码*/ 06 for (i=0;in;i+) 07 08 j=0; 09 printf( %s:t,hti.data); 10 for (k=hcdi.start;k=n;k+) 11 12 printf(%c,hcdi.cdk); 13 j+; 14 15 m+=hti.weight; 16 sum+=hti.weight*j; 17 print
8、f(n); 18 19 printf(n平均长度=%gn,1.0*sum/m); 20 ,24.2.2 问题实现,3. 求解Huffman的编码 通过对已经建立好的树进行循环遍历，向左路径记录0，向右路径记录1，直到所有节点均访问到。代码如下（代码24-3.txt）。,24.2.2 问题实现,/*对树编码*/ void CreateCode(TreeNode ht,Code hcd,int n) int i,f,c; Code hc; for (i=0;in;i+) /*根据哈夫曼树求哈夫曼编码*/ hc.start=n;c=i; f=hti.parent; while (f!=-1) /*循
9、序直到树根结点*/ if (htf.lchild=c) /*处理左孩子结点*/ hc.cdhc.start-=0; else /*处理右孩子结点*/ hc.cdhc.start-=1; c=f;f=htf.parent; hc.start+; /*start指向哈夫曼编码最开始字符*/ hcdi=hc; ,24.2.3 程序运行,单击【调试】工具栏中的按钮，根据提示输入数据，按【Enter】键，即可输出如下结果。,24.3 开发过程常见问题及解决,开发过程常见问题及解决办法如下，仅供参考。 开发中，要如何理解编码概念呢？编码，就是将一种信息用另外一种信息表示出来，而一般采用的方法就是以二进制进行编码，如ASCII(美国国家标准编码字符集)。 此程序的难点之一二叉树建立过程中，如何对已有字符进行编码这部分的理解。可以将编码过程想象成，将生面包放入微波炉，放进去的是生面包，但取出来的却是已经烤好的面包。由此可见，编码较简单，重在建树。 (3) 此程序的另一难点，是如何理解建二叉树，办法就是，将树看成一类像树的特殊链表，表中节点有几个特性，节点存放的数据，节点的左孩子，节点的右孩子，节点的双亲节点，以及此节点的权重等等，而建树的过程，就相当于将这些节点用链表的方式，按一定的约束条件将它们“串”起来。,
