福建农林大学金山学院实验报告
系（教研室）： 专业： 计算机科学与技术 年级： 08 实验课程： 姓名： 学号：
实验室号：_______ 计算机号：
实验时间： 指导教师签字： 成绩： 实验二：哈夫曼树及哈夫曼编码译码的实现（验证性、4学时）
一、 实验目的和要求
构建哈夫曼树及哈夫曼编码，输出哈夫曼树及哈夫曼编码，完成编码与译码的
算法。
（1）掌握树的有关操作算法
（2）熟悉树的基本存储方法
（3）学习利用树求解实际问题
二、 实验内容和原理
定义哈夫曼树的存储结构；输入要编码的字符权重，根据权重建立哈夫曼
树，并进行编码，最后输出哈夫曼编码。
三、 实验环境
硬件：（1）学生用微机（2）多媒体教室或远程教学（3）局域网环境
软件：（1）Windows XP中文操作系统 （2）Turbo C 3.0
四、 算法描述及实验步骤
1． 算法描述
(1).建立哈夫曼树的算法
定义各节点类型其中应包含两类数据
一是权重域weight；一是指针域而指针域中应该包括指向左右孩子
和指向双亲的指针这里分别用lchild、rdhild和parent来表示因此可
用静态三叉链表来实现，在实际构造中由于是叶子节点来构造新的
根节点其构造过程中仅与叶子节点的权重有关而与其数据域无关所
以构造过程中不用考虑其数值域，并且在链表中从叶子开始存放，
让后不断的将两颗最小权值的子树合并为一颗权值为其和的较大的
子树，逐步生成各自内部节点直到树根。
(2).哈夫曼编码的算法
将建立的哈夫曼树从每个叶子节点开始沿着双亲域回到根节点，梅走一步进行编码得到一位编码值；由于每个叶子节点的哈夫曼编码是从根节点到相应的叶子的路径的各个分支的代码组成的0和1序列，所以先得到了低位编码后得到高位编码因此可用一维数组从后向前来存放各位编码值，并用start来记录编码的起始位置。
2． 算法流程图
构建哈夫曼树算法流程
哈夫曼编码算法流程
3． 代码
#include <stdio.h>
#include <malloc.h>
#define maxvalue 10000 //定义最大权值常量
#define maxnodenumber 100 //定义节点最大数
#define maxbit 10 //定义哈弗曼编码最大长度
typedef struct //定义新数据类型即节点结构
{int weight; //权重域
int parent,lchild,rchild; //指针域
}htnode; //节点类型标识符
//typedef htnode * huffmanstree; //定义哈弗曼数类型
htnode ht[maxnodenumber]; //定义三叉链表存储数组
typedef struct //定义保存一个叶子节点哈弗曼编码的结构
{
int bit[maxbit]; //定义一维数组为编码域 int start; //定义位置域
}hcnodetype; //定义编码类型
htnode * creatstree(int n) //huffmanstree creatstree(int n) //建立哈夫曼树算法实现函
数 { int i,j,m1,m2,k1,k2; //局部变量 for(i=0;i<2*n-1;i++) //初始化各节点 { } for(i=0;i<n;i++) //权重赋初值，由用户输入 { } for(i=0;i<n-1;i++) //生成新节点构造哈夫曼树 { m1=maxvalue; //预置最小权值变量为最大权值 m2=maxvalue; //预置次小权值变量为最大权值 k1=0; //预置最小权值节点位置为下标为0处 k2=0; //预置次小权值节点位置为下标为0处 for(j=0;j<n+i;j++) //循环找出每趟最下权值和所在位置 if(ht[j].parent==-1&&ht[j].weight<m1) { } else //当小于当前次小m2则更新m2及其位置 if(ht[j].parent==-1&&ht[j].weight<m2) m2=m1; k2=k1; m1=ht[j].weight; k1=j; scanf("%d",&ht[i].weight); ht[i].weight=0; //权重初始化为0 ht[i].parent=-1; //根节点和给左右孩子初始化为-1 ht[i].lchild=-1; ht[i].rchild=-1;
{ } m2=ht[j].weight;k2=j; ht[k1].parent=n+i; //修改最小权值节点的双亲为刚生成的新节点 ht[k2].parent=n+i; //修改次小权值节点的双亲为刚生成的新节点 ht[n+i].weight=ht[k1].weight+ht[k2].weight; //将新生成的权重值填入新的根节点
}
void getstree(htnode * ht,int n) //哈夫曼编码算法及打印函数的实现
{
} ht[n+i].lchild=k1; //新生节点左孩子指向k1 ht[n+i].rchild=k2; //新生节点右孩子指向k2 return ht; //返回哈夫曼树指针 int i,j,c,p; //局部变量的定义 hcnodetype cd[maxnodenumber]; //定义存储哈夫曼编码的数组 for(i=0;i<n;i++) //循环控制对每一个节点进行编码 { c=i; //为编码各节点初始化c和j j=maxbit; do { j--; //j指向bit中存放编码为的正确位置 p=ht[c].parent; //p指向c的双亲节点 if(ht[p].lchild==c) //如果c是p的左孩子 cd[i].bit[j]=0; //编码为赋值0 else //否则即c是p的右孩子 cd[i].bit[j]=1; //编码赋值1 c=p;//更新当前指针，为下一节点编码做准备
}
} } }while(ht[p].parent!=-1); //判断是否编码结束即循环至最终根节点 cd[i].start=j; //编码完成,记下编码开始位置 for(i=0;i<n;i++) //循环打印各节点哈夫曼编码 { for(j=cd[i].start;j<maxbit;j++)//循环逐一输出 printf("%d",cd[i].bit[j]); printf("\n"); //每输出一编码后换行
int main() //主函数
{
int n;
printf("请输入节点数:"); //用户输入节点数
scanf("%d",&n);
htnode * p; // huffmanstree p //定义哈夫曼树类型p
p=(htnode * )malloc(sizeof(htnode *));//p=(huffmanstree)malloc(sizeof(huffmanstree))//分配内存空间
p=creatstree(n);//调用建立哈夫曼树函数赋返回值给p
getstree(p,n); //调用编码函数读入建立的哈夫曼树p进行编码
return 0;
}
五、 调试过程
出现该错误是因为type识别不了，即定义哈夫曼树时确切的说是type并不能定义htnode *标识符为huffmanstree：type htnode * huffmanstree
这个小错误可以通过连个方法来修改一是将type改为typedef，当然直接删除该定义完全不会影响程序的执行，但在定义建立哈夫曼树函数时返回值应直接用
htnode *；
该错原因是参数未能成功传递，其中的ht[p]系统当做是未定义的类型可知，在getstree（htnode ht，int n）时正确的应当是传递哈夫曼树的头指针即数组首地址ht因此改为getstree（htnode * ht，int n）
六、 实验结果
通过改正后成功编译连接，进行数据测试
{5,20,12,7,47，9}当然编码因为定义时大小的左右排序是不同的所以编码也不唯一，但在这里是以左小右大来分布的，所以编码结果符合预期的。
所构造哈夫曼树如图所示
七、 总结
该实验不仅让我加深了对哈夫曼树的理解，更是让我惊叹该算法的强大，一个简单的数组类型数据加之简单的链表在实现该算法后让我理解了基础理论知识的重要性，倘若在不知道这个算法的情况下。我不知道自己得花多少的时间来实现编码，或许最终还不一定能够很好的实现编码，更别说优化了。尤其树的基本存储方法更加深了我对树的理解。
附录：
第二篇：树的应用 哈夫曼编编码 和 译码
华%%%%%%%%%%%%%%%%%%学院 数据结构实验报告
2011～2012学年 第二学期 2011级 计算机 专业
班级： 学号： 姓名：
实验三 树的应用
一、实验题目：
树的应用——哈夫曼编/译码
二、实验内容：
利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。根据哈夫曼编码的原理，编写一个程序，在用户输入字符及权值的基础上求哈夫曼编码。要求：
（1） 从键盘输入字符集（字母a～z，空格）共27个字符，以及出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，并输出数组ht[]的初态和终态。
（2） 对各个字符进行哈夫曼编码，打印输出字符及对应的哈夫曼编码。
（3） 编码：从键盘输入字符串，利用已建好的哈夫曼编码，实现该字符串的编码。
（4） （选作）译码：从键盘输入二进制串，利用已建好的哈夫曼编码，将二进制串还原为字符串。
三、程序源代码：
typedef struct
{
char data;
int weight;
int parent;
int lchild;
int rchild;
}HTNode;
typedef struct
{
char cd[100];
int start;
}HCode;
//这里保存字母对应的编码，我本来想用指向字符数组的指针数组，可是后来想到利用结构体更简单。
struct Codes
{
char ch;
char codes[27];
};
#include<iostream.h>
#include<stdio.h>
#include<string.h>
const int maxsize=100;
//特色，动态编码
void tongji(char str[],int *pinlv);
void createHT(HTNode *ht,int n,int pinlv[]);
void showHT(HTNode ht[],int n);
void createHcode(HTNode ht[],HCode* hcd,int n);
void showHCode(HCode hcd[],int n,int pinlv[]);
//使字符与编码对应
void matchcodes(HCode hcd[],int pinlv[],int n,Codes* code);
void charToCode(Codes codes[],char *str);
void codeToChar(Codes codes[]);
void main()
{
cout<<"本例实现动态编码：根据输入的字符串建立编码规则，然后按此规则对输入的字符串进行编码，对输入的编码进行译码操作"<<endl;
//输入
cout<<"input a string"<<endl;
char str[maxsize];
gets(str);
//统计
int pinlv[27];
int len=0;
for(int i=0;i<27;i++)
pinlv[i]=0;
tongji(str,pinlv);
for(int k=0;k<27;k++)
if(pinlv[k]!=0)
len++;
cout<<len<<endl;
// cout<<pinlv[26]<<endl;
//构造哈夫曼树
HTNode ht[199];
createHT(ht,len,pinlv);
//哈夫曼编码
HCode hcd[27];
createHcode(ht,hcd,len);
showHCode(hcd,len,pinlv);
//字符与编码对应匹配
Codes codes[27];
matchcodes(hcd,pinlv,len,codes);
//char to code
charToCode(codes,str);
// code to char
codeToChar(codes);
}
//这个函数有错误，已经改正
void codeToChar(Codes codes[])
{
cout<<"根据上面输出的编码规则，请输入要译码的01编码（相邻编码要以逗号分割，以“#”结束）"<<endl;
char str[100];
gets(str);
cout<<str<<"的译码为："<<endl;
char temp[27]; //保存每个字符的编码，每次要赋 0 啊
int i,j;
for(i=0,j=0;i<100;i++)
{
if(str[i]!=',')
{
temp[j]=str[i];
j++;
}
else
{
temp[j]='\0';
for(int k=0;k<27;k++)
{
if(strcmp(codes[k].codes ,temp)==0)
{
cout<<codes[k].ch <<" ";
//cout.flush();
break;
}
}
j=0; //赋0 操作
}
if(str[i]=='#')
{
break;
}
}
cout<<endl;
}
void charToCode(Codes codes[],char *str)
{
char ch=*str;
int k=0;
cout<<str<<"的编码为："<<endl;
while(ch!='\0')
{
for(int i=0;i<27;i++)
{
if(codes[i].ch ==ch)
cout<<codes[i].codes<<"，";
}
k++;
ch=*(str+k);
}
cout<<endl;
}
//已经改进过的地方
void matchcodes(HCode hcd[],int pinlv[],int n,Codes* codes)
{
int i,k,m;
char ch='a';
int p=0;
char temp[27];
for(int z=0;z<26;z++)
{
temp[z]=' ';
}
temp[26]='\0';
for(i=0;i<27;i++)
{
if(pinlv[i]!=0)
{
ch='a';
ch=char(ch+i);
if(ch>='a'&&ch<='z')
{
codes[p].ch =ch;
//测试
/* if(codes[p].ch==ch)
{
cout<<"succss"<<endl;
}*/
}
else
codes[p].ch =' ';
m=0;
for(k=hcd[p].start;k<=n;k++)
{
temp[m]=hcd[p].cd [k];
m++;
}
//字符串必须给出结束符位置，否则会输出乱码啊
temp[m]='\0';
//codes[p]=temp;
strcpy(codes[p].codes ,temp);
// cout<<codes[p].ch;
// cout<<codes[p].ch<<"-----"<<codes[p].codes<<endl;
p++;
}
}
}
void showHCode(HCode hcd[],int n,int pinlv[])
{
int i,k;
char ch='a';
int p=0;
cout<<"字符"<<" "<<"对应编码"<<endl;
for(i=0;i<27;i++)
{
//每次必须从字符'a'开始
ch='a';
////
ch=char(ch+i);
if(pinlv[i]!=0)
{
if(ch>='a'&&ch<='z')
cout<<ch<<" ";
else
cout<<" "<<" ";
for(k=hcd[p].start;k<=n;k++)
cout<<hcd[p].cd [k];
p++;
cout<<endl;
}
}
}
void createHcode(HTNode ht[],HCode* hcd,int n)
{
int i,f,c;
HCode hc;
for(i=0;i<n;i++)
{
//不是书上的 hc.start =n;
hc.start =n-1;
c=i;
f=ht[i].parent ;
while(f!=-1)
{
if(ht[f].lchild ==c)
hc.cd [hc.start --]='0';
else
hc.cd [hc.start --]='1';
c=f;
f=ht[f].parent ;
}
//最后一位必须赋值为结束符
hc.cd[n]='\0';
hc.start ++;
hcd[i]=hc;
}
}
void createHT(HTNode* ht,int n,int pinlv[])
{
for(int m=0;m<=2*n-1;m++)//初始化节点的所有与域值
ht[m].parent =ht[m].lchild =ht[m].rchild =-1;
char ch='a';
int p=0;
for(int z=0;z<27;z++)//循环27个字母（a-z和''），若频数大于0，就创建节点
{
if(pinlv[z]!=0)
{
if(ch>='a'&&'z'>=ch)
{
ht[p].data =ch;
ht[p].weight =pinlv[ch-97];
}
else
{
ht[p].data =' ';
ht[p].weight =pinlv[26];
}
p++;
}
ch=char (ch+1);
}
cout<<"ht[]初态输出 ";
showHT(ht,n);
int i,k,lnode,rnode;
int min1,min2;
for(i=n;i<2*n-1;i++)
{
min1=min2=32767;
lnode=rnode=-1;
for(k=0;k<=i-1;k++)
{
if(ht[k].parent ==-1)
{
if(ht[k].weight <min1)
{
min2=min1;rnode=lnode;
min1=ht[k].weight ;lnode=k;
}
else if(ht[k].weight <min2)
{
min2=ht[k].weight ;
rnode=k;
}
}
}
ht[lnode].parent =i;ht[rnode].parent =i;
ht[i].weight =ht[lnode].weight +ht[rnode].weight ;
ht[i].lchild =lnode;ht[i].rchild =rnode;
ht[i].data ='*';
}
cout<<"ht[]终态输出 ";
showHT(ht,2*n-1);
}
void tongji(char str[],int *pinlv)
{
char ch=*str;
int k=1;
while(ch!='\0')
{ if(ch>='a'&&'z'>=ch)
pinlv[ch-97]+=1;
else
pinlv[26]+=1;
ch=*(str+k);
k++;
}
}
void showHT(HTNode ht[],int n)
{ cout<<"节点信息如下："<<endl;
cout<<"data"<<" "<<"weig"<<" "<<"pare"<<" "<<"lchd"<<" "<<"rchd"<<endl;
for(int i=0;i<n;i++)
{
cout<<ht[i].data <<" "<<ht[i].weight <<" "<<ht[i].parent <<" "<<ht[i].lchild <<" "<<ht[i].rchild <<endl;
}
}
四、 测试结果：
五、小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等）
注：内容一律使用宋体五号字，单倍行间距
通过本次实验，我感觉到自己的程序编程细节问题必须注意：如使用gets（）函数可接收带有空格的输入字符串；在进行编码译码时，必须注意，数组的上下界问题。
做一个程序，不仅要有思路，更要有细心，耐心。