完整的压缩、解压程序及测试（huffman编码）.doc

完整的压缩、解压程序及测试 本实验是由Huffman coding所实现。 1、 算法描述： 建立文件：输入一段英文字符，建立“文本文件.txt”。打印文件：一种是对文件进行逐字符的打印； 另一种是对文件以结构体为单位进行打印。计算文件：对文件进行初步统计，求出字符的种类和权重，为生成哈夫曼树做准备。哈夫曼树函数：求出哈夫曼树，保存每个字符的哈夫曼编码在“字符代码.txt”。求最值函数：此函数在求哈夫曼树时应用，保证每次选定的达到哈夫曼树要求。转化成字符函数：即用字符代码来代替字符，保存在“码本文件.txt”。破译函数：把“码本文件.txt”转化为可读的“破译文件.txt”。2、 程序代码：#include #include #include #include #define N 50 /输入字符的最多数目,可根据具体需要而定typedef struct int weight; /权重 int parent,lchild,rchild; /左右孩子HTNode,*HuffmanTree;typedef char *HuffmanCode; /建立原文件文本文件.txtvoid Creat_message() FILE *fp;char c;if(fp=fopen(文本文件.txt,wb)=NULL)printf(cannot open this file!n);return ;printf(输入原文件（一段英文，字符间无间隔，以#表示结束）！n);do /以#表示输入结束 scanf(%c,&c); fputc(c,fp); while (c!=#);fclose(fp); /逐字符打印文件（以字符为单位）void print1(char *name) FILE *fp; char c; if(fp=fopen(name,rb)=NULL)printf(cannot open this filen);return ; c=fgetc(fp); while(c!=#)printf(%c,c); c=fgetc(fp); /统计字符种类及个数，用来作为哈夫曼编码时的权重（频率）char kindN=0; /字符种类int numN=0; /字符相映的个数int count=0; /字符总数void Calculate() char c;int i=1,k;FILE *fp;if(fp=fopen(文本文件.txt,rb)=NULL)printf(cannot open this filen);return ;c=fgetc(fp);while(c!=#) for (k=0;k=i&kindk-1!=c) kindi=c;numi+;i+;c=fgetc(fp);count=i-1;/哈夫曼编码，求最小生成树及字符的哈夫曼编码int s1,s2; /标记select函数调用时返回的最值struct charcodechar data;char code20;CodeN,dN,eN;/结构体包括字符元素和字符相映的代码void HuffmanCoding ()void select(HuffmanTree Hu,int j); HuffmanTree HT; /哈夫曼树 HuffmanCode HC; /哈夫曼编码int m,i,start,f,c;char *cd;FILE *fp;if (count=1) return;m=2*count-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);for(i=1;i=count;i+)HTi.weight=numi;for(i=1;i=m;i+)HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(i=count+1;i=m;i+)select(HT,i-1);HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;HC=(HuffmanCode)malloc(count+1)*sizeof(char*); /从叶子到根逆向求每个字符的哈夫曼编码cd=(char*)malloc(count*sizeof(char);cdcount-1=0;for(i=1;i=count;i+)start=count-1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if (HTf.lchild=c) cd-start=0;else cd-start=1; HCi=(char*)malloc(count-start)*sizeof(char);strcpy(HCi,&cdstart); /复制字符串if(fp=fopen(字符代码.txt,wb)=NULL) /字符与对应的编码printf(cannot open this filen);return ;for(i=1;i=count;i+)Codei.data= kindi;strcpy(Codei.code,HCi); fwrite(&Codei,sizeof(struct charcode),1,fp); fclose(fp);/在HT1j选择parent为0且weight最小的两个结点，序号为s1,s2void select(HuffmanTree Hu,int j)int k=1,t;while(Huk.parent!=0) k+; /找第一个parent不为0的结点for(t=k;t=j;t+)if(Hut.parent=0 & Hut.weightHuk.weight)k=t; s1=k;k=1;while(Huk.parent!=0 |k=s1) k+;for(t=k;t=j;t+)if(Hut.weightHuk.weight & Hut.parent=0 &t!=s1)k=t;s2=k;/结构体struct charnode的文件的打印void print2(char *name) FILE *fp; int i=1; if(fp=fopen(name,rb)=NULL)printf(cannot open this filen);return ; while(!feof(fp) fread(&ei,sizeof(struct charcode),1,fp); printf(%c-%sn,ei.data,ei.code); i+;/使文本文件转化成码本文件void Transform() FILE *fp1,*fp2,*fp3;int i;char c;if(fp1=fopen(字符代码.txt,rb)=NULL)printf(cannot open this filen);return ; if(fp2=fopen(文本文件.txt,rb)=NULL)printf(cannot open this filen);return ; if(fp3=fopen(码本文件.txt,wb)=NULL)printf(cannot open this filen);return ;for(i=0;icount;i+)fread(&di,sizeof(struct charcode),1,fp1);while(!feof(fp2)c=fgetc(fp2);for(i=0;icount;i+)if(di.data=c)fputs(di.code,fp3);break;fputc(#,fp3); /使该文件也可用print1fclose(fp3);/把码本文件转化为可读的破译文件void Translate()FILE *fp1,*fp2,*fp3;int i,j,k;char c20=0;if(fp1=fopen(码本文件.txt,rb)=NULL)printf(cannot open this filen);return ;if(fp2=fopen(字符代码.txt,rb)=NULL)printf(cannot open this filen);return ; if(fp3=fopen(破译文件.txt,wb)=NULL)printf(cannot open this filen);return ; for(i=1;i=count;i+)fread(&di,sizeof(struct charcode),1,fp2);i=0;ci=fgetc(fp1);while(ci!=#)for(k=1;k=count;k+)if(!strcmp(c,dk.code)fputc(dk.data,fp3);for(j=0;j=i;j+) cj=0;i=-1;break;i+; ci=fgetc(fp1);fputc(#,fp3);fclose(fp1); fclose(fp2); fclose(fp3);void main() Creat_message(); /建立原文本文件 printf(您输入的文本文件是：n); print1(文本文件.txt); /打印原文本文件 printf(n); Calculate(); /对文本文件进行统计，计算字符种类和权重 HuffmanCoding (); /建立哈夫曼树，计算出哈夫曼编码 printf(每个字符相应的哈夫曼编码是：n); print2(字符代码.txt); printf(n); Transform(); /把原文本文件转化为码本文件 printf(原文件的码本文件