用赫夫曼编码完成文件压缩教资材料

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,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、h，且存在dl 上的关系hl < h；若dr  ,则dr 中存在惟一的数据元素xr ，<root, xr>  h，且存在dr 上的关系hr < h； 4）（dl， hl、）是一棵符合本定义的二叉树，称为根root的左子树，（dr， hr、）是一棵符合本定义的二叉树，称为根root的右子树。基本操作p：initbitree(&t)；操作结果：构造空二叉树。 createbitree(&t)

5、；初始条件：二叉树存在。操作结果：按输入格式构造二叉树。  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()->compr

7、essfile()->huffmancoding()->select() ->writefile()->cotoch() ->decompressfile()->chtoco(cname); ->translation()3、 调试分析1. 文件中字符数目可能非常大，不能用一个整的数组来存，所以需要从文件中一个字符一个字符来读取处理。2. 为解决文件中字符出现的不确定性，用数组character256来记录相应ascii的字符出现次数，统计完后，将出现次数非零的字符存在数组v中，并将它们的权值存在数组w中。3. 在将赫夫曼编码翻译为字符中，transl

8、ation（）中函数的变量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,lchil

10、d,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=w1;s

11、1=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)*sizeof(

12、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.parent=i

14、;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、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.dat

16、a,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

17、;/八个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、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("压缩后的文件名为:");pu

19、ts(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=fgetc(fp

20、1);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 charac

21、termaxascii+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("请键入需要压缩的文件名：");g

22、ets(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; cha

23、racterch+;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&

24、lt;=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-)bini