/*===============================
程序名:霍夫曼編碼
作者:何震 研通信0704班 07120075
注意:沒有考慮漢字寬字符,所以請以全英文文件進行測試
如有問題請聯系:07120075@bjtu.edu.cn
================================*/
#include <stdio.h>
#include <math.h>
#include <conio.h>
#define TABLELENGTH 128
#define MAXSIZE 512
typedef struct tagHTNode
{
	int Parent;//父節點
	int LeftChild;//左子節點
	int RightChild;//右子節點
	int Weight;//權重
}HTNode;//霍夫曼樹的節點結構
typedef struct tagCode
{
	char code[MAXSIZE];//Huffman編碼的字符形式數組
	int Weight;//Ascii碼在文中的權重
}Code;//Huffman碼結構
typedef HTNode HuffTree[2*TABLELENGTH];//Huffman樹
typedef Code HuffCode[TABLELENGTH];//128個Ascii碼的Huffman碼結構
int SelectHTNode(HuffTree HT,int n,int *min1,int *min2)
{//選擇0~n-1個Code中權重最小的兩個
	int cnt=0;//剩余有效Code的個數，有效是指循環中的條件，即權重大于0,且未分配父節點
	for(int i=0;i<n;i++)
	{	
		if(HT[i].Weight>0 && HT[i].Parent==-1)
			cnt++;
	}
	if(cnt<=1)//如果少于兩個，就說明樹已經構造到樹頂了
		return 0;//返回0表示到樹頂
	for(i=0;i<n;i++)
	{//找最小權重節點的序號，先初始化min1
		if(HT[i].Parent==-1 && HT[i].Weight>0)
		{
			*min1=i;
			break;
		}
	}
	for(i=0;i<n;i++)
	{//找次最小節點的序號，先初始化min2,注意條件i!=*min1,不能使之初始指向同一節點，否則結果有重合錯誤
		if(HT[i].Parent==-1 && HT[i].Weight>0 && i!=*min1)
		{
			*min2=i;
			break;
		}
	}
	for(i=0;i<n;i++)
	{
		if(HT[i].Parent==-1 && HT[i].Weight>0)
		{
			if(HT[*min1].Weight>HT[i].Weight)
			{//如果找到一個有效節點，其權重比上一最小權重節點權重小
				*min2=*min1;//把上一最小權重節點的序號賦予次最小權重節點
				*min1=i;//更新最小權重節點序號
			}
			else if(HT[*min2].Weight>HT[i].Weight && i!=*min1)//如果該節點權重不比最小權重節點小，
				*min2=i;//但比次最小權重節點小，且該節點不是最小權重節點，則更新次最小權重節點序號
		}
	}
	return 1;//返回1說明應該繼續構造樹
}
void GenerateTree(HuffTree HT,HuffCode hc)
{
	int min1,min2;
	for(int i=0;i<TABLELENGTH;i++)
	{//以下兩個循環初始化霍夫曼樹的左子，右子和父節點，并為樹底的權賦值
		HT[i].Weight=hc[i].Weight;
		HT[i].LeftChild=HT[i].RightChild=HT[i].Parent=-1;
	}
	for(;i<2*TABLELENGTH-1;i++)
	{
		HT[i].LeftChild=HT[i].RightChild=HT[i].Parent=-1;
	}
	for(i=TABLELENGTH;i<2*TABLELENGTH-1;i++)
	{//從第TABLELENGTH個節點開始為上層節點
		int r=SelectHTNode(HT,i,&min1,&min2);
		if(r<1)//從第0到i-1的底層節點中沒有賦給父節點的節點中找兩個最小權值
			break;//如果沒有找到2個最小的說明已經到了樹頂
		HT[min1].Parent=i;//為他們賦予父節點指針
		HT[min2].Parent=i;
		HT[i].LeftChild=min1;//設置當前節點左子
		HT[i].RightChild=min2;//設置當前節點右子
		HT[i].Weight=HT[min1].Weight+HT[min2].Weight;//設置當前節點權
	}
}
void GenerateCode(HuffTree HT,HuffCode hc)
{//Huffman編碼
	int Stack[MAXSIZE],top=-1,tc;
	char flag[MAXSIZE];
	HTNode th;
	for(int i=0;i<TABLELENGTH /*&& HT[i].Weight>0*/;i++)
	{//從樹底開始遍歷
		top=-1;//編碼路徑的跳數，或者說路徑的長度
		int j=0;//編碼序號
		th=HT[i];//獲得樹的一個節點
		tc=i;//獲得其序號
		while(th.Parent!=-1)
		{//如果其仍有父節點
			Stack[++top]=th.Parent;//將其父節點序號壓棧
			if(HT[th.Parent].LeftChild==tc)
			{//如果其父節點的左子為當前節點
				flag[top]='L';//flag存放編碼所依據的路徑信息
				tc=th.Parent;//向上一層
			}
			else if(HT[th.Parent].RightChild==tc)
			{//如果父節點右子為當前節點
				flag[top]='R';//路徑為向右
				tc=th.Parent;//向上一層
			}
			th=HT[Stack[top]];//獲得上一層的節點
		}
		while(top!=-1)
		{//如果路徑長度不為負數
			if(flag[top]=='L')
				hc[i].code[j++]='0';//根據flag數組進行編碼
			else
				hc[i].code[j++]='1';
			top--;
		}
		hc[i].code[j]='\0';
	}
}
int GetProbability(HuffCode hc,char *file)
{//讀文件初始化128個ascii碼的權重
	FILE *in;
	int c,nTotal=0;
	for(int i=0;i<TABLELENGTH;i++)
	{
		hc[i].Weight=0;//初始為0
	}
	in=fopen(file,"rb");//打開文件
	if(in==NULL)
	{
		printf("No such file!");
		return 0;
	}	
	while((c=fgetc(in))!=EOF)
	{//讀字符，根據Ascii碼值累加權值
		hc[c].Weight++;
		nTotal++;
		//printf("%c\n",c);
	}
	fclose(in);
	return nTotal;
}
void main()
{
	int nCount;
	char file[128];
	HuffTree HT;//Huffman樹結構
	HuffCode hc;//Huffman碼表	
	printf("Input file name:");
	gets(file);//獲取文件名
	nCount=GetProbability(hc,file);//讀文件初始化信源概率數組	
	GenerateTree(HT,hc);//構造霍夫曼樹
	GenerateCode(HT,hc);//根據霍夫曼樹進行編碼
	//測試	
	for(int i=0;i<TABLELENGTH;i++)
	{
		if(hc[i].Weight!=0)
		{
			printf("Ascii Value:%d,Weight:%5.4lf,Encode to:%s\n",i,(double)hc[i].Weight/nCount,hc[i].code);
		}
	}
	getch();
}