#include<iostream> //需要用到的头文件
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iomanip>
#include<fstream>
using namespace std;
#define maxleaf 30 //定义最多的叶子结点
#define len 20
typedef struct{ //赫夫曼树的结构体
char ch;
double weight; //权值
int parent;
int lchild;
int rchild;
}hnode,*hfmtree;
typedef hnode huffman[maxleaf*2-1];
huffman h; //定义一个结构数组
int leaves;
typedef struct{ //用于存储哈夫曼编码
int start;
int bit[len];
}hcode;
typedef hcode huffcode[maxleaf];
huffcode code;
//初始化哈夫曼树，参考书本上两个算法，并合并
void Initialization(){
//书本算法1
cout<<"输入节点的个数:"; //输入叶子结点的个数
cin>>leaves;
int i,j;
for(i=0;i<leaves*2-1;i++){ //初始化用于存储哈夫曼树的数组
h[i].ch=0;
h[i].lchild=-1;
h[i].parent=-1;
h[i].rchild=-1;
h[i].weight=0;
}
for(i=0;i<leaves;i++){ //输入结点的字符和权值
cout<<"请输入第"<<i+1<<"个字符和对应的权值(例：a 4)：";
getchar();
h[i].ch=getchar();
cin>>h[i].weight;
}
for(i=0;i<leaves-1;i++){ //生成其他的n-1个非叶子结点
double m1,m2;
int m1_pos,m2_pos; //m1存放最小的权值，m2存放次小的权值
m1=m2=65536;
m1_pos=m2_pos=0; //m1存放最小的权值的对应下标，m2存放次小的权值下标
for(j=0;j<leaves+i;j++){
if(h[j].weight<m1&&h[j].parent==-1){
m2=m1;
m1=h[j].weight;
m2_pos=m1_pos;
m1_pos=j;
}
else if(h[j].weight<m2&&h[j].parent==-1){
m2=h[j].weight;
m2_pos=j;
}
}
h[leaves+i].parent=-1; //生成新根，无双亲
h[leaves+i].lchild=m1_pos; //新根左孩子在数组的下标
h[leaves+i].rchild=m2_pos; //新根右孩子在数组的下标
h[m1_pos].parent=leaves+i; //原根的父亲位置
h[m2_pos].parent=leaves+i; //原根的父亲位置
h[leaves+i].weight=m2+m1;
if(m2==65536)break;
}
//书本算法二
int p,c;
hcode hf; //赫夫曼编码，将每个叶子结点编码
fstream file("hfmTree.txt",ios::out);
for(i=0;i<leaves;i++){
c=i;
p=h[i].parent;
hf.start=len-1;
while(p!=-1){
if(h[p].lchild==c){
hf.bit[hf.start]=0;
}
else{
hf.bit[hf.start]=1;
}
--hf.start;
c=p;
p=h[c].parent;
}
file<<h[i].ch<<"=";
cout<<h[i].ch<<"=";
for(j=hf.start+1;j<len;j++){
code[i].bit[j]=hf.bit[j];
file<<hf.bit[j];
cout<<hf.bit[j];
}file<<endl;cout<<endl;
code[i].start=hf.start+1;
}
file.close();
cout<<endl<<"构建哈夫曼树成功,其内容已保存在hfmTree.txt文件中！！！"<<endl;
system("pause");
}
//输入字符，用于实现哈夫曼编码
void Encoding(){
cout<<"请输入需要编码的字符串：";
char m;
fstream file("CodeFile.txt",ios::out);
getchar();
while((m=getchar())!='\n'){
for(int i=0;i<leaves;i++){ //遍历各个结点
if(m==h[i].ch){
for(int j=code[i].start;j<len;j++) //将对应哈夫曼编码存入文件并显示
file<<code[i].bit[j];
break;
}
}
}
file.close();
cout<<"."<<endl<<"."<<endl<<"."<<endl;
cout<<endl<<"编码成功，结果已存入文件CodeFile.txt文件中！！！"<<endl;
system("pause");
}
//将输入的字符实现译码
void decoding(){
fstream fin("Codefile.txt",ios::in); //读入要译码的文件
fstream fout("Textfile.txt",ios::out); //将代码译码后放入到文件中
int a=0;
char c[500],ch=NULL;
int k=0,m=0,i=0; //将CodeFile.txt文件的编码读入
fin>>c;
for(i=0;i<leaves;i++){
char str[50]="";
char other[20]=""; //用于存储每个叶子结点的编码，便于比较
fstream temp("tem.txt",ios::out); //用于将整形编码转换成字符型，便于比较
for(k=code[i].start;k<len;k++){
temp<<code[i].bit[k];
}
temp.close();
temp.open("tem.txt",ios::in); //用文件实现整型和字符型的转换
temp>>str;
k=len-code[i].start;
for(int a=0;a<k;a++) //将从文件读出的字符赋值给临时数组便于比较
other[a]=c[m+a];
if(!strcmp(str,other)){fout<<h[i].ch; //比较，相同则输入文件Textfile.txt中
cout<<h[i].ch;m=m+k;i=-1;} //相同的话，将i置零，进行下一轮比较
temp.close();
}
fin.close();
fout.close();
remove("tem.txt"); //将临时的文件删除
cout<<endl<<"."<<endl<<"."<<endl<<"."<<endl;
cout<<endl<<"译码成功,结果已存入文件Textfile.txt中！！"<<endl;
system("pause");
}
//选做1：实现印代码文件
void Print(){
fstream fin("CodeFile.txt",ios::in);
fstream fout("Codeprint.txt",ios::out);
char ch;
int sum=0;
cout<<"印代码文件输出如下："<<endl<<endl;
while(fin.get(ch)!=NULL){ //控制输出的字符个数
sum++;
cout<<ch;
fout<<ch;
if(sum%50==0){cout<<endl;fout<<'\n';} //判断输出的个数
}
fin.close();
fout.close();
cout<<endl<<"印代码文件成功，同时此字符形式的编码文件已写入文件CodePrin.txt中！！！"<<endl;
system("pause");
}
fstream fout("TreePrint.txt",ios::out); //建立存储的文件
void TreePrint(int m,int n){ //递归算法实现哈夫曼树的输出
if(h[m].weight==0.0)
{return;}
TreePrint(h[m].rchild,n+1);
for(int i=0;i<n;i++){
printf(" ");
fout<<" ";}
cout<<h[m].weight<<endl;
fout<<h[m].weight<<'\n';
TreePrint(h[m].lchild,n+1);
}
int main(){
while(1){ cout<<endl;
cout<<'\t'<<" ---------------------------------------------------------"<<endl;
cout<<'\t'<<" <<赫夫曼编码/译码器>>"<<endl;
cout<<'\t'<<" 请输入你的选择"<<endl;
cout<<'\t'<<" *********1：建哈夫曼树*********"<<endl;
cout<<'\t'<<" *********2： 编码 *********"<<endl;
cout<<'\t'<<" *********3： 译码 *********"<<endl;
cout<<'\t'<<" *********4：印代码文件*********"<<endl;
cout<<'\t'<<" *********5：印哈夫曼树*********"<<endl;
cout<<'\t'<<" *********6： 退出 *********"<<endl;
cout<<'\t'<<" ---------------------------------------------------------"<<endl;
char choose;
cout<<"你的选择:";
cin>>choose;
switch(choose){ //功能选择
case '1':Initialization();break; //初始化哈夫曼树
case '2':Encoding();break; //哈夫曼编码
case '3':decoding();break; //哈夫曼译码
case '4':Print();break;
//印代码文件
case '5':cout<<"输出的直观哈夫曼树如图："<<endl<<endl; //哈夫曼树的树形输出
TreePrint(2*leaves-2,0);
fout.close();
cout<<endl<<"输出成功，同时将此字符形式的赫夫曼树已写入文件TreePrint.txt中！！！"<<endl;
cout<<endl;
system("pause");break;
case '6':choose='6';break;
//退出
default:cout<<"输入错误，请重新选择！！！"<<endl;
}
if(choose=='6')break; //用于判断结束跳出while循环
}
}
