#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100
#define MAXVALUE 10000
typedef struct{
	int weight;
	int flag;
	int parent;
	char ch;
	int lchild;
	int rchild;
}HafNode;
typedef struct{
	int bit[MAX];
	int start;
	int weight;
	char ch;
}Code;
typedef struct{
	char bit[MAX];
	char ch;
	int weight;
}Coding;
 /*---------------生成哈夫曼樹的函數(shù)---------------*/
void CreatHfmTree(int weight[],char ch[],int n,HafNode haffTree[]){
	int i,j,m1,m2,x1,x2;
	for (i=0;i<2*n-1;i++){
		if(i<n){
			haffTree[i].weight=weight[i];
			haffTree[i].ch=ch[i];
		}
		else
			haffTree[i].weight=0;
		haffTree[i].parent=-1;
		haffTree[i].flag=0;
		haffTree[i].lchild=-1;
		haffTree[i].rchild=-1;
	}
	for (i=0;i<n-1;i++)
	{
		m1=m2=MAXVALUE;
		x1=x2=0;
		for (j=0;j<n+i;j++){
			if (haffTree[j].weight<m1&&haffTree[j].flag==0){
				m2=m1;x2=x1;m1=haffTree[j].weight;x1=j;
			}
			else if(haffTree[j].weight<m2 && haffTree[j].flag==0)
			{
				m2=haffTree[j].weight;x2=j;
			}
		}
		haffTree[x1].parent= n + i;
		haffTree[x2].parent = n + i;
		haffTree[x1].flag = 1;
		haffTree[x2].flag = 1;
		haffTree[n+i].weight = haffTree[x1].weight + haffTree[x2].weight;
		haffTree[n+i].lchild = x1;
		haffTree[n+i].rchild = x2;
	}
	FILE *fp;
	fp=fopen("huffman.txt","w+");
	printf("%d\n",n);
	fprintf(fp,"%d\n",n);
	for (i=0;i<n;i++) 
		fprintf(fp,"%c %d %d %d\n",haffTree[i].ch,haffTree[i].parent,haffTree[i].lchild,haffTree[i].rchild);
	for (i=n;i<2*n-1;i++)
		fprintf(fp,"%d %d %d\n",haffTree[i].parent,haffTree[i].lchild,haffTree[i].rchild); 
	fclose(fp);
}
/*-----------------哈夫曼編碼函數(shù)-------------------*/
void HaffmanCode (HafNode haffTree[],int n,Code haffCode[]){
	Code *cd=( Code *) malloc (sizeof (Code));
	int i,j,child,parent; 
	for (i=0; i<n; i++){
		cd->start=n-1;
		cd->weight=haffTree[i].weight;
		cd->ch=haffTree[i].ch;
		child=i;
		parent=haffTree[child].parent;
		while (parent !=-1){
			if (haffTree[parent].lchild==child)
				cd->bit[cd->start]=0;
			else
				cd->bit[cd->start]=1;
			cd->start--;
			child =parent;
			parent=haffTree[child].parent;
		}
		for (j=cd->start+1; j<n; j++)
			haffCode[i].bit[j]=cd->bit[j];
		haffCode [i].start = cd->start+1;
		haffCode [i].weight=cd->weight;
		haffCode [i].ch=cd->ch;
	}
} 
/*-------------------初始化操作--------------------*/
void InitHfmTree(int weight[],char ch[]){
	FILE *fp;
	int i,j,n;
	char ch1,wj[15];
	printf("現(xiàn)在進(jìn)行初始化操作。。。\n請選擇:\nA.鍵盤輸入 B.文件輸入\n");
	scanf("%c",&ch1);
	if (ch1=='A'){
		printf("請輸入字符集大小n:\n");
		scanf("%d",&n);
	}
	if (ch1=='B'){
		printf("請輸入文件名:\n");
		scanf("%s",wj);
		fp=fopen(wj,"r"); 
		fscanf(fp,"%d",&n);
	} 
	HafNode *myHaffTree=(HafNode *)malloc(sizeof (HafNode)*(2*n+1));
	Code *myHaffCode =(Code *)malloc (sizeof (Code)*n);
	for (i=0;i<n;i++){
		if (ch1=='A'){
			printf("請輸入字符和權(quán)值:\n");
			scanf("%s %d",&ch[i],&weight[i]);
		}
		if (ch1=='B')
			fscanf(fp,"%s %d",&ch[i],&weight[i]);
	}
	if (ch1=='B')
		fclose(fp);
	CreatHfmTree(weight,ch,n,myHaffTree);
	HaffmanCode(myHaffTree,n,myHaffCode);
	fp=fopen("hfmtree.txt","w+"); 
	for (i=0;i<n;i++){
		printf("%c %d ",myHaffCode[i].ch,myHaffCode[i].weight);
		fprintf(fp,"%c %d ",myHaffCode[i].ch,myHaffCode[i].weight);
		for ( j=myHaffCode[i].start; j<n; j++){ 
			printf("%d",myHaffCode[i].bit[j]);
			fprintf(fp,"%d",myHaffCode[i].bit[j]);
		}
		fprintf(fp,"\n");
		printf("\n");
	}
	fclose(fp);
	printf("初始化成功!\n");
}
 /*-----------------文件編碼過程-----------------*/
void FileCoding(){
	FILE *fp,*fp1,*fp2;
	char zf[500];
	fp=fopen("hfmtree.txt","r");
	Coding ch[100];
	char c;
	int i=0;
	while (feof(fp)==0){ 
		fscanf(fp,"%s %d %s",&ch[i].ch,&ch[i].weight,&ch[i].bit);
		i++;
	}
	fclose(fp); 
	printf("現(xiàn)在進(jìn)行編碼操作。。。\n請選擇:\nA.鍵盤輸入 B.文件輸入\n");
	scanf("%s",&c);
	if (c=='A'){
		printf("請輸入字符串:\n");scanf("%s",zf);
	} 
	char ch1[20],ch2[20];
	int j;
	if (c=='B'){
		printf("請輸入正文的文件名:\n");
		scanf("%s",&ch1);
		fp1=fopen(ch1,"r");
	}
	printf("請輸入保存結(jié)果的文件名:\n");
	scanf("%s",&ch2); 
	fp2=fopen(ch2,"w+");
	if (c=='A'){
		int len,k;
		len=strlen(zf);
		for (k=0;k<len;k++)
			for (j=0;j<i;j++)
				if (ch[j].ch==zf[k]){
					fprintf(fp2,"%s",ch[j].bit);
					printf("%s",ch[j].bit);
				}
				printf("\n"); 
	}
	if (c=='B'){
		while(feof(fp1)==0){ 
			fscanf(fp1,"%c",&c);
			for (j=0;j<i;j++)
				if (ch[j].ch==c){
					fprintf(fp2,"%s",ch[j].bit);
					printf("%s",ch[j].bit);
				}
		}
		fprintf(fp2,"\n"); 
		printf("\n");
		fclose(fp1);
	} 
	fclose(fp2);
	printf("編碼過程完成!同時已將結(jié)果存入%s中.\n\n",ch2);
}
/*----------------------譯碼操作---------------------*/
void DeCoding(){ 
	FILE *fp,*fp1; 
	fp=fopen("huffman.txt","r");
	int i,n;
	fscanf(fp,"%d",&n);
	HafNode *myHaffTree=(HafNode *)malloc(sizeof (HafNode)*(2*n+1));
	for (i=0;i<n;i++)
		fscanf(fp,"%s %d %d %d\n",&myHaffTree[i].ch,&myHaffTree[i].parent,&myHaffTree[i].lchild,&myHaffTree[i].rchild);
	for (i=n;i<2*n-1;i++)
		fscanf(fp,"%d %d %d\n",&myHaffTree[i].parent,&myHaffTree[i].lchild,&myHaffTree[i].rchild);
	fclose(fp);
	printf("請輸入譯碼文件的文件名:\n");
	char ch1[20],ch2[20];
	scanf("%s",ch1);
	printf("請輸入結(jié)果文件的文件名:\n");
	scanf("%s",ch2); 
	fp=fopen(ch1,"r");
	fp1=fopen(ch2,"w+");
	char ch;
	i=2*n-2;
	while (!feof(fp)){
		fscanf(fp,"%c",&ch); 
		if (ch=='0') //若編碼為0，則找此結(jié)點的左孩子；
			i=myHaffTree[i].lchild;
		if (ch=='1') //若編碼為1，則找此結(jié)點的右孩子；　
			i=myHaffTree[i].rchild; 
		if (i<n){
			printf("%c",myHaffTree[i].ch);
			fprintf(fp1,"%c",myHaffTree[i].ch);
			i=2*n-2;
		}
	}
	printf("\n");
	fprintf(fp1,"\n");
	fclose(fp);
	fclose(fp1);
	printf("譯碼過程完成!已將結(jié)果存入%s中.\n\n",ch2);
}
/*------------------打印代碼文件-----------------*/
void PrintCodeFile() {
	FILE *fp1,*fp2;
	printf("請輸入輸入文件的文件名：\n");
	char ch1[20],ch2[20];
	scanf("%s",ch1);
	printf("請輸入結(jié)果保存的文件名：\n");
	scanf("%s",ch2);
	fp1=fopen(ch1,"r");
	fp2=fopen(ch2,"w+");
	int count=0;
	char ch;
	while (!feof(fp1)){
		fscanf(fp1,"%c",&ch); 
		printf("%c",ch);
		fprintf(fp2,"%c",ch);
		count++;
		if (count==50){
			printf("\n");
			fprintf(fp2,"\n");
			count=0;
		}
	}
	printf("\n");
	fprintf(fp2,"\n");
	fclose(fp1);
	fclose(fp2);
	printf("打印代碼過程完成!已將結(jié)果存入%s中.\n\n",ch2);
}
/*-------------------打印哈夫曼樹結(jié)點-----------------*/
void PrintTreeCode(HafNode *huf,int n,int p,FILE *fp){
	int i;
	if (n==-1)
		return;
	PrintTreeCode(huf,huf[n].rchild,p+1,fp);
	for (i=0;i<p;i++){
		printf(" ");
		fprintf(fp," ");
	}
	if (p>=0&&huf[n].rchild==-1){
		printf("---");
		printf("%c\n",huf[n].ch); //如果此結(jié)點為葉子結(jié)點，則將此結(jié)點輸出；
		fprintf(fp,"---%c\n",huf[n].ch);
	}
	else {
		printf("@\n");            //如果此結(jié)點為非葉子結(jié)點，則輸出"@";
		fprintf(fp,"@\n");
	}
	PrintTreeCode(huf,huf[n].lchild,p+1,fp);
}
/*-----------------打印哈夫曼樹的操作----------------*/
void PrintTree(){ 
	FILE *fp;
	fp=fopen("huffman.txt","r");
	int i,n;
	fscanf(fp,"%d",&n);
	HafNode *myHaffTree=(HafNode *)malloc(sizeof (HafNode)*(2*n+1));
	for (i=0;i<n;i++)
		fscanf(fp,"%s %d %d %d\n",&myHaffTree[i].ch,&myHaffTree[i].parent,&myHaffTree[i].lchild,&myHaffTree[i].rchild);
	for (i=n;i<2*n-1;i++)
		fscanf(fp,"%d %d %d\n",&myHaffTree[i].parent,&myHaffTree[i].lchild,&myHaffTree[i].rchild);
	fclose(fp);
	printf("請輸入保存結(jié)果的文件名:\n");
	char ch1[20];
	scanf("%s",ch1);
	fp=fopen(ch1,"w+");
	PrintTreeCode(myHaffTree,2*n-2,0,fp);
	fclose(fp);
	printf("打印哈夫曼樹過程完成!同時已將結(jié)果存入%s中.\n\n",ch1); 
}
/*-------------------------打印表單----------------------*/
void Sheet(){
	printf("*******************************************************************************\n");
	printf("***** ******************** 歡迎使用哈夫曼編／譯碼器 ********************* *****\n");
	printf("***** ******************** ************************ ********************* *****\n");
	printf("***** C.編碼　　 　D.譯碼　　　T.印哈夫曼樹　　　P.印代碼文件　　　E.退出 *****\n");
	printf("*******************************************************************************\n");
}
int main(){
	int n=4;
	int weight[100];
	char ch[100],cha;
	Sheet();
	InitHfmTree(weight,ch);
	while (1){
		printf("請輸入要執(zhí)行的操作:\nC.編碼　　　D.譯碼　　　T.印哈夫曼樹　　　P.印代碼文件　　　E.退出\n");
		printf("請輸入要執(zhí)行的操作:\n");
		scanf("%s",&cha);
		if (cha=='E')
			break; 
		switch (cha){
		case 'C':FileCoding();break; //執(zhí)行編碼操作
		case 'D':DeCoding();break; //執(zhí)行譯碼操作
		case 'T':PrintTree();break; //打印哈夫曼樹
		case 'P':PrintCodeFile();break; //打印代碼文件
		}
	}
	return 0; 
}