哈夫曼编码

哈夫曼编码c++源码模板 [1]

1. include<stdio.h>
2. include<stdlib.h>
3. include<string.h>
4. define swap(x,y,t) ((t)=(x),(x)=(y),(y)=(t))
5. define N 26

char string[N]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'}; int num[N]={23,15,11,26,32,11,48,99,14,44,59,86,7,6,49,73,26,91,38,16,49,222,10,34,1,9}; typedef struct { int weight; int parent,lchild,rchild; }HTnode,*hafumantree; typedef char **hufumanode; hafumantree HT; hufumanode HC; int small(int x) { int i=0,flag,k=32767; for(;i<=x;i++) if(HT[i].weight<k&&HT[i].parent==0) { k=HT[i].weight; flag=i; } HT[flag].parent=1; return flag; } void select(int i,int *s1,int *s2) { int temp; *s1=small(i); *s2=small(i); if(*s1>*s2) swap(*s1,*s2,temp); } void hufumancoding(int *w,int n)/*编译码*/ { int m,i,s1,s2,f,c,start; hafumantree p; char *code; m=2*n-1; HT=(HTnode *)malloc(m*sizeof(HTnode)); if(!HT) { printf("\noverflow!"); exit(0); } p=HT; for(i=0;i<n;i++,p++) { (*p).weight=w[i]; (*p).parent=0; (*p).lchild=0; (*p).rchild=0; } for(;i<m;i++,p++) (*p).parent=0; for(i=n;i<m;i++) { select(i-1,&s1,&s2); HT[i].lchild=s1; HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight; HT[s1].parent=HT[s2].parent=i; } HC=(hufumanode)malloc(n*sizeof(char *));/*开始译码*/ code=(char *)malloc((n+1)*sizeof(char)); code[n]='\0'; for(i=0;i<n;i++) { start=n; c=i; for(f=HT[c].parent;f!=0;c=f,f=HT[c].parent) if(HT[f].lchild==c) code[--start]='0'; else code[--start]='1'; HC[i]=(char *)malloc((n-start)*sizeof(char)); strcpy(HC[i],&code[start]); printf("%c:",string[i]); puts(HC[i]); printf("\n"); } free(code);/*释放工作空间*/ } void main() { int *w,i=0; w=(int *)malloc(N*sizeof(int)); for(;i<N;i++) w[i]=num[i]; hufumancoding(w,N); } [2]