《用赫夫曼编码完成文件压缩[教资材料].doc》由会员分享，可在线阅读，更多相关《用赫夫曼编码完成文件压缩[教资材料].doc（17页珍藏版）》请在三一文库上搜索。
1、实验报告题目：用赫夫曼编码实现文件压缩班级：理科实验四班 姓名：王渭森学号：2015201992 完成日期：2016.6.101、 需求分析1.现实需求：1）通信线路中实现信息的最大传送，利用变长编码的方式，可以有效充分利用带宽，实现信息传送前的压缩。2).在文件保存时，利用哈夫曼编码的方式，压缩文件,可以实现硬盘存储最大的信息量。2.程序执行的命令包括：1） 读取文件。2） 新建并写入文件。3） 将文件中的字符转换为哈夫曼编码。4） 将哈夫曼编码八位一组专户为十进制，在通过十进制的ASCII码转换为字符。5） 翻译过程现将字符转为01串，再将01串翻译为原来的文件。3.测试数据1）2）3）4
2、）5）新建一个文件并压缩。2、 概要设计1.串的抽象数据类型定义为：ADT String数据对象：D=ai|aiCharacterSet,i=1,2,.,n,n=0数据关系：R1=|ai-1,aiD,i=1,2,.,n基本操作：strcpy(String &S1,String S2)初始条件：串S2存在。操作结果：由串S2复制得串S1.strlen(SString S)初始条件：串S存在。操作结果：返回S的元素个数，称为串的长度。/ADT String2. 二叉树的抽象数据类型定义为：ADT BinaryTree数据对象D：是具有相同特性的元素的集合。数据关系R：若D为空集，则称为空二叉树；若
3、D仅含一个数据元素，则R为空集，否则R=H,H是如下二元关系：1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；2）若Droot，则存在Droot的一个划分DlDr，DlDr=；3）若Dl,则Dl中存在惟一的数据元素x，H，且存在Dl上的关系HlH；若Dr,则Dr中存在惟一的数据元素xr，H，且存在Dr上的关系HrCompressFile()-HuffmanCoding()-Select() -WriteFile()-CoToCh() -DeCompressFile()-ChToCo(CName); -translation()3、 调试分析1. 文件中字符数目可能非常大，不能
4、用一个整的数组来存，所以需要从文件中一个字符一个字符来读取处理。2. 为解决文件中字符出现的不确定性，用数组character256来记录相应ASCII的字符出现次数，统计完后，将出现次数非零的字符存在数组v中，并将它们的权值存在数组w中。3. 在将赫夫曼编码翻译为字符中，translation（）中函数的变量ch，在运算中应该变它的对应的值，即为，传参应为 char &ch，而不应为char ch。4.将哈夫曼八位一组转为十进制时，01串中个数不一定为8的倍数，先遍历文件，统计01串中元素个数，将该个数除以8的余数拿出来，放入压缩文件的第一位，在依次将等于余数个数的01字符直接放入压缩文件，
5、之后的 01串为8的整数倍。5. 读取压缩后的乱码是，可能读出负数，若读出负数，让这个负数加上256再转化为2进制的01串。4、 测试结果1.如图，4为余数。压缩率：125%可见，当文件中元素个数小于8时，压缩文件反而会增大。2.压缩率：7/303.压缩率：9/30。4.原文件大小为：21.2KB压缩文件大小为11.3KB压缩率接近百分之五十。总和2、3、4可见，可见，相同大小的文件，其中元素分布越集中，压缩率越大。5.五、附录源程序文件清单：#define MAXWEIGHT 2147483647#define MAXASCII 255#define MAXNAME 100#include
6、#include#include#includetypedef struct char data;int weight;int parent,lchild,rchild;HTNode,*HuffmanTree;/动态分配数组存储赫夫曼树 typedef char *HuffmanCode;/动态分配数组存储赫夫曼编码。 void Select(HuffmanTree HT,int index,int &s1,int &s2)/从序号为1index的结点中选出两个最小的且没有双亲的结点。 int w1,w2,t,i;s1=0;s2=0;w1=MAXWEIGHT;w2=MAXWEIGHT;for(
7、i=1;i=index;i+)if(HTi.parent=0)if(HTi.weightw1)s2=s1;w2=w1;s1=i;w1=HTi.weight;else if(HTi.weightweight=m;for(p=HT+1,i=1;iweight=*w;p-lchild=0;p-rchild=0;p-parent=0;p-data=*v;for(;iweight=0;p-lchild=0;p-rchild=0;p-parent=0;for(i=n+1;i=m;i+)/在HT1.i-1选择parent为0而且weight最小的/两个结点且weight最小的两个结点，其序号分别/为s1和s
8、2Select(HT,i-1,s1,s2);HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;/-从叶子到根逆向求每个字符的霍夫曼编码-char *cd;int start,c,f;HC=(HuffmanCode)malloc(n+1)*sizeof(char*);cd=(char*)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.
9、parent) if(HTf.lchild=c)cd-start=0; else cd-start=1;HCi=(char*)malloc(n-start+1)*sizeof(char);strcpy(HCi+1,&cdstart);HCi0=vi-1-n; free(cd);return 1; void translation(FILE *fp1,FILE *fp2,char &ch,HuffmanTree HT,int i,int f)/逐字翻译压缩文件中的赫夫曼编码 if(HTi.lchild=0&HTi.rchild=0)/若为叶子结点，则成功翻译一个字符，将它输入到解压文件中 fpu
10、tc(HTi.data,fp2);if(f=0)ch=fgetc(fp1);return;if(ch=0)/若为0，则探索左孩子 f=1;ch=fgetc(fp1);translation(fp1,fp2,ch,HT,HTi.lchild,f);else if(ch=1)/若为1，则探索左孩子f=1;ch=fgetc(fp1);translation(fp1,fp2,ch,HT,HTi.rchild,f);void CoToCh(char CName)FILE *fp1,*fp2;char DNameMAXNAME=0,ch;/存放压缩后的文件名int Bin7=0,asc;/八个01一组放入
11、Bin串;二进制对应的ASCII值 int i,j,num=0,r;printf(请输入你希望得到的压缩后的文件名:);gets(DName);fp1=fopen(CName,rb);fp2=fopen(DName,wb);while(!feof(fp1)/计算0，1的数量 ch=fgetc(fp1);num+;num-;rewind(fp1);r=num%8;/八个一组多余出来的01 fputc(r+0,fp2);/将多出来的数量的值放在压缩文件第一位 for(j=1;j=r;j+)/后面r位原封不动的将01复制进来 ch=fgetc(fp1);fputc(ch,fp2);while(!fe
12、of(fp1)i=0;asc=0;memset(Bin,0,sizeof(Bin);while(!feof(fp1)&i=7)ch=fgetc(fp1);Bini=ch-0;i+; if(feof(fp1)break;for(j=0;j=i-1;j+) asc=asc*2+Binj;fputc(asc,fp2);fclose(fp1);fclose(fp2); printf(压缩后的文件名为:);puts(DName);void WriteFile(HuffmanCode HC,char FName,int k,char v)/将被压缩的文件内容写入另一个文件 FILE *fp1,*fp2;c
13、har CNameMAXNAME=0,ch;strcpy(CName,CP);strcpy(CName+2,FName);/哈夫曼编码文件命名为CP+原文件名fp1=fopen(FName,rb);fp2=fopen(CName,wb);while(1)int i;ch=fgetc(fp1);if(feof(fp1)break;for(int i=0;i=k-1;i+)if(ch=vi)fputs(HCi+1+1,fp2);/将赫夫曼编码写入哈夫曼编码文件 fclose(fp1);fclose(fp2);CoToCh(CName);void CompressFile(HuffmanTree &
14、HT,HuffmanCode &HC,int &k)/读取文件中的字符，构造哈夫曼曼树，得到每个字符的哈夫曼编码 FILE *fp;int flag;char ch,vMAXASCII+1,FNameMAXNAME;/v存放出现的字符 int characterMAXASCII+1=0;/统计每种字符出现的次数 int wMAXASCII+1;/w放字符的权值 printf(请键入要运行的操作编号：n1.压缩已有的文件n2.建立新文件，输入内容并进行压缩n);scanf(%d,&flag);/选择操作 getchar();if(flag=1)printf(请键入需要压缩的文件名：);gets(
15、FName); fp=fopen(FName,r); else if(flag=2)printf(请键入需要压缩的文件名：);gets(FName);printf(请键入文件内容：n);fp=fopen(FName,w);while(ch!=n)scanf(%c,&ch);fputc(ch,fp);fclose(fp);fp=fopen(FName,r);else printf(警告：无此操作项！);return; while(1)/逐个读取文件中的字符,数组character对应字符位置上+1int i;ch=fgetc(fp);if(feof(fp)break; characterch+;
16、for(int i=0;i=MAXASCII-1;i+) /若某字符在在文件中出现，则把它放入v，并把权值计入相同序号的w if(characteri!=0) vk=i;wk+=characteri;printf(文件中出现的字符及它们的权值:n);for(int i=0;i=k-1;i+) printf(%c-%d;n,vi,wi);HuffmanCoding(HT,HC,v,w,k); fclose(fp);printf(上述字符对应的哈夫曼编码：n); for(int i=1;i=k;i+) puts(HCi);WriteFile(HC,FName,k,v);void ChToCo(ch
17、ar DName,char CName)FILE *fp1,*fp2;int r,i,j,Bin7=0,asc;char ch;fp1=fopen(DName,rb);strcpy(CName,RCP);strcpy(CName+3,DName);fp2=fopen(CName,wb);r=fgetc(fp1)-0;for(i=1;i=r;i+)ch=fgetc(fp1);fputc(ch,fp2);while(1)ch=fgetc(fp1);if(feof(fp1)break;asc=(int)ch;if(asc=0;i-)Bini=asc%2;asc=asc/2;for(i=0;i=7;i
18、+) fputc(Bini+0,fp2);fclose(fp1);fclose(fp2);void DecompressFile(HuffmanTree HT,int k)/解压函数 FILE *fp1,*fp2;char DNameMAXNAME,FNameMAXNAME,CNameMAXNAME=0,ch;int r;printf(请键入需要解压的文件名：（注意：文件中的字符权值需与上述相同！）);gets(DName);printf(请输入解压后希望得到的文件名：);gets(FName); printf(解压后的文件名为：);puts(FName); ChToCo(DName,CNam
19、e);fp1=fopen(CName,rb);fp2=fopen(FName,wb);ch=fgetc(fp1);while(!feof(fp1)/到压缩文件末尾结束 translation(fp1,fp2,ch,HT,2*k-1,0); fclose(fp1);fclose(fp2);int main()HuffmanTree HT;HuffmanCode HC;int k=0,flag;CompressFile(HT,HC,k);printf(请键入要运行的操作编号：n1.结束进程n2.解压文件n);scanf(%d,&flag);getchar(); if(flag=1) else if(flag=2) DecompressFile(HT,k);else printf(警告：无此操作项！); return 0;17光a