C语言实现Huffman树，Huffman编码

#include<stdio.h> #include<stdlib.h> #include<string.h> #include<limits.h> #define true 1 #define false 0 typedef struct{ int weight,parent,lc,rc; }HNode,*HTree; typedef char **HCode; void select(HTree *tree,int i,int *s1,int *s2) { int k,w1,w2;//w1,w2权重,k:循环变量 w1=w2=INT_MAX; for(k=0;k<i;k++) { if(tree[0][k].parent==0)//parent为0的说明没有被选过 { if(w1<=w2) { if(tree[0][k].weight<w2) { w2=tree[0][k].weight; *s2=k; } } else { if(tree[0][k].weight<w1) { w1=tree[0][k].weight; *s1=k; } } printf("a:%d,b:%d\t",*s1,*s2); }//end if }//end for if(*s1>*s2)//调整s1,s2,使s1<=s2,不然的话就不能保证左0右1 { int temp=*s2; *s2=*s1; *s1=temp; } } void HCoding(HTree *aTree,HCode *aCode,int *w,int n) { HTree pT; char *cd=(char*)malloc(n*sizeof(char)); int m=2*n-1,i,start,c,f; if(n<=1)return; *aTree=pT=(HTree)malloc(sizeof(HNode)*m); *aCode=(HCode)malloc(sizeof(char*)*n); for(i=0;i<n;i++) { aTree[0][i].lc=aTree[0][i].rc=aTree[0][i].parent=0; aTree[0][i].weight=w[i]; } for(;i<m;i++) { aTree[0][i].lc=aTree[0][i].rc=aTree[0][i].parent=aTree[0][i].weight=0; } for(i=n;i<m;i++) { int s1=0; int s2=0; select(aTree,i,&s1,&s2); printf("\n最小的两个:(%d,%d)\n",s1,s2); pT[s1].parent=pT[s2].parent=i; pT[i].lc=s1; pT[i].rc=s2; pT[i].weight=pT[s1].weight+pT[s2].weight; } if(!cd||!(*aCode))exit(-1);//没有申请到空间 cd[n-1]=0; for(i=0;i<n;i++) { start=n-1; for(c=i,f=pT[i].parent;f;c=f,f=pT[f].parent) { cd[--start]=(pT[f].lc==c ? '0' : '1');//从根开始求编码，左零右壹 } (*aCode)[i]=(char*)malloc(sizeof(char)*(n-start)); strcpy((*aCode)[i],&cd[start]); } free(cd); } int main() { int w1[8]={5,29,7,8,14,23,3,11}; int i; HTree tree; HCode code; HCoding(&tree,&code,w1,8); for(i=0;i<15;i++) { printf("i:%2d %2d,%2d,%2d,%2d\n",i,tree[i].weight,tree[i].parent,tree[i].lc,tree[i].rc ); } for(i=0;i<8;i++) { printf("Num %2d：Weight %3d：%s\n",i,w1[i],code[i]); } system("pause"); return 0; }