哈夫曼编码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXBIT 10
#define MAXVALUE 1000
#define MAXSIZE 26
typedef struct HNode{
    int weight;
    int parent,lchild,rchild;
}HNode,*HTree;
typedef char * *Hcode;
int tongji(char *s,int cnt[],char str[]);
Hcode hafuman(HTree HT,Hcode HC,int n);
HTree creat(HTree HT,int *w,int n);
int main()
{
    char st[300],ct[26];
    int zt[26],i;
    HNode *HT;
    Hcode HC;
    int num;
    HTree s;
    printf("请输入需要编码的字符串，大写字母，以回车结束：\n");
    gets(st);
    num=tongji(st,zt,ct);
    HT=creat(HT,zt,num);
    HC=hafuman(HT,HC,num);
    for(i=0;i<num;i++)
    {
        printf("%c 出现 %d 次,编码为:",ct[i],zt[i]);
        puts(HC[i]);
        printf("\n");
    }
}
int tongji(char *s,int cnt[],char str[])
{
    char *p;
    int i,j,k;
    int temp[26];
    for(i=0;i<26;i++)
    temp[i]=0;
    for(p=s;*p!='\0';p++)
    {
        if(*p>='A'&&*p<='Z')
        {
            k=(*p)-65;
            temp[k]++;
        }
    }
        for(i=0,j=0;i<26;i++)
        {
            if(temp[i]!=0)
            {
                str[j]=i+65;
                cnt[j]=temp[i];
                j++;
            }
        }
        str[j]='\0';
        return j;
}
HTree creat(HTree HT,int *w,int n)
{
    int m,m1,m2,x1,x2,i,j;
    HNode *p;
    if(n<=1)
    return NULL;
    m=2*n-1;
    HT=(HNode *)malloc(m*sizeof(HNode));
    if(HT==NULL)
    return HT;
    for(p=HT,i=0;i<n;++i,++p,++w)
    {
        p->weight=*w;
        p->lchild=-1;
        p->rchild=-1;
        p->parent=-1;
    }
    for(;i<m;++i,++p)
    {
        p->lchild=-1;
        p->rchild=-1;
        p->parent=-1;
        p->weight=0;
    }
    for(i=n;i<m;++i)
    {
        m1=m2=MAXVALUE;
        x1=x2=0;
        for(j=0;j<i;++j)
        {
            if(HT[j].parent==-1&&HT[j].weight<m1)
            {
                m2=m1;
                x2=x1;
                m1=HT[j].weight;
                x1=j;
            }
            else if(HT[j].parent==-1&&HT[j].weight<m2)
            {
                m2=HT[j].weight;
                x2=j;
            }
        }
        HT[x1].parent=i;
        HT[x2].parent=i;
        HT[i].lchild=x1;
        HT[i].rchild=x2;
        HT[i].weight=m1+m2;
    }
    return HT;
}
Hcode hafuman(HTree HT,Hcode HC,int n)
{
    
    char *cd;
    int start,i,c,f;
    HC=(Hcode)malloc(n*sizeof(char *));
    cd=(char *)malloc(n*sizeof(char));
    cd[n-1]='\0';
    for(i=0;i<n;++i)
    {
        start=n-1;
        for(c=i,f=HT[i].parent;f!=-1;c=f,f=HT[f].parent)
        if(HT[f].lchild==c)
        cd[--start]='0';
        else
        cd[--start]='1';
        HC[i]=(char *)malloc((n-start)*sizeof(char));
        strcpy(HC[i],&cd[start]);
    }
    free(cd);
    return HC;
}