hafuman.rar_hafuman

#include<stdio.h> #include<malloc.h> #include<string.h> #include<stdlib.h> typedef struct { int weight; char ch; int parent,lchild,rchild; }HTNode,*HuffmanTree; typedef struct { char ch; char *chs; }HuffmanCode; typedef struct { char ch; int weight; }sw; typedef struct { HuffmanTree HT; HuffmanCode *HC; }huf; void select(HTNode * HT,int n,int *n1,int *n2) { int i=1; int n3; while(HT[i].parent!=0) i++; *n1=i; i++; while(HT[i].parent!=0) i++; *n2=i; if(HT[*n1].weight<HT[*n2].weight) { n3=*n1;*n1=*n2;*n2=n3;} for(i++;i<=n;i++) { if(HT[i].parent==0) { if(HT[i].weight<HT[*n1].weight) *n1=i; else if(HT[i].weight<HT[*n2].weight) *n2=i; } } } huf * HuffmanCoding(HuffmanTree HT,HuffmanCode *HC,sw *w,int n,huf *HUF) {int m,i,s1,s2,start,c,f; HuffmanTree p; char *cd; if(n<=1) return 0; m=2*n-1; HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); for(p=HT+1,i=1;i<=n;i++,p++,w++) {p->weight=w->weight;p->ch=w->ch;p->parent=0;p->lchild=0;p->rchild=0;} for(;i<=m;i++,p++) {p->weight=0;p->ch='^';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; } 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].ch=HT[i].ch; HC[i].chs=(char*)malloc((n-start)*sizeof(char)); strcpy(HC[i].chs,&cd[start]); printf("%c %-10s\n",HC[i].ch,HC[i].chs); } HUF->HT=HT; HUF->HC=HC; return HUF; } char * convert(char *chars,char *chars1,HuffmanCode *hc,int n) { char *p=chars; int i; strcpy(chars1,""); while(*p) { i=1; while(hc[i].ch!=*p&&i<=n) i++; strcat(chars1,hc[i].chs); p++; } printf("the chars translate are:%s\n",chars1); return chars1; } void transcode(HuffmanTree ht,char *chars2,char*chars3) { int i=1,p; char *q=chars2;char *r=chars3; while(ht[i].parent!=0) i++; p=i; while(*q) { while(ht[p].lchild!=0 && *q) { if(*q=='0') p=ht[p].lchild; else p=ht[p].rchild; q++; } if(ht[p].lchild==0) {*r=ht[p].ch;r++;} p=i; } *r='\0'; printf("the chars are:"); puts(chars3); } void input(int *n,sw *w) { int i; printf("input the mount of char:"); scanf("%d",n); for(i=1;i<=*n;i++,w++) {printf("input the %dth char and weight:",i); fflush(stdin); scanf("%c%d",&w->ch,&w->weight); } } void main() {HTNode HT; HuffmanCode HC,*hc; HuffmanTree ht; huf *HUF,huf2; int n; sw w[40]; char ch,inchar[500],outchar[1000]; char *abc; char *p=inchar; input(&n,w); HUF=HuffmanCoding(&HT,&HC,w,n,&huf2); printf("input chars to translate:"); fflush(stdin);//清除流,解决输入干扰 ch=getchar(); while(ch!='#') {*p=ch; p++; ch=getchar(); } *p='\0'; hc=HUF->HC; ht=HUF->HT; abc=convert(inchar,outchar,hc,n); transcode(ht,abc,outchar); }