#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#define MAXNUM 27

class HuffNode
{
public:
	char data;
	int weight;
	int father;
	int lc;
	int rc;
};
class HuffNodeCode
{
public:
	char data;
	char code[MAXNUM];
};
int Selete2Small(HuffNode *htree,int k,int *s1,int *s2);
int HufftreeCreate(HuffNode *htree,int n)
{
	int s1,s2,i;
	s1=s2=0;
	for(i=n+1;i<2*n;i++)
	{//選擇兩個父為0，權最小的樹的下標
		Selete2Small(htree,i-1,&s1,&s2);
		htree[i].data=NULL;
	//置新父節點權值
		htree[i].weight=htree[s1].weight+htree[s2].weight;
	//置根無父
		htree[i].father=0;
	//置兒子指示	
		htree[i].lc=s1;
		htree[i].rc=s2;
		htree[s1].father=i;
		htree[s2].father=i;
	}
return 0;
};

int Selete2Small(HuffNode *htree,int k,int *s1,int *s2)
{
	int i,j;
	if (k<2) return -1;
	*s1=0;*s2=0;
	//令s1,s2分別指向htree中最前面的兩個無父節點元素
	
	for (j=1;j<=k;j++)
	{
		if(htree[j].father!=0) continue;
		if(*s1==0) *s1=j;
		else {*s2=j;break;}
	}
	if(*s1==0||*s2==0) return -1;//表示htree中只有一棵樹
	if(htree[*s1].weight>htree[*s2].weight)
	{
		i=*s1;*s1=*s2;*s2=i;}
	for(i=j+1;i<=k;i++) //j從上段程序的值開始
	{
		if(htree[i].father!=0) continue;
		if(htree[i].weight<htree[*s1].weight)
		{
			*s2=*s1;
			*s1=i;
		}
		else
			if(htree[i].weight<htree[*s2].weight) *s2=i;
	}
	return 0;
}
//列表輸出哈夫曼樹
void PrintHtree(HuffNode *htree,int n)
{
	cout<<"\n輸出哈夫曼樹結構："<<endl;
	cout<<"序號"<<"  "<<"節點數據"<<"  "<<"權重"<<"  "<<"父親節點"<<"  "<<"左孩子"<<"  "<<"右孩子"<<endl;
	for(int i=1;i<=2*n-1;i++)
	{
		cout<<i<<"\t"<<htree[i].data<<"\t"<<htree[i].weight<<"\t"<<htree[i].father<<"\t"<<htree[i].lc<<"\t"<<htree[i].rc<<endl;
	}
}
//哈夫曼樹編碼
void HufftreeCode(HuffNode *htree,int n,HuffNodeCode *pcode)
{
	int i,j,k,m;
	HuffNode *curr;
	for(i=1;i<=n;i++)
	{
		curr=&htree[i];
		j=MAXNUM-1;
		k=i;
		pcode[i].data=htree[i].data;
		do 
		{
			if(n<=1) 
			{
				pcode[i].code[j]='0';
				return;
			}
			m=curr->father;
			curr=&htree[m];
			if(curr->lc==k) 
			{
				pcode[i].code[j]='0';
			}
			else
				if(curr->rc==k)
				{
					pcode[i].code[j]='1';
				}
				k=m;
				j=j-1;
		}while(curr->father!=0);
        if(curr->lc==k) pcode[i].code[j]='0';
		else
			if(curr->rc==k) pcode[i].code[j]='1';	
	}
}
//緊縮編碼表
void HuffOrder(HuffNodeCode *htreecode,HuffNodeCode *htreecdout,int n)
{
	int i,j,k,kk;
	for(i=1;i<=n;i++)
	{
		htreecdout[i].data=htreecode[i].data;
	    j=0;
		while((htreecode[i].code[j]==NULL)&&(j<MAXNUM))	{j+=1;}
		kk=0;
		for(k=j;k<MAXNUM;k++)
		{
	    	htreecdout[i].code[kk]=htreecode[i].code[k];
		    kk+=1;
		}
		if(kk<MAXNUM)
		{
			for(k=kk;k<MAXNUM;k++) htreecdout[i].code[k]=NULL;
		}
	}
}
//對輸入字符串編碼
void StrCodeing(char *str,int n,HuffNodeCode *pcode)
{
	int i,j,k,m,flag;
	k=0;
	m=strlen(str);
	for(i=0;i<m;i++)
	{
		flag=0;
		for(j=1;j<=n;j++)
		{
			if(pcode[j].data==str[i]) 
			{
				cout<<pcode[j].code;
				flag=1;
				break;
			}
		}
		//控制輸出
		k+=strlen(pcode[j].code);
		if(k>=50) {k=0;cout<<endl;}
				
	    if(flag==0) 
		{
			cout<<"字符串中含有不能編碼的字符!"<<endl;
			exit(1);
		}
	}
}

void PrintCode(HuffNodeCode *htreecdout,int n)
{
	cout<<"輸出哈夫曼樹編碼； "<<endl;
	for(int i=1;i<=n;i++)
	{
		cout<<htreecdout[i].data<<"  :   "<<htreecdout[i].code<<endl;
	}
}

//二進制譯碼
void StrConcodeing(char *chr,int n,HuffNode *htree)
{
	int i=0,m;
	m=2*n-1;
	while(chr[i]!='\0')
	{
		
		if (chr[i]=='0')
		{
			m=htree[m].lc;
		}
		else if(chr[i]=='1')
		{
			m=htree[m].rc;
		}
	    if(htree[m].lc==0) 
		{
			cout<<htree[m].data;
			m=2*n-1;
		}
		i+=1;
	}
}

//主程序
void main()
{
	int n,i,sele;
    char str1[100];
	char str2[1000];
    char chr[1];
    cout<<"輸入字符集大小：";
	cin>>n;
	HuffNode *htree=(HuffNode *) malloc(2*n*sizeof(HuffNode));
	HuffNodeCode *htreecode=(HuffNodeCode *) malloc((n+1)*sizeof(HuffNodeCode));
	HuffNodeCode *htreecdout=(HuffNodeCode *) malloc((n+1)*sizeof(HuffNodeCode));
	//對第htree[0]單元置初值
	htree[0].data=NULL;
	htree[0].father=htree[0].lc=htree[0].rc=htree[0].weight=0;
	for(i=1;i<=n;i++)
	{
		cout<<"\n輸入第"<<i<<"個字符:"<<endl;
		gets(chr);
		htree[i].data=chr[0];
		//cin>>htree[i].data;
		cout<<"\n輸入字符\""<<chr[0]<<"\"的權值:";
		cin>>htree[i].weight;
		htree[i].father=htree[i].lc=htree[i].rc=0;
	}
	//編碼數組初始化
	for(i=1;i<=n;i++)
	{
		for(int j=0;j<MAXNUM;j++)
		{
			htreecode[i].code[j]=NULL;
		}
	}
	//構造哈夫曼樹
	HufftreeCreate(htree,n);
	//列表輸出哈夫曼樹結構
	PrintHtree(htree,n);		
	//哈夫曼樹編碼
	HufftreeCode(htree,n,htreecode);
	//將編碼正序緊縮存入htreecdout中
	HuffOrder(htreecode,htreecdout,n);
	//輸出字符編碼	
	PrintCode(htreecdout,n);
	while(1)
	{
        cout<<"\n------操作表------"<<endl;	
		cout<<"1   輸入字符串，編寫二進制碼； "<<endl;
		cout<<"2   輸入二進制數據，譯碼輸出； "<<endl;
		cout<<"3   退出； "<<endl;		 
		cout<<"請選擇操作："<<endl;
	    cin>>sele;
		switch(sele)
		{
		case 1:
			{
				cout<<"請輸入要編碼的字符串:"<<endl;
			    gets(str1);
				cout<<"輸入的字符串為:"<<str1<<endl;
				//編碼
				cout<<"字符串的二進制編碼為:"<<endl;
                StrCodeing(str1,n,htreecdout);
				break;
			}
		case 2:
			{	
    			cout<<"請輸入要譯碼的二進制編碼:"<<endl;
			    gets(str2);
				cout<<"輸入的字符串為:"<<str2<<endl;
				//譯碼
				cout<<"二進制字符串的原碼為:"<<endl;
				StrConcodeing(str2,n,htree);
				break;			
			}
		case 3: exit(1);
		}
	}
}