哈夫曼编码和译码

哈夫曼编码和译码 /* 哈夫曼编码和译码 */ #include "stdio.h" #include "stdlib.h" /* 定义哈夫曼树的类型 */ typedef struct { char letter; int weight; int parent,lchild,rchild; } HTNode,*HuffmanTree; /* 定义哈夫曼编码的类型 */ typedef char **HuffmanCode; /* 选择二个最小值 */ void Select(HuffmanTree HT,int n,int *s1,int *s2) {int i,j,k; for(i=1; i<=n; i++) if (HT[i].parent == 0) { *s1=i; break; } for(j=i+1; j<=n; j++) if (HT[j].parent == 0) { *s2=j; break; } if (HT[i].weight > HT[j].weight) { *s1=j; *s2=i; } for (k=j+1; k<=n; k++) if (HT[k].parent==0 && HT[k].weightparent = NULL; p->letter = *zi; p->lchild = NULL; p->rchild = NULL; p->weight = *w;} for(;i<=m;++i,++p) { p->weight=0; p->parent=0; p->lchild=0; p->rchild=0;} for(i=n+1;i<=m;++i) { Select(*HT,i-1,&s1,&s2); (*HT)[s1].parent=i; (*HT)[s2].parent=i; (*HT)[i].lchild=s1; (*HT)[i].rchild=s2; (*HT)[i].weight=(*HT)[s1].weight+(*HT)[s2].weight;} /* huffman编码 */ *HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); cd=(char*)malloc(n*sizeof(char)); cd[n-1]='\0'; for(i=1;i<=n;++i) {Istart = n - 1; for(c=i,f=(*HT)[i].parent; f!=0; c=f,f=(*HT)[f].parent) if ((*HT)[f].lchild == c) cd[--Istart] = '0'; else cd[--Istart] = '1'; (*HC)[i] = (char *)malloc((n-Istart)*sizeof(char)); strcpy((*HC)[i], &cd[Istart]); } free(cd); } /* 主函数 */ void main() { HuffmanTree HT; HuffmanCode HC; int i,n,w[100]; char z; char zi[10]={'A','B','C','D','E','F','G','H','I'}; printf("\nInput NodeNum:"); scanf("%d",&n); for(i=0;i