实验报告与总结
一、实验目的
1、掌握哈夫曼编码原理；
2、熟练掌握哈夫曼树的生成方法；
3、理解数据编码压缩和译码输出编码的实现。
二、实验要求
实现哈夫曼编码和译码的生成算法。
三、实验内容
先统计要压缩编码的文件中的字符字母出现的次数，按字符字母和空格出现的概率对其进行哈夫曼编码，然后读入要编码的文件，编码后存入另一个文件；接着再调出编码后的文件，并对其进行译码输出，最后存入另一个文件中。
五、实验原理
1、哈夫曼树的定义：假设有n个权值，试构造一颗有n个叶子节点的二叉树，每个叶子带权值为wi，其中树带权路径最小的二叉树成为哈夫曼树或者最优二叉树；
2、哈夫曼树的构造：
weight为输入的频率数组，把其中的值赋给依次建立的HT Node对象中的data属性，即每一个HT Node对应一个输入的频率。然后根据data属性按从小到大顺序排序，每次从data取出两个最小和此次小的HT Node，将他们的data相加，构造出新的HTNode作为他们的父节点，指针parent，leftchild，rightchild赋相应值。在把这个新的节点插入最小堆。按此步骤可以构造构造出一棵哈夫曼树。
通过已经构造出的哈夫曼树，自底向上，由频率节点开始向上寻找parent,直到parent为树的顶点为止。这样，根据每次向上搜索后，原节点为父节点的左孩子还是右孩子，来记录1或0，这样，每个频率都会有一个01编码与之唯一对应，并且任何编码没有前部分是同其他完整编码一样的。
六、实验流程
①
②
③
④
⑤
⑥
⑦ 初始化，统计文本文件中各字符的个数作为权值,生成哈夫曼树； 根据符号概率的大小按由大到小顺序对符号进行排序； 把概率最小的两个符号组成一个节点； 重复步骤（2）（3），直到概率和为1； 从根节点开始到相应于每个符号的“树叶”，概率大的标“0”，概率小的标“1”； 从根节点开始，对符号进行编码； 译码时流程逆向进行，从文件中读出哈夫曼树,并利用哈夫曼树将编码序列解码。
七、实验程序
#include
#include
#include
#include
using namespace std;
typedef struct //节点结构
{
char data; //记录字符值
long int weight; //记录字符权重
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树
typedef char * *HuffmanCode; //动态分配数组存储哈夫曼编码表
void Select(HuffmanTree &HT,int i,int &s1,int &s2) //在HT[1...t]中选择parent不为0且权值最小的两个结点，其序号分别为s1和s2
{
s1=0;s2=0;
int n1=30000,n2=30000;
for(int k=1;k
{
if(HT[k].parent==0)
{
if(HT[k].weight
{
n2=n1; n1=HT[k].weight;
s2=s1; s1=k;
}
else
if(HT[k].weight
{
n2=HT[k].weight;
s2=k;
}
}
}
}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int n)//将要编码的字符串存入空树中
{
ifstream fin1("zifu.txt");
ifstream fin2("weight.txt");
if(n
int m=2*n-1;
int i;
HT=new HTNode[m+1];
char *zifu;
int *weight;
zifu= new char[n+1];
weight=new int[n+1];
for(i=1;i
{
char ch;
ch=fin1.get();
zifu[i]=ch;
}
for(i=1;i
{
fin2>>weight[i];
}
for( i=1;i
{
HT[i].data=zifu[i];
HT[i].weight=weight[i];
}
for(i=n+1;i
{
HT[i].data='@';
}
for(i=1;i
{
HT[i].parent=HT[i].lchild=HT[i].rchild=0;
}
for(i=n+1;i
{
int s1,s2;
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*));开辟一个求编码的工作空间
char *cd;
cd=(char *)malloc(n*sizeof(char));//开辟空间存放权值
cd[n-1]='\0';
for(i=1;i
{
int start=n-1;
int c,f;
for( c=i, f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子到根逆向求编码
{
if(HT[f].lchild==c)
cd[--start]='0';//若是左孩子编为'0'
else
}
void printHuffmanTree(HuffmanTree HT,int n) //显示有n个叶子结点的哈夫曼树的编码表 { ofstream fout("hfmtree.txt"); //将对应字符的的哈弗曼树存入
cout
for(int i=1;i
{
fout
cout
}
}
void printHuffmanCoding(HuffmanTree HT,HuffmanCode HC,int n)//输出字符的对应哈弗曼编码并存入code.txt文件
{
cout
ofstream fout("code.txt");
for(int i=1;i
{
cout ";
cout
fout
}
}
void code_file(HuffmanTree HT,HuffmanCode HC,int n)//对文件tobetran.txt进行编码，并将编码存入codefile文件中
{
ifstream fin("tobetran.txt");
ofstream fout("codefile.txt");
vector a;
char ch;
while((ch=fin.get())!='*')
a.push_back(ch); cd[--start]='1';//若是右孩子编为'1' } HC[i]=(char *)malloc((n-start)*sizeof(char)); //为第i个编码分配空间 strcpy(HC[i],&cd[start]); } delete []cd; //释放工作空间
cout
for(int k=0;k
coutcout
cout
for(int i=0;i
{
for(int j=1;j
{
if(a[i]==HT[j].data)
{
fout
break;
}
}
}
fin.close();
fout.close();
}
void Decoding(HuffmanTree HT,HuffmanCode HC,int n)//打开codefile文件并对文件内容进行译码
{
int const m=2*n-1;
ifstream fin("codefile.txt");
ofstream fout("textfile.txt");
vector a;
for(char c;fin>>c;)
a.push_back(c);
int count=0;
for(int k=0;k
{
coutcount++;
if(count%50==0)
cout
}
int i=0;
int p; //用p来记住m的值
cout
cout
while(i
{
p=m; //从哈弗曼数的根开始遍历
while(HT[p].lchild)
{
if(a[i]=='1')
p=HT[p].rchild;
else
p=HT[p].lchild;
i++;
}
fout
cout
}
}
void main()
{
int n;
cout
cin>>n;
printf("\n");
HuffmanTree HT; //哈夫曼树HT
HuffmanCode HC; //哈夫曼编码表HC
HuffmanCoding(HT,HC,n); //进行哈夫曼编码
printHuffmanCoding(HT,HC,n); //显示编码的字符
printf("\n");
code_file(HT,HC,n); //显示要编码的字符串，并把编码值显示出来
Decoding(HT,HC,n); //译码并显示译码后的字符串
printf("\n\n\n");
system("pause");
}
八、结果分析
哈夫曼编码是动态变长编码，临时建立概率统计表和编码树。概率小的码比较长，概率小的码比较长。概率大的码短，这样把一篇文件编码后，就会压缩许多。从树的角度看，哈夫曼编码方式是尽量把短码都利用上。首先，把一阶节点全都用上，如果码字不够时，然后，再从某个节点伸出若干枝，引出二阶节点作为码字，以此类推，显然所得码长最短，再根据建立的概率统计表合理分布和放置，使其平均码长最短就可以得到最佳码。
九、实验总结
通过这次实验，我对二叉树和哈希曼树有了更好的认识。在实验过程中，我掌握了哈曼树的构造方法，学会了如何将理论知识传换成实际应用。同时，在解决程序中遇到的一些问题的同时，我也对调试技巧有了更好的掌握，分析问题的能力也略有提高。
在实验中，我遇到了许多难点，比如：统计字符的权值，就需要我们有扎实的基础，需要有灵活的头脑，只有不断的练习，不断的训练，我们才能处理各种问题。在以后的学习中，我要不断的努力，多联系，多思考，我相信我能有所进步的。
实验报告与总结
一、实验目的
1、掌握哈夫曼编码原理；
2、熟练掌握哈夫曼树的生成方法；
3、理解数据编码压缩和译码输出编码的实现。
二、实验要求
实现哈夫曼编码和译码的生成算法。
三、实验内容
先统计要压缩编码的文件中的字符字母出现的次数，按字符字母和空格出现的概率对其进行哈夫曼编码，然后读入要编码的文件，编码后存入另一个文件；接着再调出编码后的文件，并对其进行译码输出，最后存入另一个文件中。
五、实验原理
1、哈夫曼树的定义：假设有n个权值，试构造一颗有n个叶子节点的二叉树，每个叶子带权值为wi，其中树带权路径最小的二叉树成为哈夫曼树或者最优二叉树；
2、哈夫曼树的构造：
weight为输入的频率数组，把其中的值赋给依次建立的HT Node对象中的data属性，即每一个HT Node对应一个输入的频率。然后根据data属性按从小到大顺序排序，每次从data取出两个最小和此次小的HT Node，将他们的data相加，构造出新的HTNode作为他们的父节点，指针parent，leftchild，rightchild赋相应值。在把这个新的节点插入最小堆。按此步骤可以构造构造出一棵哈夫曼树。
通过已经构造出的哈夫曼树，自底向上，由频率节点开始向上寻找parent,直到parent为树的顶点为止。这样，根据每次向上搜索后，原节点为父节点的左孩子还是右孩子，来记录1或0，这样，每个频率都会有一个01编码与之唯一对应，并且任何编码没有前部分是同其他完整编码一样的。
六、实验流程
①
②
③
④
⑤
⑥
⑦ 初始化，统计文本文件中各字符的个数作为权值,生成哈夫曼树； 根据符号概率的大小按由大到小顺序对符号进行排序； 把概率最小的两个符号组成一个节点； 重复步骤（2）（3），直到概率和为1； 从根节点开始到相应于每个符号的“树叶”，概率大的标“0”，概率小的标“1”； 从根节点开始，对符号进行编码； 译码时流程逆向进行，从文件中读出哈夫曼树,并利用哈夫曼树将编码序列解码。
七、实验程序
#include
#include
#include
#include
using namespace std;
typedef struct //节点结构
{
char data; //记录字符值
long int weight; //记录字符权重
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树
typedef char * *HuffmanCode; //动态分配数组存储哈夫曼编码表
void Select(HuffmanTree &HT,int i,int &s1,int &s2) //在HT[1...t]中选择parent不为0且权值最小的两个结点，其序号分别为s1和s2
{
s1=0;s2=0;
int n1=30000,n2=30000;
for(int k=1;k
{
if(HT[k].parent==0)
{
if(HT[k].weight
{
n2=n1; n1=HT[k].weight;
s2=s1; s1=k;
}
else
if(HT[k].weight
{
n2=HT[k].weight;
s2=k;
}
}
}
}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int n)//将要编码的字符串存入空树中
{
ifstream fin1("zifu.txt");
ifstream fin2("weight.txt");
if(n
int m=2*n-1;
int i;
HT=new HTNode[m+1];
char *zifu;
int *weight;
zifu= new char[n+1];
weight=new int[n+1];
for(i=1;i
{
char ch;
ch=fin1.get();
zifu[i]=ch;
}
for(i=1;i
{
fin2>>weight[i];
}
for( i=1;i
{
HT[i].data=zifu[i];
HT[i].weight=weight[i];
}
for(i=n+1;i
{
HT[i].data='@';
}
for(i=1;i
{
HT[i].parent=HT[i].lchild=HT[i].rchild=0;
}
for(i=n+1;i
{
int s1,s2;
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*));开辟一个求编码的工作空间
char *cd;
cd=(char *)malloc(n*sizeof(char));//开辟空间存放权值
cd[n-1]='\0';
for(i=1;i
{
int start=n-1;
int c,f;
for( c=i, f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子到根逆向求编码
{
if(HT[f].lchild==c)
cd[--start]='0';//若是左孩子编为'0'
else
}
void printHuffmanTree(HuffmanTree HT,int n) //显示有n个叶子结点的哈夫曼树的编码表 { ofstream fout("hfmtree.txt"); //将对应字符的的哈弗曼树存入
cout
for(int i=1;i
{
fout
cout
}
}
void printHuffmanCoding(HuffmanTree HT,HuffmanCode HC,int n)//输出字符的对应哈弗曼编码并存入code.txt文件
{
cout
ofstream fout("code.txt");
for(int i=1;i
{
cout ";
cout
fout
}
}
void code_file(HuffmanTree HT,HuffmanCode HC,int n)//对文件tobetran.txt进行编码，并将编码存入codefile文件中
{
ifstream fin("tobetran.txt");
ofstream fout("codefile.txt");
vector a;
char ch;
while((ch=fin.get())!='*')
a.push_back(ch); cd[--start]='1';//若是右孩子编为'1' } HC[i]=(char *)malloc((n-start)*sizeof(char)); //为第i个编码分配空间 strcpy(HC[i],&cd[start]); } delete []cd; //释放工作空间
cout
for(int k=0;k
coutcout
cout
for(int i=0;i
{
for(int j=1;j
{
if(a[i]==HT[j].data)
{
fout
break;
}
}
}
fin.close();
fout.close();
}
void Decoding(HuffmanTree HT,HuffmanCode HC,int n)//打开codefile文件并对文件内容进行译码
{
int const m=2*n-1;
ifstream fin("codefile.txt");
ofstream fout("textfile.txt");
vector a;
for(char c;fin>>c;)
a.push_back(c);
int count=0;
for(int k=0;k
{
coutcount++;
if(count%50==0)
cout
}
int i=0;
int p; //用p来记住m的值
cout
cout
while(i
{
p=m; //从哈弗曼数的根开始遍历
while(HT[p].lchild)
{
if(a[i]=='1')
p=HT[p].rchild;
else
p=HT[p].lchild;
i++;
}
fout
cout
}
}
void main()
{
int n;
cout
cin>>n;
printf("\n");
HuffmanTree HT; //哈夫曼树HT
HuffmanCode HC; //哈夫曼编码表HC
HuffmanCoding(HT,HC,n); //进行哈夫曼编码
printHuffmanCoding(HT,HC,n); //显示编码的字符
printf("\n");
code_file(HT,HC,n); //显示要编码的字符串，并把编码值显示出来
Decoding(HT,HC,n); //译码并显示译码后的字符串
printf("\n\n\n");
system("pause");
}
八、结果分析
哈夫曼编码是动态变长编码，临时建立概率统计表和编码树。概率小的码比较长，概率小的码比较长。概率大的码短，这样把一篇文件编码后，就会压缩许多。从树的角度看，哈夫曼编码方式是尽量把短码都利用上。首先，把一阶节点全都用上，如果码字不够时，然后，再从某个节点伸出若干枝，引出二阶节点作为码字，以此类推，显然所得码长最短，再根据建立的概率统计表合理分布和放置，使其平均码长最短就可以得到最佳码。
九、实验总结
通过这次实验，我对二叉树和哈希曼树有了更好的认识。在实验过程中，我掌握了哈曼树的构造方法，学会了如何将理论知识传换成实际应用。同时，在解决程序中遇到的一些问题的同时，我也对调试技巧有了更好的掌握，分析问题的能力也略有提高。
在实验中，我遇到了许多难点，比如：统计字符的权值，就需要我们有扎实的基础，需要有灵活的头脑，只有不断的练习，不断的训练，我们才能处理各种问题。在以后的学习中，我要不断的努力，多联系，多思考，我相信我能有所进步的。