哈夫曼编码

已知某系统在通信联络中只可能出现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
#include
#include
#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]='';
                   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]!='')//从根结点到叶子节点去匹配，输出最后的那个权值
         {
       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
数据结构