哈夫曼树的构造与哈夫曼编码

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 20//叶子结点最大值
#define M 2*N-1//所有结点最大值 
//静态三叉链表实现哈夫曼树 
typedef struct Huffman{
int weight;
int parent;
int lchild;
int rchild;
}huf_node,huf_tree[M+1];
//存储哈夫曼编码串的头指针数组
//由于每个哈夫曼编码是变长编码，因此使用指针数组存放每个编码串的头指针 
typedef  char* huf_code[N+1]; 

//寻找权值最小的两个结点
//在ht[1]~ht[k]的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给a,b
void select(huf_tree ht,int k,int* a,int* b){
int i;
int mi=9999,mii=9999;//两个最小的权值 ,mi对应a，mii对应b 
for(i=1;i<=k;i++){
//若该结点未加入到哈夫曼树中，parent值为空 
if(ht[i].parent==0){
if(ht[i].weight<mi){
                mi=mii;
                mii=ht[i].weight;
                *a=*b;
                *b=i;
            }
if(ht[i].weight<mii){
                mii=ht[i].weight;
                *b=i;
            }
        }
    } 
} 

//创建哈夫曼树 
void create(huf_tree ht,int w[],int n){
int i;
for(i=1;i<=n;i++){//1~n号单元存放叶子结点，初始化 
        ht[i].lchild=0;
        ht[i].rchild=0;
        ht[i].parent=0;
        ht[i].weight=w[i];
    }
int m=2*n-1;
for(i=n+1;i<=m;i++){//n+1~m号单元存放非叶子结点，初始化 
        ht[i].lchild=0;
        ht[i].parent=0;
        ht[i].rchild=0;
        ht[i].weight=0;
    }
for(i=n+1;i<=m;i++){//创建非叶子结点 
int a,b;
        select(ht,i-1,&a,&b);//在ht[1]~ht[i-1]的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给a,b
        ht[i].weight=ht[a].weight+ht[b].weight;
        ht[a].parent=i;ht[b].parent=i;
        ht[i].lchild=a;ht[i].rchild=b; 
    }
//输出哈夫曼树 
printf("哈夫曼树的终态：\n"); 
for(i=1;i<=2*n-1;i++){
printf("%d %d %d %d\n",ht[i].weight,ht[i].parent,ht[i].lchild,ht[i].rchild);
    }
} 

//求哈夫曼树的哈夫曼编码 
void cre_huf_code(huf_tree ht,huf_code hc,int n){
char* cd;
//分配当前编码的工作空间 
    cd=(char*)malloc(n*sizeof(char));
    cd[n-1]='\0';
int i;
//求n个叶子结点对应的哈夫曼编码 
for(i=1;i<=n;i++){
int start=n-1;//从右向左逐位存放编码 
int c=i;int p=ht[i].parent;//从叶子结点开始向上倒推 
while(p!=0){//不为根 
            start--;
if(ht[p].lchild==c) cd[start]='0';//左分支标 0 
else cd[start]='1';//右分支标 1 
            c=p;p=ht[p].parent;//向上倒推 
        }//结束时哈夫曼编码存储在以cd为首地址的数组中
//为第i个编码分配空间 
        hc[i]=(char*)malloc((n-start)*sizeof(char));
strcpy(hc[i],&cd[start]);//把改结点的哈夫曼编码复制到hc[i]中 
    } 
free(cd);
} 
//输出各个叶子结点的哈夫曼编码 
void visit_huf_code(huf_code hc,int n){
int i,k;
//共有n个叶子结点 
printf("各个叶子结点的哈夫曼编码：\n");
for(i=1;i<=n;i++){
//第i个叶子结点的哈夫曼编码的首地址为hc[i] 
for(k=0;*(hc[i]+(k*sizeof(char)))!='\0';k++){
printf("%c",*(hc[i]+(k*sizeof(char))));
        }
printf("\n");
    }
}
int main(){
    huf_tree ht;
int i,n,w[N];
printf("请输入叶子结点个数：");
scanf("%d",&n);
printf("请输入各个叶子结点的权值:");
for(i=1;i<=n;i++){
scanf("%d",&w[i]);
    }
    create(ht,w,n);
    huf_code hc;
    cre_huf_code(ht,hc,n);
    visit_huf_code(hc,n);
return 0;
}