数据结构实验报告
―― 实验五 简单哈夫曼编 / 译码的设计与实现
本实验的目的是通过对简单哈夫曼编 / 译码系统的设计与实现来熟练掌握树型结 构在实际问题中的应用。此实验可以作为综合实验，阶段性实验时可以选择其中的几 个功能来设计和实现。
一、【问题描述】
利用哈夫曼编码进行通信可以大大提高信道利用率， 缩短信息传输时间， 降低传输成本。
但是，这要求在发送端通过一个编码系统对待传数据预先编码， 在接收端将传来的数据进行 译码，此实验即设计这样的一个简单编 / 码系统。系统应该具有如下的几个功能：
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 、
序列， 因此先得到的分支代码为所求编码的低位码， 后得到的分支代码位所求编码的高位 码，所以设计如下数据类型：
#define MAXBIT 10
typedef struct
HaffNode[i].parent=-1;
HaffNode[i].parent=-1;
HaffNode[i].parent=-1;
HaffNode[i].parent=-1;
{
{
int bit[MAXBIT]；
int start； }HcodeType；
3 、文件 nodedata.dat 、code.dat 和 textfile.dat 。
三、【功能（函数）设计】
1、初始化功能模块。
此功能模块的功能为从键盘接收字符集大小 n ，以及 n 个字符和 n 个权值。
、建立哈夫曼树的功能模块。
此模块功能为使用 1 中得到的数据按照教材中的构造哈夫曼树的算法构造哈夫曼树， 即将 HuffNode 数组中的各个位置的各个域都添上相关的值，并将这个结构体数组存于文 件 hfmtree.dat 中。
、建立哈夫曼编码的功能模块。
此模块功能为从文件 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-1
typedef 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;
m1=HaffNode[j].weight;
m1=HaffNode[j].weight;
m1=HaffNode[j].weight;
m1=HaffNode[j].weight;
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;
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++)
{
TOC \o "1-5" \h \z 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)
if(HaffNode[p].lchild==c)
cout<<" 字符信息
cout<<" 字符信息 -- 编码信息 "<<endl;
{
if(HaffNode[p].lchild==c)
if(HaffNode[p].lchild==c)
cout<<" 字符信息
cout<<" 字符信息 -- 编码信息 "<<endl;
{
cd.bit[cd.start]=0;
else
cd.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];
}
for(i=0;i<n;i++)
cout<<HaffNode[i].inf<<"
cout<<HaffNode[i].inf<<"---";
cout<<"code.dat
cout<<"code.dat 文件不能打开 !"<<endl;
cout<<HaffNode[i].inf<<"
cout<<HaffNode[i].inf<<"---";
cout<<"code.dat
cout<<"code.dat 文件不能打开 !"<<endl;
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)
{
abort();
}
else
cout<<"
cout<<" 编译后的代码串已经存入 code.dat 文件中 !"<<endl;
cout<<"
cout<<" 编译后的代码串已经存入 code.dat 文件中 !"<<endl;
{ 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<<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<<"************* 欢 迎 进 入 编 / 译 码 系 cout<<" 请选择 (0~3):";
*********************、
*********************、'
<<endl;
int ch1;do{cout<<"
int ch1;
do{
cout<<"
1.建树"<<endl;
cout<<"
2: 编码，并显示字符和对应的编码 "<<endl;
cout<<"
3:译码 "<<endl;
cout<<"
0:退出"<<e ndl;
cout<<"********************************************************、
cout<<"
********************************************************、'
<<endl;
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,调用初始化功能模块可以正确
接收这些数据。
2 、调用建立哈夫曼树的功能模块,构造静态链表 HuffNode 的存储。
3、调用建立哈夫曼编码的功能模块,在屏幕上显示如下对应关系：
A——111、B ——110、C——10、D ——0
4 、调用译码的功能模块,输入代码串“ 111110100 ”后,屏幕上显示译码结果：
111110100 ―――― ABCD