实验一哈夫曼编码
一、实验目的
1、掌握哈夫曼编码原理；
2、熟练掌握哈夫曼树的生成方法；
3、理解数据编码压缩和译码输出编码的实现。
二、实验要求
实现哈夫曼编码和译码的生成算法。
三、实验内容
先统计要压缩编码的文件中的字符字母出现的次数，按字符字母和空格出现的概率对其
进行哈夫曼编码，然后读入要编码的文件，编码后存入另一个文件；接着再调出编码后的文件，并对其进行译码输出，最后存入另一个文件中。
五、实验原理
1、哈夫曼树的定义：假设有n个权值，试构造一颗有n个叶子节点的二叉树，每个叶子带权值为wi，其中树带权路径最小的二叉树成为哈夫曼树或者最优二叉树；
2、哈夫曼树的构造：
weight为输入的频率数组，把其中的值赋给依次建立的HT Node对象中的data属性,
即每一个HT Node对应一个输入的频率。然后根据data属性按从小到大顺序排序，每次从data取出两个最小和此次小的HT Node，将他们的data相加，构造出新的HTNode作为他们的父节点，指针pare nt，leftchild，rightchild赋相应值。在把这个新的节点插入最小堆。按此步骤可以构造构造出一棵哈夫曼树。
通过已经构造出的哈夫曼树，自底向上，由频率节点开始向上寻pare nt，直到pare nt 为树的顶点为止。这样，根据每次向上搜索后，原节点为父节点的左孩子还是右孩子，来记录1或0，这样，每个频率都会有一个01编码与之唯一对应，并且任何编码没有前部分是
同其他完整编码一样的。
六、实验流程
①初始化，统计文本文件中各字符的个数作为权值，生成哈夫曼树；
②根据符号概率的大小按由大到小顺序对符号进行排序；
③把概率最小的两个符号组成一个节点；
④重复步骤（2）（3），直到概率和为1 ；
⑤从根节点开始到相应于每个符号的树叶”概率大的标“0”概率小的标“ 1；
⑥从根节点开始，对符号进行编码；
⑦译码时流程逆向进行，从文件中读出哈夫曼树，并利用哈夫曼树将编码序列解码。七、实验程序
#in clude<iostream>
#in clude<fstream>
#in clude<ioma nip>
#in clude<vector>
using n amespace std;
typedef struct // 节点结构
{
char data; //记录字符值
long int weight; 〃记录字符权重
un sig ned int pare nt,lchild,rchild;
}HTNode,*Huffma nTree; //动态分配数组存储哈夫曼树
typedef char * *HuffmanCode; //动态分配数组存储哈夫曼编码表void Select(HuffmanTree &HT,int i,int &s1,int &s2) // 在] 且权值最小的两个结点，其序号分别为si和s2
{
s1=0;s2=0;
int n1=30000, n2=30000;
for(i nt k=1;k<=i;k++)
{
if(HT[k].pare nt==O)
{
if(HT[k].weight< n1)
{
n2=n1; n仁HT[k].weight;
s2=s1; s1=k;
}
else
if(HT[k].weight< n2)
{
n 2=HT[k].weight;
s2=k;
}
}
}
}
void Huffma nCodi ng(Huffma nTree &H T,Huffma nCode & HC,i nt n)// 空树中
{
ifstream fin 1("");
ifstream fin 2("");
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];
中选择pare nt不为0 将要编码的字符串存入
for(i=1;i<=n;i++)〃将待编码的字符放在zifu数组中
weight和weight的区别{
char ch;
ch=();
zifu[i]=ch;
}
for(i=1;i<=n;i++)〃将带编码字符对应的权值放在weight数组中
{
fin 2>>weigh t[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].pare nt=HT[i].lchild=HT[i].rchild=O;
}
for(i=n+1;i<=m;++i)
{
int s1,s2;
Select(HT,i-1,s1,s2);
HT[s1].pare nt=i; HT[s2].pare nt=i;
HT[i].lchild=s1; HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
HC=(Huffma nCode)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!=O;c=f,f=HT[f].parent) // 从叶子到根逆向求编码
{
if(HT[f].lchild==c)
cd[--start]='0'; //若是左孩子编为’O'
else
cd[--start]='1： //若是右孩子编为'1'
}
HC[i]=(char *)malloc((n-start)*sizeof(char)); // 为第 i 个编码分配空间
strcpy(HC[i],&cd[start]); } delete []cd; //释放工作空间
}
void prin tHuffma nTree(Huffma nTree HT,i nt n) { ofstream fout("");
cout<<"NUM"<<"
"<<"data"<<"
"<<"lchild"<<" "<<"rchlid"<<e ndl;
for(i nt i=1;i<=2* n-1;i++) {
fout<<HT[i].weight<<setw(3)<<HT[i].pare nt<<setw (3) <<HT[i].lchild<<setw(3)<<HT[i]. rchild<<e ndl;
cout<<i<<setw(5)<<HT[i].data<<setw(3)<<HT[i].weight<<setw (3) <<HT[i].pare nt<<set w(3)<<HT[i].lchild<<setw (3) <<HT[i].rchild<<e ndl;
} }
void printHuffmanCoding(HuffmanTree HT,HuffmanCode HC,int n)〃输出字符的对应哈弗
曼编码并存入 文件 {
cout<<"Huffma n code is:"<<e ndl; ofstream fout(""); for(i nt i=1;i<=n ;i++) {
cout<<HT[i].data<<"--> "; cout<<(HC[i])<<e ndl; fout<<(HC[i])<<e ndl; } }
void code_file(HuffmanTree HT,HuffmanCode HC,int n)// 对文件 进行编码，并 将编码存入codefile 文件中 {
ifstream fin ("tobetra n. txt"); ofstream fout(""); vector<char> a; char ch;
while((ch=())!='*')
a.push_back(ch);
cout<<"待编码的字符串为：”；
//显示有n 个叶子结点的哈夫曼树的编码表 〃将对应字符的的哈弗曼树存入
"<<"weight"<<"
"<<"pare
nt"<<"
for(i nt k=O;k<a.size();k++)
cout<<a[k];
cout<<e ndl;
cout<<"\n 编码结果:"<<endl;
for(i nt i=0;i<a.size();i++)
{
for(i nt j=1;j<=n ;j++)
{
if(a[i]==HT[j].data)
{
fout<<HC[j]; break;
}
}
}
fin. close();
fout.close();
}
void Decodi ng(Huffma nTree HT,Huffma nCode HC,i nt n)〃进
打开codefile文件并对文件内容行译码
{
int const m=2* n-1;
ifstream fin ("");
ofstream fout(""); vector<char> a;
for(char c;fi n> >c;)
a.push_back(c);
int coun t=0;
for(i nt k=0;k<a.size();k++)
{
cout<<a[k];
coun t++;
if(cou nt%50==0)
cout<<e ndl;
}
int i=0;
int p; //用p来记住m的值
cout<<e ndl;
cout<<"\n 译码结果："<<endl;
while(i<a.size())
{
p=m; //从哈弗曼数的根开始遍历
while(HT[p].lchild)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。