数据结构课程设计报告-哈夫曼树

/计算机科学学院数据结构课程设计题目：基于哈夫曼树的文件压缩/解压程序学生姓名：林华专业：计算机科学与技术班级：12级〔2班指导教师姓名及职称：陈明讲师起止时间：2014年3月——2014年4月1需求分析1.1课题背景及意义近年来,随着计算机技术的发展,多媒体计算机技术、计算机网络技术以及现代多媒体通信技术正在向着信息化、高速化、智能化迅速发展。各个领域的应用与发展,各个系统的数据量越来越大,给数据的存储、传输以及有效、快速获取信息带来了严重的障碍。数据压缩技术能够比较有效地解决这个问题。还有在最近几年中兴起的物联网和云计算都是对海量的数据进行处理和传输的,如果不对数据进行压缩,那么数据传输所需的带宽要求就很高,物理成本上也随之上升。所以说数据压缩在计算机通信中占有很重要的位置,且涉及领域多,应用广泛,与我们的生活息息相关。1.2课题要求1.2.1．实现一个基于哈夫曼树的文件压缩程序和文件解压程序。1.2.2.压缩程序能输入源文件进行压缩,输出压缩文件；1.2.3．解压程序读入压缩文件,根据相应的哈夫曼编码解压还原,得到对应的源文件。1.2.4．可选做：求出压缩率；打印哈夫曼树；对文件夹压缩；图形图形化窗口操作界面。1.3任务和要求1.3.1选择1时：输入一个待压缩的文本文件名称<可带路径>。

如:D:\1\XXX.txt

压缩文件名称=D:\1\XXX.zip1.3.2选择2时：输入一个待解压的压缩文件名称<可带路径>。

如:D:\1\YYY.txt解压文件名称=D:\1\YYY.zip2概要设计2.1问题解决的思路概述建立哈夫曼树建立哈夫曼树根据哈夫曼树解码对二进制文件进行解码根据哈夫曼树解码对二进制文件进行解码统计字符,得出统计出字符的权值n根据哈夫曼树编码统计字符,得出统计出字符的权值n根据哈夫曼树编码对编码进行压缩对编码进行压缩生成哈夫曼树生成哈夫曼树生成对应文件生成二进制文件生成对应文件生成二进制文件图1主程序流程图2.2算法思想：2.2.1输入要压缩的文件首先运行的时候,用户主界面上有菜单提示该如何使用软件,根据菜单提示选择所要执行的项,依次进行,因为各个环节之间有先后顺序。第一步为输入压缩软件的名称,由键盘输入文件路径和文件名称,读入字符数组中,打开该文件,按照提示进行压缩。若打不开,则继续输入。2.2.2读文件并计算字符频率文件将信息存放在字符数组中；计算每个字符出现的次数,申请一个结构体数组空间,用读取的字符减去字符结束符作为下标记录字符的频率。2.2.3根据字符的频率,利用Huffman编码思想创建Huffman树将所记录的字符的频率作为权值来创建Huffman树,依次选择权值最小的两个字符作为左右孩子,其和作为父结点的权值,依次进行下去,直到所有的字符结点都成为叶子结点。2.2.4由创建的Huffman树来决定字符对应的编码,进行文件的压缩根据创建的Huffman树来确定个字符的01编码,左孩子为0,右孩子为1。读取文件,依次将每个字符用他们的编码表示,即完成一次编码。2.2.5解码压缩即根据Huffman树进行译码读取编码文件,依据创建的Huffman树,定义一个指针指向根结点。从根结点开始,每读一个字符,指针变化一次〔当读取的字符是‘1’时,指针指向当前所指结点的右孩子,当读取的字符是‘0’时,指针指向当前所指结点的左孩子,直至该指针所指结点为叶子结点时结束〔即当结点的左右孩子均为空时。将当前叶子结点所代表的字符值输出到译码文件中,依次读取编码文件中的字符,按照上述方法依次进行下去直至文件2.3数据结构定义typedefstructnode//哈夫曼树结构体{longw;//权重shortp,l,r;//定义双亲,左孩子,右孩子}htnode,*htnp;typedefstructhuffman_code{unsignedcharlen;//记录该结点哈夫曼编码的长度unsignedchar*codestr;//记录该结点的哈夫曼编码}hufcode;2.5主程序的流程及模块间关系主函数实例化huffmanTree类,并实现菜单工具栏,通过用户的选择输入,用switch语句进行分支执行huffmanTree类中功能函数：1:压缩函数intcompress<char*source_file,char*obj_file>；2:解压函数intdecompress<char*source_file,char*obj_file>；并可在完成相应功能后安全退出,压缩或解压的文件在同文件夹下生成。3.详细设计核心算法huffman算法：3.1根据给定的n个权值｛w1,w2,……,wn｝构成n棵二叉树的集合F=｛T1,T2,……,Tn｝,其中每棵二叉树T1中只有一个带权的w1的根据点,其左右子树均空。3.2在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为其左右树上根结点的权值之和。3.3在F中删除这两棵树,同时将所得到的二叉树加入F中。3.4重复3.2,3.3,直到F中只含一棵树为止。这棵树便是Huffman树。Huffman树可用于构造代码总长度最短的编码方案。为了详细说明这个问题,特以下面例子来说明:图2问题详解编码完成之后,开始对源文件进行压缩。从源文件读一个字符,从叶子结点中找出和此字符相同的字符结点,将其编码写入一个临时字符组codes；当codes的长度大于等于8时,将其前8位转换成字符写入目标文件中；重复1和2此过程,直至读完源文件中的所有字符；若codes最后还有剩余的不足8位的01代码,则将其低位补0至8位,再写入目标文件。主程序模块:图3主程序模块调试分析报告由于压缩与解压过程中没有输入新生成文件的路径,因此解压后的文件会将原文件覆盖。如图：图4压缩前原文件图5压缩后生成文件图6解压后文件5.用户使用说明在运行程序之前,首先在D盘先建立一个待压缩的文件1.doc,运行程序如下图所示。图7版本测试结果图压缩：在命令行下输入1对文件进行压缩,根据提示输入刚刚建的文本文件〔1.doc,和要生成的压缩文件名称,按回车确认进行压缩。图8执行压缩操作图成功执行完毕后如下图所示。图9执行压缩操作图选择打印哈夫曼树及编码。图10执行打印操作图解压：在命令行下输入2对本程序压缩的文件进行恢复,根据提示输入待恢复的文件名称和恢复后的文件名称,按回车确定,成功执行后如下图所示。图11执行解压操作图6.测试结果详细测试结果请参见5使用功能。6.1测试报告原文件压缩后解压后1txt文件<14598b>8192b8192b2pdf文件<359398b>356352b359398b3jpg文件<31455b>28672b31455b4Mp3文件<72000b>69632b72000b参考文献[1]郑莉等编著《C++语言程序设计〔第三版》北京：清华大学出版社.[2]谭浩强.C++面向对象程序设计<第二版>[M].北京：中国铁道出版社,2009.[3]洪国胜等编著《C++Builder程序设计轻松上手》北京：清华大学出版社.[4]胡学钢等《数据结构算法设计指导》北京：清华大学出版社,1999年第1版.[5]王昆仑等编著《数据结构域算法〔高等学校计算机精品课程系列教材》中国铁道工业出版社.附录：源程序#include<stdio.h>#include<string.h>#include<stdlib.h>#include<windows.h>typedefstructnode//哈夫曼树结构体{longw;//权重shortp,l,r;//定义双亲,左孩子,右孩子}htnode,*htnp;typedefstructhuffman_code{unsignedcharlen;//记录该结点哈夫曼编码的长度unsignedchar*codestr;//记录该结点的哈夫曼编码}hufcode;typedefchar**huffmancode;intinitial_files<char*source_file,FILE**inp,char*obj_file,FILE**outp>;//文件初始信息char*create_file<char*source_file,char*obj_file>;//创建待压缩文件名intcompress<char*source_file,char*obj_file>;//压缩函数longfrequency_data<FILE*in,longfre[]>;//计算字符频率intsearch_set<htnpht,intn,int*s1,int*s2>;//查找文件intcreate_hftree<longw[],intn,htnodeht[]>;//创建哈夫曼树intencode_hftree<htnphtp,intn,hufcodehc[]>;//记录哈夫曼编码unsignedcharchars_to_bits<constunsignedcharchars[8]>;//计算文件大小intwrite_compress_file<FILE*in,FILE*out,htnpht,hufcodehc[],char*source_file,longsource_filesize>;//输入待压缩文件路径intdecompress<char*source_file,char*obj_file>;//解压函数voidget_mini_huffmantree<FILE*in,shortmini_ht[][2]>;//建立哈弗曼树中用于选择最小权值结点的函数intwrite_decompress_file<FILE*in,FILE*out,shortmini_ht[][2],longbits_pos,longobj_filesize>;//输入待解压文件路径intd_initial_files<char*source_file,FILE**inp,char*obj_file,FILE**outp>;main<>{ ints; charfile[10]; system<"color3F">; printf<"***************************************\n">; printf<"*菜单：*\n">; printf<"*1.压缩*\n">; printf<"*2.解压*\n">; printf<"*0.退出*\n">; printf<"***************************************\n">; scanf<"%d",&s>; while<s!=0> { getchar<>; switch<s> { case1: puts<"请输入待压缩文件路径：">; gets<file>; compress<file,NULL>; break; case2: puts<"请输入待解压文件路径：">; gets<file>; decompress<file,NULL>; break; default: printf<"指令错误！请重新输入指令：\n">; } puts<"">; printf<"***************************************\n">; printf<"*菜单：*\n">; printf<"*1.压缩*\n">; printf<"*2.解压*\n">; printf<"*0.退出*\n">; printf<"***************************************\n">; scanf<"%d",&s>; }}//文件初始信息intinitial_files<char*source_file,FILE**inp,char*obj_file,FILE**outp>{if<fopen<source_file,"rb">==NULL>{return-1;}if<obj_file==NULL>{if<<obj_file=<char*>malloc<256*sizeof<char>>>==NULL>{return-1;}create_file<source_file,obj_file>;}if<strcmp<source_file,obj_file>==0>{return-1;}printf<"待压缩文件:%s,压缩文件:%s\n",source_file,obj_file>;if<<*outp=fopen<obj_file,"wb">>==NULL>{return-1;}if<<*inp=fopen<source_file,"rb">>==NULL>{return-1;}free<obj_file>;return0;}//创建待压缩文件名char*create_file<char*source_file,char*obj_file>{char*temp;if<<temp=strrchr<source_file,'.'>>==NULL>{strcpy<obj_file,source_file>;strcat<obj_file,".zip">;}else{strncpy<obj_file,source_file,temp-source_file>;obj_file[temp-source_file]='\0';strcat<obj_file,".zip">;} returnobj_file;}//压缩函数intcompress<char*source_file,char*obj_file>{FILE*in,*out; charch;interror_code,i,j;floatcompress_rate;hufcodehc[256];//编码的位数最多为256位htnodeht[256*2-1];longfrequency[256],source_filesize,obj_filesize=0;error_code=initial_files<source_file,&in,obj_file,&out>;if<error_code!=0>{ puts<"文件打开失败！请重新输入文件路径：">;returnerror_code;}source_filesize=frequency_data<in,frequency>;printf<"文件大小%ld字节\n",source_filesize>;error_code=create_hftree<frequency,256,ht>;if<error_code!=0>{ puts<"建立哈夫曼树失败！">;returnerror_code;}error_code=encode_hftree<ht,256,hc>;if<error_code!=0>{ puts<"建立哈夫曼编码失败！">;returnerror_code;}for<i=0;i<256;i++>obj_filesize+=frequency[i]*hc[i].len;obj_filesize=obj_filesize%8==0?obj_filesize/8:obj_filesize/8+1;for<i=0;i<256-1;i++>obj_filesize+=2*sizeof<short>;obj_filesize+=strlen<source_file>+1;obj_filesize+=sizeof<long>;obj_filesize+=sizeof<unsignedint>;compress_rate=<float>obj_filesize/source_filesize;printf<"压缩文件大小:%ld字节,压缩比例:%.2lf%%\n",obj_filesize,compress_rate*100>;error_code=write_compress_file<in,out,ht,hc,source_file,source_filesize>; if<error_code!=0>{ puts<"写入文件失败！">;returnerror_code;}puts<"压缩完成!">; puts<"">; puts<"是否打印该文件中字符对应的huffman树及编码？">; puts<"PleaseinputYORN">; do{ scanf<"%s",&ch>; switch<ch> { case'Y': puts<"以下是哈夫曼树：">; for<i=256;i<256*2-2;i++> { if<ht[i].w>0> printf<"%-10d%-10d%-10d%-10d%-10d\n",i,ht[i].w,ht[i].p,ht[i].l,ht[i].r>; } puts<"以下是哈夫曼编码：">; for<i=0;i<256;i++> { if<frequency[i]==0> i++; else { printf<"%d\t",frequency[i]>; for<j=0;j<hc[i].len;j++> printf<"%d",hc[i].codestr[j]>; printf<"\n">; } } break; case'N': break; default: printf<"指令错误！请重新输入指令：\n">; } }while<ch!='Y'&&ch!='N'>;fclose<in>;fclose<out>;for<i=0;i<256;i++>{free<hc[i].codestr>;}return0;}//计算字符频率longfrequency_data<FILE*in,longfrequency[]>{inti,read_len;unsignedcharbuf[256];longfilesize;for<i=0;i<256;i++>//去掉权值为0的结点{frequency[i]=0;}fseek<in,0L,SEEK_SET>;read_len=256;while<read_len==256>{read_len=fread<buf,1,256,in>;for<i=0;i<read_len;i++>//初始化根结点{frequency[*<buf+i>]++;}}for<i=0,filesize=0;i<256;i++>{filesize+=frequency[i];}returnfilesize;}intsearch_set<htnpht,intn,int*s1,int*s2>{inti,x; longminValue=999999,min=0;for<x=0;x<n;x++>{if<ht[x].p==-1>break;}for<i=0;i<n;i++>{if<ht[i].p==-1&&ht[i].w<minValue>{ minValue=ht[i].w;min=i;}}*s1=min;minValue=999999,min=0;for<i=0;i<n;i++>{if<ht[i].p==-1&&ht[i].w<minValue&&i!=*s1>{ minValue=ht[i].w;min=i;}}*s2=min;return1;}//创建哈夫曼树intcreate_hftree<longw[],intn,htnodeht[]>{intm,i,s1,s2;if<n<1>return-1;m=2*n-1;if<ht==NULL>return-1;for<i=0;i<n;i++>{ht[i].w=w[i]; ht[i].p=ht[i].l=ht[i].r=-1;}for<;i<m;i++>{ht[i].w=ht[i].p=ht[i].l=ht[i].r=-1;}for<i=n;i<m;i++>{search_set<ht,i,&s1,&s2>;ht[s1].p=ht[s2].p=i;ht[i].l=s1; ht[i].r=s2;ht[i].w=ht[s1].w+ht[s2].w;}return0;}intencode_hftree<htnphtp,intn,hufcodehc[]>{inti,j,p,codelen;unsignedchar*code=<unsignedchar*>malloc<n*sizeof<unsignedchar>>;if<code==NULL>return-1;for<i=0;i<n;i++>{for<p=i,codelen=0;p!=2*n-2;p=htp[p].p,codelen++>{code[codelen]=<htp[htp[p].p].l==p?0:1>;}if<<hc[i].codestr=<unsignedchar*>malloc<<codelen>*sizeof<unsignedchar>>>==NULL>{return-1;}hc[i].len=codelen;for<j=0;j<codelen;j++>{hc[i].codestr[j]=code[codelen-j-1];}}free<code>;return0;}unsignedcharchars_to_bits<constunsignedcharchars[8]>{inti;unsignedcharbits=0;bits|=chars[0];for<i=1;i<8;++i>{bits<<=1;bits|=chars[i];}returnbits;}intwrite_compress_file<FILE*in,FILE*out,htnpht,hufcodehc[],char*source_file,longsource_filesize>{unsignedinti,read_counter,write_counter,zip_head=0xFFFFFFFF;unsignedcharwrite_char_counter,code_char_counter,copy_char_counter,read_buf[256],write_buf[256],write_chars[8],file_size=strlen<source_file>;hufcode*cur_hufcode;fseek<in,0L,SEEK_SET>;fseek<out,0L,SEEK_SET>;fwrite<&zip_head,sizeof<unsignedint>,1,out>;fwrite<&file_size,sizeof<unsignedchar>,1,out>;fwrite<source_file,sizeof<char>,file_size,out>;fwrite<&source_filesize,sizeof<long>,1,out>;for<i=256;i<256*2-1;i++>{fwrite<&<ht[i].l>,sizeof<ht[i].l>,1,out>;fwrite<&<ht[i].r>,sizeof<ht[i].r>,1,out>;}write_counter=write_char_counter=0;read_counter=256;while<read_counter==256>{read_counter=fread<read_buf,1,256,in>;for<i=0;i<read_counter;i++>{cur_hufcode=&hc[read_buf[i]];code_char_counter=0;while<code_char_counter!=cur_hufcode->len>{copy_char_counter=<8-write_char_counter>cur_hufcode->len-code_char_counter?cur_hufcode->len-code_char_counter:8-write_char_counter>;memcpy<write_chars+write_char_counter,cur_hufcode->codestr+code_char_counter,copy_char_counter>;write_char_counter+=copy_char_counter;code_char_counter+=copy_char_counter;if<write_char_counter==8>{write_char_counter=0;write_buf[write_counter++]=chars_to_bits<write_chars>;if<write_counter==256>{fwrite<write_buf,1,256,out>;write_counter=0;}}}}}fwrite<write_buf,1,write_counter,out>;if<write_char_counter!=0>{write_char_counter=chars_to_bits<write_chars>;fwrite<&write_char_counter,1,1,out>;}return0;}//建立哈弗曼树中用于选择最小权值结点的函数voidget_mini_huffmantree<FILE*in,shortmini_ht[][2]>{inti;for<i=0;i<256;i++>{mini_ht[i][0]=mini_ht[i][1]=-1;}fread<mini_ht[i],sizeof<short>,2*<256-1>,in>;}intwrite_decompress_file<FILE*in,FILE*out,shortmini_ht[][2],longbits_pos,longobj_filesize>{longcur_size;unsignedcharread_buf[256],write_buf[256],convert_bit;unsignedintread_counter,write_counter,cur_pos;fseek<in,bits_pos,SEEK_SET>;fseek<out,0L,SEEK_SET>;read_counter=256-1;cur_size=write_counter=0;cur_pos=256*2-2;while<cur_size!=obj_filesize>{if<++read_counter==256>{fread<read_buf,1,256,in>;read_counter=0;}for<convert_bit=128;convert_bit!=0;convert_bit>>=1>{cur_pos=<<read_buf[read_counter]&convert_bit>==0?mini_ht[cur_pos][0]:mini_ht[cur_pos][1]>;if<cur_pos<256>{write_buf[write_counter]=<unsignedchar>cur_pos;if<++write_counter==256>{fwrite<write_buf,1,256,out>;write_counter=0;}cur_pos=256*2-2;if<++cur_size==obj_filesize>{break;}}}}fwri