#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);    //查找最小和次小序號(hào); 
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  請(qǐng)幫助評(píng)價(jià)一下思路及改善意見!\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); 
    } 
//測(cè)試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)    //查找最小和次小序號(hào); 
{ 
    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é)束; 
    }          
}