用赫夫曼编码完成文件压缩

1、精选文档试验报告题目：用赫夫曼编码实现文件压缩班级：理科试验四班 姓名：王渭森学号：2015201992 完成日期：2016.6.101、 需求分析1.现实需求：1）通信线路中实现信息的最大传送，利用变长编码的方式，可以有效充分利用带宽，实现信息传送前的压缩。2).在文件保存时，利用哈夫曼编码的方式，压缩文件,可以实现硬盘存储最大的信息量。2.程序执行的命令包括：1） 读取文件。2） 新建并写入文件。3） 将文件中的字符转换为哈夫曼编码。4） 将哈夫曼编码八位一组专户为十进制，在通过十进制的ASCII码转换为字符。5） 翻译过程现将字符转为01串，再将01串翻译为原来的文件。3.测试数据1）2

2、）3）4）5）新建一个文件并压缩。2、 概要设计1.串的抽象数据类型定义为：ADT String数据对象：D=ai|aiCharacterSet,i=1,2,.,n,n>=0数据关系：R1=<ai-1,ai>|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：是具有相同特性的

3、元素的集合。数据关系R：若D为空集，则称为空二叉树；   若D仅含一个数据元素，则R为空集，否则R = H, H是如下二元关系： 1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； 2） 若D  root  ，则存在D  root 的一个划分Dl Dr ，DlDr =；3） 若Dl,则Dl 中存在惟一的数据元素x，<root, xl> &#

4、160;H，且存在Dl 上的关系Hl < H；若Dr  ,则Dr 中存在惟一的数据元素xr ，<root, xr>  H，且存在Dr 上的关系Hr < H； 4）（Dl， Hl、）是一棵符合本定义的二叉树，称为根root的左子树，（Dr， Hr、）是一棵符合本定义的二叉树，称为根root的右子树。基本操作P：InitBitree(&T)；操作结果：构造空二叉树。 CreateBitree(&am

5、p;T)；初始条件：二叉树存在。操作结果：按输入格式构造二叉树。  Value(T, e)；初始条件：二叉树存在，e是T中某个结点。操作结果：返回结点e的值。 Assign(&T, &e, value)； 初始条件：二叉树存在，e是T中某个结点。操作结果：结点e赋值为value 。 Parent(T, e)；初始条件：二叉树存在，e是T中某个结点。操作结果：若e是T的非根结点，则返回它的双亲，否则返回“空”。LeftChild(T, e)；初始条件：二叉树存在，e是T中

6、某个结点。操作结果：返回e的左孩子。若e无左孩子，则返回“空”。RightChild(T, e)；初始条件：二叉树存在，e是T中某个结点。操作结果：返回e的右孩子。若e无右孩子，则返回“空”。 ADT BinaryTree3. 赫夫曼树和赫夫曼编码的存储表示：typedef struct char data;int weight;int parent,lchild,rchild;HTNode,*HuffmanTree;/动态安排数组存储赫夫曼树 typedef char *HuffmanCode;/动态安排数组存储赫夫曼编码。 4.函数的调用关系图：main()->C

7、ompressFile()->HuffmanCoding()->Select() ->WriteFile()->CoToCh() ->DeCompressFile()->ChToCo(CName); ->translation()3、 调试分析1. 文件中字符数目可能格外大，不能用一个整的数组来存，所以需要从文件中一个字符一个字符来读取处理。2. 为解决文件中字符消灭的不确定性，用数组character256来记录相应ASCII的字符消灭次数，统计完后，将消灭次数非零的字符存在数组v中，并将它们的权值存在数组w中。3. 在将赫夫曼编码翻译为字符中，tr

8、anslation（）中函数的变量ch，在运算中应当变它的对应的值，即为，传参应为 char &ch，而不应为char ch。4.将哈夫曼八位一组转为十进制时，01串中个数不肯定为8的倍数，先遍历文件，统计01串中元素个数，将该个数除以8的余数拿出来，放入压缩文件的第一位，在依次将等于余数个数的01字符直接放入压缩文件，之后的 01串为8的整数倍。5. 读取压缩后的乱码是，可能读出负数，若读出负数，让这个负数加上256再转化为2进制的01串。4、 测试结果1.如图，4为余数。压缩率：125%可见，当文件中元素个数小于8时，压缩文件反而会增大。2.压缩率：7/303.压缩率：9/30。4

9、.原文件大小为：21.2KB压缩文件大小为11.3KB压缩率接近百分之五十。总和2、3、4可见，可见，相同大小的文件，其中元素分布越集中，压缩率越大。5.五、附录源程序文件清单：#define MAXWEIGHT 2147483647#define MAXASCII 255#define MAXNAME 100#include<stdio.h> #include<stdlib.h>#include<string.h>#include<memory.h>typedef struct char data;int weight;int parent,l

10、child,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(i=1;i<=index;i+)if(HTi.parent=0)if(HTi.weight<w1)s2=s1;w2=

11、w1;s1=i;w1=HTi.weight;else if(HTi.weight<w2)s2=i;w2=HTi.weight; int HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,char *v,int *w,int n)/v存放需要编码的n个字符，w存放对应的权值， /构造赫夫曼树，并求出n个字符的赫夫曼编码。 if(n=0)/没有合法字符时 printf("没有需要编码的字符!");return -1; if(n=1)/只有一个合法字符时 HC=(HuffmanCode)malloc(n+1)*siz

12、eof(char*);HC1=(char*)malloc(3*sizeof(char);HC10=*v;HC11='0'HC12=0;HT=(HuffmanTree)malloc(2*sizeof(HTNode);HT1.parent=0;HT1.lchild=0;HT1.rchild=0;HT1.weight=*w;HT1.data=*v;return 0;int s1,s2,m,i;m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);HuffmanTree p;HT->weight=m;for(p=HT+1,i=1;i

13、<=n;i+,p+,w+,v+)p->weight=*w;p->lchild=0;p->rchild=0;p->parent=0;p->data=*v;for(;i<=m;i+,p+)p->weight=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和s2Select(HT,i-1,s1,s2);HTs1.parent=i;HTs2.pare

14、nt=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.parent) if(HTf.lchild=c)cd-start='0&#

15、39; 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)/若为叶子结点，则成功翻译一个字符，将它输入到解压文件中 fputc(HTi

16、.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

17、,asc;/八个01一组放入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&

18、lt;=r;j+)/后面r位原封不动的将01复制进来 ch=fgetc(fp1);fputc(ch,fp2);while(!feof(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("压缩后的文件名为:"

19、);puts(DName);void WriteFile(HuffmanCode HC,char FName,int k,char v)/将被压缩的文件内容写入另一个文件 FILE *fp1,*fp2;char CNameMAXNAME=0,ch;strcpy(CName,"CP");strcpy(CName+2,FName);/哈夫曼编码文件命名为"'CP'+原文件名"fp1=fopen(FName,"rb");fp2=fopen(CName,"wb");while(1)int i;ch=fget

20、c(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 &HT,HuffmanCode &HC,int &k)/读取文件中的字符，构造哈夫曼曼树，得到每个字符的哈夫曼编码 FILE *fp;int flag;char ch,vMAXASCII+1,FNameMAXNAME;/v存放消灭的字符 int ch

21、aracterMAXASCII+1=0;/统计每种字符消灭的次数 int wMAXASCII+1;/w放字符的权值 printf("请键入要运行的操作编号：n1.压缩已有的文件n2.建立新文件，输入内容并进行压缩n");scanf("%d",&flag);/选择操作 getchar();if(flag=1)printf("请键入需要压缩的文件名：");gets(FName); fp=fopen(FName,"r"); else if(flag=2)printf("请键入需要压缩的文件名："

22、;);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;

23、 characterch+;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=

24、1;i<=k;i+) puts(HCi);WriteFile(HC,FName,k,v);void ChToCo(char 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)asc+=256;for(i=7;i>=0;i-)Bi