哈夫曼编码课程设计报告

1、数据结构课程设计报告基于哈夫曼树的文件压缩/解压程序 专业班级：信科2班 姓名：徐爱娟 谢静 2021-12_31 一 需求分析1.课题要求实现文件的压缩与解压并计算压缩率A软件名称：基于哈夫曼编码的文件压缩实用程序系统B软件组成： C制作平台及相关调试工具： Windows XP sp3 D运行环境：dos/ win2K/win2003/winxp/E性能特点：1. 软件由一个可执行文件组成为dos系统应用程序，体积小，高效快捷，适用范围广。2. 对单字节256叶子进行哈夫曼编码，压缩率良好3. 使用二级缓冲压缩/解压技术，速度比一般算法高4. 可压缩最大体积为4G的文件，到达Fat32文件

2、系统极限5. 文件索引体积比常规算法小50%二概要设计1. bool InitFromFile(string fileadd) 从文件中初始化哈夫曼树函数2. void HTCreat(HTNode ht,int n) 构造哈夫曼树函数3. void HCCreat(HTNode ht,HCode hcd,int n) 构造哈夫曼编码函数4. void ConvertFile(HCode hcd,string fileadd,string fileadd2) 压缩and写入文件函数5. void DecompressionFile(string fileadd2,string fileadd3

3、) 文件解压函数6. string Compression(string fileadd) 压缩函数7. string Decompression(string fileadd2) 解压函数Clock ( )三 详细设计1压缩算法局部A核心算法： Huffman编码是一种可变长编码方式，是由美国数学家David Huffman创立的，是二叉树的一种特殊转化形式。编码的原理是：将使用次数多的代码转换成长度较短的代码，而使用次数少的可以使用较长的编码，并且保持编码的唯一可解性。Huffman算法的最根本的原那么是：累计的(字符的统计数字*字符的编码长度)为最小，也就是权值(字符的统计数字*字符的编

4、码长度)的和最小。B哈夫曼树构造算法：Huffman树是二叉树的一种特殊转化形式。以下是构件Huffman树的例子：比方有以下数据， ABFACGCAHGBBAACECDFGFAAEABBB先进行统计A(8) B(6) C(4) D(1) E(2) F(3) G(3) H(1) 括号里面的是统计次数生成Huffman树：每次取最小的那两个节点(node)合并成一个节点(node)，并且将累计数值相加作为新的接点的累计数值，最顶层的是根节点(root) 注：列表中最小节点的是指包括合并了的节点在内的所有节点，已经合并的节点不在列表中运算的过程如下：1:D+H(2)2:DE+H(4)3:F+G(6

5、)4:C+DEH(8)5:B+FG(12)6:A+CDEH(16)7:ACDEH+BFG(28)那么转化为Huffman树就是Huffman树 层数 Root ACDEH BFG 1 CDEH A B FG 2 DEH C F G 3 DH E 4D H 5取左面是1 右面是0 那么有。注：层数就是位数或者说是代码长度，权值=代码长度*该字的统计次数。 代码 位数 权值A = 10 2 16B = 01 2 12C = 110 3 12D = 11111 5 5E = 1110 4 8F = 001 3 9G = 000 2 6H = 11110 5 5可以看出Huffman代码是唯一可解的(

6、uniquely decodable)，如果你读到110就一定是C ，不会有任何一个编码是以110开始的。如果不使用Huffman算法，而使用普通的编码，结果是什么呢？Huffman树 层数 Root ABCD EFGH 1 AB CD EF GH 2A B C D E F G H 3取左面是1 右面是0 那么有代码 位数 权值A = 111 3 24B = 110 3 18C = 101 3 12D = 100 3 3E = 011 3 6F = 010 3 9G = 001 3 9H = 000 3 3利用Huffman编码得到的权值累计是 73，如果利用普通定长编码的话，那么要用84字符

7、长度。从这个比拟，可以看出，Huffman是怎么进行压缩的。C哈夫曼编码结构及算法编码：将ABCDEFGH用Huffman树产生的编码对应着写到文件中，并且保存原始的Huffman树，主要是编码段的信息。一般要编码256个元素的话需要511个单位来储存Huffman树，每个Huffman树都必须有以下的结构：code,char,left,right,probability(出现次数)，通常情况是利用一个数组结构。因为在解码的时候只需要用到code，所以只需要记录每个元素的编码就可以了。解码：利用文件中保存的Huffman编码，一一对应，解读编码，把可变长编码转换为定长编码。2解压缩算法局部读出

8、结点数就能知道哈夫曼树存入局部的总长，方便读出树哈夫曼树子结点值和权值，就能由次些信息重新构造完整的哈夫曼树，和各结点的哈夫曼编码。解压时，读取一个字节8 bit用一个函数转换为8个字符用一个数组记录，其元素只是一个0或一个1，然后按哈夫曼树从顶向下查找，如果到达叶子结点，就读出该叶子结点的值，放入缓冲区中，如果不是，那么继续找，如此重复，直到缓冲区满了，就写入到解压文件中，再循环以上过程，直到处理完所有数据。和压缩时采用1M二级缓冲相同，如果的压缩时也采用此技术，也会有很大的速度优化，当然程序也变得更加复杂。四 用户使用说明1.运行huffman.exe程序，出现下面的界面2.选择相应的功能

9、，输入正确文件路径，对文件进行压缩、解压。五 设计心得体会通过这次课题实验的程序实践，我实在获益匪浅！数据结构是本学期开展的一门学科，学习好这门学科是非常重要的，在以后的程序设计方面这门学科能给我们很大的帮助。同时，学习这门学科也是艰辛的，因为它比拟难懂，这不仅需要我们要发挥我们的聪明才志，还需要我们在不断的实践中领悟。六 附录程序清单在此，给出的程序清单。#include<fstream>#include<iostream>#include<String>#include<cmath>using namespace std;struct HTN

10、ode char data; /节点数据 int weight; /权值 int parent; /父亲 int leftchild; /左孩子 int rightchild; /右孩子;typedef char* Code;HTNode *ht;Code *hcd;int maplist256; /建立字符与哈夫曼编码的映射int nodenum=0; /哈夫曼树结点数int rearnum=0; /哈夫曼编码尾补码int textlen=0; /需压缩的文件长度int codelen=0; /压缩后的文件的哈夫曼编码总长度int const bufferlen=1024; /设置读取缓冲区

11、长度int clean(); /清空节点及编码指针内容void dtobin(int num,int bin8); /十进制变换成二进制void HTCreate(HTNode ht,int n); /建立哈夫曼树void HCCreat(HTNode ht,Code hcd,int n); /提取哈夫曼编码void WriteFile(char *tmp); /写入文件unsigned char ConvertBinary(char *tmp);/变换二进制文件void ConvertFile(Code hcd,string fileadd,string fileadd2);/压缩并解压文件

12、bool InitFromFile(string fileadd);/初始化文件void DecompressionFile(string fileadd2,string fileadd3); /解压文件string Compression(string fileadd);/压缩文件string Decompression(string fileadd2); /解压文件子函数/十进制转二进制函数/int clean() delete ht;delete hcd;return 1;void dtobin(int num,int bin8) int i=0; for(i=0;i<8;i+)

13、bini=0; i=0; while(num>0) bin8-1-i=num%2; num=num/2; i+; /压缩和写入文件/void ConvertFile(Code hcd,string fileadd,string fileadd2) fstream infile(fileadd.c_str(),ios:in|ios:binary);fstream outfile(fileadd2.c_str(),ios:out|ios:binary);if(!infile) cout<<"open file fail!"<<endl;if(!ou

14、tfile) cout<<"creat file fail!"<<endl;/unsigned char ch; /写入哈夫曼树/ ch=nodenum; outfile.write(&ch,1); /写入结点数 ch=8; outfile.write(&ch,1); /写入补位数(预写入) codelen=0; outfile.write(char *)&codelen,4); /写入压缩后的文件的哈夫曼编码总长度(预写入) int h=0; for(h=0;h<nodenum;h+) outfile.write(ch

15、ar*)&hth.data,sizeof(char); outfile.write(char*)&hth.weight,sizeof(int); char tmp8; /设置缓冲区 char outbufferbufferlen; /设置写入缓冲区 char *tmpcd; int i=0,j,k,last=0; char inbufferbufferlen; int readlen=0; /infile.seekg(i,ios:beg);h=0; do infile.read(inbuffer,bufferlen); readlen=infile.gcount(); tmpc

16、d=hcdmaplist(unsigned char)inbufferi; for(i=0;i<readlen;) for(j=last;j<8 && *tmpcd!='0'j+) tmpj=*tmpcd; tmpcd+; if(j=8 && *tmpcd='0') last=0; i+; ch=ConvertBinary(tmp); /cout<<':'<<(unsigned int)ch<<' ' outbufferh=ch; h+; codele

17、n+; /压缩文件长度加一if(h=bufferlen) outfile.write(outbuffer,bufferlen); h=0; if(i<readlen) tmpcd=hcdmaplist(unsigned char)inbufferi; elsei=0;break; else if(j<8 && *tmpcd='0') last=j; i+; if(i<readlen) tmpcd=hcdmaplist(unsigned char)inbufferi; else i=0; break; /继续循换/ else if(j=8 &am

18、p;& *tmpcd!='0') last=0;/WriteFile(tmp); ch=ConvertBinary(tmp); outbufferh=ch; h+; codelen+; /压缩文件长度加一if(h=bufferlen) outfile.write(outbuffer,bufferlen); h=0; while(readlen=bufferlen);if(j=8 && readlen<bufferlen) outfile.write(outbuffer,h); else if(j<8 && readlen<

19、;bufferlen) for(k=j;k<8;k+) tmpk='0' ch=ConvertBinary(tmp); outbufferh=ch; h+; outfile.write(outbuffer,h); codelen+; /压缩文件长度加一 cout<<endl; ch=8-j; rearnum=8-j; outfile.seekp(1,ios:beg); outfile.write(&ch,1); /写入真正的补位数 outfile.seekp(2,ios:beg);outfile.write(char*)&codelen,4);

20、 /写入真正的压缩后的文件的哈夫曼编码总长度长度 outfile.close(); infile.close();/构造哈夫曼树/void HTCreate(HTNode ht,int n) int i,k,lnode,rnode; int min1,min2; for(i=0;i<2*n-1;i+) hti.parent=hti.rightchild=hti.leftchild=-1; for(i=n;i<2*n-1;i+) min1=min2=2147483647; lnode=rnode=-1; for(k=0;k<=i-1;k+) if(htk.parent=-1)

21、if(htk.weight<min1) min2=min1; min1=htk.weight; rnode=lnode; lnode=k; else if(htk.weight<min2) min2=htk.weight; rnode=k; htlnode.parent=i; htrnode.parent=i; hti.weight=htlnode.weight+htrnode.weight; hti.leftchild=lnode; hti.rightchild=rnode; /构造哈夫曼编码/void HCCreat(HTNode ht,Code hcd,int n) int

22、i,p,c; Code hc; hc=new charn; int start,tmplen; for(i=0;i<n;i+) tmplen=0; start=n-1; hcstart='0' c=i; p=hti.parent; while(p!=-1) if(htp.leftchild=c) /是左孩子结点 hc-start='0' tmplen+; else hc-start='1' tmplen+; c=p; p=htp.parent; hcdi=new charn-start; strcpy(hcdi,&hcstart);

23、 delete hc;void WriteFile(char *tmp) int i; for(i=0;i<8;i+) cout<<tmpi; cout<<' ' tmp=""unsigned char ConvertBinary(char *tmp) char ch=0; int i; for(i=0;i<8;i+) ch=(unsigned char)pow(2.0,8-i-1)*(tmpi-48)+ch; return ch;/翻开文件/bool InitFromFile(string fileadd) fstrea

24、m infile(fileadd.c_str(),ios:binary|ios:in); if(!infile)cout<<"error!"<<endl;return 0; int table256; int i,j; int len=0,num=0; unsigned char ch; for(i=0;i<256;i+) tablei=0;maplisti=-1; int readlen=0; char bufferbufferlen; /设置读取缓冲区,加快读取速度 do infile.read(buffer,bufferlen); i=0

25、; readlen=infile.gcount(); while(i<readlen) ch=(unsigned char)bufferi; tablech+; len+; i+; while(readlen=bufferlen);for(i=0;i<256;i+) if(tablei!=0) num+; ht=new HTNode2*num-1; hcd=new Codenum; for(i=0,j=0;i<256;i+) if(tablei!=0) htj.data=i; htj.weight=tablei; maplisti=j; /建立字符与哈夫曼编码的映射 j+;

26、nodenum=num; textlen=len; infile.clear();infile.close(); return 1;/从文件解压/void DecompressionFile(string fileadd2,string fileadd3) /cout<<".解压并输出新文件过程:"<<endl; fstream infile(fileadd2.c_str(),ios:in|ios:binary); fstream outfile(fileadd3.c_str(),ios:out|ios:binary); cout<<en

27、dl; /读出哈夫曼树的数据/ int h=0; char bufferbufferlen; /读入文件的缓冲区 char outbufferbufferlen; /写入文件的缓冲区 infile.read(buffer,1); nodenum=(unsigned char)*buffer;/哈夫曼树结点数 if(nodenum=0) nodenum=256; infile.read(buffer,1); rearnum=(unsigned char)*buffer; infile.read(char*)&codelen,4); /cout<<" 读出哈夫曼树数据

28、."<<endl; ht=new HTNode2*nodenum-1; hcd=new Codenodenum; /hcdlen=new intnodenum; for(h=0;h<nodenum;h+) infile.read(&hth.data,1); infile.read(char*)&hth.weight,4); /构走哈夫曼树/ HTCreate(ht,nodenum); /构造哈夫曼编码/ HCCreat(ht,hcd,nodenum); /解压并输出解压文件/ char *buffertmp=new char; int bin8,j=

29、0,i=0; int coderead=0; /记录以度的长度,用于判断何时到达文件最后一字节(用codelen比拟) int readlen=0; int child=0; int last=2*nodenum-2; /解压时记录上次指示器的位置 child=last; unsigned char outp; h=0; do infile.read(buffer,bufferlen); readlen=infile.gcount(); for(j=0;j<readlen;j+) coderead+; outp=bufferj; dtobin(outp,bin); if(coderead

30、=codelen) /到达文件尾 for(i=0;i<=8-rearnum;i+) if(htchild.leftchild=-1 && htchild.rightchild=-1) /cout<<htchild.data; outbufferh=htchild.data; h+;if(h=bufferlen) outfile.write(outbuffer,bufferlen);h=0; last=2*nodenum-2; if(i=8-rearnum)if(h!=0) outfile.write(outbuffer,h);child=last;break;

31、else i-; else if(i!=8) if(bini=0) last=htchild.leftchild; else if(bini=1) last=htchild.rightchild; child=last; else /没到达文件尾 for(i=0;i<=8;i+) if(htchild.leftchild=-1 && htchild.rightchild=-1) /cout<<htchild.data; outbufferh=htchild.data; h+;if(h=bufferlen) outfile.write(outbuffer,buf

32、ferlen); h=0; last=2*nodenum-2;if(i=8)child=last;break;else i-; else if(i!=8) if(bini=0) last=htchild.leftchild; else if(bini=1) last=htchild.rightchild; child=last; while(readlen=bufferlen); /cout<<j<<endl; infile.close(); outfile.close();string Compression(string fileadd)int i;for(i=0;

33、i<fileadd.length();i+)if(fileaddi='') fileaddi='/'string fileadd2;fileadd2=fileadd+".rax"InitFromFile(fileadd); /从文件中初始化哈夫曼树HTCreate(ht,nodenum); /构造哈夫曼树 HCCreat(ht,hcd,nodenum); /构造哈夫曼编码 ConvertFile(hcd,fileadd,fileadd2); /压缩并写入文件 clean();return fileadd2;string Decompre

34、ssion(string fileadd2) int i;for(i=0;i<fileadd2.length();i+)if(fileadd2i='') fileadd2i='/'string fileclass;string fileadd3;for(i=fileadd2.length()-5;fileadd2i!='.' && i>0;i-) fileclass.insert(0,fileadd2.substr(i,1);if(i!=0) fileadd3=fileadd2.substr(0,i)+"_&

35、quot;+'.'+fileclass;else fileadd3=fileadd2.substr(0,fileadd2.length()-4)+"_"DecompressionFile(fileadd2,fileadd3);clean();return fileadd3;int main()cout<<"缓冲区长度:"<<bufferlen<<"Bytes."<<endl<<endl;cout<<"t*n" cout<&

36、lt;"t* *n" cout<<"t* 数据结构课程设计 *n" cout<<"t* 基于哈夫曼的文件压缩解压程序 *n" cout<<"t* *n" cout<<"t*n" string fileadd;string fileadd2;char usage;docout<<""<<endl;cout<<"(1)压缩C"<<endl;cout<<&

37、quot;(2)解压D"<<endl;cout<<"(3)退出Q "<<endl;cout<<""<<endl;cout<<"*请输入选项:" cin>>usage;if(usage='C' | usage='c')cout<<"请输入压缩文件的路径:"cin>>fileadd;cout<<"压缩文件开始." fileadd2=Comp

38、ression(fileadd);cout<<"压缩文件完毕,压缩后文件的路径是:"<<fileadd2<<endl<<endl;else if(usage='D' | usage='d')cout<<"请输入解压文件的路径:"cin>>fileadd;cout<<"解压文件开始." fileadd2=Decompression(fileadd);cout<<"解压文件完毕,解压后文件的路径是:&q

39、uot;<<fileadd2<<endl<<endl;else if(usage='Q' | usage='q') return 0;while(1); return 0;#include<fstream>#include<iostream>#include<String>#include<cmath>using namespace std;struct HTNode char data; /节点数据 int weight; /权值 int parent; /父亲 int lef

40、tchild; /左孩子 int rightchild; /右孩子;typedef char* Code;HTNode *ht;Code *hcd;int maplist256; /建立字符与哈夫曼编码的映射int nodenum=0; /哈夫曼树结点数int rearnum=0; /哈夫曼编码尾补码int textlen=0; /需压缩的文件长度int codelen=0; /压缩后的文件的哈夫曼编码总长度int const bufferlen=1024; /设置读取缓冲区长度int clean(); /清空节点及编码指针内容void dtobin(int num,int bin8); /十

41、进制变换成二进制void HTCreate(HTNode ht,int n); /建立哈夫曼树void HCCreat(HTNode ht,Code hcd,int n); /提取哈夫曼编码void WriteFile(char *tmp); /写入文件unsigned char ConvertBinary(char *tmp);/变换二进制文件void ConvertFile(Code hcd,string fileadd,string fileadd2);/压缩并解压文件bool InitFromFile(string fileadd);/初始化文件void DecompressionFile(string fileadd2,string fileadd3); /解压文件string Compression(string fileadd);/压缩文件string Decompression(string fileadd2); /解压文件子函数/十进制转二进制函数/int clean() delete ht;delete hcd;return 1;void dtobin(int num,int bin8) int i=0; for(i=0;i<8;i+)