Huffman编码

//Author: Guo R.H
//Date:06.12.28
//      USTC

#include
#include
#include

typedef struct
{
    int weight;
    int parent,lchild,rchild;
}HTNode,*HTree;
typedef char ** HCode;
int Min(HTree HT, int i)
{//返回i个节点中权值最小节点的序号
    int f, j;
    int k = 100;
    for(j=0; j    {
        if(HT[j].weight        {
            k = HT[j].weight;
            f = j;
        }
    }
    HT[f].parent = 1;
    return f;
}
void Select(HTree HT, int i, int *s1, int *s2)
{//找出两个最小的权值
    int t;
    *s1 = Min(HT, i);
    *s2 = Min(HT, i);
    if(*s1 > *s2)
    {
        t = *s1;
        *s1 = *s2;
        *s2 = t;
    }
}
void CreateHTree(HTree *HT, HCode *hc, int n, int *w)
{//创建huffman树
    int i, j, m, s1, s2, num, c, f;
    m = 2*n-1;
    *HT = (HTree)malloc(m*sizeof(HTNode));
    for(i=0; i    {
        (*HT+i)->weight = *(w+i);
        (*HT+i)->parent = 0;
        (*HT+i)->lchild = 0;
        (*HT+i)->rchild = 0;        
    }
    for(; i        (*HT+i)->weight = 0;
    for(i=n; i    {
        Select(*HT, i, &s1, &s2);
        (*HT+i)->weight = (*HT+s1)->weight+(*HT+s2)->weight;
        (*HT+i)->parent = 0;
        (*HT+i)->lchild = s1;
        (*HT+i)->rchild = s2;
        (*HT+s1)->parent = i;
        (*HT+s2)->parent = i;        
    }
    *hc = (HCode)malloc(n*sizeof(char *));
    char *str = (char *)malloc(n*sizeof(char));
    str[n-1] = '\0';
    for(i=0; i    {//Huffman编码
        num = 1;
        for(c=i, f=(*HT+i)->parent; f!=0; c=f,f=(*HT+f)->parent)
        {
            if(i == (*HT+f)->lchild)
            {//左孩子编码 1
                str[n-1-num] = '1';
                num ++;
            }
            else
            {//右孩子编码 2
                str[n-1-num] = '0';
                num ++;
            }
        }
        (*hc)[i] = (char *)malloc(num*sizeof(char));
        strcpy((*hc)[i], &str[n-num]);        
    }
    printf("index weight   parent   lchild   rchild\n");
    for(j=0, i=0; i        printf("%d:  %5d %8d %8d %8d\n", j++, (*HT+i)->weight, (*HT+i)->parent, (*HT+i)->lchild, (*HT+i)->rchild);
}

int main()
{
    HTree HT;
    HCode HC;
    int *w, i, n;
    printf("please input the number of weights: ");
    scanf("%d", &n);
    w = (int *)malloc(n*sizeof(int));
    for(i=0; i        scanf("%d", w+i);
    CreateHTree(&HT, &HC, n, w);
    printf("Huffman 编码为：\n");
    for(i=0; i        printf("%d:  %s\n", w[i], HC[i]);
    return 0;
}