数据结构实验报告――实验五简单哈夫曼编/译码的设计与实现本实验的目的是通过对简单哈夫曼编/译码系统的设计与实现来熟练掌握树型结构在实际问题中的应用。
此实验可以作为综合实验，阶段性实验时可以选择其中的几个功能来设计和实现。
一、【问题描述】利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。
但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码，此实验即设计这样的一个简单编/码系统。
系统应该具有如下的几个功能：1、接收原始数据。
从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件nodedata.dat中。
2、编码。
利用已建好的哈夫曼树（如不在存，则从文件nodedata.dat中读入），对文件中的正文进行编码，然后将结果存入文件code.dat中。
3、译码。
利用已建好的哈夫曼树将文件code.dat中的代码进行译码，结果存入文件textfile.dat中。
4、打印编码规则。
即字符与编码的一一对应关系。
二、【数据结构设计】1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。
在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode的大小设置为2n-1，描述结点的数据类型为：typedef struct{int weight;//结点权值int parent;int lchild;int rchild;char inf;}HNodeType;2、求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。
求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，没回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码位所求编码的高位码，所以设计如下数据类型：#define MAXBIT 10typedef struct{int bit[MAXBIT]；int start；}HcodeType；3、文件nodedata.dat、code.dat和textfile.dat。
三、【功能（函数）设计】1、初始化功能模块。
此功能模块的功能为从键盘接收字符集大小n，以及n个字符和n个权值。
2、建立哈夫曼树的功能模块。
此模块功能为使用1中得到的数据按照教材中的构造哈夫曼树的算法构造哈夫曼树，即将HuffNode数组中的各个位置的各个域都添上相关的值，并将这个结构体数组存于文件hfmtree.dat中。
3、建立哈夫曼编码的功能模块。
此模块功能为从文件nodedata.dat中读入相关的字符信息进行哈夫曼编码，然后将结果存入code.dat中，同时将字符与0、1代码串的一一对应关系打印到屏幕上。
4、译码的功能模块。
此模块功能为接收需要译码的0、1代码串，按照3中建立的编码规则将其翻译成字符集中字符所组成的字符串形式，存入文件textfile.dat，同时将翻译的结果在屏幕上打印输出。
四、【编码实现】#include<iostream.h>#include<fstream.h>#include<string.h>#include<stdlib.h>#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 HcodeType{int bit[MaxBit];int start;};void Creat_Haffmantree(int &n){HNodeType *HaffNode=new HNodeType[2*n-1];int i,j;int m1,m2,x1,x2;for(i=0;i<2*n-1;i++){HaffNode[i].weight=0;HaffNode[i].parent=-1;HaffNode[i].lchild=-1;HaffNode[i].rchild=-1;HaffNode[i].inf='0';}for(i=0;i<n;i++){cout<<"请输入字符"<<endl;cin>>HaffNode[i].inf;cout<<"请输入该字符的权值"<<endl;cin>>HaffNode[i].weight;}for(i=0;i<n-1;i++)//构造哈夫曼树{m1=m2=Maxvalue;x1=x2=0;for(j=0;j<n+i;j++)//选取最小和次小{if(HaffNode[j].parent==-1&&HaffNode[j].weight<m1){m2=m1;x2=x1;m1=HaffNode[j].weight;x1=j;}else{if(HaffNode[j].parent==-1&&HaffNode[j].weight<m2){m2=HaffNode[j].weight;x2=j;}}}//将找出的最小和次小合并，创造其父母结点HaffNode[x1].parent=n+i;HaffNode[x2].parent=n+i;HaffNode[n+i].weight=HaffNode[x1].weight+HaffNode[x2].weight;HaffNode[n+i].lchild=x1;HaffNode[n+i].rchild=x2;HaffNode[n+i].inf=NULL;}cout<<"显示存储的哈弗曼树信息:"<<endl;cout<<"权值左孩子右孩子双亲"<<endl;for(i=0;i<2*n-1;i++){cout<<HaffNode[i].weight<<" ";cout<<HaffNode[i].lchild<<" ";cout<<HaffNode[i].rchild<<" ";cout<<HaffNode[i].parent<<" ";cout<<HaffNode[i].inf<<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++) //将存中从HaffNode[i]地址开始的sizeof(HaffNode[i])的容写入文件中outfile1.write((char*)&HaffNode[i],sizeof(HaffNode[i]));outfile1.close ();//关闭文件delete []HaffNode;}void HaffCode(int &n)//哈夫曼编码{HNodeType *HaffNode=new HNodeType[Maxnode];HcodeType *HaffCode=new HcodeType[Maxleaf];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=HaffNode[c].parent;while(p!=-1){if(HaffNode[p].lchild==c)cd.bit[cd.start]=0;elsecd.bit[cd.start]=1;cd.start--;c=p;p=HaffNode[c].parent;}for(j=cd.start+1;j<n;j++)HaffCode[i].bit[j]=cd.bit[j];HaffCode[i].start=cd.start;}for(i=0;i<n;i++){outfile<<HaffNode[i].inf;for(j=HaffCode[i].start+1;j<n;j++) outfile<<HaffCode[i].bit[j];}cout<<"字符信息--编码信息"<<endl; for(i=0;i<n;i++){cout<<HaffNode[i].inf<<"---";for(j=HaffCode[i].start+1;j<n;j++)cout<<HaffCode[i].bit[j];cout<<endl;}outfile.close ();cout<<"请输入要编码的字符串,基本元素为（";for(i=0;i<n;i++)cout<<HaffNode[i].inf<<",";cout<<")"<<endl;char inf[100];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<<"字符串编码后为:";for(int x=0;x<f;x++){for(i=0;i<n;i++){if(inf[x]==HaffNode[i].inf){for(j=HaffCode[i].start+1;j<n;j++){outfile1.write((char*)&HaffCode[i].bit[j],sizeof(HaffCode[i].bit[j]));cout<<HaffCode[i].bit[j];}}}}}cout<<endl;cout<<"编译后的代码串已经存入code.dat文件中!"<<endl;cout<<endl;outfile1.close();delete []HaffNode;delete []HaffCode;}void decode( int &n)//解码{int i;HNodeType *HaffNode=new HNodeType[2*n-1];fstream infile1;infile1.open("E:\\nodedata.dat",ios::in|ios::binary);//读出哈夫曼树if(!infile1){cout<<"nodedata.dat文件不能打开"<<endl;abort();}for(i=0;i<2*n-1;i++)infile1.read((char*)&HaffNode[i],sizeof(HNodeType));infile1.close();int tempcode[100];int num=0;for(i=0;i<100;i++)tempcode[i]=-1;HcodeType *Code=new HcodeType[n];fstream infile2;//读编码infile2.open("E:\\code.dat",ios::in|ios::binary);while(!infile2.eof()){infile2.read((char*)&tempcode[num],sizeof(tempcode[num]));num++;}infile2.close();num--;cout<<"从文件中读出的编码为"<<endl;for(i=0;i<num;i++)cout<<tempcode[i];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文件不能打开!"<<endl;abort();}while(i<num)// 小于字符串的长度{while(HaffNode[m].lchild!=-1&&HaffNode[m].rchild!=-1) {if(tempcode[i]==0){m=HaffNode[m].lchild;i++;}else if(tempcode[i]==1){m=HaffNode[m].rchild;i++;}}cout<<HaffNode[m].inf;outfile<<HaffNode[m].inf;m=2*n-2;}cout<<endl;outfile.close();cout<<"译码后的结果已经存入textfile.txt中!"<<endl;delete []HaffNode;}int main(){int n;cout<<"************* 欢迎进入编/译码系统！*********************"<<endl;int ch1;do{cout<<" 1.建树"<<endl;cout<<" 2:编码，并显示字符和对应的编码"<<endl;cout<<" 3:译码"<<endl;cout<<" 0:退出"<<endl;cout<<"********************************************************"<<endl;cout<<"请选择(0~3):";cin>>ch1;while(!(ch1<=3&&ch1>=0)) //输入不在0到4之间无效{cout<<"数据输入错误，请重新选择(0~4):";cin>>ch1;}switch(ch1){case 1:{cout<<"\t\t\t请输入编码个数"<<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，B，C，D}，并有如下对应关系，A――1、B――3，C――5，D――7，调用初始化功能模块可以正确接收这些数据。