《哈夫曼树与文件解压压缩c言代码讲义》由会员分享，可在线阅读，更多相关《哈夫曼树与文件解压压缩c言代码讲义（13页珍藏版）》请在金锄头文库上搜索。
1、1.问题描述哈弗曼树的编码与译码 功能：实现对任何类型文件的压缩与解码 输入：源文件，压缩文件 输出：解码正确性判定，统计压缩率、编码与解码速度 要求： 使用边编码边统计符号概率的方法（自适应Huffman编码） 和事先统计概率的方法（静态Huffman编码）2.1程序清单程序书签：1. main函数2. 压缩函数3. select函数4. encode函数5. 解压函数#include #include #include #include #include struct nodelong weight; /权值unsigned char ch;/字符int parent,lchild,rch
2、ild;char code256;/编码的位数最多为256位 int CodeLength;/编码长度hfmnode512;void compress();void uncompress(); /主函数void main()int choice; printf(请选择13：n); printf(1.压缩文件n); printf(2.解压文件n); printf(3.退出！n);scanf(%d,&choice);if(choice=1)compress();else if(choice=2)uncompress(); else if(choice=3)return; else printf(输
3、入错误！);/压缩函数 void compress()int i,j;char infile20,outfile20;FILE *ifp,*ofp; unsigned char c;/long FileLength,filelength=0;int n,m;/叶子数和结点数int s1,s2; /权值最小的两个结点的标号char codes256;long sumlength=0;float rate,speed;int count=0;clock_t start1, start2,finish1,finish2; double duration1,duration2;void encode(
4、struct node *nodep,int n);/编码函数int select(struct node *nodep,int pose);/用于建哈弗曼树中选择权值最小的结点的函数 printf(请输入要压缩的文件名:); scanf(%s,infile); ifp=fopen(infile,rb);if(ifp=NULL) printf(文件名输入错误，文件不存在!n); return; printf(请输入目标文件名:); scanf(%s,outfile); ofp=fopen(outfile,wb);if(ofp=NULL) printf(文件名输入错误，文件不存在!n); ret
5、urn;start1=clock() ;/开始计时1/统计文件中字符的种类以及各类字符的个数/先用字符的ASCII码值代替结点下标FileLength=0; while(!feof(ifp) fread(&c,1,1,ifp); hfmnodec.weight+; FileLength+;FileLength-; /文件中最后一个字符的个数会多统计一次，所以要减一hfmnodec.weight-;/再将ASCII转换为字符存入到结点的ch成员里，同时给双亲、孩子赋初值-1 n=0; for(i=0;i256;i+)if(hfmnodei.weight!=0)hfmnodei.ch=(unsig
6、ned char)i; n+;/叶子数 hfmnodei.lchild=hfmnodei.rchild=hfmnodei.parent=-1; m=2*n-1;/哈弗曼树结点总数 j=0; for(i=0;i256;i+)/去掉权值为0的结点 if(hfmnodei.weight!=0) hfmnodej=hfmnodei; j+; for(i=n;im;i+)/初始化根结点hfmnodei.lchild=hfmnodei.rchild=-1;hfmnodei.parent=-1;/建立哈弗曼树 for(i=n;im;i+) s1=select(hfmnode,i-1); hfmnodei.l
7、child=s1; hfmnodes1.parent=i; s2=select(hfmnode,i-1); hfmnodei.rchild=s2; hfmnodes2.parent=i; hfmnodei.weight=hfmnodes1.weight+hfmnodes2.weight; /编码encode(hfmnode,n); finish1=clock();duration1=(double)(finish1- start1) / CLOCKS_PER_SEC; /*printf( 哈弗曼树编码用时为：%f secondsn, duration1 );*/ printf(编码完成，是否查
8、看编码信息: y or n?n); c=getch(); if(c=y)printf(n); printf(叶子数为%d,结点数为%dn,n,m); for(i=0;in;i+)printf(%d号叶子结点的权值为：%ld,双亲为：%d,左右孩子：%d,编码为：%sn,i,hfmnodei.weight,hfmnodei.parent,hfmnodei.lchild,hfmnodei.code);start2=clock() ;/开始计时2 fseek(ifp,0,SEEK_SET);/将ifp指针移到文件开头位置 fwrite(&FileLength,4,1,ofp);/将FileLengt
9、h写入目标文件的前4个字节的位置 fseek(ofp,8,SEEK_SET);/再将目标文件指针ofp移到距文件开头8个字节位置 codes0=0;/将编码信息写入目标文件 while(!feof(ifp) fread(&c,1,1,ifp); filelength+; for(i=0;i=8) for(i=0;i8;i+)/将codes的前8位01代码表示的字符存入c if(codesi=1) c=(c1)|1; else c=c0) strcat(codes,00000000); for(i=0;i8;i+) if(codesi=1) c=(c1)|1; else c=c1; fwrite
10、(&c,1,1,ofp); sumlength+; sumlength+=8;printf(编码区总长为：%ld个字节n,sumlength-8); /将sumlength和n的值写入目标文件，为的是方便解压 fseek(ofp,4,SEEK_SET); fwrite(&sumlength,4,1,ofp);/把sumlength写进目标文件的第5-8个字节里 fseek(ofp,sumlength,SEEK_SET); fwrite(&n,4,1,ofp);/把叶子数n写进编码段后面的4个字节的位置/为方便解压，把编码信息存入n后面的位置/存储方式为：n*（字符值（1个字节）+该字符的01编
11、码的位数（1个字节）+编码（字节数不确定，用count来计算总值） for(i=0;in;i+) fwrite(&(hfmnodei.ch),1,1,ofp); c=hfmnodei.CodeLength;/编码最长为256位，因此只需用一个字节存储 fwrite(&c,1,1,ofp); /写入字符的编码 if(hfmnodei.CodeLength%8!=0) for(j=hfmnodei.CodeLength%8;j8;j+)/把编码不足8位的在低位补0,赋值给C，再把C写入 strcat(hfmnodei.code,0); while(hfmnodei.code0!=0)/开始存入编码，每8位二进制数存入一个字节 c=0; for(j=0;j8;j+)
