游程编码C语言.doc

从文件中读取下列二元编码00001110010101100001110001110001111010，实现其游程编码，然后再对游程序列进行哈弗曼编码。结果保存在out.dat中。程序代码：#include#include#includestruct nodeint id;int num;double probability;typedef structdouble weight;int parent,lchild,rchild;HuffmanTree;void Select(HuffmanTree *HT,int i,int *s1,int *s2)int n,T=0,T1;for(n=1;ni;n+)if(HTn.weight=HTT.weight)&HTn.parent=0)T=n;*s1=T;T1=T;T=0;for(n=1;ni;n+)if(n=T1) continue;if(HTn.weight=HTT.weight)&HTn.parent=0)T=n;*s2=T;void HuffmanCoding(HuffmanTree *HT,char *HC,double *w,int n)int m,i,start;int s1,s2,f,c;char *cd;HuffmanTree *p;if(n=1) return;m=2*n-1;HT0.weight=10000;w+;for(p=HT+1,i=1;iweight=*w;p-lchild=0;p-rchild=0;p-parent=0;for(;iweight=0;p-lchild=0;p-rchild=0;p-parent=0;for(i=n+1;i=m;+i)Select(HT,i,&s1,&s2);HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;cd=malloc(n*sizeof(char);cdn-1=0;for(i=1;i=n;+i)start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c)cd-start=1;elsecd-start=0;HCi=(char *)malloc(n-start)*sizeof(char);strcpy(HCi,&cdstart);free(cd);void initstruct(struct node p,int T)int i;for(i=1;i=T;i+)pi.id=0;pi.num=0;bability=0.0;int getI(struct node p,int e,int T)int i;for(i=1;i=T;i+)if(pi.id=e)return i;return -1;void count(struct node p,int T)int i;for(i=1;i=T;i+)pgetI(p,pi.id,T).num+;int countevent(struct node p,int T)int i,n=0;for(i=1;i=T;i+)if(pi.num!=0)n+;return n;void order(struct node p,struct node p2,int T)int i,n=1;for(i=1;i=T;i+)if(pi.num!=0)p2n+=pi;void calculateprobability(struct node p2,int T)int i,sum=0;for(i=1;i=T;i+)sum=sum+p2i.num;for(i=1;i=T;i+)bability=p2i.num/1.0/sum;void main()int n=0,m=0,i=1,t;char ch1,ch2=#;char *HC;FILE *fp1,*fp2;struct node *p,*p2;HuffmanTree *HT;double *w;if(fp1=fopen(in.dat,rb)=NULL)printf(不能打开文件！n);exit(1);if(fp2=fopen(out.dat,a)=NULL)printf(不能打开文件！n);exit(1);fprintf(fp2,n对于二元序列：);doch1=fgetc(fp1);if(ch1!=EOF)fprintf(fp2,%c,ch1);elsefprintf(fp2,n);n+;if(ch1!=ch2)m+;ch2=ch1;while(ch1!=EOF);fclose(fp1);if(fp1=fopen(in.dat,rb)=NULL)printf(不能打开文件！n);exit(1);t=m-1;p=(struct node *)malloc(m)*sizeof(struct node);initstruct(p,t);n=m=0;doch1=fgetc(fp1);n+;if(ch1!=ch2)if(n!=1)pi+.id=n-m;m=n;ch2=ch1;while(ch1!=EOF);fclose(fp1);fprintf(fp2,游程序列为：);for(i=1;i=t;i+)fprintf(fp2,%d,pi.id);fprintf(fp2,n);count(p,t);p2=(struct node *)malloc(countevent(p,t)+1)*sizeof(struct node);order(p,p2,t);calculateprobability(p2,countevent(p,t);HT=malloc(countevent(p,t)*sizeof(HuffmanTree);HC=malloc(countevent(p,t)+1)*sizeof(char *);w=(double *)malloc(countevent(p,t)+1)*sizeof(double);t=countevent(p,t);for(i=1;i=t;i+)wi=bability;for(i=1;i=t;i+)pi=p2i;HuffmanCoding(HT,HC,w,t);fprintf(fp2,该信源的Huffma