数据结构哈夫曼编码实现.doc

#include<>#include<>typedefstructhaha{ intweight; intparent,lchild,rchild,flag; chardata;}haha,*friday;typedefstructhehe{ charm; intn; structhehe*next;}hehe,*zhouwu;typedefchar**gege;voidbegin(zhouwu&l){ zhouwup,q,r; intflag;l=(zhouwu)malloc(sizeof(hehe)); l->next=NULL; l->n=0; r=p=q=l; printf("请输入要编码的字符串:"); for(inti=0;;) { p=(zhouwu)malloc(sizeof(hehe)); p->n=0; p->m=getchar(); if(p->m=='\n') break; flag=0;while(r->next!=NULL) {if(r->next->m==p->m) { r->next->n++;flag=1; free(p); break; } else r=r->next; }if(flag==0) { p->next=q->next; p->n++; q->next=p; q=p;l->n++; } r=l; }}voidselect(friday&ht,intk,int&x,int&y){ intfirst,j[2],m=0,i; for(inth=1;h<=2;h++) {for(first=32767,i=1;i<=k;i++){ if(ht[i].flag==0) { if(first>ht[i].weight) { first=ht[i].weight; j[m]=i; } }}x=j[0];y=j[1];m++;ht[x].flag=1;if(m==2)ht[y].flag=1;}}voidhuffmancoding(friday&ht,zhouwu&l){ intm; m=2*l->n-1; ht=(friday)malloc((m+1)*sizeof(haha)); fridayp; zhouwuq=l; inti; for(p=ht+1,i=1;i<=l->n;++i,++p) { p->weight=q->next->n; p->flag=0; p->parent=0; p->lchild=0; p->rchild=0; p->data=q->next->m; q=q->next; }for(;i<=m;++i,++p){ p->flag=0; p->weight=0; p->parent=0; p->lchild=0; p->rchild=0; p->data=NULL;}ints1,s2;for(i=l->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;}char**hc;hc=(gege)malloc((l->n+1)*s