哈夫曼编码实验报告.doc

哈夫曼编码实验报告
LT
3
实验一 哈夫曼编码
一、实验目的
掌握哈夫曼编码原理；
熟练掌握哈夫曼树的生成方法；
3、理解数据编码压缩和译码输出编码的实现。
二、实验要求
实现哈夫曼编码和译码的生成算法。
三、实验内容
先统计要压缩编码的文件中的字符字母出现的次数，按字符字母和空格出现的概率对其进行哈夫曼编码，然后读入要编码的文件，编码后存入另一个文件；接着再调出编码后的文件，并对其进行译码输出，最后存入另一个文件中。
五、实验原理
1、哈夫曼树的定义：假设有n个权值，试构造一颗有n个叶子节点的二叉树，每个叶子带权值为wi，其中树带权路径最小的二叉树成为哈夫曼树或者最优二叉树；
2、哈夫曼树的构造：
weight为输入的频率数组，把其中的值赋给依次建立的HT Node对象中的data属性，即每一个HT
3
Node对应一个输入的频率。然后根据data属性按从小到大顺序排序，每次从data取出两个最小和此次小的HT Node，将他们的data相加，构造出新的HTNode作为他们的父节点，指针parent，leftchild，rightchild赋相应值。在把这个新的节点插入最小堆。按此步骤可以构造构造出一棵哈夫曼树。
   通过已经构造出的哈夫曼树，自底向上，由频率节点开始向上寻找parent,直到parent为树的顶点为止。这样，根据每次向上搜索后，原节点为父节点的左孩子还是右孩子，来记录1或0，这样，每个频率都会有一个01编码与之唯一对应，并且任何编码没有前部分是同其他完整编码一样的。
六、实验流程
初始化，统计文本文件中各字符的个数作为权值,生成哈夫曼树；
根据符号概率的大小按由大到小顺序对符号进行排序；
把概率最小的两个符号组成一个节点；
重复步骤（2）（3），直到概率和为1；
从根节点开始到相应于每个符号的“树
4
5
&HT,HuffmanCode &HC,int n)//将要编码的字符串存入空树中
{
ifstream fin1("");
ifstream fin2("");
if(n<=1)return;
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<=n;i++)//将待编码的字符放在zifu数组中
{
char ch;
ch=();
zifu[i]=ch;
}
for(i=1;i<=n;i++)//将带编码字符对应的权值放在weight数组中
7
{
fin2>>weight[i];
}
for( i=1;i<=n;i++)
{
HT[i].data=zifu[i];
HT[i].weight=weight[i];
}
for(i=n+1;i<=m;i++)
{
HT[i].data='@';
}
for(i=1;i<=m;i++)
{
HT[i].parent=HT[i].lchild=HT[i].rchild=0;
}
for(i=n+1;i<=m;++i)
{
int s1,s2;
Select(HT,i-1,s1,s2);
7
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<=n;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