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

#include#includetypedef struct haha int weight; int parent,lchild,rchild,flag; char data;haha,*friday;typedef struct hehechar m;int n;struct hehe *next;hehe,*zhouwu;typedef char * *gege;void begin(zhouwu &l)zhouwu p,q,r;int flag; l=(zhouwu)malloc(sizeof(hehe);l-next=NULL;l-n=0;r=p=q=l;printf(请输入要编码的字符串: );for(int i=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;void select(friday &ht,int k,int &x,int &y)int first,j2,m=0,i;for(int h=1;h=2;h+) for(first=32767,i=1;ihti.weight)first=hti.weight;jm=i;x=j0;y=j1;m+;htx.flag=1;if(m=2) hty.flag=1;void huffmancoding(friday &ht,zhouwu &l)int m;m=2*l-n-1;ht=(friday)malloc(m+1)*sizeof(haha);friday p;zhouwu q=l;int i;for(p=ht+1,i=1;in;+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( ;iflag=0; p-weight=0;p-parent=0;p-lchild=0;p-rchild=0;p-data=NULL;int s1,s2;for(i=l-n+1;in+1)*sizeof(char *);char *cd;cd=(char *)malloc(l-n*sizeof(char);cdl-n-1=0;int c,f,start;for(i=1;in;+i)start=l-n-1;for(c=i,f=hti.parent;f!=0;c=f,f=htf.parent)if(htf.lchild=c)cd-start=0;elsecd-start=1;hci=(char *)malloc(l-n-start)*sizeof(char);int q=start;for(int d=0;dn-start;d+)hcid=cdq+;free(cd);for(i=1;in;i+)printf(字符 %c 的编码是: %sn,hti.data,hci);void translate(friday &ht,zhouwu &l)char m100;int k,j=l-n; int i=2*j-1,flag=0;printf(请输入密文编码： ); gets(m);printf(n译码后是: ); for(int c=0; ;c+)if(mc=0)break;if(mc=0)k=hti.lchild;if(mc=1) k=hti.rchild;if(mc!=0&mc!=1) system(cls);printf(n输入的密文必须是由字符0和1组成n);return; i=k;if(htk.lchild=0&htk.rchild=0)printf(%c,htk.data);i=2*j-1;flag=1;if(flag=0)system(cls);printf(密文没有相应的译码对应。n);void main()zhouwu l;friday ht;printf(该程序是对字符串进行编码，和对一串编码进行翻译。nnn);begin(l);while(l-n=1)printf(编码的字符串长度必须大于1n);begin(l); huffmancoding(ht,l);printf(编码成功n将进行译码操作n); translate(ht,l);char a;printf(n是否继续译码(y/Y)： );scanf(%