已知某系统在通信联络中只可能出现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
授权协议：创作共用 署名-非商业性使用 2.5 中国大陆除注明外，本站文章均为原创；转载时请保留上述链接。