#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#define Maxsize 100
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;//定义节点
typedef char * *HuffmanCode;
void Select(HuffmanTree HT,int n,int &s1,int &s2) //选出两个权值最小的两个节点
{
int i;
s1=s2=0;
for(i=1;i<=n;i++){
if(HT[i].weight<HT[s2].weight&&HT[i].parent==0&&s2!=0){
if(HT[i].weight<HT[s1].weight) {
s2=s1;
s1=i;
}
else s2=i;
}
if((s1==0||s2==0)&&HT[i].parent==0){
if(s1==0) s1=i;
else if(s2==0) {
if(HT[i].weight<HT[s1].weight) {
s2=s1;
s1=i;
}
else s2=i;
} // end of else if
} // end of if
} // end of for
// if(s1>s2) {
// i=s1; s1=s2; s2=i; }
}
void HuffmanCoding(HuffmanTree &Ht,HuffmanCode &HC,int *w,int n){
if(n<=1)
return ;
int m=2*n-1;
HuffmanTree HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用
HuffmanTree p;
int i;
for(p=HT,i=1;i<=n;++i,++p,++w){//初始化
//*p={*w,0,0,0,0};
p->weight=*w;
p->lchild=0;
p->parent=0;
p->rchild=0;
}
for(;i<=m;i++,++p){//初始化
// *p={0,0,0,0};
p->weight=0;
p->lchild=0;
p->parent=0;
p->rchild=0;
}
for(i=n+1;i<=m;++i){//创建哈弗曼树
int s1,s2;
Select(HT,i-1,s1,s2);
HT[s1].parent=i;
HT[s2].parent=i;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//动态分配储存单元保存哈弗曼编码
char* cd=(char*)malloc(n*sizeof(char));
cd[n-1]='\0';
for(i=1;i<=n;++i){
int start=n-1;
for(int c=i,int f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
if(HT[f].lchild=='c')
cd[--start]='0';
else
cd[--start]='1';
HC[i]=(char*)malloc((n-start)*sizeof(char));
strcpy(HC[i],&cd[start]);//复制编码
}
free(cd);//释放内存
}
void OutputHuffmanCode(HuffmanTree HT,HuffmanCode HC,int n) //输出哈弗曼编码
{
int i;
printf("\nnumber---weight---huffman code\n");
for(i=1;i<=n;i++)
printf(" %d %d %s\n",HT[i].weight,HC[i]);
}
int main(){
HuffmanTree HT;
int n,w[Maxsize];
printf("请输入你要创建的哈夫曼树的节点的个数:\n");
scanf("%d",&n);
char number;
for(int i=0;i<n;i++){
printf("请输入各节点的权值");
scanf("%d",&w[i]);
}
HuffmanCode HC;
HuffmanCoding(HT,HC,w,n);
OutputHuffmanCode(HT,HC,n);
/*for(i=1;i<=n;i++){
printf("%s\n",HC[i]);
}*/
}