//求每个结点的哈弗曼编码
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; }
typedef struct{ char ch; int num; }inf;
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; //输出权值的对应的字母
2、 功能（函数）设计
一1一 统计字母种类和个数模块
此模块的功能为从键盘接受一个字符串，统计字符串中字母种类即 结点个数，每种字母出现次数即各叶子结点的权值。全局变量s保存 输入的字符串，将种类和个数保存到info[maxleaf]中。 函数原型：void fundchar（） 如输入的字符串是“sddfffgggg”则显示如下。
return hufftree;
//返回数组首地址
}
(一) 函数功能：打印哈弗曼树的功能模块
void print(Hnodetype *hufftree){ cout<<endl<<endl<<endl; //界面优化
cout<<"哈弗曼树----"<<endl;
cout<<" "<<"rchild"<<"
}
for(m=0;m<n;m++)
//输出种类和个数
cout<<"字符"<<info[m].ch<<"有"<<info[m].num<<"个"<<endl; }
(一) 函数功能:哈弗曼树的建立模块
Hnodetype* huffmantree(){ Hnodetype *hufftree=new Hufftree;
沿着结点的双亲链表域退回到根节点，每退回一步，就走过了哈夫曼树的一
个分支，从而得到一位哈夫曼值，由于一个字符的哈夫曼编码是从根结点所
经过的路径上各分支所组成的0、1序列，因此先得到的分支代码为所求编码
的低位码，后得到的分支代码为所求编码的高位码，所以设计如下的数据类
型： const int maxbit=10; typedef struct{
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
二、实验问题描述
利用哈夫曼编码进行通信可以大大提高通信利用率，缩短信息传输时间， 降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码， 在接收端将传来的数据进行译码，此试验即设计这样的一个简单的编/译码系统 。系统应该具备如下的几个功能。
1、求出各个叶子节点的权重值 输入一个字符串，统计其中各个字母的个数和总的字母个数。
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;
//保存开始位置
"<<"weight"<<"
"<<"lchild" <<"
"<<"parent"<<endl;
//界面优化
for(int i=0;i<2*n-1;i++)
cout<<"
"<<hufftree[i].weight<<"
"
<<hufftree[i].lchild<<"
"<<hufftree[i].rchild
2、构造哈夫曼树 统计出的字母种类为叶子结点个数，每个字母个数为相应的权值，建立哈 夫曼树。
3、打印哈弗曼树的功能模块 按照一定形式打印出哈夫曼树。
4、编码 利用已经建立好的哈夫曼树进行编码。
5、译码 根据编码规则对输入的代码进行翻译并将译码。
1、实验问题分析
三、实验步骤
一1一 设计一个结构体数组保存字母的类型和个数。
// 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(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;
四、实验结果（程序）及分析
1、实验主要模块代码
(一) 函数功能：统计字母种类和个数模块
void fundchar() {
int k,m; cout<<"请输入字符串"<<endl;
cin>>s;
//s为输入的字符串
while(s[v]){v++;} cout<<"共有字符"<<v<<"个"<<endl;
typedef struct{ int weight;
//权值
int parent;
int lchild; int rchild;
//双亲
//左孩子 //右孩子
}Hnodetype; typedef Hnodetype Hufftree[maxnode];
//定义此类型的数组
、3、 求哈夫曼编码，实质上是在已经建立的哈夫曼树中，从叶子结点开始，
一5一 译码的功能模块 此模块的功能为接收需要译码的0和1代码串，按照（4）中建立的编码 规则将其翻译成字符集中字符所组成的字符串形式，并将翻译的结 果在屏幕上打印出来。
函数原型：void translation(Hnodetype *hufftree) 如输入的代码串是“110111100”，则对应的字符串是“sdfg”
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;
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;
//结点初始化
数学与计算机学院 数据结构 实验报告
年级 09数计 学号 2009432125 姓名 刘宝 成绩 专业 数电 实验地点 主楼401 指导教师 苗秀芬 实验项目 哈夫曼树解决编码解码 实验日期 10年12月24日