hf.cpp

哈夫曼数的编码

#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'));
}