您的位置首页生活百科

用c程序实现霍夫曼编码

用c程序实现霍夫曼编码

的有关信息介绍如下:

用c程序实现霍夫曼编码

这是我当时做的作业题,就是数据结构书上的那道题。不知道是否和你说的是同样一道题,代码如下: /* HuffmanCode BY Turbo C 2.0 Filename: Huffman.c Author: dcyu. Ver 1.00 */ #include #include #include #include #include typedef struct { unsigned int weight; unsigned int parent,lchild,rchild; } HTNode,*HuffmanTree; typedef char **HuffmanCode; typedef struct { unsigned int s1; unsigned int s2; } MinCode; void Error(char *message); HuffmanCode HuffmanCoding(HuffmanTree HT,HuffmanCode HC,unsigned int *w,unsigned int n); MinCode Select(HuffmanTree HT,unsigned int n); void Error(char *message) { fprintf(stderr,"Error:%s\n",message); exit(1); } HuffmanCode HuffmanCoding(HuffmanTree HT,HuffmanCode HC,unsigned int *w,unsigned int n) { unsigned int i,s1=0,s2=0; HuffmanTree p; char *cd; unsigned int f,c,start,m; MinCode min; if(n<=1) Error("Code too small!"); m=2*n-1; HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); for(p=HT,i=0;i<=n;i++,p++,w++) { p->weight=*w; p->parent=0; p->lchild=0; p->rchild=0; } for(;i<=m;i++,p++) { p->weight=0; p->parent=0; p->lchild=0; p->rchild=0; } for(i=n+1;i<=m;i++) { min=Select(HT,i-1); s1=min.s1; s2=min.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; } printf("HT List:\n"); printf("Number\t\tweight\t\tparent\t\tlchild\t\trchild\n"); for(i=1;i<=m;i++) printf("%d\t\t%d\t\t%d\t\t%d\t\t%d\n", i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild); HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); cd=(char *)malloc(n*sizeof(char *)); cd[n-1]='\0'; for(i=1;i<=n;i++) { start=n-1; for(c=i,f=HT[i].parent;f!=0;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; } MinCode Select(HuffmanTree HT,unsigned int n) { unsigned int min,secmin; unsigned int temp; unsigned int i,s1,s2,tempi; MinCode code; s1=1;s2=1; for(i=1;i<=n;i++) if(HT[i].parent==0) { min=HT[i].weight; s1=i; break; } tempi=i++; for(;i<=n;i++) if(HT[i].weights2) { temp=s1; s1=s2; s2=temp; } code.s1=s1; code.s2=s2; return code; } void main() { HuffmanTree HT=NULL; HuffmanCode HC=NULL; unsigned int *w=NULL; unsigned int i,n; printf("Input n:\n"); scanf("%d",&n); w=(unsigned int *)malloc((n+1)*sizeof(unsigned int *)); w[0]=0; printf("Enter weight:\n"); for(i=1;i<=n;i++) { printf("w[%d]=",i); scanf("%d",&w[i]); } HC=HuffmanCoding(HT,HC,w,n); printf("HuffmanCode:\n"); printf("Number\t\tWeight\t\tCode\n"); for(i=1;i<=n;i++) printf("%d\t\t%d\t\t%s\n",i,w[i],HC[i]); }