#include
#include
#include
#include

#define?MAXNUM?60
??
typedef?struct
{??
????char?ch;
????int?weight;?//權值，這個字符出現的頻率
????int?parent;
????int?left;
????int?right;
}HuffNode;
??
typedef?struct
{
????char?code[MAXNUM];
????int?start;
}HuffCode;
??
HuffNode?ht[MAXNUM*2];?//存放哈夫曼樹
??
HuffCode?hcd[MAXNUM];??//存放ht數組中對應的字符的編碼
??
int?n;?????????????????//字符的個數
??
//初始化哈夫曼樹ht
void?initHt（）
{
????FILE?*?fp;
????char?ch;
????int?i=0;
????//從文件document/character.txt中讀出要編碼的字符和權值
????if（（fp=fopen（“document/character.txt““r“））==NULL）{
????????printf（“can?not?open?the?file?character.txt“）;
????????exit（0）;
????}
????ht[i].left=ht[i].right=ht[i].parent=-1;
????while（（ch=fgetc（fp））!=EOF）{
????????if（ch==‘\n‘）{
????????????i++;
????????????ht[i].left=ht[i].right=ht[i].parent=-1;
????????}
????????else?if（（ch>=‘a‘?&&?ch<=‘z‘）||（ch>=‘A‘?&&?ch<=‘Z‘））
????????????ht[i].ch=ch;
????????else?if（ch>=‘0‘&&ch<=‘9‘）
????????????ht[i].weight=ht[i].weight*10+ch-‘0‘;
????}
????n=i+1;
????if（fclose（fp））{
????????printf（“can?not?close?the?file?character.txt“）;
????????exit（0）;
????}
}
??
//構造哈夫曼樹看成有n棵樹，選擇權值最小的兩棵樹合并
void?createHuffTree（）
{
??
????int?i=0k;
????int?minIminJ;
????int?f=0;
????minI=minJ=-1;?//minI????for（k=n;k<2*n-1;k++）{
????????//尋找ht中權值最小且無父結點的兩個結點
????????i=0;
????????f=0;
????????while（ht[i].ch!=‘\0‘）{
????????????if（ht[i].parent==-1）{
????????????????if（f==0）{
????????????????????minI=i;
????????????????????f++;
????????????????}else?if（f==1）{
????????????????????if（ht[i].weight????????????????????????minJ=minI;
????????????????????????minI=i;
????????????????????}else
????????????????????????minJ=i;
????????????????????f++;
????????????????}else{
????????????????????if（ht[i].weight????????????????????????minJ=minI;
????????????????????????minI=i;
????????????????????}else?if（ht[i].weight????????????????????????minJ=i;
????????????????}
????????????}
????????????i++;
????????}
????????//合并兩個結點
????????ht[k].ch=‘#‘;
????????ht[k].left=minI;
????????ht[k].right=minJ;
????????ht[k].weight=ht[minI].weight+ht[minJ].weight;
????????ht[k].parent=-1;
????????ht[minI].parent=ht[minJ].parent=k;
????}
}
??
//將一個字符串反轉
void?reverse（char?*str）
{
????int?ij;
????char?ch;
????for（i=0j=strlen（str）-1;i????????ch=str[i];
????????str[i]=str[j];
????????str[j]=ch;
????}
}
??
//哈夫曼編碼，通過父節點從下往上找??
void?createHuffCode（）
{
????int?ijlength;
????FILE?*?fp;
????for（i=0;i????????length=0;
????????j=i;
????????//給每個字符進行編碼
????????while（ht[j].parent!=-1）{
????????????if（ht[ht[j].parent].left==j）{
????????????????hcd[i].code[length++]=0+‘0‘;
????????????}else
????????????????hcd[i].code[length++]=1+‘0‘;
????????????j=ht[j].parent;
????????}
??
???????