#include<iostream>
#include<string.h>
#include<memory.h>
#include<malloc.h>
using namespace std;
#define M 100
char ch[100]; //输?入?的?字?符?串? char s[100]; //保馈?存?出?现?的?字?符? int b[1000]; //统?计?对?应畖的?字?符?的?个?数簓
typedef struct
{
char ch;
int weight;
int parent,left,right; //双?亲×，?左哩??孩(子哩?
char s;
}TNode,*huffmanTree; typedef struct //字?符?的?信?息( {
char ch;
int weight;
}Tdata;
void fun(huffmanTree H,int n,int &s1,int &s2) //寻?找ò最?小?的?两?个?子哩?树骸?
{
int min1,min2;
s1=s2;
min1=min2=1000000;
for(int i=0;i<=n;i++)
{
if(H[i].parent==0)
{
if(H[i].weight<min1)
{
min2=min1;min1=H[i].weight;
s2=s1;
s1=i;
}
else
{
if(min2>H[i].weight)
{
min2=H[i].weight;
s2=i;
}
}
}
}
}
void count(char ch[],char s[],int b[],int &k,Tdata data[]) //字?符?统?计?
{
cout<<"输?入?字?符?串?，?并(进?行D字?符?统?计?:";
cin>>ch;
for(int i=0;i<strlen(ch);i++)
{
int flat=1;
for(int j=0;j<k;j++)
{
if(ch[i]==s[j])
{
b[j]++;flat=0;
break;
}
}
if(flat)
{b[k++]=1;s[i]=ch[i];}
}
for(int i=0;i<k;i++)
{
cout<<s[i]<<"------->"<<b[i]<<endl;
}
for(int i=0;i<k;i++)
{
data[i].ch=s[i];
data[i].weight=b[i];
}
}
void huffmancoding(huffmanTree &H,Tdata data[],int n) //编括?码?
{
int m=2*n-1;
TNode *p;
int i;
int s1,s2;
H=(huffmanTree)malloc((m+1)*sizeof(TNode));
for(p=H,i=0;i<n;i++,p++)
{
p->ch=data[i].ch;
p->weight=data[i].weight;
p->parent=0;
p->left=0;
p->right=0;
}
for(;i<m;i++,p++)
{
p->weight=0;
p->left=0;
p->right=0;
p->parent=0;
}
for(i=n;i<m;i++)
{
fun(H,i-1,s1,s2);
if(H[s1].weight<=H[s2].weight)
{
H[s1].parent=i;H[s2].parent=i;
H[i].left=s1;H[i].right=s2;
H[s1].s='0';H[s2].s='1';
H[i].weight=H[s1].weight+H[s2].weight;
}
else
{
H[s1].parent=i;H[s2].parent=i;
H[i].left=s2;H[i].right=s1;
H[s2].s='0';H[s1].s='1';
H[i].weight=H[s1].weight+H[s2].weight;
}
}
for(int i=0;i<n;i++)
{
char ch[100];
int k=0;
int c=i;int f=H[i].parent;
while(f!=0)
{
ch[k++]=H[c].s;
c=f;f=H[f].parent;
}
cout<<data[i].ch<<" ";
while(--k>=0)
cout<<ch[k];
cout<<endl;
}
}
void translation(huffmanTree H,int n) {
int m=2*n-2;
char ch[100];
cin>>ch;
int a=0;
while(a<strlen(ch))
{
if(H[m].right==0&&H[m].left==0)
{
cout<<H[m].ch;
m=2*n-2;
}
else if((H[H[m].right].s!=ch[a])&&(H[H[m].left].s!=ch[a]))
{
cout<<"无T法ぁ?进?行D翻?译?，?请?确ā?认?是?否?输?入?正y确ā?"<<endl;
break;
}
else if(H[H[m].right].s==ch[a])
{
m=H[m].right;a++;
}
else if(H[H[m].left].s==ch[a])
{
m=H[m].right;a++;
}
}
}
int main()
{
huffmanTree H;
Tdata data[M];
int k=0;
count(ch,s,b,k,data);
huffmancoding(H,data,k);
cout<<endl<<endl;
char s;
do
{
cout<<" 输?入?你?要癮翻?译?的?01字?符?串?:";
translation(H,k);
cout<<" 是?否?继ì续?翻?译??[Y N]:";cin>>s;
}while(s=='Y'||s=='y');
return 0;
}