数据结构（C++版）哈弗曼 编码

Question

问题描述：利用哈夫曼编码进行信息通讯可以大大提高信道的利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传输数据预先编码；在接受端将传来的数据进行译码。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站编写一个哈夫曼码编码/译码系统。
基本要求：根据某字符文件统计字符出现频度，构造Huffman 树，编制Huffman编码，并将给定字符文件编码，生成编码文件；再将给定编码文件解码，生成字符文件（要求按二进制位表示编码）。
提高要求：改进Huffman编码，产生两种以上的编码方案，对同一组测试数据，用不同的编码方案编码，并从文件长度、算法复杂度等方面进行比较分析。
测试数据：找一个英文文档文件或中文文档文件。
用C++来编写，能实现基本要求和提高要求的。

Answer 1

#include
using namespace std;
HuffmanTree::HuffmanTree() //初始化空树
{
Node=NULL; //将树结点初始化为空
Info=NULL; //将字符数组初始化为空
LeafNum=0; //将叶子数初始化为0
}
HuffmanTree::~HuffmanTree() //析构函数
{
delete[] Node; //释放结点空间
delete[] Info; //释放字符存储空间
}
/////////////////////////////////////////
//初始化函数
void HuffmanTree::Initialization(int WeightNum)

{
int i,j,pos1,pos2,max1,max2;
Node=new HuffmanNode[2*WeightNum-1]; //为哈夫曼树所需的结点申请空间

Info=new char[2*WeightNum-1];
for(i=0;i {
cout cin>>Info[i];
cout<<"请输入该字符的权值或频度";
cin>>Node[i].weight; //输入权值
Node[i].parent=-1; //为根结点
Node[i].lchild=-1; //无左孩子
Node[i].rchild=-1; //无右孩子
}
//这里构造出weightnum个带权结点

for(i=WeightNum;i {
pos1=-1;
pos2=-1; //分别用来存放当前最小值和次小值的所在单元编号
max1=32767; //32767为整型数的最大值
max2=32767;
for(j=0;j if(Node[j].parent==-1)
if(Node[j].weight {
max2=max1; //原最小值变为次小值
max1=Node[j].weight; //存放最小值
pos2=pos1; //修改次小值所在单元编号
pos1=j; //修改最小值所在单元编号
}
else
if(Node[j].weight {
max2=Node[j].weight; //存放次小值
pos2=j; //修改次小值所在的单元编号
}
Node[pos1].parent=i; //修改父亲位置
Node[pos2].parent=i;
Node[i].lchild=pos1; //修改儿子位置
Node[i].rchild=pos2;
Node[i].parent=-1; //表示新结点应该是根结点
Node[i].weight=Node[pos1].weight+Node[pos2].weight;
}
LeafNum=WeightNum;
char ch;
cout cin>>ch;
if(ch=='y'||ch=='Y')
{
ofstream fop; //以二进制方式打开hfmTree.dat文件，并当重新运行时覆盖原文件
fop.open("hfmTree.dat",ios::out|ios::binary|ios::trunc);
if(fop.fail()) //文件打开失败
cout<<"文件打开失败！\n";
fop.write((char*)&WeightNum,sizeof(WeightNum)); //写入WeightNum
for(i=0;i {
fop.write((char*)&Info[i],sizeof(Info[i]));
flush(cout);
}
for(i=0;i {
fop.write((char*)&Node[i],sizeof(Node[i]));
flush(cout);
}
fop.close(); //关闭文件
}
cout }
//编码函数
void HuffmanTree::Encoder()
{
if(Node==NULL)
{
ifstream fip;
fip.open("hfmTree.dat",ios::binary|ios::in); //以二进制方式打开hfmTree.dat文件
if(fip.fail()) //文件打开失败
{
cout return; //结束本函数
}
fip.read((char*)&LeafNum,sizeof(LeafNum)); //读取叶子数
Info=new char[LeafNum];
Node=new HuffmanNode[2*LeafNum-1];
for(int i=0;i fip.read((char*)&Info[i],sizeof(Info[i]));
for(int i=0;i fip.read((char*)&Node[i],sizeof(Node[i]));
}
char *Tree; //用于存储需编码内容
int i=0,num;
char Choose;
cout cin>>Choose;
if(Choose=='1') //读取文件ToBeTran.txt
{
ifstream fip1("ToBeTran.txt");
if(fip1.fail()) //文件不存在
{
cout<<"文件打开失败!\n";
return; //结束本函数
}
char ch;
int k=0;
while(fip1.get(ch))

{
k++;

}
fip1.close();

Tree=new char[k+1];
ifstream fip2("ToBeTran.txt");
k=0;
while(fip2.get(ch))
{
Tree[k]=ch; //读取文件内容，并存到Tree中
k++;
}
fip2.close();
Tree[k]='\0'; //结束标志
cout<<"需编码内容为:";
cout<<Tree<<endl;
} //if(Choose=='2')
else

{
string tree;

cin.ignore();
cout<<"请输入需要编码的内容(可输入任意长，结束时请按2下回车):\n";
getline(cin,tree,'\n'); //输入任意长字符串，

while(tree[i]!='\0')
i++;
num=i; //计算tree长度
i=0;
Tree=new char[num+1];
while(tree[i]!='\0') //将tree中的字符转存到Tree中
{
Tree[i]=tree[i];
i++;
}
Tree[i]='\0'; //结束标志符
}
ofstream fop("CodeFile.dat",ios::trunc);

i=0;
int k=0;
char *code;
code=new char[LeafNum]; //为所产生编码分配容量为LeafNum的存储空间

while(Tree[k]!='\0') //对每一个字符编码
{
int j,start=0;
for(i=0;i<LeafNum;i++)
if(Info[i]==Tree[k])

break;
j=i;
while(Node[j].parent!=-1) //结点j非树根
{
j=Node[j].parent; //求结点j的双亲结点
if(Node[j].lchild==i) //是左子树，则生成代码0
code[start++]='0';
else

code[start++]='1'; //是右子树，则生成代码1
i=j;
}
code[start]='\0'; //置串结束符

for(i=0;i<start/2;i++) //对二进制序列进行逆置
{
j=code[i];
code[i]=code[start-i-1];
code[start-i-1]=j;
}
i=0;
while(code[i]!='\0') //存储代码
{
fop<<code[i];
i++;
}
k++;
}
fop.close();
cout<<"编码完成！且存到文件CodeFile.dat中！\n\n";
}

/////////////////////////////////////////////////////////////////////////////
//解码函数

void HuffmanTree::Decoder()
{
int i=0,k=0;
int j=LeafNum*2-1-1;

char* BitStr;

ifstream fip1("CodeFile.dat"); //利用已建好的哈夫曼树将文件CodeFile中的代码进行译码
if(fip1.fail())

{
cout<< "请先编码！\n";
return;
}
cout<<"经译码,原内容为:";
char ch;
while(fip1.get(ch))

{
k++;

}
fip1.close();

BitStr=new char[k+1];
ifstream fip2("CodeFile.dat");
k=0;
while(fip2.get(ch))
{
BitStr[k]=ch; //读取文件内容
k++;
}
fip2.close();

BitStr[k]='\0'; //结束标志符
if(Node==NULL) //还未建哈夫曼树
{
cout<<"请先编码!\n";
return;
}
ofstream fop("TextFile.dat"); //将字符形式的编码文件写入文件CodePrin中
while(BitStr[i]!='\0')
{
if(BitStr[i]=='0')
j=Node[j].lchild; //往左走
else
j=Node[j].rchild; //往右走
if(Node[j].rchild==-1) //到达叶子结点
{
cout<<Info[j]; //输出叶子结点对应的字符
j=LeafNum*2-1-1;

fop<<Info[j]; //存入文件
}

i++;
}
fop.close();
cout<<"\n译码成功且已存到文件TextFile.dat中！\n\n";
}

//////////////////////////////////////////////////////////////////////////////////////////
//输出编码函数

void HuffmanTree::Print()
{
char ch;
int i=1;
ifstream fip("CodeFile.dat");

ofstream fop("CodePrin.dat");

if(fip.fail())
{
cout<<"没有文件，请先编码！\n";
return;
}
while(fip.get(ch))
{
cout<<ch; //读取文件内容
fop<<ch; //存到文件中
if(i==50)

{
cout<<endl;
i=0;
}
i++;
}
cout<<endl;
fip.close(); //关闭CodeFile.dat文件
fop.close(); //关闭CodePrin.dat文件

}
//输出哈夫曼树

void HuffmanTree::TreePrinting()
{
if(Node==NULL)

{
cout<<"请先建立哈夫曼树！\n";
return;
}
ofstream fop("TreePrint.dat");
cout<<"结点位置(权值) "<<"编码 "<<"左孩子 "<<"编码"<<"右孩子('^'表示叶子)\n";
fop<<"结点位置(权值) "<<"编码 "<<"左孩子 "<<"编码"<<"右孩子('^'表示叶子)\n";
int i;
for(i=(2*LeafNum-2);i>LeafNum-1;i--)

{
cout< fop }
for(;i>=0;i--)
{
cout<<i<<":"<<Node[i].weight<<"("<<Info[i]<<")---^\n";
fop<<i<<":"<<Node[i].weight<<"("<<Info[i]<<")---^\n";
}
}