数学与计算机学院 数据结构 实验报告
年级 09数计
学号 ***
姓名 **
专业 数电
实验地点 主楼401
指导教师 **
实验项目 哈夫曼树解决编码解码
实验日期 XX年12月24日
一、实验目的
本实验的目的是通过对简单的哈夫曼编/译码系统的设计与实现来熟练掌握树形结构在实际问题中的应用。
二、实验问题描述
利用哈夫曼编码进行通信可以大大提高通信利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码，此试验即设计这样的一个简单的编/译码系统。系统应该具备如下的几个功能。
1、求出各个叶子节点的权重值
输入一个字符串，统计其中各个字母的个数和总的字母个数。
2、构造哈夫曼树
统计出的字母种类为叶子结点个数，每个字母个数为相应的权值，建立哈
夫曼树。
3、打印哈弗曼树的功能模块
按照一定形式打印出哈夫曼树。
4、编码
利用已经建立好的哈夫曼树进行编码。
5、译码
根据编码规则对输入的代码进行翻译并将译码。
三、实验步骤
1、实验问题分析
（1）设计一个结构体数组保存字母的类型和个数。
typedef struct{
char ch; //字母的种类
int num; //字母的个数
}inf;
（2）在构造哈夫曼树时，设计一个结构体数组Hufftree保存哈夫曼树中各结 点的信息，根据二叉树的性质可知，具有n个结点的哈夫曼树共有2n-1个结 点，所以数组大小设置为2n-1,描述结点的数据类型为：
typedef struct{
int weight; //权值
int parent; //双亲
int lchild; //左孩子
int rchild; //右孩子
}Hnodetype;
typedef Hnodetype Hufftree[maxnode]; //定义此类型的数组
（3）求哈夫曼编码，实质上是在已经建立的哈夫曼树中，从叶子结点开始， 沿着结点的双亲链表域退回到根节点，每退回一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼值，由于一个字符的哈夫曼编码是从根结点所经过的路径上各分支所组成的0、1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码为所求编码的高位码，所以设计如下的数据类型：
const int maxbit=10;
typedef struct{
int bit[maxbit]; //每个结点的哈夫曼编码
int start; //开始位置
}Hcodetype;
（4）设置全局变量。
string s; //s为输入的字符串
int n=0; //记录输入的字符串中字母的种类，即叶子结点个数
int v=0; //记录字符串中字母的总个数
inf info[maxleaf];//叶子结点类型
2、功能（函数）设计
（1）统计字母种类和个数模块
此模块的功能为从键盘接受一个字符串，统计字符串中字母种类即结点个数，每种字母出现次数即各叶子结点的权值。全局变量s保存输入的字符串，将种类和个数保存到info[maxleaf]中。
函数原型：void fundchar（）
如输入的字符串是“sddfffgggg”则显示如下。
（2）哈夫曼树的建立模块
此模块的功能为从（1）中计算出的结点个数和各个叶子结点的权值构造一棵哈弗曼树。
函数原型：Hnodetype* huffmantree()//函数返回结点类型的数组
（3）打印哈弗曼树的功能模块
此模块的功能是将由(2)建立的哈弗曼树按照一定规则＜weight,lchild,rchild,parent＞打印在屏幕上。
函数原型：void print(Hnodetype *hufftree)
如输入的字符串是”sddfffgggg”，则构造的哈夫曼树为
（4）建立哈夫曼编码的功能模块
此模块功能为将（2）中建立的哈夫曼树进行哈弗曼编码，然后将字符与对应的0、1代码串打印到屏幕上。
函数原型：void huffmancode(Hnodetype *hufftree)
如输入的字符串是“sddfffgggg”，则每个字母的代码和输入的字符串的哈夫曼编码是
（5）译码的功能模块
此模块的功能为接收需要译码的0和1代码串，按照（4）中建立的编码规则将其翻译成字符集中字符所组成的字符串形式，并将翻译的结果在屏幕上打印出来。
函数原型：void translation(Hnodetype *hufftree)
如输入的代码串是“110111100”，则对应的字符串是“sdfg”
四、实验结果（程序）及分析
1、实验主要模块代码
(一)函数功能：统计字母种类和个数模块
void fundchar()
{
int k,m;
cout＜＜"请输入字符串"＜＜endl;
cin＞＞s; //s为输入的字符串
while(s[v]){v++;}
cout＜＜"共有字符"＜＜v＜＜"个"＜＜endl; // v是全局变量
info[0].ch=s[0];info[0].num=1;
for(k=1;k＜=v;k++) //统计s中字母种类和个数
{
for(m=0;m＜=n;m++)
{if(info[m].ch==s[k]){++info[m].num;break;}}
if(m＞n){info[++n].ch=s[k];info[n].num=1;}
}
for(m=0;m＜n;m++) //输出种类和个数
cout＜＜"字符"＜＜info[m].ch＜＜"有"＜＜info[m].num＜＜"个"＜＜endl;
}
(二)函数功能:哈弗曼树的建立模块
Hnodetype* huffmantree(){
Hnodetype *hufftree=new Hufftree;
int i,j,m1,m2,x1,x2; //m1记录最小的重权值，m2为次小
for(i=0;i＜2*n-1;i++){ //结点初始化
hufftree[i].parent=-1;
hufftree[i].weight=0;
hufftree[i].lchild=-1;
hufftree[i].rchild=-1;
}
for(i=0;i＜n;i++) //将每个字母的个数当做叶子结点的权值
hufftree[i].weight=info[i].num;
for(i=0;i＜n-1;i++){
m1=m2=maxvalue;
x1=x2=0;
for(j=0;j＜n+i;j++){
if(hufftree[j].parent==-1 && hufftree[j].weight＜m1){
m2=m1;
x2=x1;
m1=hufftree[j].weight;
x1=j; //x1记录最小重权值在数组中的下标
}
else
if(hufftree[j].parent==-1 && hufftree[j].weight＜m2){
m2=hufftree[j].weight;
x2=j; //x2记录次小重权值在数组中的下标
}
}
hufftree[x1].parent=n+i;
hufftree[x2].parent=n+i;
hufftree[n+i].weight=m1+m2;
hufftree[n+i].lchild=x1;
hufftree[n+i].rchild=x2;
}
return hufftree; //返回数组首地址
}
(三)函数功能：打印哈弗曼树的功能模块
void print(Hnodetype *hufftree){
cout＜＜endl＜＜endl＜＜endl; //界面优化
cout＜＜"哈弗曼树----"＜＜endl;
cout＜＜" "＜＜"weight"＜＜" "＜＜"lchild" ＜＜" "＜＜"rchild"＜＜" "＜＜"parent"＜＜endl; //界面优化
for(int i=0;i＜2*n-1;i++)
cout＜＜" "＜＜hufftree[i].weight＜＜" "
＜＜hufftree[i].lchild＜＜" "＜＜hufftree[i].rchild
＜＜" "＜＜hufftree[i].parent＜＜endl;
}
(四)函数功能：建立哈弗曼编码的功能模块
void huffmancode(Hnodetype *hufftree){
Hcodetype huffcode[maxleaf],cd;
int i,j,c,p;
for(i=0;i＜n;i++){ //求每个结点的哈弗曼编码
cd.start=n-1;
c=i;
p=hufftree[c].parent;
while(p!=-1){ //由叶子结点向上直到树根
if(hufftree[p].lchild==c)
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;
cd.start--;
c=p;
p=hufftree[c].parent;
}
for(j=cd.start+1;j＜n;j++) //将结果保存
huffcode[i].bit[j]=cd.bit[j];//保存每位号码
huffcode[i].start=cd.start; //保存开始位置
}
cout＜＜endl＜＜endl＜＜endl;
cout＜＜"哈弗曼编码"＜＜endl;
for(i=0;i＜n;i++) //打印各个字母对应的编码
{
cout＜＜"-----------"＜＜endl;
cout＜＜info[i].ch＜＜"的代码是";
for(j=huffcode[i].start+1;j＜n;j++)
cout＜＜huffcode[i].bit[j];
cout＜＜endl;
}
cout＜＜"-----------"＜＜endl;
cout＜＜endl＜＜"输入的字符串的哈夫曼编码为："＜＜endl;
for(i=0;i＜v;i++)//打印输入的字符串的编码结果
for(int y=0;y＜=n;y++)
if(s[i]==info[y].ch)
{for(j= huffcode[y].start+1;j＜n;j++)
cout＜＜huffcode[y].bit[j];}
cout＜＜endl;
}
(五)函数功能：译码的功能模块
void translation(Hnodetype *hufftree){
string code; //code记录输入的0，1代码
int t;
cout＜＜endl＜＜endl＜＜endl;
cout＜＜"请输入代码串:";
cin＞＞code;
int num=0;
while(code[num])
num++; //确定0，1代码长度
Hnodetype *p=&hufftree[2*n-2];
cout＜＜endl＜＜endl＜＜endl;
cout＜＜"译码结果----"＜＜endl;
for(int i=0;i＜num;i++){
if(code[i]=='0') //从根向下
p=&hufftree[p-＞lchild];
else
p=&hufftree[p-＞rchild];
if(p-＞lchild==-1 && p-＞rchild==-1){ //如果到达叶子结点
t=p-＞weight; //保存叶子结点的权值
for(int j=0;j＜n;j++)
if(hufftree[j].weight==t){
cout＜＜info[j].ch; //输出权值的对应的字母
break;
}
p=&hufftree[2*n-2]; //重新从根节点开始
}
}
cout＜＜endl;
}
2、测试数据
sfddaaassss
实验结果截图
3、调试过程中出现的问题以及解决策略
译码模块中，如果输入的代码串无对应的字母，则会出错。
解决办法：提示用户输入时注意
附最终代码：
#include＜iostream＞
#include＜string＞
#define maxvalue 12
#define maxleaf 12
#define maxnode 23
using namespace std;
int n=0;
int v=0;
string s;
typedef struct{
char ch;
int num;
}inf;
inf info[12];
typedef struct{
int weight; //权值
int parent;
int lchild;
int rchild;
}Hnodetype;
typedef Hnodetype Hufftree[maxnode];
//-------------------------------------
const int maxbit=10;
typedef struct{
int bit[maxbit];
int start;
}Hcodetype;
void fundchar()
{
int k,m;
cout＜＜"请输入字符串"＜＜endl;
cin＞＞s;
while(s[v]){v++;}
cout＜＜"共有字符"＜＜v＜＜"个"＜＜endl;
info[0].ch=s[0];info[0].num=1;
for(k=1;k＜=v;k++)
{
for(m=0;m＜=n;m++)
{if(info[m].ch==s[k]){++info[m].num;break;}}
if(m＞n){info[++n].ch=s[k];info[n].num=1;}
}
for(m=0;m＜n;m++)
cout＜＜"字符"＜＜info[m].ch＜＜"有"＜＜info[m].num＜＜"个"＜＜endl;
}
Hnodetype* huffmantree(){
Hnodetype *hufftree=new Hufftree;
int i,j,m1,m2,x1,x2; //m1记录最小的重权值，m2为次小
for(i=0;i＜2*n-1;i++){ //结点初始化
hufftree[i].parent=-1;
hufftree[i].weight=0;
hufftree[i].lchild=-1;
hufftree[i].rchild=-1;
}
for(i=0;i＜n;i++) //将每个字母的个数当做叶子结点的权值
hufftree[i].weight=info[i].num;
for(i=0;i＜n-1;i++){
m1=m2=maxvalue;
x1=x2=0;
for(j=0;j＜n+i;j++){
if(hufftree[j].parent==-1 && hufftree[j].weight＜m1){
m2=m1;
x2=x1;
m1=hufftree[j].weight;
x1=j; //x1记录最小重权值在数组中的下标
}
else
if(hufftree[j].parent==-1 && hufftree[j].weight＜m2){
m2=hufftree[j].weight;
x2=j; //x2记录次小重权值在数组中的下标
}
}
hufftree[x1].parent=n+i;
hufftree[x2].parent=n+i;
hufftree[n+i].weight=m1+m2;
hufftree[n+i].lchild=x1;
hufftree[n+i].rchild=x2;
}
return hufftree; //返回数组首地址
}
void huffmancode(Hnodetype *hufftree){
Hcodetype huffcode[maxleaf],cd;
int i,j,c,p;
for(i=0;i＜n;i++){ //求每个结点的哈弗曼编码
cd.start=n-1;
c=i;
p=hufftree[c].parent;
while(p!=-1){ //由叶子结点向上直到树根
if(hufftree[p].lchild==c)
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;
cd.start--;
c=p;
p=hufftree[c].parent;
}
for(j=cd.start+1;j＜n;j++) //将结果保存
huffcode[i].bit[j]=cd.bit[j];//保存每位号码
huffcode[i].start=cd.start; //保存开始位置
}
cout＜＜endl＜＜endl＜＜endl;
cout＜＜"哈弗曼编码"＜＜endl;
for(i=0;i＜n;i++) //打印各个字母对应的编码
{
cout＜＜"-----------"＜＜endl;
cout＜＜info[i].ch＜＜"的代码是";
for(j=huffcode[i].start+1;j＜n;j++)
cout＜＜huffcode[i].bit[j];
cout＜＜endl;
}
cout＜＜"-----------"＜＜endl;
cout＜＜endl＜＜"输入的字符串的哈夫曼编码为："＜＜endl;
for(i=0;i＜v;i++)//打印输入的字符串的编码结果
for(int y=0;y＜=n;y++)
if(s[i]==info[y].ch)
{for(j= huffcode[y].start+1;j＜n;j++)
cout＜＜huffcode[y].bit[j];}
cout＜＜endl;
}
void print(Hnodetype *hufftree){
cout＜＜endl＜＜endl＜＜endl;
cout＜＜"哈弗曼树----"＜＜endl;
cout＜＜" "＜＜"weight"＜＜" "＜＜"lchild" ＜＜" "＜＜"rchild"＜＜" "＜＜"parent"＜＜endl; //界面优化
for(int i=0;i＜2*n-1;i++)
cout＜＜" "＜＜hufftree[i].weight＜＜" "
＜＜hufftree[i].lchild＜＜" "＜＜hufftree[i].rchild
＜＜" "＜＜hufftree[i].parent＜＜endl;
}
void translation(Hnodetype *hufftree){
string code; //code记录输入的0，1代码
int t;
cout＜＜endl＜＜endl＜＜endl;
cout＜＜"请输入代码串:";
cin＞＞code;
int num=0;
while(code[num])
num++;//确定0，1代码长度
Hnodetype *p=&hufftree[2*n-2];
cout＜＜endl;cout＜＜endl;cout＜＜endl;
cout＜＜"译码结果----"＜＜endl;
for(int i=0;i＜num;i++){
if(code[i]=='0')
p=&hufftree[p-＞lchild];
else
p=&hufftree[p-＞rchild];
if(p-＞lchild==-1 && p-＞rchild==-1){//如果到达叶子结点
t=p-＞weight; //保存叶子结点的权值
for(int j=0;j＜n;j++)
if(hufftree[j].weight==t){
cout＜＜info[j].ch;//输出权值的对应的字母
break;
}
p=&hufftree[2*n-2];//重新从根节点开始
}
}
cout＜＜endl;
}
int main()
{
fundchar();
Hnodetype *h;
h= huffmantree();
print(h);
huffmancode(h);
translation(h);
system("pause");
return 0;
}