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

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

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

3、.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;for(i=0;i<n-1;i+)arent=-1&&HaffNodej.weight<m1) m

4、2=m1;x2=x1;m1=HaffNodej.weight;x1=j;elseif(HaffNodej.parent=-1&&HaffNodej.weight<m2)m2=HaffNodej.weight;x2=j;arent=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<<" 显示存储的哈弗曼树

5、信息 :"<<endl;cout<<" 权值 左孩子 右孩子 双亲 "<<endl;for(i=0;i<2*n-1;i+)cout<<HaffNodei.weight<<" "cout<<HaffNodei.lchild<<" "cout<<HaffNodei.rchild<<" "cout<<HaffNodei.parent<<" "cout<

6、;<HaffNodei.inf<<endl;arent;while(p!=-1)if(HaffNodep.lchild=c)=0;else=1;c=p;p=HaffNodec.parent;for(j=+1;j<n;j+)HaffCodei.bitj=j;HaffCodei.start=;for(i=0;i<n;i+)outfile<<HaffNodei.inf;for(j=HaffCodei.start+1;j<n;j+) outfile<<HaffCodei.bitj;cout<<" 字符信息 - 编码信息

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

8、lt;<endl;char inf100;cin>>inf;int f=strlen(inf);fstream outfile1;("E:",ios:out|ios:binary);nf)for(j=HaffCodei.start+1;j<n;j+)(char*)&HaffCodei.bitj,sizeof(HaffCodei.bitj); cout<<HaffCodei.bitj;cout<<endl;cout<<" 编译后的代码串已经存入文件中 !"<<endl; cou

9、t<<endl;();delete HaffNode;delete HaffCode;void decode( int &n)child!=-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;();cout<<" 译码后的结果

10、已经存入中 !"<<endl;delete HaffNode;int main()int n;cout<<"*"<<endl;欢迎进入 编/译码系统！int ch1;docout<<" cout<<" cout<<" cout<<"1.2:3:0:建树 "<<endl;编码，并显示字符和对应的编码"<<endl;译码 "<<endl;退出 "<<endl;

11、cout<<"*”<<endl;cout<<" 请选择 (03):"cin>>ch1;while(!(ch1<=3&&ch1>=0) / 输入不在 0 到 4之间无效cout<<" 数据输入错误，请重新选择 (04):"cin>>ch1;switch(ch1)case 1:cout<<"ttt 请输入编码个数"<<endl;/ 叶子结点个数cin>>n; Creat_Haffmantree(n); break; case 2: HaffCode(n); break;case 3: decode(n); break;while(ch1!=0);return 0;五、 【运行与测试】1、令叶子结点个数n 为 4 ，权值集合为 1 ， 3 ， 5， 7 ，字符集合为 A ，