#include "stdio.h"
#include "stdlib.h"
#include "string.h"
typedef struct{
	double weight;
	int parent,lchild,rchild;
}HTnode,*HTree;
void InitData();
void select(HTree HT, int len, int* index1, int* index2);
int create(HTree* HT, double* weight, int num);
void huffmanCode(HTree HT, char** HC,int num);
void huffmanCoding();//編碼過程
void dhuffmanCoding();//譯碼過程
void show();
double data[1000][4]={0};
int length=0,l=0,n=0;
char* HC[1000];  //定義指向編碼串的指針數(shù)組
int main()
{
	int i=0;
	double qdata[1000];
	memset(HC,0,1000);
	memset(qdata,0,1000);
	InitData();
	for(i=0;i<n;i++)
		qdata[i]=data[i][3];	
	HTree HT;
	//創(chuàng)建Huffman樹
	create(&HT,qdata,n);
	//編碼
	huffmanCode(HT,HC,n);
	//打印編碼串
	for(i = 0; i < n;++i)
		printf("%f-%f-%f: %s\n",data[i][1],data[i][2],data[i][3],HC[i]);
	show();
	printf("共有：%d條記錄及%d個權值\n",length,n);
	printf("正在編碼中....\n");
	printf("正在將編碼數(shù)據(jù)寫入code.txt文件中....\n");
	huffmanCoding();
	printf("編碼完成......\n");
	printf("正在譯碼中....\n");
	printf("正在將譯碼數(shù)據(jù)寫入data.txt文件中....\n");
	dhuffmanCoding();
	printf("譯碼完成......\n");
	system("pause");
	return 0;
}
void InitData()
{
	int i,flag=0;
	double temp=0;
	FILE* p=fopen("hfm.txt","r");
	while(1)
	{
		fscanf(p,"%lf",&temp);
		for(i=0;i<n;i++)
		{
			if(temp==data[i][1])
			{
				flag=1;
				data[i][2]=data[i][2]+1;
				length++;
				for(i=0;i<n;i++)
					data[i][3]=data[i][2]/length;
				break;
			}
		}
		if(flag==0)
		{
			data[n][1]=temp;
			data[n][2]=data[n][2]+1;
			length++;
			n++;
			for(i=0;i<n;i++)
				data[i][3]=data[i][2]/length;	
		}
		if(feof(p))break;
		flag=0;
	}
	fclose(p);
}
void select(HTree HT, int len, int* index1, int* index2){
	int i;
	//初始化*index1
	for(i = 0; i < len; i++)
		if(HT[i].parent == 0){
			*index1 = i;
			break;
		}
		//求最小值*index1
		for(i = 0; i < len; i++)
			if(HT[i].parent == 0)
				if(HT[i].weight < HT[*index1].weight)
					*index1 = i;
				//初始化*index2
				for(i = 0; i < len; i++)
					if(HT[i].parent == 0 && i!= *index1){
						*index2 = i;
						break;
					}
					//求次小值*index2:
					for(i = 0; i < len; ++i)
						if(i != *index1)
							if(HT[i].parent == 0)
								if(HT[i].weight < HT[*index2].weight)
									*index2 = i;
								
}
//創(chuàng)建Huffman樹：
int create(HTree* HT, double* weight, int num){
	int i, nodeNum;
	int min1,min2;
	double* w = weight;
	HTree p;
	if(num <= 1)
		return 1;
	nodeNum = 2*num - 1;
	//分配所有結點的空間
	(*HT) = (HTree)malloc(sizeof(HTnode)*nodeNum);
	if(!(*HT))
		return -1;
	//對葉子結點初始化
	for(i = 0, p = *HT; i < num; ++i, ++p,++w){
		p->weight = *w;
		p->lchild = p->rchild = p->parent = 0;
	}
	//對剩余的非葉子結點初始化
	for( ; i < nodeNum; ++i,++p)
		p->weight = p->lchild = p->rchild =p->parent = 0;
	//鏈接各個結點形成Huffman樹
	for(i = num; i < nodeNum; ++i){
		select(*HT, i ,&min1,&min2);
		(*HT)[min1].parent = i;
		(*HT)[min2].parent = i;
		(*HT)[i].weight = (*HT)[min1].weight + (*HT)[min2].weight;
		//最小值為其左孩子，次小值為其右孩子，也可以按照反順序，那么得到的編碼有些不同
		(*HT)[i].lchild = min1;
		(*HT)[i].rchild = min2;
	}
	return 1;
}
//編碼函數(shù)：在已建立的Huffman樹的基礎之上進行編碼（從字符到對應的01串的過程）
void huffmanCode(HTree HT, char** HC,int num){
	int i,temp,start,par;
	char* workSpace;
	//申請求編碼要用的工作空間，該空間最大為2*num-1-num+1 = num個字節(jié)
	workSpace = (char*)malloc(num*sizeof(char));
	//不需要執(zhí)行下面的語句，因為HC一般從主函數(shù)傳入
	//HC = (char**)malloc(num*sizeof(char*));
	//逆向求字符編碼，首先將工作空間用字符串結束標志初始化：
	workSpace[num-1] = '\0';
	//雙重循環(huán)依次對各個字符求編碼 
	for(i = 0; i < num ; ++i){
		start = num -1;
		//循環(huán)結束標志是結點的雙親結點為0，也即到達了根結點了
		for(temp = i,par = HT[i].parent;     par != 0;      temp = par,par = HT[par].parent)
			if(HT[par].lchild == temp)
				workSpace[--start] = '0';
			else
				workSpace[--start] = '1';
			//為當前求得的字符編碼分配適當大小的空間
			*(HC+i) = (char*)malloc((num - start)*sizeof(char));
			//從工作空間拷貝編碼串到分配好的區(qū)域中
			strcpy( *(HC+i) , &workSpace[start]);
	}
	//釋放工作空間
	free(workSpace);
}
void huffmanCoding()
{
	int i=0;
	double temp=0;
	FILE* p=fopen("hfm.txt","r");
	FILE* fp=fopen("code.txt","w");
	while(1)
	{
		fscanf(p,"%lf",&temp);
		for(i=0;i<n;i++)
		{
			if(data[i][1]==temp)
			{
				fprintf(fp,"%s\n",HC[i]);
				break;
			}
		}
		if(feof(p))break;
	}
	fclose(p);
	fclose(fp);
}
void dhuffmanCoding()
{
	int i=0;
	long int m=0,k=0;
	char temp[20];	
	FILE* p=fopen("code.txt","r");
	FILE* fp=fopen("data.txt","w");
	while(1)
	{
		memset(temp,0,20);
		fgets(temp,20,p);
		if(feof(p))break;
		m=atoi(temp);
		for(i=0;i<n;i++)
		{
			k=atoi(HC[i]);
			if(m==k)
			{
				fprintf(fp,"%f\n",data[i][1]);
				break;
			}
		}
	}
	fclose(p);
	fclose(fp);
}
void show()
{
	printf("\n\t\t-************************************-\n");
	printf("\t\t-* 此程序演示哈夫曼編碼以及譯碼過程 *-\n");
	printf("\t\t-* www.coolboys.cn  Design by cooky *-\n");
	printf("\t\t-************************************-\n");
}