哈夫曼编码C语言资料讲解.pptVIP

第24章哈夫曼编码的实现 问题描述 问题分析及实现 开发过程常见问题及解决 第24章哈夫曼编码的实现 问题描述 问题分析及实现 开发过程常见问题及解决 第24章哈夫曼编码的实现 问题描述 问题分析及实现 开发过程常见问题及解决 第24章哈夫曼编码的实现 问题描述 问题分析及实现 开发过程常见问题及解决 哈夫曼编码的实现 现实的信息生活中，需要存储的信息是越来越多。在通信行业中，为了提高通信的效率，各路济济的人才也是绞尽脑汁了。本章将讲解为了减小信息的编码及通信的编码，需要重新对信息进行编码的一种非常重要的编码算法。哈夫曼编码现已应用到了很多行业，那么如何实现哈夫曼编码呢？它又有什么优势呢？ 24.1 问题描述 哈夫曼编码（Huffman Coding）是一种编码方式，是可变字长编码（VLC）的一种。 Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就称为Huffman编码。以哈夫曼树─即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。 在本章，使用C语言实现一个Huffman编码的程序，可对预先定制的字符串及权重重新编码，打印每个字符串对应的编码。在数据通讯中，经常需要将传送的文字转换成由二进制字符0、1组成的二进制代码，称之为编码。如果在编码时考虑字符出现的频率，将重复出现次数较高的字符采用尽可能短的编码，出现频率低的字符采用稍长的编码，构造一种不等长编码，则电文的代码就可能更短。因此，哈夫曼编码是一种用于构造使电文的编码总长最短的编码方案。 24.2 问题分析及实现 24.2.1 问题分析 24.2.2 问题实现 24.2.3 程序运行 24.2 问题分析及实现 由问题描述可知，我们要实现的是打印Huffman编码。在输入，处理，输出的环节中，要求的输入指的预先设定好的字符串及相应的权重，处理，就是Huffman树创建的过程，而输出，就是将最终处理后的结果打印出来。 Huffman编码，其中心目的就是为了使编码后的数据量比编码前的原始数据量有一个数量级的下降。换言之，就是为了压缩。无论是它应用在通信行业，信息存储方面，都是为了这一目的。那么，怎么实现呢？在问题分析阶段，我们给出具体的更详细的讲解。 24.2.1 问题分析 Huffman的本质是压缩，那么压缩如何实现呢？采用哈夫曼（Huffman）树，也称最优二叉树建树，树建好后，就等于每个节点上的编码已经编好，只需要打印出来。那么还记得前几章讲到的如何建立一个最优二叉树吗？带权路径长度最小的二叉树就是Huffman树。所以求树的带权路径长度，就成为了关键。 24.2.2 问题实现 带权路径长度最小，就成了我们需要实现的目标。就是说，权重越大，离树的根部越近，这点相当于，一个单位的人员，权利越大，他的位置就离这个单位最高领导的位置越近，相反，越无足轻重，则离领导岗位就越远。 给定字符集的哈夫曼树生成后，求哈夫曼编码的具体实现过程是：依次以叶子T[i]为出发点，向上回溯至根为止。上溯时走左分支则生成代码0，走右分支则生成代码1。实现的代码如下。 24.2.2 问题实现 1. 采用结构体保存过程数据 通过定义两个结构体类型，分别记录二叉树的信息和编码的信息。代码如下（代码24-1.txt） 24.2.2 问题实现 01 #include stdio.h 02 #include string.h 03 #define Node 100 /*叶子结点数*/ 04 #define M 2*Node-1 /*树中结点总数*/ 05 typedef struct 06 { 07 int parent; /*父结点*/ 08 int lchild; /*左子结点*/ 09 int rchild; /*右子结点*/ 10 char data[10]; /*结点值*/ 11 int weight; /*权重*/ 12 } TreeNode; /*树结构体*/ 13 typedef struct 14 { 15 char cd[Node]; /*存放哈夫曼码*/ 16 int start; 17 } Code; /*编码结构体*/ 24.2.2 问题实现 2. 输出结果 将结果输出至屏幕，以循环打印的方式，调用标准输入输出函数printf，将结果回显。代码如下（代码24-2.txt）。 24.2.2 问题实现 01 void DispCo