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

1、用哈夫曼编码实现文件压缩实验报告课程名称实验学期 2012 至2013学年 第 一 学期学生所在系部年级20处专业班级学生姓名学号任课教师兰芸 实验成绩_、实验题目I:用哈夫曼编码实现文件压缩二、I实验目的|:1、了解文件的概念。2、掌握线性链表的插入、删除等算法。3、掌握Huffman树的概念及构造方法。4、掌握二叉树的存储结构及遍历算法。5、利用Huffman树及Huffman编码,掌握实现文件压缩的一般原理。三、|实验设备与环境|:微型计算机、Windows系列操作系统、Visual C-H-6.0软件四、|实验内容根据ascii码文件中各ascii字符出现的频率情况创建Haffinan

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

3、符出现频率构造Huffman树，然后将树中结点引向其左孩子的 分支标“0”，引向其右孩子的分支标“1” :每个字符的编码即为从根到每 个叶子的路径上得到的0、1序列。解压根据存放在文件中的编码表和文件压缩后的编码，进行一对一的翻译过程。六、|详细设计压缩的代码#include <stdio.h>#include <stnng.h>#include <stdlib.h>#include <conio.h>stmct headunsigned char b; long count;long paientjchjch; char bits256;/*t

4、he charactor*/*the frequency*/*make a tree*/*the hafiiimaii code*/ header512Jmp;void yasuo()/*压缩*/char filename255,outputfile255,buf512;unsigned char c; char weiijiaimiing255;longlong nun 1 ,pt 1 ,flength;FILE *ifp,*ofp;prmtf(”输入文件地址及文件名:“)；gets(filenaine);ifp=fopen(filename,"rb");/* 打开源文件

5、 *7while(ifp=NULL) pnntf(”打开文件出错E);pnntfC*重新输入文件地址及文件名”)；gets(filename);ifp=fdpen(filename/,rbH);prmtf(”输入压缩后的文件地址和文件名及后缀:”); gets(wenj laimiuig);ofp=fopen(wenjiaimiuig,HwbH);严创建并打开目的文件引wliile(ofp=NULL)pnntfC重新输入压缩后的文件地址和文件名及后缀门;ofp=fopen(weiij laimiHigflength=0:wliile(?feof(ifp)严读取 lfp 文件*7严读取lfp文件

6、*7fiead(&c headerc.couiit+; flength+-r；严按位读取勺flength-1; headerc.couiit-l; fbi(i=0;i<512;i-H-) 严读取文件结束可 严构造哈界曼树*/if(headeri .coxuit! =0)headeii.b=(unsigned char)i;else headeri.b=O;headeri .paient=-l;headerich=headeri .rch=-l;for(j=i+l;j<256;j+)if(headeri.count<headerj.count)tmp=headeri;

7、headeri=headerj; headeij=tmp;fbr(i=0;i<256;i-H-) if(headeri .couiit=0) break;n=i；m=2*n-l;niuil=999999999; for(j=Oj<iJ+)if(headerj .parent!1) contmue;>lieaderj .count)Ptl=J；min 1 =headerj .count; contmue;headeri .count=headerptl.count; headerptl .paient=i;headeri.lch=ptl; mml=999999999;for(j

8、=Oj<iJ+)if(headerj .parent!1) contmue;if(niiiil >headerj .count)PM；mini =headerj .count;continue;headeri .count-r=headerpt 1 .count;header i.rch=ptl;headerfptl .parent=i;fbr(i=O;i<n;i-H-)f=l;headeri.bitsO=O;while(headerf .paient!= 1)J=f;f=headerf .parent;if(headerf.lch=j)j=stilen(headeri bi

9、ts); meininove(headeii.bits+Lheaderi.bits,j+l);headeri .bitsO=,O,;elsej=strlen(headeri bits); meininove(headeii.bits+Lheaderi.bits,j+l); headeii.bitsO V;/*哈期曼构造结束*/fseek(ifp,O,SEEK_SET);/*把文件指针指向文件的开头*/fvrite(&flength,sizeof(int), 1 .ofp); 把哈州曼代码写入 0炉文件 fseek(ofp, & SEEK_SET);buf0=0;f=0;ptl=

10、8；wliile(?feof(ifp)c=fgetc(ifp);/从流中读取一个字符，并增加文件指针的位置f+；foi(i=0;i<n;i-H-)if(c=headeri.b) break;sticat(buf,headeii.bits); /把 headeri.bits 所指字符串添加到 buf 结尾处 j=sUlen(buf);计算字符串buf的长度c=0;while(j>=8)for(i=0;i<8;i+)if(bufli=*r)c=(c«l)|l;else c=c«l;ptl 卄；strcpy(buf,buf8); j=stilen(buf);if

11、(f=flength)break;strcat(buf, ”00000000“)；foi(i=0;i<8;i-H-)if(bufli=r)c=(c«l)|l;else c=c«l;fvvrite(&c 丄 l,ofp);ptl+;fseek(ofjp,4,SEEK_SET); /*fseek用于二进制方式打开的文件，移动文件读写指针位 置第一个是文件流，第3个是指针零点位置，第2个是把指针移动到的地点.*/fvrite(&ptl,sizeof(long), 1 ,ofp); /*是要输出数据的地址，每次写入的位数擞据项的个数, 目标文件地址*/fsee

12、k(ofp,ptl,SEEK_SET);fwrite(&n,sizeof(long), 1 ,ofp);fvvrite( & (h 啓 deiib), 1J ,ofp);c=stilen(headeri.bits);fvvrite(&c 丄 l,ofp);j=stilen(headeri.bits);if(j%8!=0)严按八位读取可fo【(f=j%8;忆 8 計+)strcat(headeri.bits/'OH);while(headeri.bitsO !=0)c=0;for(j=0j<8;j 卄)if(headeri.bitsj=T) c=(c

13、1; 1)|1;else c=c«l; strcpy(headeri.bitsJieaderi.bits+8); /* 把从 headeri.bits+8 地址开始且含有NULL结束符的字符串赋值到以headeii.bits开始的地址空间*/fclose(ifp);fclose(ofp);pmitf(”压缩成功n”)；void main()/* 主函数 */printf(”输入a开始压缩n”)；pmitf(”输入b结束压缩®”)；wliile(l)chai- c;c=getch();if(ca1)vasuoQ;elseif(c=b)return;压缩的图解解压的代码#inc

14、lude <stdio.h>#include <stnng.h>#include <stdlib.h>#include <conio.h>stmct headunsigned char b; /*the charactoi*/long count; /*the fiequency*/long paientjchjch; /*make a tree*/char bits256; /*the haffiinian code*/header512,tmp;void jieya()/* 解压 */chai- filename255,outputfile2

15、55,buf255.bx255; unsigned char c; cliai weiijiamiiuig255;longlong flength;FILE *ifp,*ofp;pnntfC要解压的文件：”)； gets(filenaine);严打开源文件引严创建并打开目的文件引ifp=fdpen(filename,Hrbn);while(ifp=NULL) pnntf(”打开文件出错n“);pnntf("重新输入文件地址及文件名”)； gets(filename);ifp=fdpen(filename/*ibH)；pnntf(-输入解压后的文件地址和文件名及后缀:”); gets(

16、wei)j lannmig);ofp=fbpen(wenjiaimiuig,MwbH); wliile(ofp=NULL)ofp=fopen(Md:123 解压的文件.txtwb”)；fiead(&flength、sizeof(loiig), 1 afp);fread(&fisizeof(long), 1 jfp);fseek(ifp,f,SEEK_SET);fread(&n,sizeof(loiig),l afp);fbr(i=O;i<n;i-H-)fiead(&headd ib J J afp);fiead(&c 丄 ld);P=(long)c

17、;headeri.count=p; headeri.bitsO=O;if(p%8>0)m=p/8+l;else m=p/8;for(j=0j<mj+)fiead( &c,l 丄®);itoa(f.buf2); f=stilen(buf);for(l=8;l>f;l)strcat(headeri .bits/O,r); strcat(headeri.bits,buf);headeri .bitsp=O;fbr(i=O;i<n;i-H-)for(j=i+l;j<nj+)if(strlen(headeri .bits)>strlen(header

18、j .bits)tmp=headeri; headeri=headerj; headeij=tnip;p=strlen(headern-1 .bits); fs 亡 ek(i 如&SEEK_SET); m=0;bxO=O;wlule(l)while(stilen(bx)<(unsigned mt)p)fiead( &c,l 丄); f=c; itoa(f?buf,2); f=stilen(buf); for(l=8:l>f;l)strcat(bx：rOM); strcat(bx,buf);fbr(i=O;i<n;i+)if(memcmp(headeri.bit

19、s,bx,headeri.count)=0) break:sticpv(bx.bx+headeri.count); c=headeri.b;fvvrite(&c,l 丄 ofp);m-H-； if(m=flengtli) break;fclose(ifp); fclose(ofp);pmirff解压成功n”);return;void main()pnntfC输入a开始解压5”); pmitf(”输入b结束解压11”)；wliile(l)clw c;c=getch();if(c=,a,)Jieya();elseif(c=b)return;七、测试结果及分析:F F:新建文件夹Debugyasuo.exea :f:123.txt址和文件名及后缀:f:321.txt压缩前的文件夹中的内容m库，国圉片楠迅皆下裁J育乐壬件夹API官左文档日文版CHMg.c旨库回图片鈕迅雷下裁:写计算机& 本itSBS （C：）口 本（DO口 本it泌盘CE：）§可移动越盅（F:）S 123huahuahuarunqiJi u盘软件大