哈夫曼树的应用实例（哈夫曼树的应用）

本文目录

• 哈夫曼树的应用
• 哈夫曼编码的应用举例
• 哈夫曼树编码的应用（Java语言）
• 哈夫曼树应用（C语言）

哈夫曼树的应用

#include《stdio.h》
#include《stdlib.h》
#include《string.h》
#include《conio.h》a
#include《graphics.h》
#define MAXVALUE 200 /*权值的最大值*/
#define MAXB99v 30 /*最大的编码位数*/
#define MAXNODE 30 /*初始的最大的结点数*/
strUCt haffnode
{char data;
int weight;
int flag;
int parent; /*双亲结点的下标*/
int leftchild; /*左孩子下标*/
int rightchild; /*右孩子下标*/
};
struct haffcode
{int bit;
int start; /*编码的起始下标*/
char data;
int weight; /*字符权值*/
};
/*函数说明*/
/************************************************************************/
void pprintf(struct haffcode haffcode,int n);
/*输出函数*/
void haffmantree(int weight);
/*建立哈夫曼树*/
void haffmancode(struct haffnode hafftree);
/*求哈夫曼编码*/
void test(struct haffcode haffcode,int n);
/*测试函数*/
void end();
/*结束界面函数*/
/************************************************************************/
void haffmantree(int weight)
/*建立叶结点个数为n，权值数组为weight的哈夫曼树*/
{int i,j,m1,m2,x1,x2;
/*哈夫曼树hafftree初始化，n个叶结点共有2n-1个结点*/
for(i=0;i《2*n-1;i++)
{if(i《n) {hafftree;
hafftree; /*叶结点*/
}
else {hafftree.weight=0; /*非叶结点*/
hafftree.data=’\0’;
}
hafftree.parent=0; /*初始化没有双亲结点*/
hafftree.flag=0;
hafftree.leftchild=-1;
hafftree.rightchild=-1;
}
for(i=0;i《n-1;i++) /*构造哈夫曼树n-1个非叶结点*/
{m1=m2=MAXVALUE;
x1=x2=0;
for(j=0;j《n+i;j++)
{if(hafftree.flag==0)
{m2=m1;
x2=x1;
m1=hafftree.weight;
x1=j;
}
else if(hafftree.flag==0)
{m2=hafftree.weight;
x2=j;
}
}
hafftree.parent=n+i;
hafftree.parent=n+i

哈夫曼编码的应用举例

哈夫曼树─即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。 在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称“熵编码法”），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。这种方法是由David.A.Huffman发展起来的。 例如，在英文中，e的出现概率很高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位(bit)来表示，而z则可能花去25个位（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个位。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。若能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。

哈夫曼树编码的应用（Java语言）

1）编写函数实现选择parent为0且权值最小的两个根结点的算法
2）编写函数实现统计字符串中字符的种类以及各类字符的个数。
3）编写函数构造赫夫曼树。
4）编写函数实现由赫夫曼树求赫夫曼编码表。
5）编写函数实现将正文转换为相应的编码文件。
6）编写函数实现将编码文件进行译码。
7）编写主控函数，完成本实验的功能。

哈夫曼树应用（C语言）

Huffman(C)

Input: C一组节点，节点中储存了字符以及该字符在文件中出现的频率

Output: Huffman树的根节点

Algorithm:

      n=length(C)

      insert(Q,C) //注：把C中的每一个节点都插入minHeap中

      for i 从0到n-2 do

         创建一个新的空节点z

         z.leftchild=x=extract-min(Q)

         z.rightchild=y=extract-min(Q)

         z.frequence=x.frequence+y.frequence

         insert(Q,z)

      end for

      return extract-min(Q)

如图所示，因为每次都取出2个最小的节点，然后合并它们。所以第一次选择C和D合并为新的节点它的频率是2。然后把这个新节点插入Q。而B和R的频率都是2，和新的节点频率相同，根据不同的min-heap算法，在此处可能有所不同。本例选择的是先入先出，因此先合并B和R得到一个新节点4。之后再取出2个最小的节点，即新的2和新的4，合并它们得到新节点6。最后合并节点A和新节点6得到根节点11。