精华内容
下载资源
问答
  • 哈夫曼树编码参考程序 含 h头文件 main函数分开
  • 哈夫曼树
  • 哈夫曼树及哈夫曼树编码

    千次阅读 2015-09-09 15:50:57
    本文转自哈夫曼树及哈夫曼树编码 在一般的数据结构的书中,树的那章后面,著者一般都会介绍一下哈夫曼(HUFFMAN) 树和哈夫曼编码。哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛,如 JPEG中就应用...

    本文转自哈夫曼树及哈夫曼树编码

    在一般的数据结构的书中,树的那章后面,著者一般都会介绍一下哈夫曼(HUFFMAN)

    树和哈夫曼编码。哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛,如

    JPEG中就应用了哈夫曼编码。 首先介绍什么是哈夫曼树。哈夫曼树又称最优二叉树,

    是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点

    的权值乘上其到根结点的 路径长度(若根结点为0层,叶结点到根结点的路径长度

    为叶结点的层数)。树的带权路径长度记为WPL= (W1*L1+W2*L2+W3*L3+...+Wn*Ln)

    ,N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径

    长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。

    哈夫曼编码步骤:

    一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,...,Ti,...,Tn},其中每棵二叉树Ti中只有一个权值为Wi的根结点,它的左右子树均为空。(为方便在计算机上实现算 法,一般还要求以Ti的权值Wi的升序排列。)
    二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树,新二叉树的根结点的权值为其左右子树的根结点的权值之和。
    三、从F中删除这两棵树,并把这棵新的二叉树同样以升序排列加入到集合F中。
    四、重复二和三两步,直到集合F中只有一棵二叉树为止。

    简易的理解就是,假如我有A,B,C,D,E五个字符,出现的频率(即权值)分别为5,4,3,2,1,那么我们第一步先取两个最小权值作为左右子树构造一个新树,即取1,2构成新树,其结点为1+2=3,如图:

    12

    虚线为新生成的结点,第二步再把新生成的权值为3的结点放到剩下的集合中,所以集合变成{5,4,3,3},再根据第二步,取最小的两个权值构成新树,如图:

    13

    再依次建立哈夫曼树,如下图:

    14

    其中各个权值替换对应的字符即为下图:

    15

    所以各字符对应的编码为:A->11,B->10,C->00,D->011,E->010

    霍夫曼编码是一种无前缀编码。解码时不会混淆。其主要应用在数据压缩,加密解密等场合。

     

    C语言代码实现:

    /*-------------------------------------------------------------------------
     * Name:   哈夫曼编码源代码。
     * Date:   2011.04.16
     * Author: Jeffrey Hill+Jezze(解码部分)
     * 在 Win-TC 下测试通过
     * 实现过程:着先通过 HuffmanTree() 函数构造哈夫曼树,然后在主函数 main()中
     *           自底向上开始(也就是从数组序号为零的结点开始)向上层层判断,若在
     *           父结点左侧,则置码为 0,若在右侧,则置码为 1。最后输出生成的编码。
     *------------------------------------------------------------------------*/
    #include <stdio.h>
    #include<stdlib.h>
     
    #define MAXBIT      100
    #define MAXVALUE  10000
    #define MAXLEAF     30
    #define MAXNODE    MAXLEAF*2 -1
     
    typedef struct 
    {
        int bit[MAXBIT];
        int start;
    } HCodeType;        /* 编码结构体 */
    typedef struct
    {
        int weight;
        int parent;
        int lchild;
        int rchild;
        int value;
    } HNodeType;        /* 结点结构体 */
     
    /* 构造一颗哈夫曼树 */
    void HuffmanTree (HNodeType HuffNode[MAXNODE],  int n)
    { 
        /* i、j: 循环变量,m1、m2:构造哈夫曼树不同过程中两个最小权值结点的权值,
            x1、x2:构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/
        int i, j, m1, m2, x1, x2;
        /* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */
        for (i=0; i<2*n-1; i++)
        {
            HuffNode[i].weight = 0;//权值 
            HuffNode[i].parent =-1;
            HuffNode[i].lchild =-1;
            HuffNode[i].rchild =-1;
            HuffNode[i].value=i; //实际值,可根据情况替换为字母  
        } /* end for */
     
        /* 输入 n 个叶子结点的权值 */
        for (i=0; i<n; i++)
        {
            printf ("Please input weight of leaf node %d: \n", i);
            scanf ("%d", &HuffNode[i].weight);
        } /* end for */
     
        /* 循环构造 Huffman 树 */
        for (i=0; i<n-1; i++)
        {
            m1=m2=MAXVALUE;     /* m1、m2中存放两个无父结点且结点权值最小的两个结点 */
            x1=x2=0;
            /* 找出所有结点中权值最小、无父结点的两个结点,并合并之为一颗二叉树 */
            for (j=0; j<n+i; j++)
            {
                if (HuffNode[j].weight < m1 && HuffNode[j].parent==-1)
                {
                    m2=m1; 
                    x2=x1; 
                    m1=HuffNode[j].weight;
                    x1=j;
                }
                else if (HuffNode[j].weight < m2 && HuffNode[j].parent==-1)
                {
                    m2=HuffNode[j].weight;
                    x2=j;
                }
            } /* end for */
                /* 设置找到的两个子结点 x1、x2 的父结点信息 */
            HuffNode[x1].parent  = n+i;
            HuffNode[x2].parent  = n+i;
            HuffNode[n+i].weight = HuffNode[x1].weight + HuffNode[x2].weight;
            HuffNode[n+i].lchild = x1;
            HuffNode[n+i].rchild = x2;
     
            printf ("x1.weight and x2.weight in round %d: %d, %d\n", i+1, HuffNode[x1].weight, HuffNode[x2].weight);  /* 用于测试 */
            printf ("\n");
        } /* end for */
      /*  for(i=0;i<n+2;i++)
        {
            printf(" Parents:%d,lchild:%d,rchild:%d,value:%d,weight:%d\n",HuffNode[i].parent,HuffNode[i].lchild,HuffNode[i].rchild,HuffNode[i].value,HuffNode[i].weight);
                      }*///测试 
    } /* end HuffmanTree */
     
    //解码 
    void decodeing(char string[],HNodeType Buf[],int Num)
    {
      int i,tmp=0,code[1024];
      int m=2*Num-1;
      char *nump;
      char num[1024];
      for(i=0;i<strlen(string);i++)
      {
       if(string[i]=='0')
      num[i]=0;        
      else
      num[i]=1;                    
      } 
      i=0;
      nump=&num[0];
      
     while(nump<(&num[strlen(string)]))
     {tmp=m-1;
      while((Buf[tmp].lchild!=-1)&&(Buf[tmp].rchild!=-1))
      {
      
       if(*nump==0)
       {
         tmp=Buf[tmp].lchild ;          
       } 
       else tmp=Buf[tmp].rchild;
       nump++;
            
      } 
      
      printf("%d",Buf[tmp].value);                                  
     }
     
      
    }
     
     
    int main(void)
    {
        
        HNodeType HuffNode[MAXNODE];            /* 定义一个结点结构体数组 */
        HCodeType HuffCode[MAXLEAF],  cd;       /* 定义一个编码结构体数组, 同时定义一个临时变量来存放求解编码时的信息 */
        int i, j, c, p, n;
        char pp[100];
        printf ("Please input n:\n");
        scanf ("%d", &n);
        HuffmanTree (HuffNode, n);
       
        
        for (i=0; i < n; i++)
        {
            cd.start = n-1;
            c = i;
            p = HuffNode[c].parent;
            while (p != -1)   /* 父结点存在 */
            {
                if (HuffNode[p].lchild == c)
                    cd.bit[cd.start] = 0;
                else
                    cd.bit[cd.start] = 1;
                cd.start--;        /* 求编码的低一位 */
                c=p;                    
                p=HuffNode[c].parent;    /* 设置下一循环条件 */
            } /* end while */
            
            /* 保存求出的每个叶结点的哈夫曼编码和编码的起始位 */
            for (j=cd.start+1; j<n; j++)
            { HuffCode[i].bit[j] = cd.bit[j];}
            HuffCode[i].start = cd.start;
        } /* end for */
        
        /* 输出已保存好的所有存在编码的哈夫曼编码 */
        for (i=0; i<n; i++)
        {
            printf ("%d 's Huffman code is: ", i);
            for (j=HuffCode[i].start+1; j < n; j++)
            {
                printf ("%d", HuffCode[i].bit[j]);
            }
            printf(" start:%d",HuffCode[i].start);
           
            printf ("\n");
            
        }
    /*    for(i=0;i<n;i++){
        for(j=0;j<n;j++)
            {
                 printf ("%d", HuffCode[i].bit[j]);           
            }
            printf("\n");
            }*/
        printf("Decoding?Please Enter code:\n");
        scanf("%s",&pp);
    decodeing(pp,HuffNode,n);
        getch();
        return 0;
    }

    展开全文
  • 哈夫曼树和哈夫曼树编码

    千次阅读 2014-05-28 14:50:01
    哈夫曼编码哈夫曼树的一个应用。哈夫曼编码应用广泛,如 JPEG中就应用了哈夫曼编码。 首先介绍什么是哈夫曼树哈夫曼树又称最优二叉树, 是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中...

    在一般的数据结构的书中,树的那章后面,著者一般都会介绍一下哈夫曼(HUFFMAN)

    树和哈夫曼编码。哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛,如

    JPEG中就应用了哈夫曼编码。 首先介绍什么是哈夫曼树。哈夫曼树又称最优二叉树,

    是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点

    的权值乘上其到根结点的 路径长度(若根结点为0层,叶结点到根结点的路径长度

    为叶结点的层数)。树的带权路径长度记为WPL= (W1*L1+W2*L2+W3*L3+...+Wn*Ln)

    ,N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径

    长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。

    哈夫曼编码步骤:

    一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,...,Ti,...,Tn},其中每棵二叉树Ti中只有一个权值为Wi的根结点,它的左右子树均为空。(为方便在计算机上实现算 法,一般还要求以Ti的权值Wi的升序排列。)
    二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树,新二叉树的根结点的权值为其左右子树的根结点的权值之和。
    三、从F中删除这两棵树,并把这棵新的二叉树同样以升序排列加入到集合F中。
    四、重复二和三两步,直到集合F中只有一棵二叉树为止。

    简易的理解就是,假如我有A,B,C,D,E五个字符,出现的频率(即权值)分别为5,4,3,2,1,那么我们第一步先取两个最小权值作为左右子树构造一个新树,即取1,2构成新树,其结点为1+2=3,如图:

    12

    虚线为新生成的结点,第二步再把新生成的权值为3的结点放到剩下的集合中,所以集合变成{5,4,3,3},再根据第二步,取最小的两个权值构成新树,如图:

    13

    再依次建立哈夫曼树,如下图:

    14

    其中各个权值替换对应的字符即为下图:

    15

    所以各字符对应的编码为:A->11,B->10,C->00,D->011,E->010

    霍夫曼编码是一种无前缀编码。解码时不会混淆。其主要应用在数据压缩,加密解密等场合。

     

    C语言代码实现:

    /*-------------------------------------------------------------------------
     * Name:   哈夫曼编码源代码。
     * Date:   2011.04.16
     * Author: Jeffrey Hill+Jezze(解码部分)
     * 在 Win-TC 下测试通过
     * 实现过程:着先通过 HuffmanTree() 函数构造哈夫曼树,然后在主函数 main()中
     *           自底向上开始(也就是从数组序号为零的结点开始)向上层层判断,若在
     *           父结点左侧,则置码为 0,若在右侧,则置码为 1。最后输出生成的编码。
     *------------------------------------------------------------------------*/
    #include <stdio.h>
    #include<stdlib.h>
     
    #define MAXBIT      100
    #define MAXVALUE  10000
    #define MAXLEAF     30
    #define MAXNODE    MAXLEAF*2 -1
     
    typedef struct 
    {
        int bit[MAXBIT];
        int start;
    } HCodeType;        /* 编码结构体 */
    typedef struct
    {
        int weight;
        int parent;
        int lchild;
        int rchild;
        int value;
    } HNodeType;        /* 结点结构体 */
     
    /* 构造一颗哈夫曼树 */
    void HuffmanTree (HNodeType HuffNode[MAXNODE],  int n)
    { 
        /* i、j: 循环变量,m1、m2:构造哈夫曼树不同过程中两个最小权值结点的权值,
            x1、x2:构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/
        int i, j, m1, m2, x1, x2;
        /* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */
        for (i=0; i<2*n-1; i++)
        {
            HuffNode[i].weight = 0;//权值 
            HuffNode[i].parent =-1;
            HuffNode[i].lchild =-1;
            HuffNode[i].rchild =-1;
            HuffNode[i].value=i; //实际值,可根据情况替换为字母  
        } /* end for */
     
        /* 输入 n 个叶子结点的权值 */
        for (i=0; i<n; i++)
        {
            printf ("Please input weight of leaf node %d: \n", i);
            scanf ("%d", &HuffNode[i].weight);
        } /* end for */
     
        /* 循环构造 Huffman 树 */
        for (i=0; i<n-1; i++)
        {
            m1=m2=MAXVALUE;     /* m1、m2中存放两个无父结点且结点权值最小的两个结点 */
            x1=x2=0;
            /* 找出所有结点中权值最小、无父结点的两个结点,并合并之为一颗二叉树 */
            for (j=0; j<n+i; j++)
            {
                if (HuffNode[j].weight < m1 && HuffNode[j].parent==-1)
                {
                    m2=m1; 
                    x2=x1; 
                    m1=HuffNode[j].weight;
                    x1=j;
                }
                else if (HuffNode[j].weight < m2 && HuffNode[j].parent==-1)
                {
                    m2=HuffNode[j].weight;
                    x2=j;
                }
            } /* end for */
                /* 设置找到的两个子结点 x1、x2 的父结点信息 */
            HuffNode[x1].parent  = n+i;
            HuffNode[x2].parent  = n+i;
            HuffNode[n+i].weight = HuffNode[x1].weight + HuffNode[x2].weight;
            HuffNode[n+i].lchild = x1;
            HuffNode[n+i].rchild = x2;
     
            printf ("x1.weight and x2.weight in round %d: %d, %d\n", i+1, HuffNode[x1].weight, HuffNode[x2].weight);  /* 用于测试 */
            printf ("\n");
        } /* end for */
      /*  for(i=0;i<n+2;i++)
        {
            printf(" Parents:%d,lchild:%d,rchild:%d,value:%d,weight:%d\n",HuffNode[i].parent,HuffNode[i].lchild,HuffNode[i].rchild,HuffNode[i].value,HuffNode[i].weight);
                      }*///测试 
    } /* end HuffmanTree */
     
    //解码 
    void decodeing(char string[],HNodeType Buf[],int Num)
    {
      int i,tmp=0,code[1024];
      int m=2*Num-1;
      char *nump;
      char num[1024];
      for(i=0;i<strlen(string);i++)
      {
       if(string[i]=='0')
      num[i]=0;        
      else
      num[i]=1;                    
      } 
      i=0;
      nump=&num[0];
      
     while(nump<(&num[strlen(string)]))
     {tmp=m-1;
      while((Buf[tmp].lchild!=-1)&&(Buf[tmp].rchild!=-1))
      {
      
       if(*nump==0)
       {
         tmp=Buf[tmp].lchild ;          
       } 
       else tmp=Buf[tmp].rchild;
       nump++;
            
      } 
      
      printf("%d",Buf[tmp].value);                                  
     }
     
      
    }
     
     
    int main(void)
    {
        
        HNodeType HuffNode[MAXNODE];            /* 定义一个结点结构体数组 */
        HCodeType HuffCode[MAXLEAF],  cd;       /* 定义一个编码结构体数组, 同时定义一个临时变量来存放求解编码时的信息 */
        int i, j, c, p, n;
        char pp[100];
        printf ("Please input n:\n");
        scanf ("%d", &n);
        HuffmanTree (HuffNode, n);
       
        
        for (i=0; i < n; i++)
        {
            cd.start = n-1;
            c = i;
            p = HuffNode[c].parent;
            while (p != -1)   /* 父结点存在 */
            {
                if (HuffNode[p].lchild == c)
                    cd.bit[cd.start] = 0;
                else
                    cd.bit[cd.start] = 1;
                cd.start--;        /* 求编码的低一位 */
                c=p;                    
                p=HuffNode[c].parent;    /* 设置下一循环条件 */
            } /* end while */
            
            /* 保存求出的每个叶结点的哈夫曼编码和编码的起始位 */
            for (j=cd.start+1; j<n; j++)
            { HuffCode[i].bit[j] = cd.bit[j];}
            HuffCode[i].start = cd.start;
        } /* end for */
        
        /* 输出已保存好的所有存在编码的哈夫曼编码 */
        for (i=0; i<n; i++)
        {
            printf ("%d 's Huffman code is: ", i);
            for (j=HuffCode[i].start+1; j < n; j++)
            {
                printf ("%d", HuffCode[i].bit[j]);
            }
            printf(" start:%d",HuffCode[i].start);
           
            printf ("\n");
            
        }
    /*    for(i=0;i<n;i++){
        for(j=0;j<n;j++)
            {
                 printf ("%d", HuffCode[i].bit[j]);           
            }
            printf("\n");
            }*/
        printf("Decoding?Please Enter code:\n");
        scanf("%s",&pp);
    decodeing(pp,HuffNode,n);
        getch();
        return 0;
    }
    展开全文
  • 哈夫曼树与哈夫曼编码代码实现

    千次阅读 多人点赞 2020-03-18 12:43:30
    哈夫曼树与哈夫曼编码的理解 数据压缩 含义 通过对数据重新的编码,减少数据占用的空间存储;使用的时候再进行解压缩,恢复数据的原有特性。 类别 无损压缩——压缩过程没有数据丢失,解压得到原有数据特性。 有损...

    数据压缩

    含义
    通过对数据重新的编码,减少数据占用的空间存储;使用的时候再进行解压缩,恢复数据的原有特性。
    类别

    1. 无损压缩——压缩过程没有数据丢失,解压得到原有数据特性。
    2. 有损压缩——压缩过程会丢失数据的部分信息,如压缩BMP位图为JPEG会导致精度损失

    编码类型

    1. 定长编码方案:每个字符的编码长度一样,如ASCII码,128个字符,都是用8位二进制码表示的,最高位为0,每个字符的编码与频率无关;
    2. 变长编码方案:每个字符的编码长度与其出现的频率有关,出现的频率越高,其二进制编码的长度越越短;频率越低,则二进制编码长度越长;
      最后总数据的编码长度最短,实现压缩数据。

    哈夫曼编码就是一种无损压缩方法,一种变长编码方案

    哈夫曼编码

    我们这里使用例子来演示
    现在存在字符串,长度15,各个字符及频率:A7,B5,C1,D2

    AAAABBBCDDBBAAA
    

    需要我们进行二进制编码,明显
    采用ASCII码编码,15个字符15字节,编码的长度为 15*8=120位

    使用哈夫曼编码
    1.我们先得到字符出现的频率集合(也叫权重集合),按从小到大排序

    {1257}
    

    2.构造哈夫曼树
    规则就是
    1.在频率集合中找出字符中最小的两个;小的在左边,大的在右边;这两个兄弟组成二叉树。他们的双亲为他们的频率(权值)之和。
    2.在频率表中删除此次找到的两个数,并加入此次最小两个数的频率和(把他们的双亲加入,然后排序)。

    在这里插入图片描述
    第一步,C1,D2最小 我们将其合成N3,3=1+2,得到的频率排序后的表为

    {357}
    

    在这里插入图片描述
    第二步,重复第一步,N3和B5合成N8,8=3+5我们将得到频率排序后的表为

    {78}
    

    在这里插入图片描述
    第三步,重复第一步,A7和N8合成N15,15=7+8我们将得到频率排序后的表为

    {15}
    

    此时只剩下一个数,我们就结束构造了。

    然后
    开始哈夫曼编码,左子树为边值0,右子树边值为1,代码里面我们是使用数组保存的
    我们得到的哈夫曼树为
    在这里插入图片描述
    得到的哈夫曼编码为(从根结点往下面叶子结点看)

    元素 编码
    A 0
    B 11
    C 100
    D 101

    所以我们最后的字串编码为 00001111111001011011111000,长度26位
    对比ASCII编码,压缩比为 120:26

    此时,我们传送任何由ABCD构成的字串,压缩与解压缩都是按照这个编码
    我们可以发现,哈夫曼编码得到的编码长度不一,而且,任何一个字符的编码都不是另一字符的编码前缀,所以不会导致识别错,保证了译码的唯一性。

    原因 我们这里约定了小的是左子树,大的是右子树,保证了哈夫曼树的唯一性,而且我们的编码元素都是处在叶子结点,结合树的一对多的关系我们就能知道每一个字符的编码唯一,不是其余字符编码的前缀

    哈夫曼树

    一些二叉树的概念

    1. 路径长度
      从结点X到结点Y的所经过的结点序列叫做从X到Y的一条路径,路径的边数叫做路径长度。从根结点到其余结点的路径长度之和叫做该二叉树的路径长度(Path Length),简称PL。
      n个结点的完全二叉树的路径长度最短,长度最短的又不仅仅是完全二叉树。
    2. 外路径长度
      从根结点到所有的叶子结点的路径长度之和为二叉树的外路径长度
    3. 带权路径长度
      因为字符的权值,即出现是频率不同,所有我们使用带权的二叉树来编码,根到X结点的带权路径长度就是从根结点到X结点的路径长度与X结点的权值的乘积,**二叉树的带权外路径长度就是所有的叶子结点的带权路径长度之和(Weight external Path Length)**简称WPL。

    哈夫曼树的定义
    就是同结点个数的所有的二叉树中,WPL最小的二叉树,HuffmanTree,也叫最优二叉树所以哈夫曼树不一定是唯一的!
    如图,四棵树的WPL都是26.
    在这里插入图片描述
    要想得到唯一一颗哈夫曼树,就要约束左右子树
    哈夫曼树构建的约束规则就是:合并结点时,权值较小的结点是左孩子,权值较大的是右孩子。

    代码演示

    我们现在对ABCDEFGH编码,使用三叉静态链表实现。
    1.构建哈夫曼树

    //定义哈夫曼树的结构
    typedef struct {
    	int data;//data域存储权值
    	int parent,lchild,rchild;//双亲与孩子
    } HTNode,*HuffmanTree;
    
    /*typedef struct{
    	string<char> str;
    
    }HuffmanTreenode,*HuffmancodeTree;*/
    //哈夫曼树的初始化 
    int InitHuffmanTree(HuffmanTree H,int weight,int parent,int lchild,int rchild)
    {
    	//HT = (HuffmanTree)malloc(n*sizeof(HTNode));//空间分配_我们通过createHuffmanTree来调用,无须分配
    	H->lchild=lchild;
    	H->rchild=rchild;
    	H->parent =parent;
    	H->data = weight;
    }
    
    //建立哈夫曼树!
    void CreateHuffmanTree(HuffmanTree &HT,int n,int *W)
    {
    	//叶子结点的初始化,相当于n棵树,每颗树只有一个结点,那么最后构造过程总的结点个数为:2*n-1 
    	//n-1+n = 2*n-1 
    
    	HT = (HuffmanTree)malloc((2*n-1)*sizeof(HTNode));//n个叶子结点的哈夫曼树结点是2n-1;
    	for(int i=0; i<n; i++) {
    		InitHuffmanTree(HT+i,W[i],-1,-1,-1);//初始化-1 
    	}
    	//开始寻找最小的两个叶子结点,构造哈夫曼树
    	for(int i=n; i<2*n-1; i++) { //我们构造n-1个度为2的结点
    		int min1=65522,min2=min1;//这里的两个数分别代表第一小,第二小
    		int x1=-1,x2=-1;//用来记录下标
    		for(int j=0; j<i; j++) {
    			if((HT+j)->parent==-1)//表示叶子结点没有父母
    				if((HT+j)->data<min1) {
    					min2=min1;
    					min1=(HT+j)->data;
    					x2=x1;
    					x1=j;
    				} else if((HT+j)->data<min2) {
    					min2=(HT+j)->data;
    					x2=j;
    
    				}
    		}
    		//合并两个叶子,让他们有同一个双亲
    		(HT+x1)->parent =i;
    		(HT+x2)->parent =i;
    		//然后我们让HT[i]指向这两个孩子,为了后来的逆序哈夫曼编码
    
    		InitHuffmanTree(HT+i,min2+min1,-1,x1,x2) ;//父结点构造 
    	}
    }
    //完成哈夫曼树的生成;
    

    2.哈夫曼树的编码

    //获得哈夫曼编码,n是指叶子个数,path是我们要获得的字符的编码 
    void HuffmanTreeCode(HuffmanTree HT,char *str,int n,int path,int &e)
    {
    	int i=0,j=0,m=0;
    	int child =path;//假设我们现在在叶子结点为child索引的地方,如1
    
    	int parent = (HT+child)->parent;//获取第一个叶子结点的父节点 的值 
    	//printf("leafe node is:%d \n",(HT+child)->data);
    
    	//开始逆序寻找根节点,及生成编码
    	for(i=n-1; parent!=-1; i--)  //当前结点不是根结点 ,逆序
    		if((HT+parent)->lchild==child) { //他的双亲指向的左孩子是不是我们当前遍历的这个叶子
    			str[j++] = '0';
    			child = parent;///此时parent!=-1 ,表示还有父节点 
    			parent=(HT+child)->parent;
    		} else {
    			str[j++] = '1';//实现编码
    			child = parent;
    			parent=(HT+child)->parent;
    		}
    	e=j;//表示一个叶子结点的编码结束
    
    }//一次获取一个字符的编码,时间复杂度为O(n)
    
    

    过程类似如图(借图):在这里插入图片描述
    3.打印所有的字符的编码

    for(int k=0; k<n; k++) {
    		HuffmanTreeCode(HT,str,n,k,e) ;
    		for(int j=e-1;j>=0 ; j--)
    			printf("%c ",str[j]);
    		printf("\n\n");
    	}
    

    上图:
    在这里插入图片描述
    在这里插入图片描述
    源代码

    #include "stdio.h"
    #include "malloc.h"
    #include "string.h"
    #include "string"
    
    //定义哈曼夫树的结构
    typedef struct {
    	int data;//data域存储权值
    	int parent,lchild,rchild;//双亲与孩子
    } HTNode,*HuffmanTree;
    
    /*typedef struct{
    	string<char> str;
    
    }HuffmanTreenode,*HuffmancodeTree;*/
    //哈曼夫树的初始化 
    void InitHuffmanTree(HuffmanTree H,int weight,int parent,int lchild,int rchild)
    {
    	//HT = (HuffmanTree)malloc(n*sizeof(HTNode));//空间分配
    	H->lchild=lchild;
    	H->rchild=rchild;
    	H->parent =parent;
    	H->data = weight;
    }
    
    //建立哈夫曼树!
    void CreateHuffmanTree(HuffmanTree &HT,int n,int *W)
    {
    	//叶子结点的初始化,相当于n棵树,每颗树只有一个结点,那么最后构造过程总的结点个数为:2*n-1 
    	//n-1+n = 2*n-1 
    
    	HT = (HuffmanTree)malloc((2*n-1)*sizeof(HTNode));//n个叶子结点的哈夫曼树结点是2n-1;
    	for(int i=0; i<n; i++) {
    		InitHuffmanTree(HT+i,W[i],-1,-1,-1);//初始化-1 
    	}
    	//开始寻找最小的两个叶子结点,构造哈夫曼树
    	for(int i=n; i<2*n-1; i++) { //我们构造n-1个度为2的结点
    		int min1=65522,min2=min1;//这里的两个数分别代表第一小,第二小
    		int x1=-1,x2=-1;//用来记录下标
    		for(int j=0; j<i; j++) {
    			if((HT+j)->parent==-1)//表示叶子结点没有父母
    				if((HT+j)->data<min1) {
    					min2=min1;
    					min1=(HT+j)->data;
    					x2=x1;
    					x1=j;
    				} else if((HT+j)->data<min2) {
    					min2=(HT+j)->data;
    					x2=j;
    
    				}
    		}
    		//合并两个叶子,让他们有同一个双亲
    		(HT+x1)->parent =i;
    		(HT+x2)->parent =i;
    		//然后我们让HT[i]指向这两个孩子,为了后来的逆序哈夫曼编码
    
    		InitHuffmanTree(HT+i,min2+min1,-1,x1,x2) ;//父结点构造 
    	}
    }
    //完成哈夫曼树的生成;
    
    //获得哈夫曼编码,n是指叶子个数,path是我们要获得的字符的编码 
    void HuffmanTreeCode(HuffmanTree HT,char *str,int n,int path,int &e)
    {
    	int i=0,j=0,m=0;
    	int child =path;//假设我们现在在叶子结点为child索引的地方,如1
    
    	int parent = (HT+child)->parent;//获取第一个叶子结点的父节点 的值 
    	//printf("leafe node is:%d \n",(HT+child)->data);
    
    	//开始逆序寻找根节点,及生成编码
    	for(i=n-1; parent!=-1; i--)  //当前结点不是根结点 ,逆序
    		if((HT+parent)->lchild==child) { //他的双亲指向的左孩子是不是我们当前遍历的这个叶子
    			str[j++] = '0';
    			child = parent;///此时parent!=-1 ,表示还有父节点 
    			parent=(HT+child)->parent;
    		} else {
    			str[j++] = '1';//实现编码
    			child = parent;
    			parent=(HT+child)->parent;
    		}
    	e=j;//表示一个叶子结点的编码结束
    
    }
    
    
    int main()
    {
    	int i,n;
    	int *w,e;
    
    	HuffmanTree HT;
    	//printf("Node Number:");
    	scanf("%d",&n);  //权值个数
    	w=(int *)malloc(n*sizeof(int)); //权值数组
    	//printf("Input weights:");
    	for ( i=0; i<n; i++) //录入权值
    		scanf("%d",&w[i]);
    	CreateHuffmanTree(HT,n,w);
    	//printf("the first node is:%d\n",HT->data);
    	//printf("create sussessfully\n");
    
    	//定义一个数组存储哈夫曼编码
    	char str[n];
    	for(int k=0; k<n; k++) {
    		HuffmanTreeCode(HT,str,n,k,e) ;
    		for(int j=e-1;j>=0 ; j--)
    			printf("%c",str[j]);
    		printf("\n");
    	}
    	free(HT);
    	return 0;
    }//main
    
    展开全文
  • 哈夫曼树和哈夫曼树编码一、名词介绍二、哈夫曼树的基本概念三、构建哈夫曼树四、哈弗曼树中结点结构五、哈弗曼树中的查找算法六、构建哈弗曼树的代码实现七、哈夫曼编码八、完整代码(可运行)九、总结 一、名词...

    一、名词介绍

    (1)路径:在一棵树中,一个结点到另一个结点之间的通路,称为路径。图 1 中,从根结点到结点 a 之间的通路就是一条路径。

    (2)路径长度:在一条路径中,每经过一个结点,路径长度都要加 1 。例如在一棵树中,规定根结点所在层数为1层,那么从根结点到第 i 层结点的路径长度为 i - 1 。图 1 中从根结点到结点 c 的路径长度为 3。

    (3)结点的权:给每一个结点赋予一个新的数值,被称为这个结点的权。例如,图 1 中结点 a 的权为 7,结点 b 的权为 5。

    (4)结点的带权路径长度:指的是从根结点到该结点之间的路径长度与该结点的权的乘积。例如,图 1 中结点 b 的带权路径长度为 2 * 5 = 10 。

    树的带权路径长度为树中所有叶子结点的带权路径长度之和。通常记作 “WPL” 。例如图 1 中所示的这颗树的带权路径长度为:

    WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3

    在这里插入图片描述

    二、哈夫曼树的基本概念

    当用 n 个结点(都做叶子结点且都有各自的权值)试图构建一棵树时,如果构建的这棵树的带权路径长度最小,称这棵树为“最优二叉树”,有时也叫“赫夫曼树”或者“哈夫曼树”

    在构建哈弗曼树时,要使树的带权路径长度最小,只需要遵循一个原则,那就是:权重越大的结点离树根越近。在图 1 中,因为结点 a 的权值最大,所以理应直接作为根结点的孩子结点。

    三、构建哈夫曼树

    对于给定的有各自权值的 n 个结点,构建哈夫曼树有一个行之有效的办法:
    (1)在 n 个权值中选出两个最小的权值,对应的两个结点组成一个新的二叉树,且新二叉树的根结点的权值为左右孩子权值的和;
    (2)在原有的 n 个权值中删除那两个最小的权值,同时将新的权值加入到 n–2 个权值的行列中,以此类推;
    (3)重复 1 和 2 ,直到所以的结点构建成了一棵二叉树为止,这棵树就是哈夫曼树。
    在这里插入图片描述
    上图中,(A)给定了四个结点a,b,c,d,权值分别为7,5,2,4;第一步如(B)所示,找出现有权值中最小的两个,2 和 4 ,相应的结点 c 和 d 构建一个新的二叉树,树根的权值为 2 + 4 = 6,同时将原有权值中的 2 和 4 删掉,将新的权值 6 加入;进入(C),重复之前的步骤。直到(D)中,所有的结点构建成了一个全新的二叉树,这就是哈夫曼树。

    四、哈弗曼树中结点结构

    构建哈夫曼树时,首先需要确定树中结点的构成。由于哈夫曼树的构建是从叶子结点开始,不断地构建新的父结点,直至树根,所以结点中应包含指向父结点的指针。但是在使用哈夫曼树时是从树根开始,根据需求遍历树中的结点,因此每个结点需要有指向其左孩子和右孩子的指针。

    所以,哈夫曼树中结点构成用代码表示为:

    //哈夫曼树结点结构
    typedef struct 
    {
      int weight;  //结点权重
      int parent, left, right;  //父结点、左孩子、右孩子在数组中的位置下标
    }HTNode, *HuffmanTree;

    五、哈弗曼树中的查找算法

    构建哈夫曼树时,需要每次根据各个结点的权重值,筛选出其中值最小的两个结点,然后构建二叉树。

    查找权重值最小的两个结点的思想是:从树组起始位置开始,首先找到两个无父结点的结点(说明还未使用其构建成树),然后和后续无父结点的结点依次做比较,有两种情况需要考虑:

    (1)如果比两个结点中较小的那个还小,就保留这个结点,删除原来较大的结点;
    (2)如果介于两个结点权重值之间,替换原来较大的结点;

    代码实现:

    //HT数组中存放的哈夫曼树,end表示HT数组中存放结点的最终位置,s1和s2传递的是HT数组中权重值最小的两个结点在数组中的位置
    void Select(HuffmanTree HT, int end, int *s1, int *s2)
    {
      int min1, min2;
      //遍历数组初始下标为 1
      int i = 1;
      //找到还没构建树的结点
      while(HT[i].parent != 0 && i <= end)
      {
        i++;
      }
      min1 = HT[i].weight;
      *s1 = i;
      i++;
      while(HT[i].parent != 0 && i <= end)
      {
        i++;
      }
      //对找到的两个结点比较大小,min2为大的,min1为小的
      if(HT[i].weight < min1)
      {
        min2 = min1;
        *s2 = *s1;
        min1 = HT[i].weight;
        *s1 = i;
      }
      else
      {
        min2 = HT[i].weight;
        *s2 = i;
      }
      //两个结点和后续的所有未构建成树的结点做比较
      for(int j=i+1; j <= end; j++)
      {
        //如果有父结点,直接跳过,进行下一个
        if(HT[j].parent != 0)
        {
          continue;
        }
        //如果比最小的还小,将min2=min1,min1赋值新的结点的下标
        if(HT[j].weight < min1)
        {
          min2 = min1;
          min1 = HT[j].weight;
          *s2 = *s1;
          *s1 = j;
        }
        //如果介于两者之间,min2赋值为新的结点的位置下标
        else if(HT[j].weight >= min1 && HT[j].weight < min2)
        {
          min2 = HT[j].weight;
          *s2 = j;
        }
      }
    }

    注意:s1和s2传入的是实参的地址,所以函数运行完成后,实参中存放的自然就是哈夫曼树中权重值最小的两个结点在数组中的位置。

    六、构建哈弗曼树的代码实现

    //HT为地址传递的存储哈夫曼树的数组,w为存储结点权重值的数组,n为结点个数
    void CreateHuffmanTree(HuffmanTree *HT, int *w, int n)
    {
      if(n <= 1) 
        return;   // 如果只有一个编码就相当于0
      int m = 2*n-1;   // 哈夫曼树总节点数,n就是叶子结点
      *HT = (HuffmanTree) malloc((m+1) * sizeof(HTNode));   // 0号位置不用
      HuffmanTree p = *HT;
      // 初始化哈夫曼树中的所有结点
      for(int i = 1; i <= n; i++)
      {
        (p+i)->weight = *(w+i-1);
        (p+i)->parent = 0;
        (p+i)->left = 0;
        (p+i)->right = 0;
      }
      //从树组的下标 n+1 开始初始化哈夫曼树中除叶子结点外的结点
      for(int i = n+1; i <= m; i++)
      {
        (p+i)->weight = 0;
        (p+i)->parent = 0;
        (p+i)->left = 0;
        (p+i)->right = 0;
      }
      //构建哈夫曼树
      for(int i = n+1; i <= m; i++)
      {
        int s1, s2;
        Select(*HT, i-1, &s1, &s2);
        (*HT)[s1].parent = (*HT)[s2].parent = i;
        (*HT)[i].left = s1;
        (*HT)[i].right = s2;
        (*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
      }
    }

    七、哈夫曼编码

    哈夫曼编码就是在哈夫曼树的基础上构建的,这种编码方式最大的优点就是用最少的字符包含最多的信息内容

    根据发送信息的内容,通过统计文本中相同字符的个数作为每个字符的权值,建立哈夫曼树。对于树中的每一个子树,统一规定其左孩子标记为 0 ,右孩子标记为 1 。这样,用到哪个字符时,从哈夫曼树的根结点开始,依次写出经过结点的标记,最终得到的就是该结点的哈夫曼编码。

    文本中字符出现的次数越多,在哈夫曼树中的体现就是越接近树根,编码的长度越短

    在这里插入图片描述
    如上图所示,字符 a 用到的次数最多,其次是字符 b 。字符 a 在哈夫曼编码是 0 ,字符 b 编码为 10 ,字符 c 的编码为 110 ,字符 d 的编码为 111 。

    使用程序求哈夫曼编码有两种方法:

    1)从叶子结点一直找到根结点,逆向记录途中经过的标记。
    例如,图 3中字符 c 的哈夫曼编码从结点 c 开始一直找到根结点,结果为:0 1 1 ,所以字符 c 的哈夫曼编码为:1 1 0(逆序输出)。
    
    (2)从根结点出发,一直到叶子结点,记录途中经过的标记。
    例如,求图 中字符 c 的哈夫曼编码,就从根结点开始,依次为:1 1 0

    采用方法(1)的实现代码为:

    //HT为哈夫曼树,HC为存储结点哈夫曼编码的二维动态数组,n为结点的个数
    void HuffmanCoding(HuffmanTree HT, HuffmanCode *HC, int n)
    {
      *HC = (HuffmanCode) malloc((n+1) * sizeof(char *));
      char *cd = (char *)malloc(n*sizeof(char)); //存放结点哈夫曼编码的字符串数组
      cd[n-1] = '\0';//字符串结束符
      for(int i=1; i<=n; i++)
      {
        //从叶子结点出发,得到的哈夫曼编码是逆序的,需要在字符串数组中逆序存放
        int start = n-1;
        //当前结点在数组中的位置
        int c = i;
        //当前结点的父结点在数组中的位置
        int j = HT[i].parent;
        // 一直寻找到根结点
        while(j != 0)
        {
          // 如果该结点是父结点的左孩子则对应路径编码为0,否则为右孩子编码为1
          if(HT[j].left == c)
            cd[--start] = '0';
          else
            cd[--start] = '1';
          //以父结点为孩子结点,继续朝树根的方向遍历
          c = j;
          j = HT[j].parent;
        }
        //跳出循环后,cd数组中从下标 start 开始,存放的就是该结点的哈夫曼编码
        (*HC)[i] = (char *)malloc((n-start)*sizeof(char));
        strcpy((*HC)[i], &cd[start]);
      }
      //使用malloc申请的cd动态数组需要手动释放
      free(cd);
    }

    采用方法(2)的实现代码为:

    //HT为哈夫曼树,HC为存储结点哈夫曼编码的二维动态数组,n为结点的个数
    void HuffmanCoding(HuffmanTree HT, HuffmanCode *HC, int n)
    {
      *HC = (HuffmanCode) malloc((n+1) * sizeof(char *));
      int m = 2*n-1;
      int p = m;
      int cdlen = 0;
      char *cd = (char *)malloc(n*sizeof(char));
      //将各个结点的权重用于记录访问结点的次数,首先初始化为0
      for (int i=1; i<=m; i++) 
      {
        HT[i].weight = 0;
      }
      //一开始 p 初始化为 m,也就是从树根开始。一直到p为0
      while (p) 
      {
        //如果当前结点一次没有访问,进入这个if语句
        if (HT[p].weight == 0) 
        {
          HT[p].weight = 1;  //重置访问次数为1
          //如果有左孩子,则访问左孩子,并且存储走过的标记为0
          if (HT[p].left != 0) 
          {
            p = HT[p].left;
          }
          else if(HT[p].right == 0) // 当前结点没有左孩子,也没有右孩子,说明为叶子结点,直接记录哈夫曼编码
          {
            (*HC)[p] = (char*)malloc((cdlen+1)*sizeof(char));
            cd[cdlen] = '\0';
            strcpy((*HC)[p], cd);
          }
        }
        else if(HT[p].weight == 1) // 如果weiget为1,说明访问过一次,即使是左孩子返回的
        {
          HT[p].weight = 2;  //设置访问次数为2
          //如果有右孩子,遍历右孩子,记录标记值 1
          if (HT[p].right != 0) 
          {
            p = HT[p].right;
            cd[cdlen++] = '1';
          }
        }
        else //如果访问次数为2,说明左孩子都遍历完了,返回父结点
        {
          HT[p].weight = 0;
          p = HT[p].parent;
          --cdlen;
        }
      }
    }

    八、完整代码(可运行)

    #include<stdlib.h>
    #include<stdio.h>
    #include<string.h>
    
    //哈夫曼树结点结构
    typedef struct 
    {
      int weight;//结点权重
      int parent, left, right;//父结点、左孩子、右孩子在数组中的位置下标
    }HTNode, *HuffmanTree;
    //动态二维数组,存储哈夫曼编码
    typedef char **HuffmanCode;
    //HT数组中存放的哈夫曼树,end表示HT数组中存放结点的最终位置,s1和s2传递的是HT数组中权重值最小的两个结点在数组中的位置
    void Select(HuffmanTree HT, int end, int *s1, int *s2)
    {
      int min1, min2;
      //遍历数组初始下标为 1
      int i = 1;
      //找到还没构建树的结点
      while(HT[i].parent != 0 && i <= end)
      {
        i++;
      }
      min1 = HT[i].weight;
      *s1 = i;
      i++;
      while(HT[i].parent != 0 && i <= end)
      {
        i++;
      }
      //对找到的两个结点比较大小,min2为大的,min1为小的
      if(HT[i].weight < min1)
      {
        min2 = min1;
        *s2 = *s1;
        min1 = HT[i].weight;
        *s1 = i;
      }
      else
      {
        min2 = HT[i].weight;
        *s2 = i;
      }
      //两个结点和后续的所有未构建成树的结点做比较
      for(int j=i+1; j <= end; j++)
      {
        //如果有父结点,直接跳过,进行下一个
        if(HT[j].parent != 0)
        {
          continue;
        }
        //如果比最小的还小,将min2=min1,min1赋值新的结点的下标
        if(HT[j].weight < min1)
        {
          min2 = min1;
          min1 = HT[j].weight;
          *s2 = *s1;
          *s1 = j;
        }
        else if(HT[j].weight >= min1 && HT[j].weight < min2)   // 如果介于两者之间,min2赋值为新的结点的位置下标
        {
          min2 = HT[j].weight;
          *s2 = j;
        }
      }
    }
    
    //HT为地址传递的存储哈夫曼树的数组,w为存储结点权重值的数组,n为结点个数
    void CreateHuffmanTree(HuffmanTree *HT, int *w, int n)
    {
      if(n<=1) 
        return;     // 如果只有一个编码就相当于0
      int m = 2*n-1;   // 哈夫曼树总节点数,n就是叶子结点
      *HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0号位置不用
      HuffmanTree p = *HT;
      // 初始化哈夫曼树中的所有结点
      for(int i = 1; i <= n; i++)
      {
        (p+i)->weight = *(w+i-1);
        (p+i)->parent = 0;
        (p+i)->left = 0;
        (p+i)->right = 0;
      }
    
      //从树组的下标 n+1 开始初始化哈夫曼树中除叶子结点外的结点
      for(int i = n+1; i <= m; i++)
      {
        (p+i)->weight = 0;
        (p+i)->parent = 0;
        (p+i)->left = 0;
        (p+i)->right = 0;
      }
    
      //构建哈夫曼树
      for(int i = n+1; i <= m; i++)
      {
        int s1, s2;
        Select(*HT, i-1, &s1, &s2);
        (*HT)[s1].parent = (*HT)[s2].parent = i;
        (*HT)[i].left = s1;
        (*HT)[i].right = s2;
        (*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
      }
    }
    
    //HT为哈夫曼树,HC为存储结点哈夫曼编码的二维动态数组,n为结点的个数
    void HuffmanCoding(HuffmanTree HT, HuffmanCode *HC, int n)
    {
      *HC = (HuffmanCode) malloc((n+1) * sizeof(char *));
      char *cd = (char *)malloc(n*sizeof(char)); //存放结点哈夫曼编码的字符串数组
      cd[n-1] = '\0';//字符串结束符
      for(int i=1; i<=n; i++)
      {
        //从叶子结点出发,得到的哈夫曼编码是逆序的,需要在字符串数组中逆序存放
        int start = n-1;
        //当前结点在数组中的位置
        int c = i;
        //当前结点的父结点在数组中的位置
        int j = HT[i].parent;
        // 一直寻找到根结点
        while(j != 0)
        {
          // 如果该结点是父结点的左孩子则对应路径编码为0,否则为右孩子编码为1
          if(HT[j].left == c)
            cd[--start] = '0';
          else
            cd[--start] = '1';
          //以父结点为孩子结点,继续朝树根的方向遍历
          c = j;
          j = HT[j].parent;
        }
        //跳出循环后,cd数组中从下标 start 开始,存放的就是该结点的哈夫曼编码
        (*HC)[i] = (char *)malloc((n-start)*sizeof(char));
        strcpy((*HC)[i], &cd[start]);
      }
      //使用malloc申请的cd动态数组需要手动释放
      free(cd);
    }
    
    //打印哈夫曼编码的函数
    void PrintHuffmanCode(HuffmanCode htable, int *w, int n)
    {
      printf("Huffman code : \n");
      for(int i = 1; i <= n; i++)
        printf("%d code = %s\n",w[i-1], htable[i]);
    }
    
    int main(void)
    {
      int w[5] = {2, 8, 7, 6, 5};
      int n = 5;
      HuffmanTree htree;
      HuffmanCode htable;
      CreateHuffmanTree(&htree, w, n);
      HuffmanCoding(htree, &htable, n);
      PrintHuffmanCode(htable, w, n);
    
      return 0;
    }

    运行结果:

    Huffman code :
    2 code = 100
    8 code = 11
    7 code = 01
    6 code = 00
    5 code = 101

    九、总结

    程序运行效果图如下:
    在这里插入图片描述
    本节的程序中对权重值分别为 2,8,7,6,5 的结点构建的哈夫曼树如上图(A)所示。图 中(B)是另一个哈夫曼树,两棵树的带权路径长度相同。

    程序运行效果图之所以是(A)而不是(B),原因是在构建哈夫曼树时,结点 2 和结点 5 构建的新的结点 7 存储在动态树组的最后面,所以,在程序继续选择两个权值最小的结点时,直接选择了的叶子结点 6 和 7 。

    展开全文
  • 主要为大家详细介绍了C++实现哈夫曼树编码解码,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 哈夫曼树编码-C语言

    千次阅读 多人点赞 2019-11-10 17:02:45
    哈夫曼树编码 1.实验目的 了解二叉树的定义,理解二叉树的基本性质和存储结构,掌握哈夫曼树的构造,实现哈夫曼编码与译码算法。 2.实验内容 从键盘输入一串电文字符与权值,输出对应的哈夫曼编码;从键盘输入一...
  • 哈夫曼树编码

    2007-07-06 23:29:43
    哈夫曼树编码 <br>C++实现
  • 哈夫曼树及哈夫曼编码 C++代码实现

    万次阅读 多人点赞 2010-11-15 21:36:00
    /*哈夫曼编码*/ #include <iostream> using namespace std; //***********************...//构造哈夫曼树 //******************************** /*哈夫曼树顺序表的定义*/ typedef struct { intweight; ...
  • 数据结构课程 实验报告 实验名称 哈弗曼编码和译码 专业班级 电子信息科学与技术0904 姓 名 秦杰 学 号 1404090506 指导教师 胡志坤 2011年 11月 实验四哈夫曼编码和译码 实验目的和要求 掌握哈夫曼树的基本概念及其...
  • 实现哈夫曼树编码的算法可分为两大部分:(1)构造哈夫曼树;(2)在哈夫曼树上求叶结点的编码;哈夫曼树构造算法:(1)由给定的n个权值构造n棵只有一个叶结点的二叉树,从而得到一个二叉树的集合F={T1,T2,,...,TN}(2)...
  • 哈夫曼树编码解码.c

    2019-11-21 19:16:53
    该文件是关于用C语言构建哈夫曼树代码,其中包括对字符的统计、对文档读取然后包括建树的过程,和对哈夫曼树解码的过程。
  • 数据结构课程设计哈夫曼树编码解码。
  • 哈夫曼树及哈夫曼编码详解【完整版代码

    万次阅读 多人点赞 2018-06-17 11:42:30
    赫夫曼(Huffman Tree),又称最优二叉树,是一类带权路径长度最短的。假设有n个权值{w1,w2,…,wn},如果构造一棵有n个叶子节点的二叉树,而这n个叶子节点的权值是{w1,w2,…,wn},则所构造出的带权路径长度最小...
  • #include<stdio.h> #define n 8 #define m (2*n-1) //创建结点结构体 typedef struct huffnode { int weight; int parent; int lchild; int rchild; }huffnode; //创建每个字母的结构体 ...//存放每一个
  • 主要介绍了Python完成哈夫曼树编码过程及原理详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,539
精华内容 3,015
关键字:

哈夫曼树编码代码