//用于對字符的Huffman編碼
//首先輸入要編碼的字符個數例：6個，和要編碼的字符例：a,b,c,d,e,f
//被編碼的字符串保存在文件"in"中
//HUFFMAN編碼保存在文件"out_1"中, 譯碼保存在文件"out_2"中
#include<iostream.h>
#include<fstream.h>
typedef char ElemType;
#define MAXSIZE 100//H樹中的最大葉子結點數
struct HTNode
{
	ElemType v;//表示結點
	int weight;//結點的權重
	int parent,lchild,rchild;//結點的雙親、左右兒子
};
class Huffman
{
private:
	HTNode HTN[2*MAXSIZE-1];//表示結點HUFFMAN樹結點個數
	int sum;//結點個數
public:
	Huffman();//構造函數
	void FWrite();//把輸入的字符串保存在文件中
	void HTNodeWeight();//求一個結點的權值
	void InitHT();//初始化一棵樹
	void CreateHT();//構造HUFFMAN樹
	void HTCoding();//對文件編碼
	void HTUnCoding();//對文件譯碼
	void Selectmins(int n,int &s1,int &s2);//找樹中0……n-1中的最小的兩個結點返回值放s1,s2中
};
Huffman::Huffman()
{
	sum=0;
}
void Huffman::InitHT()
{
	int i;
	cout<<"請輸入葉子結點個數"<<endl;
	cin>>sum;
	cout<<"請依次輸入葉子結點的名稱"<<endl;
	for(i=0;i<sum;i++)
	{
		cin>>HTN[i].v;
		HTN[i].weight=0;
		HTN[i].parent=0;
		HTN[i].lchild=HTN[i].rchild=0;
	}
}
void Huffman::FWrite()
{
	char ch;
	ofstream fout;
	fout.open("in",ios::trunc);//打開文件的同時刪除同名文件
	if(!fout)
	{
		cout<<"When writing coding,cannot open file"<<endl;
	}
	cout<<"請依次輸入被編碼的字符串以'＠'結束(同時保存在文件'in'中)"<<endl;
	cin>>ch;
	while(ch!='@')
	{
		fout<<ch;
		cin>>ch;
	}
	fout.close();
}
void Huffman::HTNodeWeight()
{
	char ch;//保存返回字符
	int i;
	ifstream fin;
	fin.open("in");
	if(!fin)
	{
		cout<<"When reading,cannot open file"<<endl;
	}
	while(fin)//文件in結束時返回值為-1
	{
		fin.get(ch);//從第i個位置讀一個字符用ch保存
		for(i=0;i<sum;i++)
		{
			if(HTN[i].v==ch)
				HTN[i].weight++;
		}
	}
	fin.close();
	cout<<"葉子結點的權重分別為:"<<endl;
	for(i=0;i<sum;i++)
		cout<<HTN[i].weight<<" ";
	cout<<endl;
}
void Huffman::CreateHT()
{
	int s1,s2;//保存返回值
	int i,m;//H樹中結點個數
	m=2*sum-1;
	for(i=sum;i<m;i++)
	{
		HTN[i].v='@';
		HTN[i].weight=0;
		HTN[i].parent=0;
		HTN[i].lchild=HTN[i].rchild=0;
	}
	for(i=sum;i<m;i++)
	{
		Selectmins(i,s1,s2);
		HTN[s1].parent=i;
		HTN[s2].parent=i;
		HTN[i].lchild=s1;
		HTN[i].rchild=s2;
		HTN[i].weight=HTN[s1].weight+HTN[s2].weight;
	}
}
void Huffman::HTCoding()//從葉子到根逆向求每個字符的赫夫曼編碼
{
	int i,j,c,f,start;
	char cd[MAXSIZE][MAXSIZE+1];
	//存編碼cd[i]中HTN[i].v的編碼
	//cd[i][0]中存放HTN[i].v
	for(i=0;i<sum;i++)
	{
		start=MAXSIZE;//編碼結束位置
		cd[i][0]=HTN[i].v;
		for(c=i,f=HTN[i].parent;f!=0;c=f,f=HTN[c].parent)//從葉子到根逆向求編碼
		{
			if(HTN[f].lchild==c)
				{cd[i][start]='0';start--;}
			else
				{cd[i][start]='1';start--;}
		}
	}//編碼完畢
	for(i=0;i<sum;i++)//輸出葉子結點字符對應的編碼
	{
		cout<<cd[i][0]<<": ";
		for(j=1;j<=MAXSIZE;j++)
			if(cd[i][j]=='1'||cd[i][j]=='0')
				cout<<cd[i][j];
		cout<<endl;
	}
	ofstream fout;
	ifstream fin;
	char ch;
	fout.open("out_1",ios::trunc);//打開文件的同時刪除同名文件
	if(!fout)
	{
		cout<<"When writing coding,cannot open file"<<endl;
	}
	fin.open("in");
	if(!fin)
	{
		cout<<"When reading,cannot open file"<<endl;
	}
	cout<<"輸入的字符串編碼為:(同時保存在文件'out_1'中)"<<endl;
	while(fin)//文件in結束時返回值為-1
	{
		fin.get(ch);//從第i個位置讀一個字符用ch保存		
		for(i=0;i<sum;i++)
			if(HTN[i].v==ch)
				for(j=1;j<=MAXSIZE;j++)
					if(cd[i][j]=='1'||cd[i][j]=='0')
					{
						fout.put(cd[i][j]);	
						cout<<cd[i][j];
					}
	}
	fin.close();
	fout.close();
	cout<<endl;
}
void Huffman::HTUnCoding()
{
	HTNode HN;//  用于保存H樹結點
	ofstream fout;
	ifstream fin;
	char ch;
	fout.open("out_2",ios::trunc);//打開文件的同時刪除同名文件
	if(!fout)
	{
		cout<<"When writing coding,cannot open file"<<endl;
	}
	fin.open("out_1");
	if(!fin)
	{
		cout<<"When reading the file 'out_1',cannot open file"<<endl;
	}
	cout<<"輸入的字符串的編碼譯后為:(同時保存在文件'out_2'中)"<<endl;
	while(fin)//文件in結束時返回值為-1
	{
lable_1:
		HN=HTN[2*sum-2];//把根結點賦給HN
lable_2:
		fin.get(ch);//從第i個位置讀一個字符用ch保存
		if(ch=='0')
		{
			HN=HTN[HN.lchild];
			if(HN.v=='@')
				goto lable_2;
			else
			{
				fout<<HN.v;
				cout<<HN.v;
				goto lable_1;
			}//else
		}//if
		if(ch=='1')
		{
			HN=HTN[HN.rchild];
			if(HN.v=='@')
				goto lable_2;
			else
			{
				fout<<HN.v;
				cout<<HN.v;
				goto lable_1;
			}//else
		}//if
	}//while(fin)
	fin.close();
	fout.close();
}
void Huffman::Selectmins(int n,int &s1,int &s2)
{
	int temp,min1=0,min2=0;
	//表示樹的葉子結點中具有最小權值的結點并賦初值0假設HTN[i].weight不為0
	int i;
	for(i=0;i<n;i++)
	{
		if(HTN[i].parent==0&&min1==0)
		{
			min1=HTN[i].weight;
			s1=i;
			break;
		}
	}
	i++;//不加1　則min2=min1
	for(i;i<n;i++)
	{
		if(HTN[i].parent==0&&min2==0)
		{
			min2=HTN[i].weight;
			s2=i;
			break;
		}
	}
	if(min2<min1)//min1<min2這兩個為被查找的結點中最小的兩個結點
	{
		temp=min1;
		min1=min2;
		min2=temp;
		temp=s1;
		s1=s2;
		s2=temp;
	}
	for(i=0;i<n;i++)
	{
		if(HTN[i].parent==0&&HTN[i].weight<min1)
		{
			min2=min1;
			min1=HTN[i].weight;
			s2=s1;
			s1=i;
		}
		else
			if(HTN[i].parent==0&&HTN[i].weight<min2&&HTN[i].weight>min1)
			{
				min2=HTN[i].weight;
				s2=i;
			}
	}
}
void main()
{
	char flag;//用于選擇進行編碼的類型
	Huffman HT;
	HT.InitHT();//H樹的初始化
	cout<<"你是要對直接輸入的字符串編碼還是對文件中已經有的字符進行編碼?"<<endl;
	cout<<"對已有的文件編碼時請鍵入'1'并且把文件名改為:'in'存入相應的地方"<<endl;
	cout<<"否則請鍵入'2'"<<endl;
	cin>>flag;
	switch(flag)
	{
	case '1':break;
	case '2':HT.FWrite();break; 
	}
	HT.HTNodeWeight();
	HT.CreateHT();
	HT.HTCoding();
	HT.HTUnCoding();
}