介绍

哈夫曼（Haffman）这种方法的基本思想如下：

①由给定的n个权值{W1，W2，…，Wn}构造n棵只有一个叶子结点的二叉树，从而得到一个二叉树的集合F={T1，T2，…，Tn}。

②在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和。

③在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中。

④重复②、③两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。

对于同一组给定叶子结点所构造的哈夫曼树，树的形状可能不同，但带权路径长度值是相同的，一定是最小的。

哈夫曼树的构建

为了方便操作，用静态链表作为哈夫曼树的存储。在构造哈夫曼树时，设置一个结构数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode的大小设置为2n-1，结点的结构形式如下：

weight lchild rchild parent

其中，weight域保存结点的权值，lchild和rchild域分别保存该结点的左、右孩子结点在数组HuffNode中的序号，从而建立起结点之间的关系。为了判定一个结点是否已加入到要建立的哈夫曼树中，可通过parent域的值来确定。初始时parent的值为-1，当结点加入到树中时，该结点parent的值为其双亲结点在数组HuffNode中的序号，就不会是-1了。构造哈夫曼树时，首先将由n个字符形成的n个叶子结点存放到数组HuffNode的前n个分量中，然后根据前面介绍的哈夫曼方法的基本思想，不断将两个较小的子树合并为一个较大的子树，每次构成的新子树的根结点顺序放到HuffNode数组中的前n个分量的后面。

代码：

#define maxvalue 1e6 //定义最大权值整数常量#define maxleaf 1e3 //定义哈夫曼树中结点个数整数常量#define maxnode maxleaf*2-1typedef struct{
   int weight;int parent;int lchild;int rchild;}HNodeType;HNodeType* HuffTree(){
   HNodeType node[maxnode];int i,j,n;int m1,m2,x1,x2;cin>>n;//输入叶子结点个数for(int i = 0;i < n;i++){
   node[i].weight=0;node[i].parent=-1;node[i].lchild=-1;node[i].rchild=-1;//初始化结点}for(int i = 0;i < n;i++){
   cin>>node[i].weight;//输入n个叶子结点的权值}for(int i = 0;i

哈夫曼编码

构造编码的时候人们希望解决的两个问题是：

①编码总长最短。

②译码的唯一性。哈夫曼树可用于构造使电文的编码总长最短的编码方案。

具体做法如下：设需要编码的字符集合为{d1，d2，…，dn}，它们在电文中出现的次数或频率集合为{w1，w2，…，wn}，以d1，d2，…，dn作为叶子结点，w1，w2，…，wn作为它们的权值，构造一棵哈夫曼树，规定哈夫曼树中的左分支代表0，右分支代表1，则从根结点到每个叶子结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码，称为哈夫曼编码。

实现哈夫曼编码的算法可分为两大部分：

①构造哈夫曼树。

②在哈夫曼树上求叶结点的编码。

求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域退回到根结点，每退回一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值。由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码为所求编码的高位码。可以设置一结构数组HuffCode用来存储各字符的哈夫曼编码信息，数组元素的结构如下：

bit start

其中，分量bit为一维数组，用来保存字符的哈夫曼编码，start表示该编码在数组bit中的开始位置。所以，对于第i个字符，它的哈夫曼编码存放在HuffCode[i].bit中的从HuffCode[i].start到n的分量上。

算法实现；（写法一）

#define maxbit 1e6 //定义编码的最大长度整数常量typedef struct{
   int bit[maxbit];int start;}Hcode;void HuffCode(){
   node huffnode[maxnode];//node为上面的代码定义的结点类型Hcode huffcode[maxcode],cd;//cd为一临时编码结点int i,j,c,p;huffnode=HuffTree();//HuffTree为上面实现的建立哈夫曼树的函数for(int i = 0;i < n;i++){
   cd.start=n-1;//注意start从n-1开始c=i;p=node[c].parent;while(p!=-1){
   if(node[p].lchild==c)cd.bit[cd.start]=0;else cd.bit[cd.start]=1;cd.start--;c=p;//从叶节点往上p=node[c].parent;//p变成c的父节点}for(j=cd.start+1;j

写法二：

typedef HuffNode{
   char data;//待编码的符号double weight;//符号出现的频率int parent,lchild,rchild;}HTnode,*HuffmanTree;

编码：从叶结点回退，左分支记0 右记1

void Code(HuffmanTree &HT,int n,int i,char *code){
   //求第i个字符的编码int p,parent,start;char *cd;cd = new char[n];cd[n-1] = '\0';start = n-1;p = i;//p是当前结点的下标parent = HT[i].parent;//当前结点的父节点下标while(parent != -1){
   if(HT[parent].lchild == p)cd[--start] = '0';elsecd[--start] = '1';p = parent;parent = HT[patent].parent;//沿双亲回退}strcpy(code,&cd[start]);delete[]cd;}

转载地址：http://cxten.baihongyu.com/

你可能感兴趣的文章

java 获取年月日时分秒和当月第一天和最后一天