版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、#include <string.h>#include <stdlib.h>#include <conio.h>struct headunsigned char b; /记录字符在数组中的位置 long count; /字符出现频率(权值)long parent,lchild,rchild; /定义哈夫曼树指针变量 char bits256; /定义存储哈夫曼编码的数组 header512,tmp;/*压缩*/void compress()char filename255,outputfile255,buf512; unsigned char c;long
2、i,j,m,n,f;long min1,pt1,flength,length1,length2;double div;FILE *ifp,*ofp;printf("t请您输入需要压缩的文件:"); gets(filename);ifp=fopen(filename,"rb");if(ifp=NULL)printf("nt文件打开失败!nn");return;printf("t请您输入压缩后的文件名:"); gets(outputfile);ofp=fopen(strcat(outputfile,".hub
3、"),"wb"); if(ofp=NULL)printf("nt压缩文件失败!nn");return;flength=0;while(!feof(ifp)fread(&c,1,1,ifp);headerc.count+; /字符重复出现频率+1flength+; /字符出现原文件长度+1flength-;length1=flength; /原文件长度用作求压缩率的分母headerc.count-;for(i=0;i<512;i+)if(headeri.count!=0) headeri.b=(unsigned char)i;/*将
4、每个哈夫曼码值及其对应的ASCII码存放在一维数组headeri中,且编码表中的下标和ASCII码满足顺序存放关系*/else headeri.b=0;headeri.parent=-1;headeri.lchild=headeri.rchild=-1; /对结点进行初始化for(i=0;i<256;i+) /根据频率(权值)大小,对结点进行排序,选择较小的结点进树 for(j=i+1;j<256;j+)if(headeri.count<headerj.count)tmp=headeri;headeri=headerj;headerj=tmp;for(i=0;i<256
5、;i+) if(headeri.count=0) break;n=i; /外部叶子结点数为n个时,内部结点数为n-1,整个哈夫曼树的需要的结点数为2*n-1. m=2*n-1;for(i=n;i<m;i+) /构建哈夫曼树min1=999999999; /预设的最大权值,即结点出现的最大次数for(j=0;j<i;j+)if(headerj.parent!=-1) continue;/parent!=-1说明该结点已存在哈夫曼树中,跳出循环重新选择新结点*/if(min1>headerj.count)pt1=j;min1=headerj.count;continue;head
6、eri.count=headerpt1.count;headerpt1.parent=i; /依据parent域值(结点层数)确定树中结点之间的关系headeri.lchild=pt1; /计算左分支权值大小min1=999999999;for(j=0;j<i;j+)if(headerj.parent!=-1) continue;if(min1>headerj.count)pt1=j;min1=headerj.count;continue;headeri.count+=headerpt1.count;headeri.rchild=pt1; /计算右分支权值大小headerpt1.p
7、arent=i;for(i=0;i<n;i+) /哈夫曼无重复前缀编码f=i;headeri.bits0=0; /根结点编码0while(headerf.parent!=-1)j=f;f=headerf.parent;if(headerf.lchild=j) /置左分支编码0j=strlen(headeri.bits);memmove(headeri.bits+1,headeri.bits,j+1);/依次存储连接“0”“1”编码headeri.bits0='0'else /置右分支编码1j=strlen(headeri.bits);memmove(headeri.bit
8、s+1,headeri.bits,j+1);headeri.bits0='1'fseek(ifp,0,SEEK_SET); /从文件开始位置向前移动0字节,即定位到文件开始位置 fwrite(&flength,sizeof(int),1,ofp);/*用来将数据写入文件流中,参数flength指向欲写入的数据地址,总共写入的字符数以参数size*int来决定,返回实际写入的int数目1*/fseek(ofp,8,SEEK_SET);buf0=0; /定义缓冲区,它的二进制表示00000000f=0;pt1=8;/*假设原文件第一个字符是"A",8位2
9、进制为01000001,编码后为0110识别编码第一个'0', 那么我们就可以将其左移一位,看起来没什么变化。下一个是'1',应该|1,结果00000001同理4位都做完,应该是00000110,由于字节中的8位并没有全部用完,我们应该继续读下一个字符, 根据编码表继续拼完剩下的4位,如果字符的编码不足4位,还要继续读一个字符,如果字符编码超过4位,那么我们将把剩下的位信息拼接到一个新的字节里*/while(!feof(ifp)c=fgetc(ifp);f+;for(i=0;i<n;i+)if(c=headeri.b) break;strcat(buf,h
10、eaderi.bits);j=strlen(buf);c=0;while(j>=8) /对哈夫曼编码位操作进行压缩存储for(i=0;i<8;i+)if(bufi='1') c=(c<<1)|1;else c=c<<1;fwrite(&c,1,1,ofp);pt1+; /统计压缩后文件的长度strcpy(buf,buf+8); /一个字节一个字节拼接j=strlen(buf);if(f=flength) break;if(j>0) /对哈夫曼编码位操作进行压缩存储strcat(buf,"00000000");
11、for(i=0;i<8;i+)if(bufi='1') c=(c<<1)|1;else c=c<<1;fwrite(&c,1,1,ofp);pt1+;fseek(ofp,4,SEEK_SET);fwrite(&pt1,sizeof(long),1,ofp);fseek(ofp,pt1,SEEK_SET);fwrite(&n,sizeof(long),1,ofp);for(i=0;i<n;i+)fwrite(&(headeri.b),1,1,ofp);c=strlen(headeri.bits);fwrite(&
12、amp;c,1,1,ofp);j=strlen(headeri.bits);if(j%8!=0) /若存储的位数不是8的倍数,则补0for(f=j%8;f<8;f+)strcat(headeri.bits,"0");while(headeri.bits0!=0)c=0;for(j=0;j<8;j+) /字符的有效存储不超过8位,则对有效位数左移实现两字符编码的连接 if(headeri.bitsj='1') c=(c<<1)|1; /|1不改变原位置上的“0”“1”值else c=c<<1;strcpy(headeri.b
13、its,headeri.bits+8); /把字符的编码按原先存储顺序连接fwrite(&c,1,1,ofp);length2=pt1-;div=(double)length1-(double)length2)/(double)length1; /计算文件的压缩率fclose(ifp);fclose(ofp);printf("nt压缩文件成功!n");printf("t压缩率为 %f%nn",div*100);return;/*解压缩*/void uncompress()char filename255,outputfile255,buf255,
14、bx255;unsigned char c;long i,j,m,n,f,p,l;long flength;FILE *ifp,*ofp;printf("t请您输入需要解压缩的文件:");gets(filename);ifp=fopen(strcat(filename,".hub"),"rb");if(ifp=NULL)printf("nt文件打开失败!n");return;printf("t请您输入解压缩后的文件名:");gets(outputfile);ofp=fopen(outputfil
15、e,"wb");if(ofp=NULL)printf("nt解压缩文件失败!n");return;fread(&flength,sizeof(long),1,ifp); /读取原文件长度,对文件进行定位 fread(&f,sizeof(long),1,ifp);fseek(ifp,f,SEEK_SET);fread(&n,sizeof(long),1,ifp);for(i=0;i<n;i+)fread(&headeri.b,1,1,ifp);fread(&c,1,1,ifp);p=(long)c; /读取原文
16、件字符的权值headeri.count=p;headeri.bits0=0;if(p%8>0) m=p/8+1;else m=p/8;for(j=0;j<m;j+)fread(&c,1,1,ifp);f=c;itoa(f,buf,2); /将f转换为二进制表示的字符串f=strlen(buf);for(l=8;l>f;l-)strcat(headeri.bits,"0");strcat(headeri.bits,buf);headeri.bitsp=0;for(i=0;i<n;i+) /根据哈夫曼编码的长短,对结点进行排序 for(j=i+1
17、;j<n;j+)if(strlen(headeri.bits)>strlen(headerj.bits)tmp=headeri;headeri=headerj;headerj=tmp;p=strlen(headern-1.bits);fseek(ifp,8,SEEK_SET);m=0;bx0=0;while(1) /通过哈夫曼编码的长短,依次解码,从原来的位存储还原到字节存储 while(strlen(bx)<(unsigned int)p)fread(&c,1,1,ifp);f=c;itoa(f,buf,2);f=strlen(buf);for(l=8;l>f
18、;l-) /在单字节内对相应位置补0strcat(bx,"0");strcat(bx,buf);for(i=0;i<n;i+)if(memcmp(headeri.bits,bx,headeri.count)=0) break;strcpy(bx,bx+headeri.count); /*从压缩文件中的按位存储还原到按字节存储字符, 字符位置不改变*/c=headeri.b;fwrite(&c,1,1,ofp);m+; /统计解压缩后文件的长度if(m=flength) break; /flength是原文件长度fclose(ifp);fclose(ofp);p
19、rintf("nt解压缩文件成功!n");if(m=flength) /对解压缩后文件和原文件相同性比较进行判断(根据文件大小) printf("t解压缩文件与原文件相同!nn");else printf("t解压缩文件与原文件不同!nn");return;/*主函数*/int main()int c;while(1) /菜单工具栏printf("t _n"); printf("n");printf("t * 压缩、解压缩 小工具 * n");printf("t _n"); printf("t _n"); printf("t| |n");printf("t| 1.压缩 |n");printf("t| 2.解压缩 |n");printf("t| 0.退出 |n");printf("t|_|n&qu
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024年光学纤维面板系列项目合作计划书
- 年产20000吨生物质颗粒燃料林业资源综合利用项目可行性研究报告写作模板-备案审批
- 2020年7月英语六级真题及参考答案完整版
- 2024年超低频综合参数测试仪项目合作计划书
- 2024年天然气液化模块合作协议书
- 梦想演讲稿800字(34篇)
- 三年级上册美术教案-第16课 新颖的电脑|人教新课标
- KUD教学目标下的单元逆向设计与实施
- 2024年内蒙古包头市中考物理押题试卷(二)
- 习作《续写故事》(教案)部编版语文三年级上册
- 家谱编印合同
- 2024年云南省三校生高考计算机信息类备考试题库汇总-上(单选题部分)
- 计算机操作系统(第二版)课件:Linux内存管理机制
- 《银河帝国-基地》阅读试卷及答案
- 2024年山西建设投资集团有限公司招聘笔试参考题库含答案解析
- 医用电子细胞培养箱的原理与应用
- 中国的民族融合与多元文化
- 一年级上册数学期末质量分析
- 炼丹炉-国货品牌趋势洞察报告 2023
- 梅尼埃病个案护理
- 家庭教育宣传做智慧家长讲座家庭教育家长会课件
评论
0/150
提交评论