用哈夫曼编码C语言实现文件压缩.doc

《用哈夫曼编码C语言实现文件压缩.doc》由会员分享，可在线阅读，更多相关《用哈夫曼编码C语言实现文件压缩.doc（14页珍藏版）》请在三一文库上搜索。

1、用哈夫曼编码实现文件压缩实 验 报 告课程名称 数据结构B 实验学期 2012 至 2013 学年 第 一 学期学生所在系部 计算机学院 年级 2011 专业班级 信管B111 学生姓名 学号 任课教师 兰芸 实验成绩 一、实验题目：用哈夫曼编码实现文件压缩二、实验目的：1、 了解文件的概念。2、 掌握线性链表的插入、删除等算法。3、掌握Huffman树的概念及构造方法。4、掌握二叉树的存储结构及遍历算法。5、利用Huffman树及Huffman编码，掌握实现文件压缩的一般原理。三、实验设备与环境：微型计算机、Windows 系列操作系统 、Visual C+6.0软件四、实验内容：根据asc

2、ii码文件中各ascii字符出现的频率情况创建Haffman树，再将各字符对应的哈夫曼编码写入文件中，实现文件压缩。五、概要设计：（1）构造Hufffman树的方法Hufffman算法构造Huffman树步骤：I. 根据给定的n个权值w1,w2,wn，构造n棵只有根结点的二叉树，令起权值为wj。II. 在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和。III. 在森林中删除这两棵树，同时将新得到的二叉树加入森林中。IV. 重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树。（2）Huffman编码：数据通信用的二进制编码思想：根据

3、字符出现频率编码，使电文总长最短编码：根据字符出现频率构造Huffman树，然后将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列。(3) 解压 根据存放在文件中的编码表和文件压缩后的编码，进行一对一的翻译过程。六、详细设计： 压缩的代码#include #include #include #include struct head unsigned char b; /*the charactor*/ long count; /*the frequency*/ long parent,lch,rch; /*make a tr

4、ee*/ char bits256; /*the haffuman code*/ header512,tmp; void yasuo() /*压缩*/ char filename255,outputfile255,buf512; unsigned char c; char wenjianming255; long i,j,m,n,f; long min1,pt1,flength; FILE *ifp,*ofp; printf(输入文件地址及文件名:); gets(filename); ifp=fopen(filename,rb); /*打开源文件*/while(ifp=NULL) printf

5、打开文件出错n); printf(重新输入文件地址及文件名); gets(filename); ifp=fopen(filename,rb); printf(输入压缩后的文件地址和文件名及后缀:); gets(wenjianming); ofp=fopen(wenjianming,wb); /*创建并打开目的文件*/while(ofp=NULL)printf(重新输入压缩后的文件地址和文件名及后缀:); ofp=fopen(wenjianming,wb); flength=0; while(!feof(ifp) /*读取ifp文件*/ fread(&c,1,1,ifp); /*按位读取*/

6、headerc.count+; flength+; flength-1; headerc.count-1; /*读取文件结束*/ for(i=0;i512;i+) /*构造哈弗曼树*/ if(headeri.count!=0) headeri.b=(unsigned char)i; else headeri.b=0; headeri.parent=-1; headeri.lch=headeri.rch=-1; for(i=0;i256;i+) for(j=i+1;j256;j+) if(headeri.countheaderj.count) tmp=headeri; headeri=heade

7、rj; headerj=tmp; for(i=0;i256;i+) if(headeri.count=0) break; n=i; m=2*n-1; for(i=n;im;i+) min1=999999999; for(j=0;jheaderj.count) pt1=j; min1=headerj.count; continue; headeri.count=headerpt1.count; headerpt1.parent=i; headeri.lch=pt1; min1=999999999; for(j=0;jheaderj.count) pt1=j; min1=headerj.count

8、 continue; headeri.count+=headerpt1.count; headeri.rch=pt1; headerpt1.parent=i; for(i=0;in;i+) f=i; headeri.bits0=0; while(headerf.parent!=-1) j=f; f=headerf.parent; if(headerf.lch=j) j=strlen(headeri.bits); memmove(headeri.bits+1,headeri.bits,j+1); headeri.bits0=0; else j=strlen(headeri.bits); mem

9、move(headeri.bits+1,headeri.bits,j+1); headeri.bits0=1; /*哈弗曼构造结束*/ fseek(ifp,0,SEEK_SET); /*把文件指针指向文件的开头*/ fwrite(&flength,sizeof(int),1,ofp); /把哈弗曼代码写入ofp文件 fseek(ofp,8,SEEK_SET); buf0=0; f=0; pt1=8; while(!feof(ifp) c=fgetc(ifp); /从流中读取一个字符，并增加文件指针的位置 f+; for(i=0;i=8) for(i=0;i8;i+) if(bufi=1) c=

10、c1)|1; else c=c0) strcat(buf,00000000); for(i=0;i8;i+) if(bufi=1) c=(c1)|1; else c=c1; fwrite(&c,1,1,ofp); pt1+; fseek(ofp,4,SEEK_SET); /*fseek 用于二进制方式打开的文件,移动文件读写指针位置.第一个是文件流,第3个是指针零点位置,第2个是把指针移动到的地点. */ fwrite(&pt1,sizeof(long),1,ofp); /*是要输出数据的地址,每次写入的位数,数据项的个数，目标文件地址*/ fseek(ofp,pt1,SEEK_SET);

11、fwrite(&n,sizeof(long),1,ofp); for(i=0;in;i+) fwrite(&(headeri.b),1,1,ofp); c=strlen(headeri.bits); fwrite(&c,1,1,ofp); j=strlen(headeri.bits); if(j%8!=0) /*按八位读取*/ for(f=j%8;f8;f+) strcat(headeri.bits,0); while(headeri.bits0!=0) c=0; for(j=0;j8;j+) if(headeri.bitsj=1) c=(c1)|1; else c=c1; strcpy(he

12、aderi.bits,headeri.bits+8); /*把从headeri.bits+8地址开始且含有NULL结束符的字符串赋值到以headeri.bits开始的地址空间 */ fwrite(&c,1,1,ofp); fclose(ifp); fclose(ofp); printf(压缩成功n); void main() /*主函数*/printf(输入a开始压缩n);printf(输入b结束压缩n);while(1)char c; c=getch(); if(c=a) yasuo(); else if(c=b) return;压缩的图解解压的代码#include #include #in

13、clude #include struct head unsigned char b; /*the charactor*/ long count; /*the frequency*/ long parent,lch,rch; /*make a tree*/ char bits256; /*the haffuman code*/ header512,tmp; void jieya() /*解压*/ char filename255,outputfile255,buf255,bx255; unsigned char c; char wenjianming255; long i,j,m,n,f,p,

14、l; long flength; FILE *ifp,*ofp; printf(要解压的文件：); gets(filename); ifp=fopen(filename,rb); /*打开源文件*/while(ifp=NULL) printf(打开文件出错n); printf(重新输入文件地址及文件名); gets(filename); ifp=fopen(filename,rb); printf(输入解压后的文件地址和文件名及后缀:); gets(wenjianming); ofp=fopen(wenjianming,wb); /*创建并打开目的文件*/while(ofp=NULL) ofp

15、fopen(d:123解压的文件.txt,wb); 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;i0) m=p/8+1; else m=p/8; for(j=0;jf;l-) strcat(headeri.bits,0); strcat(headeri.bits,buf); headeri.bitsp=0; for(i=0;in;i+) for(j=i+1;jstrlen(header

16、j.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)f;l-) strcat(bx,0); strcat(bx,buf); for(i=0;in;i+) if(memcmp(headeri.bits,bx,headeri.count)=0) break; strcpy(bx,bx+headeri.count); c=headeri.b; fwrite(&c,1,1,ofp);

17、 m+; if(m=flength) break; fclose(ifp); fclose(ofp); printf(解压成功n); return; void main() /*主函数*/printf(输入a开始解压n);printf(输入b结束解压n);while(1)char c; c=getch(); if(c=a) jieya(); else if(c=b) return;七、测试结果及分析：压缩前的文件夹中的内容压缩后的文件夹中的内容解压后文件夹中的内容 八、教师评语：教 师 评 价评定项目ABCD评定项目ABCD算法正确界面美观，布局合理程序结构合理操作熟练语法、语义正确解析完整实验结果正确文字流畅报告规范题解正确其他：评价教师签名：年 月 日