哈夫曼编码译码的设计与实现

1、1软件学院课程设计报告设计名称： 数据结构课程设计 选题名称： 哈夫曼编码/译码的设计与实现 姓 名： 学 号： 专业班级： 移动 一 班 系 （院）： 软件学院 设计时间： 2014.6.12014.6.4 目 录一、需求分析-3 二、系统设计-33、 程序流程图-10四、实现代码-13五、总结-23六、参考书目-23数据结构课程设计报告 第 22 页 共 23 页1、 需求分析哈夫曼编码是一种应用广泛且非常有效的数据压缩技术，哈夫曼编码是一种编码方式，以哈夫曼树，带权路径长度最小的二叉树，经常应用于数据压缩。哈夫曼编码使用一张特殊的编码表将源字符进行编码。这张编码表的特殊在于，它是根据每一

2、个源字符出现的估算概率而建立起来的。哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码成为哈夫曼编码，树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是哈夫曼编码。哈夫曼译码输入字符串可以把它编译成二进制代码。输入二进制代码时可以编译成字符串。2、 系统设计构造哈夫曼树时，使用静态链表作为哈夫曼树的存储。在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点

3、，所以数组HuffNode的大小设置为2n-1，求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。求哈夫曼编码实际上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，每回退一步，就走过了哈夫曼的一个分支，从而得到一位哈夫曼编码值。由于一个字符的哈夫曼编码就是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码为所求的高位码1、初始化功能模块此功能模块的功能为从键盘接受字符集大小n，以及n个字符和n个权值。2、建立哈夫曼编码的功能模块此模块功能为使用1中得到的数据按照教材中的构造哈弗曼的

4、算法构造哈弗曼树，即将HuffNode数组中的各个位置的各个域都填上相关的值，并将这个结构体数组存于文件nodedata.dat中。函数原型为：void Creat_Haffmantree(int &n)HNodeType *HaffNode=new HNodeType2*n-1;int i,j;int m1,m2,x1,x2;for(i=0;i<2*n-1;i+)HaffNodei.weight=0;HaffNodei.parent=-1;HaffNodei.lchild=-1;HaffNodei.rchild=-1;HaffNodei.inf='0'for(i

5、=0;i<n;i+)cout<<"请输入字符"<<endl;cin>>HaffNodei.inf;cout<<"请输入该字符的权值"<<endl;cin>>HaffNodei.weight;for(i=0;i<n-1;i+)/构造哈夫曼树m1=m2=Maxvalue;x1=x2=0;for(j=0;j<n+i;j+)/选取最小和次小if(HaffNodej.parent=-1&&HaffNodej.weight<m1)m2=m1;x2=x1;m

6、1=HaffNodej.weight;x1=j;elseif(HaffNodej.parent=-1&&HaffNodej.weight<m2)m2=HaffNodej.weight;x2=j;/将找出的最小和次小合并，创造其父母结点HaffNodex1.parent=n+i;HaffNodex2.parent=n+i;HaffNoden+i.weight=HaffNodex1.weight+HaffNodex2.weight;HaffNoden+i.lchild=x2;HaffNoden+i.rchild=x1;HaffNoden+i.inf=NULL;cout<

7、<"显示存储的哈弗曼树信息:"<<endl; cout<<"权值左孩子右孩子双亲"<<endl; for(i=0;i<2*n-1;i+) cout<<HaffNodei.inf<<" " cout<<HaffNodei.weight<<" " cout<<HaffNodei.lchild<<" " cout<<HaffNodei.rchild<<&quo

8、t; " cout<<HaffNodei.parent<<endl; /写入文件fstream outfile1;outfile1.open("E:nodedata.dat",ios:out|ios:trunc|ios:binary);/建立进行写入的文件if(!outfile1) /没有创建成功则显示相应信息cout<<"nodedata.dat文件不能打开"<<endl;abort();for(i=0;i<2*n-1;i+) /将内存中从HaffNodei地址开始的sizeof(Haff

9、Nodei)的内容写入文件中outfile1.write(char*)&HaffNodei,sizeof(HaffNodei);outfile1.close ();/关闭文件delete HaffNode;3、建立哈弗曼编码功的功能模块此模块功能是从文件nodedata.dat中读入相关的字符信息进行哈弗曼编码，然后将结果存入code.dat中，同时将字符与0和1代码串的一一对应关系显示到屏幕上。函数原型为：void HaffCode(int &n)/哈夫曼编码HNodeType *HaffNode=new HNodeTypeMaxnode;HcodeType *HaffCod

10、e=new HcodeTypeMaxleaf;HcodeType cd;int i,j,c,p;fstream in("E:nodedata.dat",ios:in|ios:binary);in.read(char*)HaffNode,(2*n-1)*sizeof(HNodeType);in.close();fstream outfile;outfile.open("E:codedata.dat",ios:out|ios:binary);/建立进行写入的文件for(i=0;i<n;i+)cd.start=n-1;c=i;p=HaffNodec.pa

11、rent;while(p!=-1)if(HaffNodep.lchild=c)cd.bitcd.start=0;elsecd.bitcd.start=1;cd.start-;c=p;p=HaffNodec.parent;for(j=cd.start+1;j<n;j+)HaffCodei.bitj=cd.bitj;HaffCodei.start=cd.start;for(i=0;i<n;i+) outfile<<HaffNodei.inf;for(j=HaffCodei.start+1;j<n;j+)outfile<<HaffCodei.bitj; co

12、ut<<"字符信息-编码信息"<<endl; for(i=0;i<n;i+) cout<<HaffNodei.inf<<"-" for(j=HaffCodei.start+1;j<n;j+) cout<<HaffCodei.bitj; cout<<endl; outfile.close ();cout<<"请输入要编码的字符串,基本元素为（"for(i=0;i<n;i+)cout<<HaffNodei.inf<<

13、;","cout<<")"<<endl;char inf100;cin>>inf;int f=strlen(inf);fstream outfile1;outfile1.open("E:code.dat",ios:out|ios:binary);/建立进行写入的文件if(!outfile1) cout<<"code.dat文件不能打开!"<<endl; abort(); else cout<<endl; cout<<"字符

14、串编码后为:" for(int x=0;x<f;x+) for(i=0;i<n;i+) if(infx=HaffNodei.inf) for(j=HaffCodei.start+1;j<n;j+) outfile1.write(char*)&HaffCodei.bitj,sizeof(HaffCodei.bitj); cout<<HaffCodei.bitj; cout<<endl; cout<<"编译后的代码串已经存入code.dat文件中!"<<endl; cout<<end

15、l; outfile1.close(); delete HaffNode;delete HaffCode;4. 此模块功能为接收需要译码的0、1代码串，按照3中建立的编码规则将其翻译成字符集中字符所组成的字符串形式，存入文件textfile.dat，同时将翻译的结果在屏幕上打印输出。接受0、1代码串有两种形式，一种是直接输入，一种是从文件中读取。函数原型为：void decode( int &n)/解码int i;HNodeType *HaffNode=new HNodeType2*n-1;fstream infile1;infile1.open("E:nodedata.da

16、t",ios:in|ios:binary);/读出哈夫曼树if(!infile1)cout<<"nodedata.dat文件不能打开"<<endl;abort();for(i=0;i<2*n-1;i+)infile1.read(char*)&HaffNodei,sizeof(HNodeType);infile1.close(); int tempcode100;int num=0;for(i=0;i<100;i+)tempcodei=-1;HcodeType *Code=new HcodeTypen;cout<&l

17、t;"请选择要做的操作："<<endl;cout<<"输入串解码，请按4"<<endl;cout<<"从文件中解码，请按5"<<endl;int q;cin>>q;while(q>5|q<4)cout<<"输入错误请重新输入"cin>>q;switch(q)case 4:cout<<"请输入要解码的0,1串(按其他键结束输入）："<<endl;i=0;cin>

18、>tempcodei;while(tempcodei=0|tempcodei=1)i+;num=i;cin>>tempcodei;cout<<"输入的编码为："for(i=0;i<num;i+)cout<<tempcodei;cout<<endl;int m=2*n-2;i=0;cout<<"译码后为："<<endl; fstream outfile; outfile.open("E:textfile.txt",ios:out); if(!outfil

19、e) cout<<"textfile.txt文件不能打开!"<<endl; abort(); while(i<num)/ 小于字符串的长度 while(HaffNodem.lchild!=-1&&HaffNodem.rchild!=-1) if(tempcodei=0)m=HaffNodem.lchild;i+;else if(tempcodei=1)m=HaffNodem.rchild;i+; cout<<HaffNodem.inf;outfile<<HaffNodem.inf;m=2*n-2; cou

20、t<<endl; outfile.close(); cout<<"译码后的结果已经存入textfile.txt中!"<<endl; delete HaffNode; break;case 5:fstream infile2;/读编码infile2.open("E:code.dat",ios:in|ios:binary);while(!infile2.eof()infile2.read(char*)&tempcodenum,sizeof(tempcodenum);num+;infile2.close();num-

21、;cout<<"从文件中读出的编码为"<<endl;for(i=0;i<num;i+)cout<<tempcodei; cout<<endl; int m=2*n-2; i=0; cout<<endl; cout<<"译码后为:"<<endl; fstream outfile; outfile.open("E:textfile.txt",ios:out); if(!outfile) cout<<"textfile.txt文件

22、不能打开!"<<endl; abort(); while(i<num)/ 小于字符串的长度 while(HaffNodem.lchild!=-1&&HaffNodem.rchild!=-1) if(tempcodei=0)m=HaffNodem.lchild;i+;else if(tempcodei=1)m=HaffNodem.rchild;i+; cout<<HaffNodem.inf;outfile<<HaffNodem.inf;m=2*n-2; cout<<endl; outfile.close(); cou

23、t<<"译码后的结果已经存入textfile.txt中!"<<endl; delete HaffNode; break; 3、 程序流程图1. 系统结构图 哈夫曼编码译码器 退出 译码 编码 建树2. 各部分功能图建树： 开始 初始化哈夫曼链表且有2n-1个节点 i=1i<n<<p->weight=countip=p->next for(i=n;i<2*n-1;i+) 结束编码：开始 将字符存入哈夫曼编码结构体数组的字符单元中if(q=q->Parent->LChild)HCi.code-HCi.sta

24、rt=1HCi.code-HCi.start=0 p=p->nexti=n时 结束译码： 开始Root指向根节点 P!=rootp=p->RChildcodei=0 p=p->LChildp->LChild=NULL&&p->RChild=NULLsk+=strj p=root 结束4、 实现代码/#include "stdafx.h"#include<iostream>#include<fstream>#include<string.h>#include<stdlib.h>usi

25、ng namespace std;#define MaxBit 10#define Maxvalue 100#define Maxleaf 100#define Maxnode Maxleaf*2-1typedef struct int weight;int parent;int lchild;int rchild;char inf;HNodeType;struct HcodeTypeint bitMaxBit;int start;void Creat_Haffmantree(int &n)HNodeType *HaffNode=new HNodeType2*n-1;int i,j;i

26、nt m1,m2,x1,x2;for(i=0;i<2*n-1;i+)HaffNodei.weight=0;HaffNodei.parent=-1;HaffNodei.lchild=-1;HaffNodei.rchild=-1;HaffNodei.inf='0'for(i=0;i<n;i+)cout<<"请输入字符"<<endl;cin>>HaffNodei.inf;cout<<"请输入该字符的权值"<<endl;cin>>HaffNodei.weight;

27、for(i=0;i<n-1;i+)/构造哈夫曼树m1=m2=Maxvalue;x1=x2=0;for(j=0;j<n+i;j+)if(HaffNodej.parent=-1&&HaffNodej.weight<m1)m2=m1;x2=x1;m1=HaffNodej.weight;x1=j;elseif(HaffNodej.parent=-1&&HaffNodej.weight<m2)m2=HaffNodej.weight;x2=j;/创造其父母结点HaffNodex1.parent=n+i;HaffNodex2.parent=n+i;Ha

28、ffNoden+i.weight=HaffNodex1.weight+HaffNodex2.weight;HaffNoden+i.lchild=x2;HaffNoden+i.rchild=x1;HaffNoden+i.inf=NULL;cout<<"显示存储的哈弗曼树信息:"<<endl; cout<<"权值左孩子右孩子双亲"<<endl; for(i=0;i<2*n-1;i+) cout<<HaffNodei.inf<<" " cout<<Ha

29、ffNodei.weight<<" " cout<<HaffNodei.lchild<<" " cout<<HaffNodei.rchild<<" " cout<<HaffNodei.parent<<endl; /写入文件fstream outfile1;outfile1.open("E:nodedata.dat",ios:out|ios:trunc|ios:binary);/建立进行写入的文件if(!outfile1) /没有创建

30、成功则显示相应信息cout<<"nodedata.dat文件不能打开"<<endl;abort();for(i=0;i<2*n-1;i+) /将内存中从HaffNodei地址开始的sizeof(HaffNodei)的内容写入文件中outfile1.write(char*)&HaffNodei,sizeof(HaffNodei);outfile1.close ();/关闭文件delete HaffNode;void HaffCode(int &n)/哈夫曼编码HNodeType *HaffNode=new HNodeTypeMax

31、node;HcodeType *HaffCode=new HcodeTypeMaxleaf;HcodeType cd;int i,j,c,p;fstream in("E:nodedata.dat",ios:in|ios:binary);in.read(char*)HaffNode,(2*n-1)*sizeof(HNodeType);in.close();fstream outfile;outfile.open("E:codedata.dat",ios:out|ios:binary);/建立进行写入的文件for(i=0;i<n;i+)cd.start

32、=n-1;c=i;p=HaffNodec.parent;while(p!=-1)if(HaffNodep.lchild=c)cd.bitcd.start=0;elsecd.bitcd.start=1;cd.start-;c=p;p=HaffNodec.parent;for(j=cd.start+1;j<n;j+)HaffCodei.bitj=cd.bitj;HaffCodei.start=cd.start;for(i=0;i<n;i+) outfile<<HaffNodei.inf;for(j=HaffCodei.start+1;j<n;j+)outfile<

33、;<HaffCodei.bitj; cout<<"字符信息-编码信息"<<endl; for(i=0;i<n;i+) cout<<HaffNodei.inf<<"-" for(j=HaffCodei.start+1;j<n;j+) cout<<HaffCodei.bitj; cout<<endl; outfile.close ();cout<<"请输入要编码的字符串,基本元素为（"for(i=0;i<n;i+)cout<&

34、lt;HaffNodei.inf<<","cout<<")"<<endl;char inf100;cin>>inf;int f=strlen(inf);fstream outfile1;outfile1.open("E:code.dat",ios:out|ios:binary);/建立进行写入的文件if(!outfile1) cout<<"code.dat文件不能打开!"<<endl; abort(); else cout<<end

35、l; cout<<"字符串编码后为:" for(int x=0;x<f;x+) for(i=0;i<n;i+) if(infx=HaffNodei.inf) for(j=HaffCodei.start+1;j<n;j+) outfile1.write(char*)&HaffCodei.bitj,sizeof(HaffCodei.bitj); cout<<HaffCodei.bitj; cout<<endl; cout<<"编译后的代码串已经存入code.dat文件中!"<&l

36、t;endl; cout<<endl; outfile1.close(); delete HaffNode;delete HaffCode;void decode( int &n)/解码int i;HNodeType *HaffNode=new HNodeType2*n-1;fstream infile1;infile1.open("E:nodedata.dat",ios:in|ios:binary);/读出哈夫曼树if(!infile1)cout<<"nodedata.dat文件不能打开"<<endl;abo

37、rt();for(i=0;i<2*n-1;i+)infile1.read(char*)&HaffNodei,sizeof(HNodeType);infile1.close(); int tempcode100;int num=0;for(i=0;i<100;i+)tempcodei=-1;HcodeType *Code=new HcodeTypen;cout<<"请选择要做的操作："<<endl;cout<<"输入串解码，请按4"<<endl;cout<<"从文件中

38、解码，请按5"<<endl;int q;cin>>q;while(q>5|q<4)cout<<"输入错误请重新输入"cin>>q;switch(q)case 4:cout<<"请输入要解码的0,1串(按其他键结束输入）："<<endl;i=0;cin>>tempcodei;while(tempcodei=0|tempcodei=1)i+;num=i;cin>>tempcodei;cout<<"输入的编码为："

39、;for(i=0;i<num;i+)cout<<tempcodei;cout<<endl;int m=2*n-2;i=0;cout<<"译码后为："<<endl; fstream outfile; outfile.open("E:textfile.txt",ios:out); if(!outfile) cout<<"textfile.txt文件不能打开!"<<endl; abort(); while(i<num)/ 小于字符串的长度 while(Haf

40、fNodem.lchild!=-1&&HaffNodem.rchild!=-1) if(tempcodei=0)m=HaffNodem.lchild;i+;else if(tempcodei=1)m=HaffNodem.rchild;i+; cout<<HaffNodem.inf;outfile<<HaffNodem.inf;m=2*n-2; cout<<endl; outfile.close(); cout<<"译码后的结果已经存入textfile.txt中!"<<endl; delete Haf

41、fNode; break;case 5:fstream infile2;/读编码infile2.open("E:code.dat",ios:in|ios:binary);while(!infile2.eof()infile2.read(char*)&tempcodenum,sizeof(tempcodenum);num+;infile2.close();num-;cout<<"从文件中读出的编码为"<<endl;for(i=0;i<num;i+)cout<<tempcodei; cout<<e

42、ndl; int m=2*n-2; i=0; cout<<endl; cout<<"译码后为:"<<endl; fstream outfile; outfile.open("E:textfile.txt",ios:out); if(!outfile) cout<<"textfile.txt文件不能打开!"<<endl; abort(); while(i<num)/ 小于字符串的长度 while(HaffNodem.lchild!=-1&&HaffNodem.rchild!=-1) if(tempcodei=0)m=HaffNodem.lchild;i+;else if(tempcodei=1)m=HaffNodem.rchild;i+; cout<<HaffNodem.inf;outfile<<HaffNodem.inf;m=2*n-2; cout<<endl; outfile.close(); cout<<"译码后的结果已经存入t