哈夫曼编码

实验六:哈夫曼编码

已知某系统在通信联络中只可能出现8种字符,其概率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,试设计哈夫曼编码。

综合训练:试编写一个将百分制分数转换为五级分制的程序。要求其时间性能尽可能好(即平均比较次数尽可能少)。假设学生成绩的分布情况如下:

分数 0-59 60-69 70-79 80-89 90-100

比例 0.05 0.15 0.40 0.30 0.10

参考源码

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#define ERROR 0

#define OK 1

typedef int Status;

typedef struct {//声明赫夫曼树的结点

         int weight;

         int parent;

         int lchild;

         int rchild;

}Htnode,*Huffmantree;

typedef char ** Huffmancode;//相当于声明一个二维数组,来记录每个权值对应的编码。

void Select (Huffmantree &HT,int t,int &p,int &q);//选择结点中权值最小的两个结点,用p,q来返回。

void creathuffmantree(Huffmantree &HT,Huffmancode &HC,int *w,int n)//创建赫夫曼树。

{

         int m,i,p,q,j,start,s;

         if(n<=1)

          return;

         m=2*n-1;//当n大于1时,就需要2*n-1个结点

         HT=(Huffmantree)malloc(sizeof(Htnode)*(m+1));//因为0不存东西,而从1开始存,所以申请m+1个空间。

         for(i=1;i<=n;i++)//对叶子结点进行初始化,除权之外全赋值为0。

         {

                   HT[i].weight=w[i-1];

                   HT[i].parent=0;

                   HT[i].rchild=0;

                   HT[i].lchild=0;

         }

         for(i=n+1;i<=m;i++)//对非叶子结点进行初始化,所有的值全为0

         {

                   HT[i].weight=0;

                   HT[i].parent=0;

                   HT[i].rchild=0;

                   HT[i].lchild=0;

         }

         for(i=n+1;i<=m;i++)//这是创建树的主要步骤,找出权值和最小的两棵树,再把它们合并成一棵树,依次进行,知道走后还剩仅有的一棵树。

         {

                   Select(HT,i-1,p,q);//这是选择权值最小的两棵树的函数,并用p,q来返回,在上面已经声明过。

                   HT[i].weight=HT[p].weight+HT[q].weight;//对刚合并的新树的根结点的权值进行赋值。

                   HT[i].lchild=p;//新树的左孩子赋为p;

                   HT[i].rchild=q;//新树的右孩子赋为q;

             HT[p].parent=i;//把他们的双亲都赋为i;

                   HT[q].parent=i;

         }

         HC=(Huffmancode)malloc(sizeof(char*)*(n+1));//申请一个大小为n+1的存放指针的数组。

         char* cd=(char*)malloc(sizeof(char)*n);//申请一个一维数组,作为一个中转站,最后把他复制到HC中的一个数组中。

 

         for(i=1;i<=n;i++)//对赫夫曼树的数组从1到n进行依次遍历,这是从叶子结点到根节点。

         {

                   start=n-1;//对这个一位数组进行倒着存,最后正着读取。

              cd[start]='\0';

                   s=i;

                   while(HT[s].parent!=0)

                   {

                            j=s;

                            s=HT[s].parent;

                            if(HT[s].lchild==j)//如果该结点是双亲结点的左孩子,应该把它赋为0;

                                     cd[--start]='0';

                            if(HT[s].rchild==j)//如果该结点是双亲结点的右孩子,应该把它赋为1;

                                     cd[--start]='1';

                   }

                   HC[i]=(char *)malloc(sizeof(char)*(n-start));

                   strcpy(HC[i],&cd[start]);//把cd数组里的内容复制到HC[i]里,再用cd去盛其他的编码。

         }

         free(cd);//最后可以把cd数组给释放了。

}

void Select (Huffmantree & HT,int t,int &min1,int &min2)//选择结点中权值最小的两个结点,用p,q来返回。

{

         int i=1,flag=0;

         while(flag<2)//这个while循环是为了找出前两棵树的根结点,把他们当成最小的两棵树,以后来做比较,求出最小的两个。

         {

           if(HT[i].parent!=0)//如果不是根结点,继续朝后找,直到找到根结点。

                     i++;

           else//如果是根结点,就把他们分别赋给min1和min2.

           {

                     if(flag==0)

             min1=i;

                     else

                              min2=i;

                    flag++;

                    i++;

           }

         }

         if(HT[min1].weight>HT[min2].weight)//对min1和min2进行比较,把最小的的付给min1,第二小的付给min2.

         {

                   t=min1;

                   min1=min2;

                   min2=t;

         }

    while(i<=t)//把以后的各个结点的权值与最小的两个比较,调整下,最后得出的就是最小的两个结点。

         {

                   if(HT[i].parent!=0)//如果不是根结点,继续朝后找,直到找到根结点。

                            i++;

                   else

                   {

                            if(HT[i].weight<=HT[min1].weight)//如果该结点的权值比最小的结点还小,把最小的两个全重新赋值。

                            {

                                     min2=min1;

                                     min1=i;

                            }

                            else if(HT[i].weight>=HT[min1].weight&&HT[i].weight<=HT[min2].weight)//如果该结点的权值在最小和第二小之间的话,

                                     //就把第二小的重新赋值。

                                     min2=i;

                            i++;

                   }

         }

 

}

Status exhuffmantree(Huffmantree &HT,int  m,char *code,int *ex,int &j)//这是解码的函数,m为那棵树的根结点,code是输入的赫夫曼码,

//解码后最后给他存到ex数组中,j为数组的长度。

{

         int i=0,k=m;

         while(code[i]!='\0')//从根结点到叶子节点去匹配,输出最后的那个权值

         {

       if(code[i]=='0'&&HT[k].lchild!=0)//如果code[i]是0,并且左孩子不为0,则继续朝叶子结点找。

            {

                k=HT[k].lchild;

                      i++;

            }

            else if(code[i]=='1'&&HT[k].rchild!=0)//如果code[i]是1,并且右孩子不为0,则继续朝叶子结点找。

            {

                      k=HT[k].rchild;

                      i++;

            }

            else if(HT[k].rchild==0&&HT[k].lchild==0)//如果是叶子结点,则把它的权值赋给ex[j].

            {

                      ex[j]=HT[k].weight;

                j++;

                      k=m;

            }

            else//其他的则返回ERROR。

                      return ERROR;

         }

         if(HT[k].rchild==0&&HT[k].lchild==0)//当跳出循环的时候,说明应该到了叶子结点,如果是叶子结点,则把它的权值赋给ex[j].

         {

                   ex[j]=HT[k].weight;

             return OK;

         }

         else//其他的则返回ERROR。

                   return ERROR;

}

int main()

{

         Huffmantree HT;

         Huffmancode HC;

         char Code[100];

         int i, n,a[100],b[100],j=0,t;

         printf("输入叶子结点的个数n为:\n");

         scanf("%d",&n);

         printf("依次输入n个叶子结点的权值为:\n");

         for(i=0;i<n;i++)

                   scanf("%d",&a[i]);

    creathuffmantree(HT,HC,a,n);

         printf("输出该赫夫曼树各个叶子结点的编码为:\n");

         for(i=1;i<=n;i++)

         {

                   t=0;

      while(HC[i][t]!='\0')

           {

                     printf("%c",HC[i][t]);

                     t++;

           }

           putchar(' ');

         }

         putchar('\n');

         getchar();

         printf("输入该赫夫曼树关联的要译码的code数组:\n");

         gets(Code);

   exhuffmantree(HT,2*n-1,Code,b,j);

         printf("输出解码后的各权值为:\n");

   for(i=0;i<=j;i++)

            printf("%d ",b[i]);

   putchar('\n');

    return 0;          

}

参考

迁移自谢先斌的博客:http://blog.sina.com.cn/s/blog_002e203101010bvn.html

完毕。