#include<ctype.h>
#include<iostream.h>
int num10=0;
struct node {
int data;
int parent;
int lchild;
int rchild;
};
int found(node ht[]){
int quan[30];
int quandata=-1;
int count;
int i,j=0,k,l=0,m;
for(i=0;i<30;i++)
{
quan[i]=-1;
}
cout<<"-----本程序是解决哈夫曼编码,译码,和树的打印的程序----"<<endl;
cout<<"---------请输入权值,以零为结束符-----------"<<endl;
do{
cin>>quandata;
if(quandata!=0)
{
quan[j]=quandata;
j++;
}
}while(quandata!=0);
for(k=0;k<32;k++)
{
ht[k].parent=0;
ht[k].lchild=0;
ht[k].rchild=0;
ht[k].data=-1;
}
do{
if(quan[l]!=-1)
{
ht[l].data=quan[l];
l++;
}
}while(quan[l]!=-1);
count=l;
for( m=count;m<2*count-1;m++)
{
int s1,s2;
int num1,num2;
s1=s2=65535;
for(int n=0;n<m;n++)
{
if((ht[n].data<s1)&&(ht[n].parent==0))
{
s1=ht[n].data;
num1=n;
}
}
ht[num1].parent=m;
for(n=0;n<m;n++)
{
if((ht[n].data<s2)&&(ht[n].parent==0))
{
s2=ht[n].data;
num2=n;
}
}
ht[num2].parent=m;
ht[m].data=s1+s2;
ht[m].lchild=num1;
ht[m].rchild=num2;
}
return count;
}
//编码
void edit(node ht[],int count2)
{
for(int i1=0;i1<count2;i1++)
{
int start=count2;
int c=i1;
int f=ht[c].parent;
int code[10];
for(int t=0;t<10;t++)
{
code[t]=-1;
}
do
{
if(ht[f].lchild==c)
{
code[start]=0;
}
else {
code[start]=1;
}
start=start-1;
c=f;
f=ht[c].parent;
}while(f!=0);
cout<<ht[i1].data<<":";
for(int u=0;u<=count2;u++)
{
if(code[u]!=-1)
{
cout<<code[u]<<" ";
}
}
cout<<endl;
}
}
//译码
int traslate(node ht[])
{
int count1[100];
int p,q=0;
int num3,num4,num5;
cout<<"请输入要译的二进制代码!"<<endl;
cout<<"每两个0,1之间请以空格或回车隔开,以-1为结束符!(<100位)"<<endl;
do
{
cin>>num5;
if((num5!=0)&&(num5!=1)&&(num5!=-1))
{
cout<<"输入错误,请重新输入"<<endl;
}
count1[q]=num5;
q++;
}while(count1[q-1]!=-1);
num3=num4=0;
for(int z=0;z<32;z++)
{
if(ht[z].data>num3)
{
num3=ht[z].data;
num4=z;
}
}
p=num4;
cout<<"译码后为:"<<endl;
for(int x=0;x<100;x++)
{
if((ht[p].lchild==0)&&(ht[p].rchild==0))
{
cout<<ht[p].data<<" ";
}
else
{
if(count1[x]==0)
{
p=ht[p].lchild;
if((ht[p].lchild==0)&&(ht[p].rchild==0))
{
cout<<ht[p].data<<" ";
p=num4;
}
}
else
{
if(count1[x]==1)
{
p=ht[p].rchild;
if((ht[p].lchild==0)&&(ht[p].rchild==0))
{
cout<<ht[p].data<<" ";
p=num4;
}
}
}
}
}
cout<<"\n";
cout<<"这是打印后的哈夫曼树"<<endl;
return num4;
}
//计算空格数目,以完成打印输出;
void indentblanks(int num7)
{
for(int d=0;d<num7;d++)
cout<<" ";
}
//打印程序,这里用到了递归的算法;
//参数分别是最大的跟的结点数组表示的下标,
//数组的头结点,要打的层次数目;
void print(int num9,int num6,node ht[],int level)
{//cout<<num6<<endl;
//cin>>num10;
if(num6<=num9&&num6>0)
{
print( num9,ht[num6].rchild,ht,level+1);
indentblanks(6*(level-1));
if((ht[num6].lchild!=0)||(ht[num6].rchild!=0))
cout<<ht[num6].data<<"根"<<endl;
else
cout<<ht[num6].data<<endl;
print(num9,ht[num6].lchild,ht,level+1);
}
}
void main()
{
int first1,first2;
char y;
node ht1[32];
int number;
do
{
number=found(ht1);
cout<<"编码后的结果为:"<<endl;
edit(ht1,number);
first1=first2=traslate(ht1);
print(first1,first2,ht1,4);
cout<<"继续么?(输入y/Y)"<<endl;
cin>>y;
}while((y=='y')||(y=='Y'));
}