Home Archives Categories Tags

C++ 哈夫曼编码

发布时间: 更新时间: 总字数:2481 阅读时间:5m 作者: 分享

哈夫曼编码

实验六:哈夫曼编码

已知某系统在通信联络中只可能出现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;          

}

参考

最新评论
加载中...