#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define M 10000    //定義字符串最大長度
#define N 128        //定義葉子節點個數


typedef struct node              //定義哈夫曼樹節點結構體
{
	int weight;
	struct node *LChild,*RChild,*Parent;  //分別指向該節點的左孩子，右孩子，和雙親節點
	struct node *next;                    //指向建立的哈夫曼樹的下一個節點
}HFMNode,*HFMTree;


typedef struct                   //定義哈夫曼編碼的結構體
{
	char ch;                      //存儲對應的字符
	char code[N+1];                //存儲對應字符的編碼
	int start;                     //存儲編碼的起始位置
}CodeNode;

int n;               //存儲真正葉子節點個數



void clearscreen()
{
system("cls");
}


void Open(char s[])               //打開存放字符或編碼的文件，將其存入字符串數組中
{
	char name[10];
	FILE *fp;
	int i=0;
	printf("請輸入要打開的文件名：");
	gets(name);                               //要打開的文件名
	if((fp=fopen(name,"rt"))==NULL)
		{
			printf("打開失敗！\n");             //若打開失敗，則直接退出
			exit(1);
		}
	s[i++]=fgetc(fp);
	while(s[i-1]!=EOF)
		s[i++]=fgetc(fp);
	s[i]='\0';                           //存取字符串結束
	fclose(fp);
}


void Save(char s[])                        //保存字符或編碼到文件中
{
	char name[10];
	FILE *fp;
	printf("請輸入要保存的文件名：");
	gets(name);
	if((fp=fopen(name,"wt"))==NULL)
		{
			printf("存儲失敗！");
			exit(1);
		}
	fputs(s,fp);
	printf("\n保存成功，文件名為:%s。\n",name);
	printf("\n按回車鍵繼續...");
	getchar();
	fclose(fp);

}




void SearchStr(char s[],char str[],int count[])  
{
	//查找字符串中字符的個數和每個字符出現的次數
	int i,j,k=0;
	for(i=0;i<N;i++)    //初始化每個字符出現的次數
		count[i]=0;
	for(i=0;s[i];i++)
		{
			for(j=0;j<k;j++)            //在str[]中查找是否有該字符
				if(str[j]==s[i])
					{
						count[j]++;
						break;
					}
			if(j==k)                     //在str[]中無該字符，將其存入最后一個單元
				{
					str[k]=s[i];
					count[k++]++;
				}
		}
	str[k]='\0';                  //將字符串結尾置\0
	n=k;                            //將實際的字符個數作為葉子節點個數存入n
}

void SelectMin(HFMTree HT,int k,HFMTree *HT1,HFMTree *HT2)
{
	//查找哈夫曼鏈表中兩個權值最小的節點
	int i,min;
	HFMTree p;
	min=32767;
	for(i=0,p=HT;i<k;i++,p=p->next)
		if(p->weight<min&&p->Parent==0)
			{
				min=p->weight;
				*HT1=p;
			}
	min=32767;
	for(i=0,p=HT;i<k;i++,p=p->next)
		if(p->weight<min&&p->Parent==0&&p!=*HT1)  //令第二個最小的節點不等于第一個節點
			{
				min=p->weight;
				*HT2=p;
			}
	
}



void CreatHFMTree(HFMTree *HT,int count[])
{
	//創建哈夫曼樹
	int i;
	HFMTree p,HT1,HT2;   //HT1，HT2分別存放權值最小和次小的節點的位置
	p=*HT=(HFMTree)malloc(sizeof(HFMNode));
	p->next=p->LChild=p->RChild=p->Parent=NULL;  //初始化哈夫曼鏈表且有2n-1個節點
	for(i=1;i<2*n-1;i++)
		{
			p->next=(HFMTree)malloc(sizeof(HFMNode));
			p=p->next;
			p->next=p->LChild=p->RChild=p->Parent=NULL;
		}

	for(i=0,p=*HT;i<n;i++)                //將各個字符出現的次數作為權值
	{		                             //存入哈夫曼鏈表的前n個單元中
			p->weight=count[i];
			p=p->next;
		}

	for(i=n;i<2*n-1;i++)                 //將后n-1個節點賦權值，建樹
		{
			SelectMin(*HT,i,&HT1,&HT2);  //每次從前i個節點中選取權值最小的兩個節點
			HT1->Parent=HT2->Parent=p;    
			p->LChild=HT1;
			p->RChild=HT2;
			p->weight=HT1->weight+HT2->weight;  //將兩個節點的權值相加存入最后一個節點中
			p=p->next;                            //p指向下一個沒有存儲權值的節點
		}

}


void HFMCode(HFMTree HT,CodeNode HC[],char str[])
{
	//從每個葉子節點開始，利用哈夫曼樹對每個字符進行編碼，最終建立一個哈夫曼表
	int i;
	HFMTree q,p=HT;
	for(i=0;i<n;i++)             //將字符存入哈夫曼編碼結構體數組的字符單元中
		{
			HC[i].ch=str[i];
			HC[i].code[n-1]='\0';  //初始化編碼的最后一位
		}
	for(i=0;i<n;i++)
		{
			HC[i].start=n-1;
			for(q=p;q->Parent;q=q->Parent)   //判斷q所指向的節點，左孩子置0，右孩子置1
				if(q==q->Parent->LChild)
					HC[i].code[--HC[i].start]='0';
				else	HC[i].code[--HC[i].start]='1';
			p=p->next;                   //判斷下一個葉子節點
		}


}



void TotalCoding(char s[],CodeNode HC[],char code[])
{
	//利用哈夫曼編碼表對整個字符串進行編碼
	int i,j;
	code[0]='\0';            //編碼數組初始化
	for(i=0;s[i];i++)                 //將每個字符在哈夫曼編碼表中對應的編碼存入存放總編碼的數組中
		for(j=0;j<n;j++)
		if(s[i]==HC[j].ch)
			strcpy(code+strlen(code),HC[j].code+HC[j].start);
}

void DeCoding(char code[],HFMTree HT,char str[],char s[])
{
	//對哈夫曼編碼進行解碼，放入字符串s中
	int i,j,k=0;
	HFMTree root,p,q;
	for(root=HT;root->Parent;root=root->Parent); //用root指向哈夫曼樹的根結點
	for(i=0,p=root;code[i];i++)            //從根結點開始按編碼順序訪問樹
	{                                      
			if(code[i]=='0')
				p=p->LChild;
			else	p=p->RChild;
			if(p->LChild==NULL&&p->RChild==NULL) //到根節點時將該節點對應的字符輸出
				{
					for(j=0,q=HT;q!=p;q=q->next,j++);
						s[k++]=str[j];
					p=root;                  //回溯到根結點
				}	
		}
	s[k]='\0';                //解碼完畢，在字符串最后一個單元存入'\0'
}


void Coding(char s[],char str[],char code[],int count[],HFMTree *HT,CodeNode HC[])
{
	clearscreen();
	printf("\n打開存放字符串的文件...\n\n");
	Open(s);                    //打開源碼文件
	SearchStr(s,str,count);  //查找字符串中不同的字符及其出現的次數
	CreatHFMTree(HT,count); //用每個字符出現的次數作為葉子節點的權值建立哈夫曼樹
	HFMCode(*HT,HC,str);      //利用哈夫曼樹對每個葉子節點進行編碼，存入編碼表中
	TotalCoding(s,HC,code); //利用編碼表對字符串進行最終編碼
	printf("\n讀入的字符串為:\n");
	puts(s);
	printf("\n最終的哈夫曼編碼是:\n");
	puts(code);
	printf("\n保存編碼,");
	Save(code);                 //保存最終的哈夫曼編碼
}


void TransCode(char code[],char str[],char ss[],HFMTree *HT,CodeNode HC[])
{
	clearscreen();
	printf("\n打開編碼的文件...\n\n");
	Open(code);                           //打開編碼文件
	DeCoding(code,*HT,str,ss);  //將編碼進行解碼存入字符串數組ss[]中
	printf("\n得到的最終字符串為:\n");
	puts(ss);
	printf("\n保存譯碼，");
	Save(ss);                        //保存譯碼后的字符串
}

void main()
{
	//主函數
	char s[M],ss[M];         //定義字符串數組，s[]存放將要編碼的字符串，ss[]存解碼后的字符串
	char str[N];             //存放輸入的字符串中n個不同的字符
	int count[N];            //存放n個不同字符對應的在原字符串中出現的次數
	char code[M];            //存放最終編碼完成后的編碼
	char choice;
	HFMTree HT;              //定義一個哈夫曼樹的鏈表
	CodeNode HC[N];          //定義一個哈夫曼編碼表的數組，存放每個字符對應的哈夫曼編碼
	do
	{
		clearscreen();
		printf("\n\n");
		printf("                       ************哈夫曼樹************\n");
		printf("                       **                            **\n");
		printf("                       **        1.編碼。            **\n");
		printf("                       **        2.譯碼。            **\n");
		printf("                       **        0.退出。            **\n");
		printf("                       **                            **\n");
		printf("                       **                            **\n");
		printf("                       **                            **\n");
		printf("                       ** 請輸入相應操作的序號(0-2)  **\n");
		printf("                       ********************************\n");
		scanf("%c",&choice);
		getchar();
		switch(choice)
		{
			case '1': Coding(s,str,code,count,&HT,HC);break; //對字符串進行編碼
			case '2': TransCode(code,str,ss,&HT,HC);break;  //對編碼進行解碼
			case '0': break;
			default : printf(" 輸入錯誤！請重新輸入！\n");
		}
	}while(choice!='0');
	
}