哈夫曼树最优搜索算法.cpp

哈夫曼树最优搜索算法。欢迎使用haffman编/译码程序

#include<iostream.h>
#include<malloc.h>
#include<string.h>
#include<iomanip.h>


struct htnode
{
    char data;
 int weight;
 int parent;
 int lchild;
 int rchild;
}*ht,*p; 

   int s1,s2,t,n;
   char**hc,*ch,get='0';

 void selete(htnode*hc,int k,int*s1,int*s2); 

 void Encoding();
 void printcode();
 char q();
 void Init();
 void Decoding();
 void Printtree();
 

 void  main() //*************************************************************主函数
 {                       
    cout<<"\n                        欢迎使用haffman编/译码程序\n\n";
    cout<<"               本程序是对报文进行---①编码  ②译码 ③ 打印等 \n\n";
    cout<<"             请根据需要(选择性) 操作   (注意：若未初始化则会出错)\n\n";
    cout<<"                   程序制作者:   陆建军  陆重道  陆振海  \n\n";
	cout<<"                   ************让我们开始吧!!**********\n\n";
    cout<<"   ";
	int i; 
    for(i=1;i<=37;i++)  cout<<"* ";    
	cout<<"\n   *   初始化:1   编码:2  译码:3   打印代码:4 ";
    cout<<"打印树存储结构：5  退出:6   *\n";cout<<"   ";
	for(i=38;i>1;i--)	cout<<"* ";  
	 
      loop1:  
      get=q();   
      loop2:
      cin>>get;   
	  switch(get){
    case'1':{	Init();         goto loop1;  }  
	case'2':{   Encoding();     goto loop1;  }
	case'3':{   Decoding();     goto loop1;  }
    case'4':{	printcode();    goto loop1;  }
	case'5':{   Printtree();    goto loop1;  }
	case'6':{   cout<<setw(40)<<"\n您已经退出该程序*********";
				cout<<"谢谢使用本程序!!!\n\n\n\n\n"; break;  } 
    default:{   cout<<setw(30)<<"\n对不起您选择出错!!!\n\n\n";
		        cout<<"请再选择:  ";    goto loop2;  } } 	 
 }

char q()  //********************************************************菜单
{cout<<"\n\n\n请选择:  ";	return 0;}

void selete(htnode*hc,int k,int*s1,int*s2)//**************寻找两个小权值
{
	    signed long m1=1000,m2=1000;
		for(int j=1;j<=k;j++)
		{
			if(hc[j].weight<m1&&hc[j].parent==0)
			{
				m2=m1;
				*s2=*s1;
				m1=hc[j].weight;
				*s1=j;
			}
			else if(hc[j].weight<m2&&hc[j].parent==0)
			{
				m2=hc[j].weight;
				*s2=j;
			}
		}
}


void Init()        //******************************************初始化函数
{	int m=0;      
	int*weit;        
	char*a,*cd;
	 
	cout<<"\n\n请输入叶子结点的 总个数n:   ";
	cin>>n;  
	weit=(int*)malloc((n+1)*sizeof(int)); 
	a=(char*)malloc((n+1)*sizeof(char)); 
	
	cout<<"\n请输入报文串:";
	cout<<"(形如：You_are_good ....   ( 空格用  \" _ \"  代替 )    [回车]  ";
	cout<<"\n\n***********报文串为:";
	for(int i=1;i<=n;i++) 
	{
		cin>>a[i]; 
	}

	cout<<"\n\n请输入n个权值:";
	cout<<"(形如：14 52 70 ...      ( 各权值间用(空格)隔开 )    [回车]";
    cout<<"\n\n\n*****对应的权植序列:";
	for( i=1;i<=n;i++)  
	{
		cin>>weit[i]; 
	}

	
	m=2*n-1;                          
	if((ht=new htnode[m+1])==NULL)
	{
		cout<<"分配内存失败!!\n";
	}
	for(i=1,p=ht,++p;i<=n;++i,++p)
	{
		p->data=a[i];   
		p->weight=weit[i];
		p->parent=0;
		p->lchild=0;
		p->rchild=0;	}
	for(i=n;i<=m;++i,++p)
	{
		p->data=NULL;   
		p->weight=0;
		p->parent=0; 
		p->lchild=0;
		p->rchild=0;
	}
	for(i=n+1;i<=m;++i)
	{
		selete(ht,i-1,&s1,&s2);    
		ht[s1].parent=i;      
		ht[s2].parent=i;
		if(s1<s2)
		{
			ht[i].lchild=s1;	
			ht[i].rchild=s2;
		}
		else
		{
			ht[i].lchild=s2; 
			ht[i].rchild=s1;}
		ht[i].weight=ht[s1].weight+ht[s2].weight;
	}
    if((hc=(char**)malloc((n+1)*sizeof(char)))==NULL )
	{
		cout<<"分配内存失败\n";	
	}
	if((cd=(char*)malloc((n)*sizeof(char)))==NULL) 
	{
		cout<<"分配内存失败\n";	
	}
	
	cd[n-1]='\0'; 
	for(i=1;i<=n;++i)   
	{	
		int start=n-1;    
		for(long c=i,f=ht[i].parent;f!=0;c=f,f=ht[f].parent)
		{
			if(ht[f].lchild==c) 
				cd[--start]='0';
			else 
				cd[--start]='1';
		}

		if((hc[i]=(char*)malloc((n-start)*sizeof(char)))==NULL)
		{
			cout<<"内存分配失败\n";
		}
		strcpy(hc[i],&cd[start]);   
	}
	free(cd);
    cout<<"\n\n初始化 OK 了!********请进行其它操作!!!";
}



void Encoding()     //**************************************************编码
{
	if(ht==NULL)  
	{
	cout<<endl;
	cout<<setw(59)<<"对不起您还没有：没有初始化****      请重新选择\n\n";
		return;
	}
	else{

		int i=1,j=0;	
          char  ch[128];               
	      cout<<"请输入上面报文串: ";
		  cin>>ch;
		 
		  cout<<"\n字符串 "<<ch<<" 的编码为:  ";
		  do{
			  for(i=1;ch[j]!=ht[i].data;i++);
			  {
				  cout<<hc[i]<<" "; 
			  if(i%15==0)cout<<"                               \n\n\n";}
		  j++;
		  }while(ch[j]!='\0');            
		}
}
void Decoding() //*************************************************************译码
{
	if(ht==NULL)cout<<setw(59)<<"对不起您还没有：没有初始化*****  请重新选择\n\n";
	else{
	int m=0;
	char de[200];
	cout<<"输入编码串:";
	cin>>de;
      cout<<"\n\n编码串"<<de<<" 对应的字符为：\n\n     ";
	do{
		int i=2*n-1;       
		for(;ht[i].lchild!=0 ;m++)  
		{
			if(de[m]=='0')         
			{ i=ht[i].lchild;}
			else  {i=ht[i].rchild;}
		}
		cout<<ht[i].data<<"  ";
	}while(de[m]!='\0');     
	cout<<"\n\n";
	}
}
void  printcode() // **************************************************打印报文代码
{

	int i;
	if(ht==NULL){
		cout<<setw(59)<<"对不起您还没有：初始化*****        请重新选择\n\n";
	}
	else{
		cout<<"\n\n编码文件打印结果为：\n\n";
	for(i=1;i<=n;++i)
	{cout<<setw(10)<<i<<setw(7)<<ht[i].data<<"       "<<hc[i];cout<<"\n\n";}
    cout<<"\n\n";
	return;
	}
}

void Printtree()    //****************************************************打印树的结构图
{ 
	if(ht==NULL)cout<<setw(59)<<"对不起您还没有：没有初始化*****    请重新选择\n\n";
	else{int i;      
		cout<<"\n\n         *****打印******哈夫曼树***存储结构******图表****** \n\n";   
		cout<<"  number"<<"       data   "<<"   weight";
		cout<<"      parent"<<"     lchilde"<<"     rchlide\n";

		for(i=1;i<=2*n-1;i++)   
		{cout<<setw(6)<<i<<setw(12)<<ht[i].data<<setw(10)<<ht[i].weight<<setw(12);
		 cout<<ht[i].parent<<setw(12)<<ht[i].lchild<<setw(12)<<ht[i].rchild<<"\n\n"; }

	   	cout<<"\n\n\n\n";
  	 
	}
}