#include<iostream>
#include<string>
using namespace std;
typedef int * intzhi;
typedef struct
{
	char a;
	int quan;
}Data,*Dzhi;
typedef struct
{
	Data weight;
	int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char** HuffmanCode;
///函數(shù)一查找最小的兩個(gè)數(shù)的序號
void Select(HuffmanTree A,int n,int &a1,int &a2)
{
	int i,t,tt,j,a3;
	for( i=1;i<=n;i++)
	{
		if(A[i].parent!=0) continue;
		else 
		{
			for(int j=i+1;j<=n;j++)
			{
				if(A[j].parent!=0) continue;
				else
				{
					if(A[i].weight.quan<=A[j].weight.quan) t=i;
					else
					{
						t=j;
						break;
					}
				}
			}
			i=j-1;
		}
	}
	a1=t;////找到最小的數(shù)
	/////////
    for(i=1;i<=n;i++)
	if(A[i].parent!=0||i==a1) continue; 
	if(i==n+1) a3=n;//////liumangzuofa

	for(i=1;i<=n;i++)
	{
		if(A[i].parent!=0||i==a1) continue;   
	
	    else 		
		{
			    for( j=i+1;j<=n;j++)
				{
					if(A[j].parent!=0||j==a1) continue;
					else
					{
						if(A[i].weight.quan<=A[j].weight.quan) tt=i;
						else	
						{
							tt=j;	
						    break;
						}
					}
				
				}
				i=j-1;
		}
    
		
	}
     a2=tt;
	 if(a2<0)
	 a2=a3;
      
	
}
			

//函數(shù)二編碼函數(shù)
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,Dzhi w,int n)
{
	if(n<=1) return;
	int m=2*n-1;
  	HT=new HTNode[m+1];
	HuffmanTree p;
	int i,s1=0,s2=0;
	for(p=HT+1, i=1;i<=n;++i,++p,++w) ///0號單元未用
	{
		p->weight.a =w->a ;
        p->weight.quan =w->quan ;
		p->lchild =0;
		p->parent =0;
		p->rchild =0;
	}
	for(i=n+1;i<=m;++i,++p) 
	{
	p->lchild =0;
		p->parent =0;
		p->rchild =0;
		
	}
	for(i=n+1;i<=m;++i) ///建立哈服滿樹

	{
		Select (HT,i-1,s1,s2);
		HT[s1].parent=i;
		HT[s2].parent=i;
		HT[i].lchild=s1;
		HT[i].rchild=s2;
		HT[i].weight.quan=HT[s1].weight.quan+HT[s2].weight.quan;
	}
	HC=(HuffmanCode) malloc ((n+1)*sizeof (char*));///指向char型指針的指針
	char* cd=new char[n];
	cd[n-1]='\0';
	for(i=1;i<=n;++i)
	{
		int start=n-1,c,f;
		for(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';
		}
		HC[i]=(char*)new char[n-start];
		strcpy(HC[i],&cd[start]);////HC放譯碼
	}
	delete (cd);
}
 ///函數(shù)三////譯碼函數(shù)
void translate( HuffmanTree B,int n,intzhi &z)////n是葉子結(jié)點(diǎn)的個(gè)數(shù)  變量是整形指針的引用
{
	int i=0,j=0,t,a4=0;
	int p,b;
	b=2*n-1;
	p=b;///根結(jié)點(diǎn)的序號
	char s[100];
	z=new int[100];
	cout<<"請輸入要譯碼的編碼"<<endl;	
   	cin>>s;
	while(s[i]!=NULL)
	{
		while(B[p].lchild!=0 || B[p].rchild!=0)
		{
            t=i;
			if(s[i]=='0') p=B[p].lchild;
			else if
				(s[i]=='1') p=B[p].rchild;
			else if(s[i]==NULL) break;////else if的用法不能只寫if !!!!!!!!!!!!!!!!!!!!
			i++;
		}
		if(i==t)
		{
			cout<<"輸入的譯碼有誤，不能完全編譯,部分的編譯為："<<endl;
			break;
		}

		z[j++]=p;
		p=b;//重新回到根結(jié)點(diǎn)
	}
}

	

void main()
{
	int a1,a2=1,a3=0;
	cout<<"請輸入要建立哈夫曼樹的字符個(gè)數(shù)："<<endl;
	cin>>a1;
	Data zifu[50];
	cout<<"請依次輸入字符和權(quán)值："<<endl;//存儲從0開始
	for(int i=0;i<a1;i++)	
	cin>>zifu[i].a >>zifu[i].quan ;
	Dzhi ww=zifu;
	HuffmanTree HT1;
	HuffmanCode HC1;
	HuffmanCoding(HT1,HC1,ww,a1);
	/////////////以上建立了哈夫曼樹并實(shí)現(xiàn)了編碼//////////
	while(a2++)
	{
		cout<<"請選擇您所需要的操作：p:為打印編碼。d:為譯碼并輸出。q:為退出"<<endl;
		char AA;
		cin>>AA;
		if(AA=='q') break;
		switch(AA)
		{
			case 'p':
				{
					for(i=1;i<=a1;i++)
					{
					   cout<<HC1[i]; 
					}
					cout<<endl;
					break;
				}
			case 'd':
				{
					int *n1;
					translate( HT1,a1,n1);
					int j=0,t;
					while(n1[j]>0 )////(n1[j]!=NULL;不行
					{
						if(a3%10==0) cout<<endl;
						t=n1[j++];
						cout<<zifu[t-1].a ;///從T-1開始算
						a3++;
					}
					cout<<endl;
					break;
				}

		}
	}
	delete HT1,HC1;////////delete n1;?
}