文档介绍：精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
实验四 哈夫曼编码的贪心算法设计（4 //在(*ht)[1]~(*ht)[i-1]的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给s1、s2
Select(ht,i-1,&s1,&s2);
(*ht)[s1].parent=i;
(*ht)[s2].parent=i;
(*ht)[i].LChild=s1;
(*ht)[i].RChild=s2;
(*ht)[i].weight=(*ht)[s1].weight+(*ht)[s2].weight;
printf("%d (%d, %d)\n",(*ht)[i].weight,(*ht)[s1].weight,(*ht)[s2].weight);
}
printf("\n");
}
//从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码
void CrtHuffmanCode(HuffmanTree *ht, HuffmanCode *hc, int n)
{
char *cd; //定义的存放编码的空间
int a[100];
int i,start,p,w=0;
unsigned int c;
hc=(HuffmanCode *)malloc((n+1)*sizeof(char *)); //分配n个编码的头指针
cd=(char *)malloc(n*sizeof(char)); //分配求当前编码的工作空间
cd[n-1]='\0'; //从右向左逐位存放编码，首先存放编码结束符
for(i=1; i<=n; i++) //求n个叶子结点对应的哈夫曼编码
{
a[i]=0;
start=n-1; //起始指针位置在最右边
for(c=i,p=(*ht)[i].parent; p!=0; c=p,p=(*ht)[p].parent) //从叶子到根结点求编码
{
if( (*ht)[p].LChild==c)
{
cd[--start]='1'; //左分支标1
a[i]++;
}
else
精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
{
cd[--start]='0'; //右分支标0
a[i]++;
}
}
hc[i]=(char *)malloc((n-start)*sizeof(char)); //为第i个编码分配空间
strcpy(hc[i],&cd[start]); //将cd复制编码到hc
}
free(cd);
for(i=1; i<=n; i++)
printf(" 权值为%d的哈夫曼编码为：%s\n",(*ht)[i].weight,hc[