一、实验目的
编写一个程序，构造一棵哈夫曼树，对输入数据进行哈夫曼编码，输出对应的编码，并对下表所示的数据进行验证。
二、实验内容
CreateHT 构造哈夫曼树。
main CreateHCode 构造哈夫曼编码。
DispHCode 输出哈夫曼编码。
注：输入为一组符号（可以是字符串或者字符），及各个符号对应的频率，输出为各个符号对应的编码。
样例：
输入：
aa 5 b 3 c 7
输出：
aa 00
b 01
c 1
对应的哈夫曼树为（无需输出）：
由哈夫曼树可知，编码跟需要编码的符号是没关系的，只跟其频率有关系。即把以上树的aa改为a, 把b改为d, 则输出：a 00 d 01 c 1
三、实验步骤
四、结果与分析
出现的问题：代码运行找不出错误。
解决的方法：
结果：
五、本次实验的心得体会
进一步的了解哈夫曼树，加深了对哈夫曼树的印象。
六、源程序（带注释）
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct Tree {
int weight,left,right,parent;
};
typedef struct Tree Tree;
void dispHCode(int n)
{
int i;
for (i=0;i<n;i++)
printf("%s %s\n,s[i],code[i]);
}
int main()
{
int n,i;
scanf("%d",&n);
for (i=0;i<n;i++)
scanf("%s%d",s[i],&p[i]);
createHT(n);
createHCode(n);
dispHCode(n);
return 0;
}
void creatNode(int i,int w,int l,int r,int p)
{
tree[i].weight=w;
tree[i].left=l;
tree[i].right=r;
tree[i].parent=p;
}
void createHT(int n)
{
int i,next,min1,min2;
for(i=0;i<n;i++)
createNode(i,p[i],-1,-1,-1);
next=n;
while (next<2*n-1)
{
min1=min2=-1;
for(i=0;i<next;i++)
{
if (tree[i].parent>-1)
continue;
if (min! == -1 || tree[i].weight < tree[min1].weight)
{
min2 = min1;
min1 = i;
} else if (min2 == -1 || tree[i].weight < tree[min2].weight)
min2 = i;
}
createNode(next,tree[min1].weight+tree[min2].weight,min1,min2,-1);
tree[min1].parent = next;
tree[min2].parent = next;
next++;
}
return;
}
void travel(int i,char hcode[], int k)
{
if (tree[i].left == -1)
{
hcode[k] =0;
strcpy(code[i],hcode);
}
else
{
hcode[k] = '0';
travel(tree[i].left,hcode,k+1);
hcode[k] = '1';
travel(tree[i].right,hcode,k+1);
}
return;
}
void createHCode(int n)
{
char hcode[100];
if (i==1)
{
code[0][0]='0';
code[0][1]=0;
}
else travel(2*n-2,hcode,0);
}
第二篇：哈夫曼树的实验报告1
一、 需求分析
1、 本演示程序实现Haffman编/译码器的作用， 目的是为信息收发站提供一个编/译系统，从而使信息收发站利用Haffman编码进行通讯，力求达到提高信道利用率，缩短时间，降低成本等目标。系统要实现的两个基本功能就是：① 对需要传送的数据预先编码；② 对从接收端接收的数据进行译码；
2、 本演示程序需要在终端上读入n个字符（字符型）及其权值（整形），用于建立Huffman树,存储在文件hfmanTree.txt中；如果用户觉得不够清晰还可以打印以凹入表形式显示的Huffman树；
3、 本演示程序根据建好的Huffman树，对文件的文本进行编码，结果存入文件CodeFile中；然后利用建好的Huffman树将文件CodeFile中的代码进行译码，结果存入文件TextFile中；最后在屏幕上显示代码（每行50个），同时显示对CodeFile中代码翻译后的结果；
4、 本演示程序将综合使用C++和C语言；
5、 测试数据：
(1)教材例6-2中数据：8个字符，概率分别是0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，可将其的权值看为5，29，7，8，14，23，3，11
(2)用下表给出的字符集和频度的实际统计数据建立Haffman树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”.
一、 概要设计
1、 设定哈夫曼树的抽象数据类型定义
ADT Huffmantree{
数据对象：D={ai| ai ∈Charset,i=1,2,3,……n,n≥0}
数据关系：R1＝{< ai-1, ai >| ai-1, ai ∈D, i=2,3,……n}
基本操作：
Initialization(&HT，&HC,w，n,ch)
操作结果：根据n个字符及其它们的权值w[i],建立Huffman树HT,用字符数组ch[i]作为中间存储变量，最后字符编码存到HC中；
Encodeing(n)
操作结果：根据建好的Huffman树，对文件进行编码，编码结果存入到文件CodeFile中
Decodeing(HT,n)
操作结果：根据已经编译好的包含n个字符的Huffman树HT，将文件的代码进行翻译，结果存入文件TextFile中
} ADT Huffmantree
2、本程序主要包括三个模块
1）主程序模块
void main()
{
输入信息，初始化；
选择需要的操作；
生成Huffman树；
执行对应的模块程序；
输出结果；
}
2）编码模块——根据建成的Huffman树对文件进行编码；
3）译码模块——根据相关的Huffman树对编码进行翻译；
各模块的调用关系如图所示
二、 详细设计
1、树类型定义
typedef struct {
unsigned int weight; //权值
char ch1; //储存输入的字符
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
2、编码类型定义
typedef char **HuffmanCode;
哈夫曼编译器的基本操作设置如下
Initialization(HuffmanTree &HT，HuffmanCode &HC,int *w，int &n,char *ch)
//根据输入的n个字符及其它们的权值w[i],建立Huffman树HT,用字符数组ch[i]作为中间存储变量存储编码，最后转存到HC中；
Encodeing(int n)
//根据建好的包含n个字符的Huffman树，对文件进行编码，编码结果存入到文件CodeFile中
Decodeing(HuffmanTree HT,int n)
//根据已经编译好的包含n个字符的Huffman树HT，对文件的代码进行翻译，结果存入文件TextFile中
基本操作操作的算法
![文本框: void Initialization(HuffmanTree &HT,HuffmanCode &HC,int *w,int &n,char *ch)
{ //根据输入n个字符及其权值w[i]创建哈夫曼树HT和对字符编码HC
cin>>n; //输入包含的字符数
cin.get(ch[m]); //输入字符集,包括需要的空格
cin>>w[d]; //输入对应的权值
if(n<=1)
return; //出错处理
num=2*n-1;
HT=(HuffmanTree)malloc((num+1)*sizeof(HTNode)); //0号单元未用
//初始化
for(p=HT+1,i=1;i<=n;i++,p++){
p->weight=w[i-1]; p->lchild=0; p->parent=0; p->rchild=0; p->ch1 =ch[i-1];
}
for(;i<=num;p++,i++){
p->weight=0; p->lchild=0; p->parent=0; p->rchild=0; p->ch1 =‘*';
}
for(i=n+1;i<=num;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;
}
//---从叶子到根逆向求每个字符的哈夫曼编码----
HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); //分配n个字符编码的头指针向量
char * cd=(char *)malloc(n*sizeof(char)); //定义cd为字符数组，存储编码
cd[n-1]=‘\0’; //编码结束符
for(i=1;i<=n;i++){ //逐个字符求哈夫曼编码
int start=n-1; //编码结束符位置
for(int f=HT[i].parent,c=i;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));
strcpy(HC[i],&cd[start]);
}
//-----输出文件hfmTree.txt,保存生成树
ofstream fout ("hfmTree.txt");
fout<<ch[i]; //向文件hfmTree.txt输入字符
fout<<endl;
fout<<HC[j]<<endl; //向文件hfmTree.txt输入编码
fout.close();
free(cd);
}](https://upload2.fanwen118.com/wk001/4000404/4000404_img_003.png)
![文本框: void Encoding(int n)
{ //编码：对文件TobeTran.txt进行编码
char *a=(char *)malloc(n*sizeof(char));
char **b=(char **)malloc(n*sizeof(char *));
for(int m=0;m<20;m++) b[m]=(char *)malloc(n*sizeof(char));
//利用c语言的动态分配,用a[g]存储字符,b[g][i]存储字符对应的编码
ifstream fin ("hfmTree.txt",ios::in); //读入文件
fin.get(a[i2]); //从文件中读取字符存入a[i2]
fin>>b[j]; //从文件中读取编码存入b[j][ ]中
fin.close();
ifstream fin1("ToBeTran.txt");
ofstream fout ("CodeFile.txt");
while(fin1.get(s)){
for(int g=0;g<n;g++) {
if(a[g]==s) //寻找和hfmTree搭配的字符
fout<<b[g]; //根据字符存储的位置进行输出相对应的编码
}
}
fin1.close();
fout.close();
}](https://upload2.fanwen118.com/wk001/4000404/4000404_img_004.png)
![文本框: void Decoding(HuffmanTree ht,int n)
{ //译码：对CodeFile.txt文件进行译码
ifstream fin ("CodeFile.txt");
ofstream fout ("TextFile.txt");
fin>>s;
HuffmanTree head=ht+2*n-1; //从根结点向下求译码
while(s[0]!=‘\0’){ //判断文件开始有没有结束符
while(s[i]!=‘\0’) {//判断文件内部有没有结束符
if(s[i]==‘1') head=ht+head->rchild;
else if(s[i]==‘0') head=ht+head->lchild;
if((head->lchild)==0&&(head->rchild) ==0)
{
fout<<(head->ch1);
head=ht+2*n-1;
}
i++;
}
i=0;
fin>>s;
}
fin.close();
fout.close();
}](https://upload2.fanwen118.com/wk001/4000404/4000404_img_005.png)
主函数及其他函数的算法
![文本框: void Print(){ //打印代码文件，显示在终端，每行50个代码,
//同时显示翻译后的结果TextFile.
ifstream fin ("CodeFile.txt");
ifstream fin1("TextFile.txt");
while(fin1.get(s1))
cout<<s1;
fin>>s;
for(i=0;s[i]!=‘\0';i++){
cout<<s[i];
if((i+1)%50==0) cout<<endl;
}
cout<<endl;
fin.close();
fin1.close();
}](https://upload2.fanwen118.com/wk001/4000404/4000404_img_008.png)
![文本框: void select(HuffmanTree HT,int n,int &s1,int &s2){ //依次比较，从哈夫曼树的中parent为0的节点中选择出两个权值最小的
if(!HT[i].parent&&！HT[S1]&&!HT[S2]){
if(HT[i].weight<HT[s1].weight){
s2=s1; s1=i;
}
else if(HT[i].weight<HT[s2].weight&&i!=s1)
s2=i;
}](https://upload2.fanwen118.com/wk001/4000404/4000404_img_009.png)
void main(){
while(TURE){
cin>>需要的操作请求c;
switch(c){
case 1:
Initialization(HT,hc,w,n,ch);
break;
case 2:
Encoding(n);
break;
case 3:
Decoding(HT,n);
break;
case 4:
Print();
break;
case 5:
PrintTree(HT,HT+2*n-1,1);
break;
case 6:
m=FALSE;
}
}
}
3、函数的调用关系图
三、 调试分析
1、 本次实习作业最大的难点就是文件的读和写，这需要充分考虑到文件里面的格式，例如空格，换行等等，由于不熟悉C++语言和C语言的文件的输入和输出，给编程带来了很大的麻烦；
2、 原本计划将文本中的换行格式也进行编码，也由于设计函数比较复杂，而最终放弃；
3、 一开始考虑打印哈夫曼树的凹入表时是顺向思维，希望通过指针的顺序变迁来实现打印，但问题是从根结点到叶子结点的指针不是顺序存储的，所以未能成功，后来查找相关资料，最终利用递归的方法解决问题；
4、 程序中的数组均采用了动态分配的方法定义，力求达到减少空间的浪费；
5、 时间的复杂度主要是由查树这个步骤决定，因为无论是编码还是译码都需要对Huffman树进行查找和核对，但考虑到英文字母和空格也就是27个字符，影响不是很大；
6、 程序无论在屏幕显示还有文件存储方面都达到了不错的效果；
7、 程序不足的地方就是在文件文本格式方面处理得还是不够，或许可以通过模仿WORD的实现来改善。
四、 用户手册
1、 本程序运行于windows XP,windows vists,DOS系统，只需要运行“Huffmantree.exe”；
2、 进入演示程序后即显示一个有功能操作选择的界面，如下图：
用户可以根据不同的需求进行选择操作；
3、 如图介绍，选择“1”时，由用户输入信息进行创建Huffman树，得到的Huffman树存在文件hfmTree.txt中；
4、 选择“2”时，程序将对文件ToBeTran.txt中的内容进行编码，结果存入CodeFile.txt中；
5、 选择“3”时，程序将对文件CodeFile中的代码进行翻译，结果存入文件TextFile中；
6、 选择“4”时，将会在屏幕上打印编译“ToBeTran.txt”得到的代码和翻译“CodeFile.txt”后得到的原文;
7、 选择“5”时，将会在屏幕上打印哈夫曼树的凹入表形式并存在文件“TreePrint.txt”中；
8、 退出程序，选择“6”。
五、 测试结果
1、权值为5，29，7，8，14，23，3，11创建的哈夫曼树凹入表形式如下：
*100
*58
*29
*15
8
7
14
29
*42
23
*19
11
*8
5
3
结果跟书上的显示吻合
2、根据给出的字符和频度统计表创建Huffman树，得到的“THIS PROGRAM IS MY FAVORITE”编码是：
1111011111110001110001101001000010110011010010101011011110110001000111000110110110100101000110111101111010110011001011000111101011
根据编码：
1111011111110001110001101001000010110011010010101011011110110001000111000110110110100101000110111101111010110011001011000111101011
的翻译结果是：
“THIS PROGRAM IS MY FAVORITE”，数据吻合。
六、 附录
HuffmanTree.cpp //主程序