데이터 구조 - 하프 만 트 리 및 하프 만 인 코딩 코드 구현

#define MAXLEAFNUM 50 //             

typedef struct node{
    char ch;//       
    int weight;//  
    int parent;//         ， 0      
    int lChild,rChild;//            ， 0       
}HuffmanTree[2*MAXLEAFNUM];

typedef char* HuffmanCode[MAXLEAFNUM + 1];

void select(HuffmanTree HT,int n,int &s1,int &s2)
{
    s1 = 1;
    s2 = 2;
    int nMinW = HT[1].weight;

    for(int  i = 1; i <= n;i++){
        if(HT[i].parent != 0){
            continue;
        }
        if(nMinW > HT[i].weight){
            nMinW = HT[i].weight;
            s1 = i;
        }
    }
    if(s1 != 1){
        nMinW = HT[1].weight;
    }else{
        nMinW = HT[2].weight;
    }
    for(int  i = 1; i <= n -1;i++){
        if(HT[i].parent != 0 || i == s1){
            continue;
        }

        if(nMinW > HT[i].weight){
            nMinW = HT[i].weight;
            s2 = i;
        }
    }
}

//      
void createHTree(HuffmanTree HT,char *c,int *w,int n)
{
    int i,s1,s2;
    if(n <= 1){
        return;
    }

    for(i = 1; i <= n;i++){//  n        
        HT[i].ch = c[i - 1];
        HT[i].weight = w[i - 1];
        HT[i].parent = HT[i].lChild = HT[i].rChild = 0;
    }
    for(;i < 2 * n;i++){
        HT[i].parent = HT[i].lChild = HT[i].rChild = 0;
    }

    for(i = n + 1; i < 2 *n; 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;
    }
}

//         ，             ，                 
//n         HT     1~n， i(1<= i <= n)         HC[i] 
void HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int n)
{
    char *cd;
    int i,start,c,f;

    if(n <= 1){
        return;
    }
    cd = (char*)malloc( n * sizeof(char));//           
    cd[n -1] = '\0';//   
    for(i = 1; i <= n;i++){
        start = n - 1;
        for(c = i,f = HT[i].parent;f != 0;c = f,f = HT[f].parent){//              
            if(HT[f].lChild == c){//                ，        0，   1
                cd[start] = '0';
            }else{
                cd[start] = '1';
            }
            start--;
        }
        HC[i] = (char*)malloc((n - start) * sizeof(char));
        strcpy(HC[i],&cd[start]);
        free(cd);
    }
}

//         
void Decoding(HuffmanTree HT,int n,char *buff)
{
    int p = 2 * n - 1;
    while (*buff) {
        if((*buff) == '0'){
            p = HT[p].lChild;
        }else{
            p = HT[p].rChild;
        }

        if(HT[p].lChild == 0 && HT[p].rChild == 0){
            cout << HT[p].ch << endl;
            p = 2 * n - 1;
        }
        buff++;
    }
}