#include <stdio.h>
#include <stdlib.h>
#define MaxSize 50
typedef struct{
char c; //代碼;
int w; //代碼權(quán)值;
char code[MaxSize]; //代碼的Huffman編碼;
}HuffCode[MaxSize];
typedef struct{
int Weight; //權(quán)值;
int LChild,RChild,Parent;
}HTNode,HuffTree[MaxSize];
//================================================================================
void HuffmanTree(HuffTree HT,int length,HuffCode hc); //生成Huffman樹;
void SelectHTNode(HuffTree HT,int n,int *min1,int *min2); //查找最小和次小序號;
void HuffmanCode(HuffTree HT,int len,HuffCode hc); //生成Huffman編碼;
//================================================================================
int main(void)
{
HuffTree HT; //Huffman樹;
HuffCode HC; //Huffman編碼;
int i,len;
printf("<<<< Huffman編碼生成程序 >>>>\t\tby Haroldi.\n\n 請幫助評價一下思路及改善意見!\t多謝了:-)...\n\n\n\n");
printf("\n輸入代碼數(shù)量："); scanf("%d",&len); system("cls");printf("代碼數(shù)量：%2d\n\n",len);
printf("輸入代碼及權(quán)值(e.g.: \"a16[回車]\" )：\n");
for(i=1;i <= len;i++)
{
while(getchar() != '\n') NULL;
printf("No.%2d： ",i);
HC[i].c = getchar();
scanf("%d",&HC[i].w);
}
HuffmanTree(HT,len,HC);
HuffmanCode(HT,len,HC);

printf("\n輸出Huffman編碼：\n");
for(i = 1;i<=len;i++)
{
printf("\n %c :",HC[i].c);
puts(HC[i].code);
}
//測試Huffman樹結(jié)構(gòu);
printf("\n\n輸出Huffman樹結(jié)構(gòu)：");system("pause");
printf("\nHT[i]:\t權(quán)值\t雙親\t左孩子\t右孩子\n");
for(i = 1;i<2*len;i++)
{
if(i <= len) printf("(%c)",HC[i].c);
printf("%2d:\t %2d;\t%2d,\t %2d,\t %2d.\n",\
i,HT[i].Weight,HT[i].Parent,HT[i].LChild,HT[i].RChild);
}
return 0;
}
//================================================================================
void HuffmanTree(HuffTree HT,int length,HuffCode hc) //Huffman樹初始化;
{
int i,min1,min2;
HT[0].Weight = 65535;
for(i = 1;i <= length;i++)
{
HT[i].Weight = hc[i].w;
HT[i].LChild = HT[i].RChild = HT[i].Parent = -1;
}
for(;i < 2*length;i++) //i初值 = length+1;
{
HT[i].LChild = HT[i].RChild = HT[i].Parent = -1;
}

for(i = length+1;i < 2*length;i++)
{
SelectHTNode(HT,i,&min1,&min2);
HT[min1].Parent = i;
HT[min2].Parent = i;
HT[i].LChild = min1;
HT[i].RChild = min2;
HT[i].Weight = HT[min1].Weight + HT[min2].Weight;
}
}
//================================================================================
void SelectHTNode(HuffTree HT,int n,int *min1,int *min2) //查找最小和次小序號;
{
int i;
*min1 = *min2 = 0;
for(i = 1;i < n;i++)
{
if(HT[i].Parent == -1)
{
if(HT[*min1].Weight >= HT[i].Weight)
{
*min2 = *min1;
*min1 = i;
}
else if(HT[*min2].Weight > HT[i].Weight) *min2 = i;
}
}
}
//================================================================================
void HuffmanCode(HuffTree HT,int len,HuffCode hc) //生成Huffman編碼;
{
int i,j,tc,Stack[MaxSize],top = -1;
char flag[MaxSize];
HTNode th;
for(i = 1;i <= len;i++)
{
top = -1; //棧初始化;
j = 0; //hc[i].code串首位置偏移;
th = HT[i]; //當(dāng)前結(jié)點(diǎn)th;
tc = i; //當(dāng)前結(jié)點(diǎn)標(biāo)記tc;
while(th.Parent != -1)
{ //當(dāng)前結(jié)點(diǎn)th雙親P入棧,由P的孩子是th,確定flag;確定下次結(jié)點(diǎn)標(biāo)記tc;
Stack[++top] = th.Parent;
if(HT[th.Parent].LChild == tc) {flag[top] = 'L'; tc = th.Parent;}
if(HT[th.Parent].RChild == tc) {flag[top] = 'R'; tc = th.Parent;}
th = HT[Stack[top]]; //下一結(jié)點(diǎn);
} 
while(top != -1)
{
if(flag[top] == 'L') hc[i].code[j++] ='0';
else hc[i].code[j++] ='1';
Stack[top--]; //出棧;
}
hc[i].code[j] ='\0'; //當(dāng)前串結(jié)束;
} 
}
//================================================================================