《哈弗曼树的文件压缩和解压实验报告(C语言).doc》由会员分享，可在线阅读，更多相关《哈弗曼树的文件压缩和解压实验报告(C语言).doc（13页珍藏版）》请在三一办公上搜索。
1、Lab05 树结构的应用学号： 姓名： 实验时间：2011.5.241.问题描述哈弗曼树的编码与译码 功能：实现对任何类型文件的压缩与解码 输入：源文件，压缩文件 输出：解码正确性判定，统计压缩率、编码与解码速度 要求： 使用边编码边统计符号概率的方法（自适应Huffman编码） 和事先统计概率的方法（静态Huffman编码） 。2.1程序清单程序书签：1. main函数2. 压缩函数3. select函数4. encode函数5. 解压函数#include #include #include #include #include struct nodelong weight; /权值unsig
2、ned char ch;/字符int parent,lchild,rchild;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(); el
3、se if(choice=3)return; else printf(输入错误！);/压缩函数 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; dou
4、ble duration1,duration2;void encode(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(of
5、p=NULL) printf(文件名输入错误，文件不存在!n); return;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(h
6、fmnodei.weight!=0)hfmnodei.ch=(unsigned 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+
7、) s1=select(hfmnode,i-1); hfmnodei.lchild=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 seco
8、ndsn, duration1 );*/ printf(编码完成，是否查看编码信息: 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指针移到文件开头位置 fwr
9、ite(&FileLength,4,1,ofp);/将FileLength写入目标文件的前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(c
10、odesi=1) c=(c1)|1; else c=c1; fwrite(&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个字节的位置/为方便解压，把编码信
11、息存入n后面的位置/存储方式为：n*（字符值（1个字节）+该字符的01编码的位数（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
12、,0); while(hfmnodei.code0!=0)/开始存入编码，每8位二进制数存入一个字节 c=0; for(j=0;j8;j+) if(hfmnodei.codej=1) c=(c1)|1; else c=c1; strcpy(hfmnodei.code,hfmnodei.code+8);/编码前移8位，继续存入编码 count+; /编码占的字节数的总值 fwrite(&c,1,1,ofp); printf(n); finish2=clock(); duration2=(double)(finish2- start2) / CLOCKS_PER_SEC; /*printf( 写入
13、目标文件用时为：%f secondsn, duration2);*/ printf( 压缩用时为：%f secondsn, duration1+duration2); speed=(float)FileLength/(duration1+duration2)/1000; printf(n压缩速率为：%5.2f KB/Sn,speed);printf(n); printf(源文件长度为：%ld个字节n,FileLength);sumlength=sumlength+4+n*2+count; /计算压缩后文件的长度printf(压缩后文件长度为：%ld个字节n,sumlength);rate=(f
14、loat)sumlength/(float)FileLength;printf(压缩率(百分比)为：%4.2f%n,rate*100); fclose(ifp); fclose(ofp); return;/返回书签/建立哈弗曼树中用于选择最小权值结点的函数int select(struct node *nodep,int pose) int i;int s1;long min=2147483647;/s初值为long型的最大值for(i=0;i=pose;i+)if(nodepi.parent!=-1)continue;if(nodepi.weightmin)min=nodepi.weight
15、; s1=i;return s1;/返回书签/哈弗曼编码函数void encode(struct node *nodep,int n) /从叶子向根求每个字符的哈弗曼编码int start;int i,f,c;char codes256;codesn-1=0; /编码结束符for(i=0;in;i+) /逐个字符求哈弗曼编码 start=n-1; for(c=i,f=nodepi.parent;f!=-1;c=f,f=nodepf.parent) start-; if(nodepf.lchild=c) codesstart=0; else codesstart=1; strcpy(nodepi
16、.code,&codesstart); nodepi.CodeLength=strlen(nodepi.code); /返回书签/解压函数void uncompress() /解压文件 clock_t start, finish; double duration;FILE *ifp,*ofp; char infile20,outfile20; long FileLength,sumlength,filelength;int n,m; int i,j,k;char buf256,codes256; unsigned char c;int maxlength;float speed; printf
17、(请输入要解压的文件名:); 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); return;start=clock() ;/开始计时 fread(&FileLength,4,1,ifp);/从压缩文件读出FileLength、sumlength fread(&sumlength,4
18、,1,ifp); fseek(ifp,sumlength,SEEK_SET); /利用sumlength读出n的值 fread(&n,4,1,ifp); printf(n解码信息:源文件长度为%d个字节,字符种类n=%dn,FileLength,n); for(i=0;i0) m=hfmnodei.CodeLength/8+1;/m为编码占的字节数 else m=hfmnodei.CodeLength/8; for(j=0;jstrlen(buf);k-) strcat(hfmnodei.code,0); /再把二进制编码存进hfmnode.code中 strcat(hfmnodei.code
19、,buf); hfmnodei.codehfmnodei.CodeLength=0;/去掉编码中多余的0 /找出编码长度的最大值 maxlength=0; for(i=0;imaxlength) maxlength=hfmnodei.CodeLength;/开始写入目标文件 fseek(ifp,8,SEEK_SET); /指针指向编码区，开始解码 filelength=0; codes0=0; buf0=0; while(1) while(strlen(codes)strlen(buf);k-) strcat(codes,0);/把缺掉的0补上 strcat(codes,buf);/codes
20、中此时存的为一串01编码 for(i=0;in;i+) /在codes中查找能使其前weight位和hfmnode.code相同的i值，weight即为codelength if(memcmp(hfmnodei.code,codes,(unsigned int)hfmnodei.CodeLength)=0) break; strcpy(codes,codes+hfmnodei.CodeLength);/更新codes的值 c=hfmnodei.ch; fwrite(&c,1,1,ofp); filelength+; if(filelength=FileLength) break;/写入结束 f
21、inish = clock(); duration = (double)(finish - start) / CLOCKS_PER_SEC; printf( n解压完成，解压用时为：%f secondsn, duration ); fseek(ifp,0,SEEK_SET); FileLength=0; while(!feof(ifp) fread(&c,1,1,ifp); FileLength+;FileLength-; speed=(float)FileLength/duration/1000;/*printf(此文件长度为：%ld个字节n,FileLength);*/printf(n解压
22、速度为：%5.2fKB/Sn,speed); fclose(ifp); fclose(ofp); return;2.2程序运行结果：1.对文件xue.doc（45，056字节）进行压缩，压缩后存储在文件b.txt中，压缩速率为：3003.73KB/S，压缩率为75.50%。程序运行结果截图如下：2.再对b.txt文件进行解压，目标文件为pp.doc,解压后的文件PP.doc与源文件xue.doc完全相同，解压速度为180.94 KB/S。程序运行结果如下：2.3算法描述（1） 压缩文件压缩文件时要先对源文件进行统计，统计字符的种类及出现的次数（即权值）。统计完成之后，建立哈弗曼树：每次选取权值
23、最小且无parent的结点作为左右孩子，建成一棵二叉树，且设置新的二叉树的根结点的权值为其左右孩子的权值之和。直至建成含有2*n-1个结点的哈弗曼树。给每种字符进行编码。按照从叶子到根的顺序求其编码。算法和图示如下：for(i=0;in;i+) start=n-1; for(c=i,f=nodepi.parent;f!=-1;c=f,f=nodepf.parent) start-; if(nodepf.lchild=c) codesstart=0; else codesstart=1; strcpy(nodepi.code,&codesstart);编码完成之后，开始对源文件进行压缩。1. 从
24、源文件读一个字符，从叶子结点中找出和此字符相同的字符结点，将其编码写入一个临时字符组codes；2. 当codes的长度大于等于8时，将其前8位转换成字符写入目标文件中；3. 重复1和2此过程，直至读完源文件中的所有字符；4. 若codes最后还有剩余的不足8位的01代码，则将其低位补0至8位，再写入目标文件。 同时为了便于解码，将源文件的长度FileLength、编码区的长度以及叶子结点的个数n、每个叶子结点的信息也存入目标文件。存储方式如下图所示：FileLength4BSumlength4B源文件编码区叶子数n4B叶子结点信息字符值1B字符的编码位数1B字符的编码. | 1个结点的信息| sumlength（2）解压文件 从被压缩的文件中读出FileLength、n的值，以及每个叶子结点的信息：字符、字符对应的编码。 开始解码： 1.从被压缩的文件编码区读出一个字符，将其值转化成二进制形式（不足8位的高位要补0），存入codes中，直至codes的长度不小于所有叶子结点的编码的长度； 2.用for循环查找出第一个和codes的01字符串匹配的叶子结点编码，将该叶子结点的字符写入目标文件，并将codes的字符串前移，前移位数=该叶子结点编码的长度。 3.重复1和2过程，直至写入的字符数与源文件的长度FileLength相同。
