huffman树及其编码

#include <stdio.h>
#include <malloc.h>
#include <string.h>

typedef struct {
    unsigned int weight;
    unsigned int parent,lchild,rchild;
}HTNode, *HuffmanTree;

typedef char **HuffmanCode;

//从ht[1,n]中找出没有父节点，权值最小的s1,s2
void select(HuffmanTree ht,int n,int *s1,int *s2){
    int i;
    *s1 = *s2 = 0;
    for(i=1; i<=n; i++){
        if(ht[i].parent==0){
            if(*s1==0)
                *s1 = i;
            else if(*s2==0){
                if(ht[*s1].weight>ht[i].weight){
                    *s2 = *s1;
                    *s1 = i;}
                else
                    *s2 = i;
            }else{    //s1,s2都有值
                if(ht[i].weight<=ht[*s1].weight){
                            *s2 = *s1;
                            *s1 = i;
                    }else if(ht[i].weight>ht[*s1].weight&&ht[i].weight<ht[*s2].weight)
                                *s2 = i;
            }
        }
    }//end for
}

/*
    根据huffman树进行编码,从叶子节点开始
*/
void codingFromLeaf(HuffmanTree tr,HuffmanCode *co,int n){
    char *cd;
    int i,start;
    unsigned int c,f;
    *co = (HuffmanCode)malloc((n+1)*sizeof(char *));
    cd = (char *)malloc(n*sizeof(char));    //临时空间,用来拼接编码
    cd[n-1] = '\0';
    for(i=1; i<=n; i++){    //求n个编码
        start = n - 1;
        for(c=i,f=tr[i].parent; f!=0; c=f,f=tr[f].parent)
            if(tr[f].lchild==c)
                cd[--start] = '0';
            else
                cd[--start] = '1';
        (*co)[i] = (char *)malloc((n-start)*sizeof(char));
        strcpy((*co)[i],&cd[start]);
    }
    free(cd);
}
/*
    根据huffman树进行编码,从根节点开始
*/
void codingFromRoot(HuffmanTree tr,HuffmanCode *co,int n){
    int p,cdlen,i,m;
    char *cd;
    m = 2*n-1;
    p = m;
    cd = (char *)malloc((n-1)*sizeof(char));
    cdlen = 0;
    *co = (HuffmanCode)malloc((n+1)*sizeof(char *));
    for(i=0; i<=m; i++)
            tr[i].weight = 0;
    while(p){
        if(tr[p].weight==0){ //向左
            tr[p].weight = 1;
            if(tr[p].lchild!=0){
                p = tr[p].lchild;
                cd[cdlen++] = '0';
            }else if(tr[p].rchild==0){   
                (*co)[p] = (char *)malloc((cdlen+1)*sizeof(char));
                cd[cdlen] = '\0';
                strcpy((*co)[p],cd);
            }
        }else if(tr[p].weight==1){    //向右
            tr[p].weight = 2;
            if(tr[p].rchild!=0){
                p = tr[p].rchild;
                cd[cdlen++] = '1';
            }
        }else{    //tr[p].weight==2
            tr[p].weight = 0;
            p = tr[p].parent;
            cdlen--;
        }
    }//end while
}
/*
    w存放n个字符的权值，构造huffman树ht，并求出n个字符的huffman编码存放在hc
*/
void huffmanCoding(HuffmanTree *ht, HuffmanCode *hc, int *w, int n){
    int m;    //节点数
    int i,s1,s2;
    HuffmanTree p;
    if(n<=1)    return;
    m = 2*n-1;
    *ht = (HuffmanTree)malloc((m+1)*sizeof(HTNode));
    for(i=1,p=*ht+1; i<=n; i++,p++,w++){//初始化n个叶子节点
            (*p).weight = *w;
            (*p).lchild = (*p).rchild = (*p).parent = 0;
        }
    for(; i<=m; i++,p++)//初始化其余n-1个节点
            (*p).weight = (*p).lchild = (*p).rchild = (*p).parent = 0;
    for(i=n+1; i<=m; i++){    //建立huffman树
        select(*ht,i-1,&s1,&s2);
        (*ht)[s1].parent = (*ht)[s2].parent = i;
        (*ht)[i].lchild = s1;
        (*ht)[i].rchild = s2;
        (*ht)[i].weight = (*ht)[s1].weight + (*ht)[s2].weight;
    }

    codingFromLeaf(*ht,hc,n);
    //codingFromRoot(*ht,hc,n);
}

void main(){
    int weight[4]= {7,5,2,4},n,i;
    HuffmanTree tree;
    HuffmanCode code;
    n = 4;
   
    huffmanCoding(&tree,&code,weight,n);
    for(i=1; i<=n; i++)
        printf("%s\n",*(code+i));
   
}