Huffman编码的应用-课程设计

1、重庆科技学院数据结构课程设计报告学 院:电气与信息工程学院专业班级:计科2010-01学生姓名： XXX学 号:201044*设计地点（单位）计算机基础自主学习中心设计题目：Huffman编码的应用完成日期：2012年1月13日指导教师评语：成绩（五级记分制）：指导教师（签字）:_ _ 一课程设计任务书设计题目：Huffman编码的应用学生姓名XXX课艮程名称数据结构课程设计专业班级计科 2010-01地点计算机基础自主学习中心起止时间2011.12.31-2012.1.13设利用赫夫E曼编码的实现原理码对数据进行无损压缩，设计个实现Huffman压缩计的编码和解码的程序。具体要求如下：内1）

2、读入待压缩的文本文件；容2）统计分析文本文件中各字符的出现频度,以频度作为构造Huffman树的权值。及3）根据各字符出现的不同频度构造Huffman树，然后规定每种字符的Huffma n要编码。求4）再次读入待压缩的文本文件，然后根据各字符的 Huffman编码逐一替代，将得到的编码流写入到新的文件中，并且计算压缩率。5）解码过程：先读入上一步骤得到的新文件，将其看作比特流，根据Huffma n树，对比特流逐位译码，将解码结果又写入一个新的文件中。设测试数据要求：计参自行设计一个能说明压缩效果和过程的实例，待压缩的文本文件字符不能少于参1000 个。数进2011.12.31完成任务的讲解、并

3、接受课程设计任务，选定课程设计的题目度2012.01.04了解任务的算法、并画出算法的程序流程图，对任务的关键技术进行验要证、并确定解决办法求2012.01.05-2012.01.06编制程序2012.01.09对程序进行调试，设计测试用例进行测试2012.01.10整理课程设计的过程、并进行总结，完善程序功能2012.01.11编写课程设计报告初稿2012.01.12完善课程设计报告、并准备答辨2012.01.13提交课程设计报告和程序，进行答辨参考1.严蔚敏吴伟民，数据结构，清华大学出版社，2007.3考资2.李春保，数据结构教程，清华大学出版社,2005.1料3.（美）Stephen P

4、rata, C Primer Plus 中文版（第五版）,人民邮电出版社，2005.2苴丿、它说1.本表应在母次头施前一周由负责教师填与一份，学院审批后交学院教务办备案，份由负责教师留用。2.若填写内容较多可另纸附后。3.题多名学生共用的，在设计明内容、参数、要求等万面应有所区别。系主任：雷亮指导教师：向毅/彭军/王双明/龙冯文/黄永文2011年12月26日摘要随着多媒体技术的迅猛发展，压缩技术也快速发展起来。Huffman高效率压缩编码, 其压缩程度很高，目前在很多领域已经开始广泛应用，具有良好的市场前景。这次课程 设计运用的huffmam高效率编码，对编码译码，对文件进行逐位读，写。实现压

5、缩文件, 再对文件进行解压。实现了对数据的压缩及解压，并且可以运用在软件上面。效果高效 很实用。关键字：软件高效模块目录摘要III目录IV1设计内容与要求11.1设计内容11.2设计要求12需求分析22.1系统实现的目标22.2系统实现方案23系统设计33.1总体功能的实现33.2总体流程图44系统实现54.1构造哈夫曼树 54.2哈夫曼编码65系统实现75.1主要代码实现75.2测试结果106总结13致谢14参考文献151设计内容与要求1.1设计内容通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文 字的二进制码形式的字符串。但在信息传递时，总希望总长度尽可能最短，即采

6、用最短 码。作为信息管理专业的学生，我们应该很好的掌握这门技术。在课堂上，我们能过学 到许多的理论知识，但我们很少有过自己动手实践的机会！课程设计就是为解决这个问 题提供了一个平台。1.2设计要求读入待压缩的文本文件；统计分析文本文件中各字符的出现频度，以频度作为构造 Huffman树的权值。根据各字符出现的不同频度构造Huffman树，然后规定每种字符的 Huffman编码。再次读入待压缩的文本文件，然后根据各字符的Huffman编码逐一替代, 将得到的编码流写入到新的文件中，并且计算压缩率。解码过程：先读入上一步骤得到 的新文件，将其看作比特流，根据Huffman树，对比特流逐位译码，将解

7、码结果又写入 一个新的文件中。2需求分析2.1系统实现的目标在当今信息爆炸时代，如何采用有效的数据压缩技术来节省数据文件的存储空间和 计算机网络的传送时间已越来越引起人们的重视。哈夫曼编码正是一种应用广泛且非常 有效的数据压缩技术。2.2系统实现方案哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼 编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支 表示“0”码，指向右子树的分支表示“ 1”码，取每条路径上的“0”或“1”的序列作 为和各个对应的字符的编码，这就是哈夫曼编码。3系统设计3.1总体功能的实现本程序设计包括两个模块:主程序模块和子程

8、序模块。在主页面可以清楚了解系统的功能实现，在控制台菜单页面，根据需要，可以根据 提示进行选择，选择后可以进行相应的操作。compress()和decompress()1通过菜单选 择，调用子函数，从而实现对功能的要求，如图3.1总体功能图。3.2总体流程图根据对huffman功能分析，设计得到该系统的总体功能图如图3.24系统实现4.1构造哈夫曼树创建哈夫曼树输出字符统计情况4.2哈夫曼编码图4.25系统实现5.1主要代码实现5.11主掉函数int in itial_files(char *source_file name,FILE *i np,char *obj_file name,FIL

9、E *outp);char *create_file name(char *source_file name,char* obj_file name);int compress(char *source_file name,char *obj_file name);long freque ncy_data(FILE *in,long fre);int search_set(ht np ht,i nt n ,i nt *s1, int *s2);int create_hftree(l ong w,i nt n,htnode ht);int en code_hftree(ht np htp,i n

10、t n, hufcode hc);un sig ned char chars_to_bits(c onst un sig ned char chars8);int write_compress_file(FILE *in,FILE *out,htnp ht,hufcode hc,char* source_filename,longsource_filesize);int decompress(char *source_file name,char *obj_file name);void get_mini_huffmantree(FILE* in,short mini_ht2);int wri

11、te_decompress_file(FILE *in,FILE* out,short mini_ht2,long bits_pos,long obj_filesize);int d_in itial_files(char *source_file name,FILE *i np,char *obj_file name,FILE *outp);5.12压缩文件时的代码int compress(char *source_file name,char *obj_file name)FILE *in, *out;char ch;int error_code,i,j;_7float compress_

12、rate;hufcode hc256;htnode ht256*2-1;long freque ncy256,source_filesize,obj_filesize=0;error_code=in itial_files(source_file name,&in,o bj_file name,&o ut);if(error_code!=0)puts(文件打开失败！请重新输入文件路径：);retur n error_code;source_filesize=freque ncy_data(i n, freque ncy);printf(” 文件大小 %ld 字节 n,source_filesi

13、ze);error_code=create_hftree(freque ncy,256,ht);if(error_code!=0)puts(建立哈夫曼树失败！);retur n error_code;error_code=e ncode_hftree(ht,256,hc);if(error_code!=0)puts(建立哈夫曼编码失败！);retur n error_code;for(i=0;i256;i+)obj_filesize+=freque ncyi*hci.le n;obj_filesize=obj_filesize%8=0?obj_filesize/8:obj_filesize/8

14、+1;for(i=0;i256-1;i+)obj_filesize+=2*sizeof(short);obj_filesize+=strle n( source_file name)+1; obj_filesize+=sizeof( Ion g);obj_filesize+=sizeof(unsigned int);compress_rate=(float)obj_filesize/source_filesize;printf(压缩文件大小:%ld 字节，压缩比例:%.2lf%n,obj_filesize,compress_rate*100); error_code=write_compres

15、s_file(i n,o ut,ht,hc,source_file name,source_filesize); if(error_code!=0)puts(写入文件失败！”)；retur n error_code;puts(压缩完成!);puts();puts(是否打印该文件中字符对应的huffman树及编码？ ”)；puts(Please in put Y OR N);doscan f(%s, &ch);switch(ch)case Y:puts(以下是哈夫曼树：”)；for(i=256;i0)prin tf(%-10d%-10d%-10d%-10d%-10dn ,i,h ti.w,hti

16、.p,hti,h ti.r);puts(以下是哈夫曼编码：”)；for(i=0;i256;i+)if(freque ncyi=O)i+;elseprin tf(%dt,freque ncyi);for(j=0;jhci.le n;j+)printf( %d,hci.codestrj);prin tf(n ”);break;case N:break;default :printf(指令错误！请重新输入指令：n”)；while(ch!=Y&ch!=N);fclose(i n);fclose(out);for(i=0;i256;i+)free(hci.codestr);return 0;5.13解压

17、文件时的代码int decompress(char *source_file name,char *obj_file name)interror_code;FILE*in, *out;shortmi ni_ht256*2-12;long obj_filesize;error_code=d_ in itial_files(source_file name,&in,o bj_file name ,&o ut); if(error_code!=0)puts(打开文件失败！请重新输入文件路径：);retur n error_code;fread(&o bj_filesize,sizeof( Ion g

18、),1,i n);printf(解压文件大小:%ld 字节 n,obj_filesize);get_mi ni_huffma ntree(i n,mi ni_ht);error_code=write_decompress_file(i n,out,mi ni_ht,ftell(i n),obj_filesize);if(error_code!=0)puts(”解压缩失败！”)；retur n error_code;puts(解压缩完成!);fclose(i n);fclose(out);return 0; 5.2测试结果进入主页面，如图5.1图5.1查看哈弗曼码，如图5.2育花 SS(1199

19、4914090 2012-1-13 0.50:12图5.3输入文件路劲及压缩效果显示，如图5.347x叮牛釆“訪啊.c 件:玉痢建文件夹Debug2.c,17732字节大小：13914字节压缩比例汐3.爛f建文件夹bug.z ip丈件中予简对应的huffnsn树及编码?Please input OR N1.0.菜单:-压缩-解压缩-退出-图5.46总结通过两周的课程设计使我对哈夫曼树以及哈夫曼编码有了更深的认识更加明白哈 夫曼编码译码在信息技术中的重要性和地位。许多的错误让我明白了一个道理-细心是 非常重要的。同时，对于编程者而言，思路清晰是相当重要的。在适当的时候和同学一 起交流探讨是一个十

20、分好的学习机会。这次课程设计不但让我学得了一些编程知识，还学会了系统的做一份课程设计报告, 学会了如何截图，学会了如何更好的画流程图，明白了做事情只有认真，才能真正做得 更好！通过这次课程设计，我看清楚了自己的编程功底和动手能力还不如人意，这主要是 平时实践太少的缘故。我想，在未来的暑假中，我会努力尝试编写一些程序。虽然我们 信息管理专业的学生，但现在编程的能力太差了，毕竟多精通一门技术总是好事。在这个程序中，还有许多地方值得完善。比如，读出文本只能是大写的文档，空格 和小写不能识别，更不用说是任意的ASQ码字符了。由于时间问题，暂时不能实现了。 我想在暑假里好好研究这个问题。致谢写出在本次课

21、程设计及论文完成过程中，为你提供帮助的人，并表达谢意签名日期 2012/1/12参考文献1严蔚敏 吴伟民，数据结构，清华大学出版社，2007.32 李春葆，数据结构教程，清华大学出版社，2005.13.（美）Stephen Prata, C Primer Plus中文版（第五版），人民邮电出版社，2005.2*i np,charhc,char*代码：#i nclude #i nclude #include #i nclude typedef struct nodelong w;short p,l,r;ht no de,*ht np;typedef struct huffma n_code _u

22、n sig ned char len;un sig ned char *codestr;hufcode;typedef char *huffma ncode;intin itial_files(char*source_file name,FILE*obj_filename,FILE *outp);char *create_file name(char *source_file name,char* obj_file name);int compress(char *source_file name,char *obj_file name);long freque ncy_data(FILE *

23、i n,long fre);int search_set(ht np ht,i nt n ,i nt *s1, int *s2);int create_hftree(l ong w,i nt n,htnode ht);int en code_hftree(ht np htp,i nt n ,hufcode hc);un sig ned char chars_to_bits(c onst un sig ned char chars8);int write_compress_file(FILE*in ,FILE*out,ht np ht,hufcodesource_file name,l ong

24、source_filesize);int decompress(char *source_file name,char *obj_file name);void get_mini_huffmantree(FILE* in,short mini_ht2);int write_decompress_file(FILE *in ,FILE* out,shortmin i_ht2,lo ngbits_pos,l ong obj_filesize);*source_file name,FILE* in p,charintdn itial_files(char*obj_file name,FILE *ou

25、tp);int main() int s;char file name10; system(color 3F); prin tf(*n);printf(*n);printf( *n);printf(1.2.*n);printf(0.菜单:压缩解压缩退出*n);printf(*n);*scan f(%d,&s); while(s!=0)getchar(); switch(s) case 1:puts(请输入待压缩文件路径：); gets(file name);compress(file name,NULL); break;case 2:puts(请输入待解压文件路径：); gets(file n

26、ame);decompress(file name,NULL);break;case 0:return 0; default :printf(指令错误！请重新输入指令：n);puts();printf(*n);printf(*n);printf(* 1*n);printf(* 2*n);printf(* 0*n);printf(*n);菜单:压缩解压缩退出sca nf(%d,&s);return 0;intin itial_files(char*source_file name,FILE*i np,char*obj_file name,FILE *outp) _if(fope n(source

27、_file name,rb)=NULL)return -1;if(obj_file name=NULL) _if(obj_file name=(char*)malloc(256*sizeof(char)=NULL)return -1;create_file name(source_file name,obj_file name); if(strcmp(source_file name,obj_file name)=O) 一 一return -1;printf(待压缩文件:%s,压缩文件:%sn,source_filename,obj_filename);if(*outp=fope n(obj_

28、file name,wb)=NULL) _return -1;if(*i np=fope n(source_file name,rb)=NULL)return -1;free(obj_file name);return 0;char *create_file name(char *source_file name,char* obj_file name) char *temp;if(temp=strrchr(source_file name,.)=NULL) _ strcpy(obj_file name,source_file name); strcat(obj_file name,.zip)

29、;elsestrncpy(obj_file name,source_file name,temp-source_file name); obj_file nametemp-source_file name=O;strcat(obj_file name,.zip); _retur n obj_file name; _int compress(char *source_file name,char *obj_file name) 一 一FILE *in ,*out;char ch;int error_code,i,j;float compress_rate;hufcode hc256;htnode

30、 ht256*2-1;long freque ncy256,source_filesize,obj_filesize=0;error_code=in itial_files(source_file name,&in,o bj_file name，&。ut); if(error_code!=0) _puts(文件打开失败！请重新输入文件路径：); retur n error_code; _source_filesize=freque ncy_data(i n, freque ncy);printf(文件大小 %ld 字节n,source_filesize);error_code=create_h

31、ftree(freque ncy,256,ht);if(error_code!=0)puts(建立哈夫曼树失败！);retur n error_code;error_code=e ncode_hftree(ht,256,hc);if(error_code!=0) _puts(建立哈夫曼编码失败！);retur n error_code; _for(i=0;i256;i+)obj_filesize+=freque ncyi*hci.le n; obj_filesize=obj_filesize%8=0?obj_filesize/8:obj_filesize/8+1; for(i=0;i256-1

32、;i+)obj_filesize+=2*sizeof(short);obj_filesize+=strle n( source_file name)+1; obj_filesize+=sizeof( Ion g);压缩比obj_filesize+=sizeof(unsigned int); compress_rate=(float)obj_filesize/source_filesize; printf(一 压缩M 件大-小:%ld 字节 ，例:%.2lf%n,obj_filesize,compress_rate*100);error_code=write_compress_file(i n,

33、 out,ht,hc,source_file name,source_file size);if(error_code!=0)puts(写入文件失败！);retur n error_code; _puts(压缩完成!);puts();puts(是否打印该文件中字符对应的 huffman树及编码？);puts( Please in put Y OR N);dosca nf(%s,&ch);switch(ch)case Y:puts(以下是哈夫曼树：); for(i=256;i0)prin tf(%-10d%-10d%-10d%-10d%-10dn,i,hti.w,hti.p,hti.l,hti

34、.r);puts(以下是哈夫曼编码：);for(i=0;i256;i+)if(freque ncyi=0)i+；elseprin tf(%dt,freque ncyi); for(j=0;jhci.le n;j+)printf( %d,hci.codestrj); prin tf(n); break;case N: break; default :n);prin tf(指令错误！请重新输入指令：while(ch!=Y&ch!=N);fclose(i n);fclose(out);for(i=0;i256;i+)free(hci.codestr);return 0;long freque ncy

35、_data(FILE *i n,long freque ncy) _inti,read_le n;un sig ned char buf256;long filesize;for(i=0;i256;i+)freque ncyi=0;fseek(i n,0L,SEEK_SET);read_le n=256;while(read_le n=256) _readen=fread(buf,1,256,i n); for(i=0;iread_le n;i+) _freque ncy*(buf+i)+;for(i=0,filesize=0;i256;i+)filesize+=freque ncyi;ret

36、urn filesize;int search_set(ht np ht,i nt n ,i nt *s1, int *s2) _int i,x;long mi nV alue = 1000000,min = 0;for(x=0;x n; x+)if(htx.p=-1) break;for(i=0;i n ;i+)if(hti.p=-1 & hti.w mi nV alue)mi nV alue = hti.w;min=i;*s1 = min;mi nV alue = 1000000,min = 0;for(i=0;i n ;i+)if(hti.p=-1 & hti.w mi nV alue

37、& i != *s1) mi nV alue = hti.w;min=i;*s2 = mi n;return 1;int create_hftree(l ong w,i nt n,htnode ht)int m,i,s1,s2;if (n 1)return -1;m=2* n-1;if (ht=NULL) return -1;for(i=0;i n ;i+)hti.w=wi;hti.p=hti.l=hti.r=-1;for(;im;i+)hti.w=hti.p=hti.l=hti.r=-1;for(i=n;im;i+)search_set(ht,i,&s1,&s2);hts1.p = hts2

38、.p = i;hti.l = s1;hti.r = s2;hti.w = hts1.w + hts2.w;return 0;int en code_hftree(ht np htp,i nt n ,hufcode hc) _int i,j,p,codele n;un sig ned char *code=(un sig ned char*)malloc( n*sizeof( un sig ned char);if (code=NULL) return -1;for(i=0;i n ;i+)for(p=i,codele n=0;p!=2* n-2;p=htpp.p,codele n+)codec

39、odele n=(htphtpp.p.l=p?0:1);charif(hci.codestr= (un sig ned*)malloc(codele n)*sizeof( un sig ned char)=NULL)return -1;hci.le n=codele n;for(j=0;jcodele n;j+) hci.codestrj=codecodele n-j-1;free(code);return 0;un sig ned char chars_to_bits(c onst un sig ned char chars8) 一一int i;un sig ned char bits=0;

40、bits|=chars0;for(i=1;i8;+i)bits=1;bits|=charsi;return bits;hc,char*charint write_compress_file(FILE*in ,FILE*out,ht npht,hufcodesource_file name,l ong source_filesize)un sig ned int i,read_co un ter,write_co un ter,zip_head=0xFFFFFFFF; un sig nedwrite_char_c oun ter,code_char_co un ter,copy_char_co

41、un ter,read_buf256,write_buf256,write_chars8,file name_size=strle n(source _file name);hufcode *cur_hufcode;fseek(i n,0L,SEEK_SET);fseek(out,0L,SEEK_SET);fwrite(&zip_head,sizeof( un sig ned in t),1,out);fwrite(&file name_size,sizeof( un sig ned char),1,out); fwrite(source_file name,sizeof(char),file

42、 name_size,out);fwrite(&source_filesize,sizeof(lo ng),1,out);for(i=256;i256*2-1;i+)fwrite(&(hti.l),sizeof(hti.l),1,out);fwrite(&(hti.r),sizeof(hti.r),1,out);write_cou nter=write_char_co un ter=O;read_co un ter=256;while(read_co un ter=256)read_c oun ter=fread(read_buf,1,256,i n);for(i=O;ile n) 一copy

43、_char_co un ter=(8-write_char_co un tercur_hufcode-le n-code_char_co un ter ?cur_hufcode-le n-code_char_co un ter8-write_char_co un ter);memcpy(write_chars+write_char_co un ter,cur_hufcode-codestr+code_char_co un ter,copy_char_co un ter);write_char_co un ter+=copy_char_c oun ter;code_char_co un ter+

44、=copy_char_co un ter; if(write_char_c oun ter=8) 一 一write_char_c oun ter=O;write_bufwrite_cou nte叶+=chars_to_bits(write_chars);if(write_c oun ter=256) _fwrite(write_buf,1,256,out); write_co un ter=O; _fwrite(write_buf,1,write_co un ter,out);if(write_char_c oun ter!=O) 一 一write_char_cou nter=chars_to_bits(write_chars); fwrite(&write_char_c oun ter,1,1,out);return O;void get_mi ni_huffma ntree(FILE* in ,short mi ni_ht2)int i;for(i=0;i=1)cur_pos=(read_bufread_co un ter&conv ert_bit)=0?mi ni_htcur_pos0:mi ni_htcur_pos1);if(cur_pos256)write_bufwrite_c oun ter=(u nsig ned