哈夫曼树及其应用实验报告
实验 四 哈夫曼树及其的应用
一、实验目的
1．在二叉树基本操作的基础上，掌握对二叉树的一些其它操作的具体实现方法。
2.掌握构造哈夫曼树以及哈夫曼编码的方法。
3、熟练掌握哈夫曼树（最优二叉树）特征及其应用
二、实验内容
题目一、哈夫曼树和哈夫曼编码：
从终端输入若干个字符，统计（或指定）字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，然后对各字符进行哈夫曼编码。
设计要求：
⑴ 哈夫曼殊和哈夫曼编码的存储表示参考教材事例
⑵ 在程序中构造四个子程序为
① int freqchar(char *text, HTree *t) /*统计字符出现的频率*/
② int createhtree(HTree *t) /*根据字符出现的频率建立哈夫曼树*/
③ void coding(HTree *t,int head_i,char *code)
/*对哈夫曼树进行编码*/
④ void printhtree(HTree *t,int head_i,int deep,int* path)
/*中序打印树*
三、实验步骤
㈠、数据结构与核心算法的设计描述
struct frequence//统计频率
{
char a;
int n;
}
typedef struct
{
unsigned int weight;// 用来存放各个结点的权值
unsigned int parent,lchild,rchild;//指向双亲、 孩子结点的指针
}HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树
typedef char **HuffmanCode;
void Frequent()
void HuffmanCoding(HuffmanTree &HT,HuffmanCode&HC,int *w,int n)
//w存放n个权值, 构造哈夫曼树p, 并求出哈夫曼编码hc
㈡、函数调用及主函数设计
Main()调用HuffmanTree()函数；
HuffmanTree（）函数调用Frequent()函数
㈢ 程序调试及运行结果分析
以下是程序调试结果的截图及说明
上图是从终端输入一串字符，并把并且统计字符个数作为权值的运行结果。
上图是打印哈夫曼树运行结果
上图是输出哈夫曼编码的运行结果
㈣ 实验总结
哈夫曼编码是二叉树的具体应用，哈夫曼编码的实验不仅巩固了我对二叉树应用和理解，还加深了我对树的具体应用的理解，在实验过程中，刚开始对哈夫曼的编程没有头绪，突然发现自己书看的太少，并且对算法理解的不透彻，课后也没有好好复习所学知识。总的来说，哈夫曼树的操作我还不是很熟练，因此还要好好练习，才能真正理解哈夫曼树的应用，所以在课后，我还会好好练习树的使用。
四、主要算法流程图及程序清单
struct frequence//统计频率
{
char a;
int n;
}
typedef struct
{
unsigned int weight;// 用来存放各个结点的权值
unsigned int parent,lchild,rchild;//指向双亲、 孩子结点的指针
}HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树
typedef char **HuffmanCode;
void Frequent()
{
frequence ch[27];
int i=0;
for(;i<=26;i++)//初始化结构体数组
{
ch[i].n=0;
}
cout<<"输入一串字符（输入#键结束输入）："<<endl;
char c;
cin>>c;
bool flag;
while(c!='#')
{
i=1;
flag=false;
for(;i<=ch[0].n;i++)
{
if(c==ch[i].a)
{
flag=true;
break;
}
}
if(flag)//已存在
{
ch[i].n++;
}
else//不存在
{
ch[0].n++;
ch[ch[0].n].n++;
ch[ch[0].n].a=c;
}
cin>>c;
}
for(int j=1;j<=ch[0].n;j++)
{
cout<<ch[j].a<<" "<<ch[j].n<<endl;
}
}
void Select(HuffmanTree HT,int i,int &s1,int &s2)
{
int j,k=1;
while(HT[k].parent!=0)
k++;
s1=k;
for(j=1;j<=i;++j)
if(HT[j].parent==0&&HT[j].weight<HT[s1].weight)
s1=j;
k=1;
while((HT[k].parent!=0||k==s1))
k++;
s2=k;
for(j=1;j<=i;++j)
if(HT[j].parent==0&&HT[j].weight<HT[s2].weight&&j!=s1)
s2=j;
}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode&HC,int *w,int n)
{ //w存放n个权值, 构造哈夫曼树p, 并求出哈夫曼编码hc
int m,i,s1,s2,start,c,f;
HuffmanTree p;
if(n<=1)
return;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(p=HT+1,i=1;i<=n;++i,++p,++w)
{
p->weight=*w;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(;i<=m;++i,++p)
{
p->weight=0;
p->parent=0;
p->lchild=0;
}
cout<<endl<<endl<<"打印哈夫曼树:"<<endl;
for(i=n+1;i<=m;++i)//建立赫夫曼树
{
Select(HT,i-1,s1,s2);
HT[s1].parent=i;
HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
cout<<" i weight parent lchild rchild"<<endl;
for(p=HT+1,i=1;i<=m;i++,p++)
cout<<setw(2)<<i<<setw(7)<<p->weight<<setw(6)<<p->parent<<setw(7)<<p->lchild<<setw(8)<<p->rchild<<endl;
HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
char *cd;
cd=(char *)malloc(n*sizeof(char));//分配求编码的工作空间
cd[n-1]='\0';
cout<<"哈夫曼编码如下:"<<endl;
for(i=1;i<=n;++i)//逐个字符求赫夫曼编码
{
start=n-1;
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子到根逆向求编码
if(HT[f].lchild==c)
cd[--start]='0';
else
cd[--start]='1';
HC[i]=(char*)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间
strcpy(HC[i],&cd[start]);
printf("\nHT[%d] 节点哈夫曼编码: %s",i,HC[i]);
}
cout<<endl;
free(cd);
}
int main()
{
HuffmanTree HT;
HuffmanCode HC;
Frequent();
int m,n;
int *w,W[maxsize];
cout<<"输入上面字符种类的个数: "<<endl;
cin>>m;
cout<<"依次输入上述字符出现的频率作为要构造的哈夫曼树的权值:"<<endl;
for(n=0;n<m;++n)
{ cin>>W[n];}
w=W;
HuffmanCoding(HT,HC,w,m);
return 0;
}
第二篇：哈夫曼树编码实验报告
哈夫曼树编码实验报告
姓名：沈雅丽 班级：09092311 学号：09923102
需求分析：
构建哈夫曼树及哈夫曼编码，输出哈夫曼树及哈夫曼编码，完成编码与译码的算法。掌握树的有关操作算法。熟悉树的基本存储方法。学习利用树求解实际问题
概要设计：
ADT HuffmanTree{
数据对象：D={ai| ai∈CharSet,i=1,2,……,n, n≥0}
数据关系：R={< ai-1, ai > ai-1, ai∈D, ai-1<ai ,i=2，3，……，n}
构造哈夫曼树：
for(i=n+1;i<=m;++i) // 建赫夫曼树
{ // 在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2
select(HT,i-1,s1,s2);
HT[s1].parent=HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
求哈弗曼编码：
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
// 分配n个字符编码的头指针向量([0]不用)
cd=(char*)malloc(n*sizeof(char)); // 分配求编码的工作空间
cd[n-1]='\0'; // 编码结束符
for(i=1;i<=n;i++)
{ // 逐个字符求赫夫曼编码
start=n-1; // 编码结束符位置
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
// 从叶子到根逆向求编码
if(HT[f].lchild==c)
cd[--start]='0';
else
cd[--start]='1';
HC[i]=(char*)malloc((n-start)*sizeof(char));
// 为第i个字符编码分配空间
strcpy(HC[i],&cd[start]); // 从cd复制编码(串)到HC
详细设计：
typedef struct
{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; // 动态分配数组存储赫夫曼树
typedef char **HuffmanCode; // 动态分配数组存储赫夫曼编码表
//建立哈夫曼树
int m,i,s1,s2,start;
unsigned c,f;
HuffmanTree p;
char *cd;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0号单元未用
for(p=HT+1,i=1;i<=n;++i,++p,++w)
{
(*p).weight=*w;
(*p).parent=0;
(*p).lchild=0;
(*p).rchild=0;
}
for(;i<=m;++i,++p)
(*p).parent=0;
for(i=n+1;i<=m;++i) // 建赫夫曼树
{ // 在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2
select(HT,i-1,s1,s2);
HT[s1].parent=HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
源代码：
#include<malloc.h> // malloc()等
#include<limits.h> // INT_MAX等
#include<stdio.h> // EOF(=^Z或F6),NULL
#include<iostream.h> // cout,cin
typedef struct
{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; // 动态分配数组存储赫夫曼树
typedef char **HuffmanCode; // 动态分配数组存储赫夫曼编码表
int min(HuffmanTree t,int i)
{ // 函数void select()调用
int j,flag;
unsigned int k=UINT_MAX; // 取k为不小于可能的值
for(j=1;j<=i;j++)
if(t[j].weight<k&&t[j].parent==0)
{k=t[j].weight;flag=j; }
t[flag].parent=1;
return flag;
}
void select(HuffmanTree t,int i,int &s1,int &s2)
{ // s1为最小的两个值中序号小的那个
int j;
s1=min(t,i);
s2=min(t,i);
if(s1>s2)
{
j=s1;
s1=s2;
s2=j;
}
} // 以上同algo6-1.cpp
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) // 前半部分为算法6.12
{ // w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC
int m,i,s1,s2,start;
unsigned c,f;
HuffmanTree p;
char *cd;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0号单元未用
for(p=HT+1,i=1;i<=n;++i,++p,++w)
{
(*p).weight=*w;
(*p).parent=0;
(*p).lchild=0;
(*p).rchild=0;
}
for(;i<=m;++i,++p)
(*p).parent=0;
for(i=n+1;i<=m;++i) // 建赫夫曼树
{ // 在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2
select(HT,i-1,s1,s2);
HT[s1].parent=HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
// 分配n个字符编码的头指针向量([0]不用)
cd=(char*)malloc(n*sizeof(char)); // 分配求编码的工作空间
cd[n-1]='\0'; // 编码结束符
for(i=1;i<=n;i++)
{ // 逐个字符求赫夫曼编码
start=n-1; // 编码结束符位置
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
// 从叶子到根逆向求编码
if(HT[f].lchild==c)
cd[--start]='0';
else
cd[--start]='1';
HC[i]=(char*)malloc((n-start)*sizeof(char));
// 为第i个字符编码分配空间
strcpy(HC[i],&cd[start]); // 从cd复制编码(串)到HC
}
free(cd); // 释放工作空间
}
void main()
{
HuffmanTree HT;
HuffmanCode HC;
int *w,n,i;
printf("请输入权值的个数(>1)：");
scanf("%d",&n);
w=(int*)malloc(n*sizeof(int));
printf("请依次输入%d个权值(整型)：\n",n);
for(i=0;i<=n-1;i++)
scanf("%d",w+i);
HuffmanCoding(HT,HC,w,n);
for(i=1;i<=n;i++)
puts(HC[i]);
}
运行结果及指示：
调试分析：
1.深刻体会构建哈夫曼树的整个过程，对整体有个总的理解；
2.复习以前所学C语言的一些语法，例如：for循环，if循环，while循环
3.理解哈夫曼的编码过程，编码思想
4.此程序的不足之处在于在进行哈夫曼编码时未能对字符进行编制，有待改进。
5.基本上没有什么太大的问题，在调用select（）这个函数时，想把权值最小的两个结点的序号带回HuffmanCoding()，所以把那2个序号设置成了引用。
6.在编程过程中，在什么时候分配内存，什么时候初始化花的时间比较长
7.最后基本上实现后，发现结果仍然存在问题，经过分步调试，发现了特别低级的输入错误。把HT[i].weight=HT[s1].weight+HT[s2].weight;中的s2写成了i