#include<iostream>
#include<cstring>
using namespace std;
//哈夫曼树的存储表示
typedef char ElemType;
typedef struct
{
ElemType data; //结点存的数据
int weight; //结点的权值
int parent,lchild,rchild; //结点的双亲、左孩子、右孩子的下标
} HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树
void Select(HuffmanTree HT,int n,int &s1,int &s2);
//构造哈夫曼树
/*算法步骤：
1.初始化：首先动态申请2n个单元，然后循环2n-1次，从1号单元开始，依次将1至2n-1所有单元中的双亲、左孩子、右孩子
的下标都初始化为0；最后再循环n次，输入前n个单元中叶子节点的权值
2.创建树：循环n-1次，通过n-1次的选择、删除与合并来创建哈夫曼树。
选择是从当前森林中选择双亲为0且权值最小的两个树根结点s1和s2；
删除是指将结点s1和s2的双亲改为非0；合并就是将s1和s2的权值和作为一个新结点的权值依次存入到数组的第n+1之后的单元中，
同时记录这个新结点左孩子的下标为s1，右孩子的下标为s2*/
void CreateHuffmanTree(HuffmanTree &HT,int n)
{
//构造哈夫曼树HT
if(n<=1)
{
cout<<"HuffmanTree节点数输入错误！"<<endl;
return;
}
int m=2*n-1;
int s1=1,s2=1;
HT=new HTNode[m+1]; //0号单元未用，所以需要动态分配m+1个单元，HT[m]表示根结点
for(int i=1; i<=m; ++i) //将1~m号单元中的双亲、左孩子、右孩子的下标都初始化为0
{
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for(int i=1; i<=n; ++i) //输入前n个单元中叶子结点的权值（包括空格）
{
cout<<"请输入第"<<i<<"个叶子结点的数据（字符）："<<endl;
char c;//用来保存之前键入的回车键
c=cin.get();
HT[i].data=cin.get();
cout<<"请输入第"<<i<<"个叶子结点的权值："<<endl;
cin>>HT[i].weight;
}
//--------------------------初始化工作结束，下面开始创建完整哈夫曼树
for(int i=n+1; i<=m; ++i)
{
//通过n-1次的选择、删除、合并来创建哈夫曼树
Select(HT,i-1,s1,s2); //在HT[k](1<=k<=i-1)中选择两个其双亲域为0且权值最小的结点，并返回它们在HT中的序号s1和s2
HT[s1].parent=i;
HT[s2].parent=i; //得到新结点i，从森林中删除s1，s2，将s1和s2的双亲域由0改为i
HT[i].lchild=s1;
HT[i].rchild=s2; //s1，s2分别作为i的左右孩子
HT[i].weight=HT[s1].weight+HT[s2].weight; //i的权值为左右孩子权值之和
}
}
//在HT中选择两个其双亲域为0且权值最小的结点，返回它们在HT中的序号s1和s2
void Select(HuffmanTree HT,int n,int &s1,int &s2)
{
int i=1;//开始初始化wetmin1,wetmin2，使用一个i往后找，HT[i].parent==0的结点
int temp;
int wetmin1,wetmin2;
//开始寻找前两个HT[i].parent==0的结点，给wetmin1,wetmin2初始化
while(HT[i].parent!=0)
i++;
wetmin1=HT[i].weight;
s1=i;
i++;
while(HT[i].parent!=0)
i++;
wetmin2=HT[i].weight;
s2=i;
i++;//从初始值后面的结点开始遍历
//初始化wetmin1,wetmin2，将小的赋值给wetmin1
if(wetmin1>wetmin2)
{
temp=wetmin2;
wetmin2=wetmin1;
wetmin1=temp;
temp=s2;
s2=s1;
s1=temp;
}
for(i; i<=n; i++)
{
if(HT[i].parent==0&&HT[i].weight<wetmin1)
{
wetmin2=wetmin1;
wetmin1=HT[i].weight;
s2=s1;
s1=i;
}
else if(HT[i].parent==0&&HT[i].weight<wetmin2)
{
wetmin2=HT[i].weight;
s2=i;
}
}
}
//哈夫曼编码表的的存储表示
typedef char **HuffmanCode;//动态分配数组存储哈夫曼编码表
//根据哈夫曼树求哈夫曼编码
void CreateHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int &n)
{
//从叶子到根逆向求每个字符的哈夫曼编码，存储在编码表HC中
HC=new char*[n+1]; //分配存储n个字符编码的编码表动态空间
char *cd=new char[n]; //分配临时存放每个字符编码的动态数组空间
cd[n-1]='\0'; //（末尾）编码结束符
for(int i=1; i<=n; i++) //逐个字符求哈夫曼编码
{
int start=n-1; //start开始时指向最后，即编码结束符位置
int c=i,f=HT[i].parent;//f指向结点c的双亲结点
while(f!=0) //从叶子结点开始向上回溯，直到根结点
{
--start;
if(HT[f].lchild==c) cd[start]='0';//结点c是f的左孩子，则生成代码0
else cd[start]='1'; //结点c是f的右孩子，则生成代码1
c=f;
f=HT[f].parent; //继续向上回溯
} //求出第i个字符的编码（结点为c，双亲为f；之后结点为f，双亲为HT[f].parent）
HC[i]=new char[n-start]; //为第i个字符编码分配空间
strcpy(HC[i],&cd[start]); //将求得的编码从临时空间cd复制到HC的当前行中（导入：#include<cstring>）
} //for
delete cd; //释放临时空间
}
//替换所有子串
string subreplace(string resource_str, string sub_str, string new_str)
{
string::size_type pos = 0;
while((pos = resource_str.find(sub_str)) != string::npos) //替换所有指定子串
{
resource_str.replace(pos, sub_str.length(), new_str);
}
return resource_str;
}
//解码
void decode(string s,HuffmanTree HT,int n)
{
int p=2*n-1;
int lens=s.size();
for(int i=0; i<lens; i++)
{
//对编码一位一位进行查找，找到对应的叶节点为止
if(s[i]=='0')
{
if(HT[p].lchild!=0)
{
p=HT[p].lchild;
}
}
else if(s[i]=='1')
{
if(HT[p].rchild!=0)
{
p=HT[p].rchild;
}
}
if(HT[p].rchild==0&&HT[p].lchild==0)
{
//如果是叶子结点，输出，然后让p重新指向数顶，开始新一轮寻找
cout<<HT[p].data;
p=2*n-1;
}
}
cout<<endl;
}
//菜单
void Menu()
{
cout<<"\n**************************************************"<<endl;
cout<<"1.输入HuffmanTree的参数.******"<<endl;
cout<<"2.初始化HuffmanTree参数.******"<<endl;
cout<<"3.创建HuffmanTree和编码表.*****"<<endl;
cout<<"4.输出编码表.******************"<<endl;
cout<<"5.输入编码，并翻译为字符.*****"<<endl;
cout<<"6.输入字符，并实现转码.********"<<endl;
cout<<"7.退出.************************"<<endl;
cout<<"**************************************************"<<endl;
cout<<"请输入选择：";
}
int main()
{
Menu();
HuffmanTree HT=NULL;
HuffmanCode HC=NULL;
int choose,n;
char c;//用来保存之前键入的回车键
cin>>choose;
while(choose!=7)
{
switch(choose)
{
case 1:
case 2:
cout<<"请输入结点的个数：";
cin>>n;
CreateHuffmanTree(HT,n);
if(n>1)
{
cout<<"HuffmanTree初始化完成！"<<endl;
}
break;
case 3:
if(HT==NULL)
{
cout<<"请先创建HuffmanTree！"<<endl;
}
else
{
CreateHuffmanCode(HT,HC,
