数据结构哈夫曼编码试验报告

1、数据结构实验报告 实验五 简单哈夫曼编 /译码的设计与实现本实验的目的是通过对简单哈夫曼编/译码系统的设计与实现来熟练掌握树型结构在实际问题中的应用。此实验可以作为综合实验，阶段性实验时可以选择其中的几 个功能来设计和实现。一、【问题描述】利用哈夫曼编码进行通信可以大大提高信道利用率， 缩短信息传输时间， 降低传输成本。 但是，这要求在发送端通过一个编码系统对待传数据预先编码， 在接收端将传来的数据进行 译码，此实验即设计这样的一个简单编/码系统。系统应该具有如下的几个功能：1、接收原始数据。从终端读入字符集大小n,以及n个字符和n个权值，建立哈夫曼树，并将它存于文件nodedata.dat

2、中。2、编码。利用已建好的哈夫曼树（如不在内存,则从文件 nodedata.dat 中读入）,对文件中的正 文进行编码,然后将结果存入文件 code.dat 中。3、 译码。利用已建好的哈夫曼树将文件code.dat 中的代码进行译码,结果存入文件 textfile.dat 中。4、打印编码规则。即字符与编码的一一对应关系。二、【数据结构设计】1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。 在构造哈夫曼树时,设计一个结构体数组 HuffNode 保存哈夫曼树中各结点的信息,根据二叉树的性质可知,具有 n 个叶子结点的哈夫曼树共有 2n-1 个结点,所以数组 HuffNode 的大小设置为

3、2n-1 ,描述结点的数据类型为： typedef structint weight;/ 结点权值int parent;int lchild;int rchild;char inf;HNodeType;2、 求哈夫曼编码时使用一维结构数组HuffCode 作为哈夫曼编码信息的存储。求哈夫曼编码, 实质上就是在已建立的哈夫曼树中, 从叶子结点开始, 沿结点的双亲链 域回退到根结点,没回退一步,就走过了哈夫曼树的一个分支,从而得到一位哈夫曼码值, 由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1 序列,因此先得到的分支代码为所求编码的低位码,后得到的分支代码位所求

4、编码的高位 码,所以设计如下数据类型：#define MAXBIT 10typedef structint bitMAXBIT ；int start ；HcodeType ； 3、文件 nodedata.dat、 code.dat 和 textfile.dat 。三、【功能(函数)设计】1、初始化功能模块。此功能模块的功能为从键盘接收字符集大小n,以及n个字符和n个权值。2、建立哈夫曼树的功能模块。此模块功能为使用 1 中得到的数据按照教材中的构造哈夫曼树的算法构造哈夫曼树,即将 HuffNode 数组中的各个位置的各个域都添上相关的值,并将这个结构体数组存于文件 hfmtree.dat 中。

5、3、建立哈夫曼编码的功能模块。此模块功能为从文件 nodedata.dat中读入相关的字符信息进行哈夫曼编码，然后将结果 存入code.dat中，同时将字符与 0、1代码串的对应关系打印到屏幕上。4、译码的功能模块。此模块功能为接收需要译码的 0、 1 代码串,按照 3中建立的编码规则将其翻译成字符 集中字符所组成的字符串形式, 存入文件 textfile.dat ,同时将翻译的结果在屏幕上打印输出。四、【编码实现】#include<iostream.h> #include<fstream.h> #include<string.h> #include<

6、stdlib.h> #define MaxBit 10 #define Maxvalue 100/应该大于权重之和 #define Maxleaf 100#define Maxnode Maxleaf*2-1typedef structint 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

7、 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=0;i<n;i+)coutvv"请输入字符"<<endl;cin>>HaffNodei.inf;cout«"请输入该字符的权值"<<endl;cin>>HaffNodei.we

8、ight; 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;else if(HaffNodej.parent=-1&&HaffNodej.weight<m2) m2=HaffNodej.weight; x2=j;/将找出的最小和次小合并，创造其父母结点 HaffNode

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

10、<<""cout<<HaffNodei.lchild<<""cout<<HaffNodei.rchild<<""cout<<HaffNodei.parent<<""cout<<HaffNodei.inf<<endl;/写入文件fstream outfile1;outfilel.ope n("E: no dedata.dat",ios:out|ios:tru nc|ios:bi nary);

11、/建立进行写入的 文件if(!outfile1) / 没有创建成功则显示相应信息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)/ 哈夫曼编码HNo

12、deType *HaffNode=new HNodeTypeMaxnode;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.ope n("E:codedata.dat",ios:out|ios:bi nary)

13、;/建立进行写入的文件 for(i=0;i<n;i+)cd.start=n-1;c=i;p=HaffNodec.parent;while(p!=-1) if(HaffNodep.lchild=c) cd.bitcd.start=0; else cd.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;

14、for(j=HaffCodei.start+1;j<n;j+) outfile<<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 ();coutvv"请输入要编码的字符串，基本

15、元素为("； for(i=0;i<n;i+)cout<<HaffNodei.inf<<","cout<<")"<<endl;char inf100;cin>>inf;int f=strlen(inf);fstream outfile1;outfilel.ope n("E:code.dat",ios:out|ios:b in ary);/ 建立进行写入的文件 if(!outfile1)cout<<"code.dat文件不能打开!"

16、<<endl;abort();else cout<<endl;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;coutvv"编译后的

17、代码串已经存入code.dat文件中!"<<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.da

18、t文件不能打开"<<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; fstream in file2; 读编码 infile2.open("E:code.dat",ios:in|ios:binary);while

19、(!infile2.eof() infile2.read(char*)&tempcodenum,sizeof(tempcodenum); num+;infile2.close();num-; coutvv"从文件中读出的编码为"<<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.o

20、pen("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<<Haf

21、fNodem.inf; outfile<<HaffNodem.inf; m=2*n-2; cout<<endl; outfile.close();cout«"译码后的结果已经存入textfile.txt中!"<<endl; delete HaffNode;int main()int n;统！cout<<"*欢 迎 进 入 编 / 译 码 系*、'<<endl;int ch1;docout«"1.建树"<<e ndl;cout<<"2:编码，并显示字符和对应的编码 &quo