#include<stdio.h> 
#include<conio.h> 
#include<iostream.h> 
#include<string.h> 
#include<stdlib.h> 

#define MAXVALUE 10000 /*權值最大值*/ 
#define MAXLEAF 30 /*葉子最多個數*/ 
#define MAXNODE MAXLEAF*2-1 /* 結點數的個數*/ 
#define MAXBIT 50 /*編碼的最大位數*/ 

typedef struct node /*結點類型定義*/ 
{ 
char letter; 
int weight; 
int parent; 
int lchild; 
int rchild; 
}HNodeType; 

typedef struct /*編碼類型定義*/ 
{ 
char letter; 
int bit[MAXBIT]; 
int start; 
}HCodeType; 

typedef struct /*輸入符號的類型*/ 
{ 
char s; 
int num; 
}lable; 

void HuffmanTree(HNodeType HuffNode[],int n,lable a[]) 
{ 
int i,j,m1,m2,x1,x2,temp1; 
char temp2; 
for(i=0;i<2*n-1;i++) /*結點初始化*/ 
{ 
HuffNode[i].letter=NULL; 
HuffNode[i].weight=0; 
HuffNode[i].parent=-1; 
HuffNode[i].lchild=-1; 
HuffNode[i].rchild=-1; 
} 
for(i=0;i<n-1;i++) 

for(j=i+1;j<n-1;j++) /*對輸入字符按權值大小進行排序*/ 
if(a[j].num>a[i].num) 
{ 
temp1=a[i].num; 
a[i].num=a[j].num; 
a[j].num=temp1; 
temp2=a[i].s; 
a[i].s=a[j].s; 
a[j].s=temp2; 
} 

for(i=0;i<n;i++) 
{ 
HuffNode[i].weight=a[i].num; 
HuffNode[i].letter=a[i].s; 
} 
for(i=0;i<n-1;i++) /*構造huffman樹*/ 
{ 
m1=m2=MAXVALUE; 
x1=x2=0; 
for(j=0;j<n+i;j++)/*尋找權值最小與次小的結點*/ 
{ 
if(HuffNode[j].parent==-1&&HuffNode[j].weight<m1) 
{ 
m2=m1; 
x2=x1; 
m1=HuffNode[j].weight; 
x1=j; 
} 
else if(HuffNode[j].parent==-1&&HuffNode[j].weight<m2) 
{ 
m2=HuffNode[j].weight; 
x2=j; 
} 
} 
HuffNode[x1].parent=n+i; 
HuffNode[x2].parent=n+i; /*權值最小與次小的結點進行組合*/ 
HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight; 
HuffNode[n+i].lchild=x1; 
HuffNode[n+i].rchild=x2; 
} 
} 

void HuffmanCode(int n,lable a[]) 
{ 
HNodeType HuffNode[MAXNODE]; 
HCodeType HuffCode[MAXLEAF],cd; 
int i,j,c,p; 

HuffmanTree(HuffNode,n,a); 

for(i=0;i<n;i++) /*按結點位置進行編碼*/ 
{ 
cd.start=n-1; 
c=i; 
p=HuffNode[c].parent; 
while(p!=-1) 
{ 
if(HuffNode[p].lchild==c) 
cd.bit[cd.start]=0; 
else cd.bit[cd.start]=1; 
cd.start--; 
c=p; 
p=HuffNode[c].parent;} 
for(j=cd.start+1;j<n;j++) /*儲存編碼*/ 
HuffCode[i].bit[j]=cd.bit[j]; 
HuffCode[i].start=cd.start; 
} 
for(i=0;i<n;i++) 
{ 
HuffCode[i].letter=HuffNode[i].letter; 
printf(" %c ",HuffCode[i].letter); 

for(j=HuffCode[i].start+1;j<n;j++) 
printf("%d",HuffCode[i].bit[j]); 
printf("\n"); 
} 
} 

void main() 
{ 
lable data[30]; 
char s[100],*p; 
int i,count=0; 
for(;;) 
{ 
cout<<" /*----------------------------------------------/"<<endl; 
cout<<" / 求哈夫曼編碼,直到輸入為end結束! /"<<endl; 
cout<<" /*----------------------------------------------/"<<endl; 

printf(" Input some letters:"); 
scanf("%s",&s); 
if(!strcmp(s,"end")) 
exit(0); 
for(i=0;i<30;i++) 
{ 
data[i].s=NULL; 
data[i].num=0; 
} 
p=s; 
while(*p) /*計算字符個數與出現次數(即權值)*/ 
{ 
for(i=0;i<=count+1;i++) 
{ 
if(data[i].s==NULL) 
{ 
data[i].s=*p; 
data[i].num++; 
count++; 
break; 
} 
else if(data[i].s==*p) 
{ 
data[i].num++; 
break; 
} 
} 
p++; 
} 
printf("\n"); 
printf(" different letters:%d\n",count); 

for(i=0;i<count;i++) 
{ 
printf(" %c ",data[i].s); 
printf("weight:%d",data[i].num); 
printf("\n"); 
} 
HuffmanCode(count,data); 
count=0; 
} 

getch(); 
}