#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";
  	 
	}
}