#include <stdio.h>
#include<conio.h>
#include<string.h>
#define N 10 /*待編碼字符的個(gè)數(shù)，即樹(shù)中葉結(jié)點(diǎn)的最大個(gè)數(shù)*/
#define M 2*N-1 /*樹(shù)中總的結(jié)點(diǎn)數(shù)目*/
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode; /*樹(shù)中結(jié)點(diǎn)的結(jié)構(gòu)*/
typedef struct {
char data; /*待編碼的字符*/
int weight; /*字符的權(quán)值 */
char code[N]; /*字符的編碼 */
} HTCode;
void Init(HTCode hc[],int *n){
/*初始化，讀入待編碼字符的個(gè)數(shù)n，從鍵盤輸入n個(gè)字符和n個(gè)權(quán)值*/
int i;
printf("\n輸入待編碼字符的個(gè)數(shù)n：n=");
scanf("%d",&(*n));
printf("\n依次輸入 %d個(gè)字符\n",*n);
for (i=1;i<=*n;i++)
{ hc[i].data=getch();
printf("%c",hc[i].data);}
printf("\n依次輸入 %d 個(gè)字符的權(quán)值，以空格隔開(kāi)\n",*n);
for (i=1;i<=*n;i++) scanf("%d",&(hc[i].weight));
}
void Select(HTNode ht[],int k,int *s1,int *s2){
/*ht[1…k]中選擇parent為0，并且weight最小的兩個(gè)結(jié)點(diǎn)
其序號(hào)由指針變量s1,s2指向*/
int i;
for (i=1;i<=k && ht[i].parent!=0 ;i++);
*s1=i;
for (i=1;i<=k;i++)
if (ht[i].parent==0 && ht[i].weight<ht[*s1].weight) *s1=i;
for (i=1; i<=k ; i++)
if (ht[i].parent==0 && i!=*s1) break;
*s2=i;
for (i=1;i<=k;i++)
if ( ht[i].parent==0 && i!=*s1 && ht[i].weight<ht[*s2].weight) *s2=i;
}
void HuffmanCoding(HTNode ht[],HTCode hc[],int n){
/*構(gòu)造Huffman樹(shù)ht，并求出n個(gè)字符的編碼*/
char cd[N];
int i,j,m,c,f,s1,s2,start;
m=2*n-1;
for (i=1;i<=m;i++){
if (i<=n) ht[i].weight=hc[i].weight;
else ht[i].weight=0;
ht[i].parent=ht[i].lchild=ht[i].rchild=0;
}
for (i=n+1;i<=m;i++){
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;
}
cd[n-1]='\0';
for (i=1;i<=n;i++) {
start=n-1;
for (c=i,f=ht[i].parent;f;c=f,f=ht[f].parent)
if (ht[f].lchild==c) cd[--start]='0';
else cd[--start]='1';
strcpy(hc[i].code,&cd[start]);
}
}
void main(){
int i,m,n,w[N+1];
HTNode ht[M+1];
HTCode hc[N+1];
Init(hc,&n); /*初始化*/
HuffmanCoding(ht,hc,n);/*構(gòu)造Huffman樹(shù)，并形成字符的編碼*/
/*輸出字符的編碼*/
for (i=1;i<=n;i++)printf("\n%c --- %s",hc[i].data,hc[i].code);
}
