赫夫曼树编码的算法及应用习题--数据结构

痛定思痛。 2022-04-10 01:29 156阅读 0赞

# **赫夫曼树编码的算法及应用习题** #

**1.构造赫夫曼树的方法**

1.根据给定的n个权值\{w1,w2,---wn\},构成n棵二叉树的集合F=\{T1,T2...,Tn\}，其中每棵二叉树中只有一个带权为Wi的根结点，其左右子树为空。

2.在F中选取两棵根结点的权值最小的树作为左右子树（一般小左大右）构造新的二叉树，且置新的二叉树的权值为两棵子树权值之和。

3.在F中删除这两个树，同时将新树加入到F中。

4.重复2、3两步，直到F中只有一棵树。

具体实例：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmcxMzU2Mzc1ODEyOA_size_16_color_FFFFFF_t_70][]

**2.赫夫曼编码：**

**编码：从叶子结点到根结点的最短路径**

**译码：从根结点到叶子结点的最短路径**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmcxMzU2Mzc1ODEyOA_size_16_color_FFFFFF_t_70 1][]

**具体算法实现：**

/*求赫夫曼编码。实现算法6.12的程序 */
    
     typedef struct
     {
       unsigned int weight;
       unsigned int parent,lchild,rchild;
     }HTNode,*HuffmanTree; /* 动态分配数组存储赫夫曼树 */
     typedef char **HuffmanCode; /* 动态分配数组存储赫夫曼编码表 */
    
    
     #include<string.h>
     #include<malloc.h> /* malloc()等 */
     #include<limits.h> /* UINT_MAX ，C中常量INT_MAX和INT_MIN分别表示最大、最小整数*/
     #include<stdio.h> 
    
    
    
     int min1(HuffmanTree t,int i)
     { /* 函数void select()调用 
        求赫夫曼树中结点权值最小的的是哪个二叉树*/
       int j,flag;              //flag是用来标记第几个结点
       unsigned int k=UINT_MAX; /* 取k为不小于可能的值，无符号整型最大值 */
       for(j=1;j<=i;j++)
         if(t[j].weight<k&&t[j].parent==0)
           k=t[j].weight,flag=j;
       t[flag].parent=1;
       return flag;
     }
    
     void select(HuffmanTree t,int i,int *s1,int *s2)
     { /* s1为最小的两个值中序号小的那个，把它作为左子树 */
       int j;
       *s1=min1(t,i);
       *s2=min1(t,i);
       if(*s1>*s2)
       {
         j=*s1;
         *s1=*s2;
         *s2=j;
       }
     }
    
     void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n) /* 算法6.12 */
     { /* w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC */
       int m,i,s1,s2,start;
       unsigned c,f;
       HuffmanTree p;
       char *cd;                        //用来存放字符
       if(n<=1)
         return;
       m=2*n-1;
       *HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /* 0号单元未用，开辟赫夫曼树的存储空间 */
       for(p=*HT+1,i=1;i<=n;++i,++p,++w)
       {
        //构建n棵带权值的叶子结点
         (*p).weight=*w;
         (*p).parent=0;
         (*p).lchild=0;
         (*p).rchild=0;
       }
       for(;i<=m;++i,++p){
        //继续使接下来要构造的赫夫曼树每个非叶子结点为空
         (*p).parent=0; 
       }
       for(i=n+1;i<=m;++i) /* 建赫夫曼树 */
       { /* 在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2 */
         select(*HT,i-1,&s1,&s2);
         (*HT)[s1].parent=(*HT)[s2].parent=i;   //把i作为一个树的根结点
         (*HT)[i].lchild=s1;
         (*HT)[i].rchild=s2;
         (*HT)[i].weight=(*HT)[s1].weight+(*HT)[s2].weight;
       }
       /* 从叶子到根逆向求每个字符的赫夫曼编码 */
       *HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
       /* 分配n个字符编码的头指针向量([0]不用) */
       cd=(char*)malloc(n*sizeof(char)); /* 分配求编码的工作空间 */
       cd[n-1]='\0'; /* 编码结束符 */
       for(i=1;i<=n;i++)
       { /* 逐个字符求赫夫曼编码 */
         start=n-1; /* 编码结束符位置 */
         for(c=i,f=(*HT)[i].parent;f!=0;c=f,f=(*HT)[f].parent)
         /* 从叶子到根逆向求编码 */
           if((*HT)[f].lchild==c)
             cd[--start]='0';
           else
             cd[--start]='1';
         (*HC)[i]=(char*)malloc((n-start)*sizeof(char));
         /* 为第i个字符编码分配空间 */
         strcpy((*HC)[i],&cd[start]); /* 从cd复制编码(串)到HC */
       }
       free(cd); /* 释放工作空间 */
     }
    
     void main()
     {
       HuffmanTree HT;
       HuffmanCode HC;
       int *w,n,i;
       printf("请输入权值的个数(>1)：");
       scanf("%d",&n);
       w=(int*)malloc(n*sizeof(int));
       printf("请依次输入%d个权值(整型)：\n",n);
       for(i=0;i<=n-1;i++)
         scanf("%d",w+i);                    //w是个指针为地址，不加&符号
       printf("赫夫曼编码为:\n");
       HuffmanCoding(&HT,&HC,w,n);
       for(i=1;i<=n;i++){
        printf("%d\t",i);
         puts(HC[i]);
       }
     }

# 欢迎关注，更多博文请浏览本人其他文章。 #

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmcxMzU2Mzc1ODEyOA_size_16_color_FFFFFF_t_70]: /images/20220404/c61a9b580afd4545b2ec17c57a02468f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmcxMzU2Mzc1ODEyOA_size_16_color_FFFFFF_t_70 1]: /images/20220404/49cb939d5d314e228c5e4587761eee06.png