#include<stdio.h>
#include<malloc.h>
#include<string.h>
#define CL 16          //編碼的長度
#define NULL 0
#define N 50          //用于存儲基本字符集的字符數(shù)組的長度
#define TL 50         //電文長度
typedef struct
{
	unsigned int weight;
	unsigned int parent,lchild,rchild;
	char date;
}HTNode,*HuffmanTree;
typedef char**HuffmanCode;

void Select(HuffmanTree &HT,unsigned n,int&s1,int&s2)
{// 在HT[1..i-1]中選擇parent為0且weight最小的兩個結(jié)點
	int min=-1;
	for(unsigned i=1;i<=n;i++)
	{
		if(min<0&&HT[i].parent==0){min=HT[i].weight;s1=i;}
		else if(min>HT[i].weight&&HT[i].parent==0){min=HT[i].weight;s1=i;}
	}
	min=-1;
	for(unsigned j=1;j<=n;j++)
	{
		if(min<0&&HT[j].parent==0&&j!=s1){min=HT[j].weight;s2=j;}
		else if(min>HT[j].weight&&HT[j].parent==0&&j!=s1){min=HT[j].weight;s2=j;}
	}
}

void InitHfmTree() 
{ // w存放n個字符的權(quán)值(均>0)，構(gòu)造哈夫曼樹HT, 并求出n個字符的哈夫曼編碼HC
  FILE*fp;
  HuffmanTree HT;
  int n,i,j,s1,s2,root,w[N];   
  char str[N],ch;	
  printf("請輸入字符總數(shù)：\n");
  scanf("%d",&n);
  ch=getchar();  //接收執(zhí)行scanf時最后輸入的回車
  root=2*n-1;
  printf("請輸入字符串：\n");
  gets(str);
  printf("請依次輸入權(quán)值：\n");
	for(i=0;i<n;i++)
	{
		scanf("%d",&w[i]);
		ch=getchar();  //接收執(zhí)行scanf時最后輸入的回車
	}
  if(n<=1)return;
  root=2*n-1;
  HT=(HuffmanTree)malloc((root+1)*sizeof(HTNode));  // 0號單元未用
  for (i=1; i<=n; i++) 
  { //初始化
    HT[i].weight=w[i-1];
    HT[i].parent=0;
    HT[i].lchild=0;
    HT[i].rchild=0;
	HT[i].date=str[i-1];
  }
  for (i=n+1; i<=root; i++)
  { //初始化
    HT[i].weight=0;
    HT[i].parent=0;
    HT[i].lchild=0;
    HT[i].rchild=0;
	HT[i].date=14;
  }
  printf("\n哈夫曼樹的構(gòu)造過程如下所示：\n");
  printf("HT初態(tài):\n  結(jié)點  weight  parent  lchild  rchild   date");
  for (i=1; i<=root; i++)
    printf("\n%4d%8d%8d%8d%8d%8c",i,HT[i].weight,HT[i].parent,HT[i].lchild, HT[i].rchild,HT[i].date);
    printf("    按任意鍵，繼續(xù) ...");
  ch=getchar();
  for (i=n+1; i<=root; ++i) 
  {  // 建哈夫曼樹
    Select(HT, i-1, s1, s2);// 在HT[1..i-1]中選擇parent為0且weight最小的兩個結(jié)點，其序號分別為s1和s2。
    HT[s1].parent = i;  HT[s2].parent = i;
    HT[i].lchild = s1;  HT[i].rchild = s2;
    HT[i].weight = HT[s1].weight + HT[s2].weight;
    printf("\nselect: s1=%d   s2=%d\n", s1, s2);
    printf("  結(jié)點  weight  parent  lchild  rchild   date");
    for (j=1; j<=i; j++)
      printf("\n%4d%8d%8d%8d%8d%8c",j,HT[j].weight,HT[j].parent,HT[j].lchild, HT[j].rchild,HT[j].date);
    printf("    按任意鍵，繼續(xù) ...");//程序執(zhí)行暫停
    ch=getchar();
  }
  //---建立文件hfmTree并將哈弗曼樹存入文件---
	if((fp=fopen("htmTree","wb"))==NULL)
	{printf("CANNOT OPEN FILE!\n");return;}
	for(i=1;i<=root;i++)
		if(fwrite(&HT[i],sizeof(HTNode),1,fp)!=1)printf("FILE WRITE ERROR!\n");
	fclose(fp);
	printf("*********哈弗曼樹已存入文件htmTree*********\n");
	free(HT);
} //  HuffmanTree
void EnCoding()//編碼函數(shù)
{ //對電文tbt進行編碼并存儲到文件CodeFile中
	FILE*fp;
	char *cd,TBT[TL];
	int  start,root=0,n,tbl;
	unsigned int i,flag=0,c,f;
	HuffmanTree HT;
	HuffmanCode hc,HC;
	HT=(HuffmanTree)malloc((2*N-1)*sizeof(HTNode));
	hc=(HuffmanCode)malloc(TL*sizeof(char*));
	HC=(HuffmanCode)malloc(N*sizeof(char*));
	//---從文件hfmTree讀取哈弗曼樹---
	if((fp=fopen("htmTree","rb"))==NULL)
	{printf("CANNOT OPEN FILE!\n");return;}
	flag=fread(&HT[root+1],sizeof(HTNode),1,fp);
	while(flag==1)
	{
		root++;
		flag=fread(&HT[root+1],sizeof(HTNode),1,fp);	
	}
	fclose(fp);
	//--- 從葉子到根逆向求每個字符的哈夫曼編碼 ---
	n=(root+1)/2;
	HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
	cd = (char *)malloc(n*sizeof(char));    // 分配求編碼的工作空間
	cd[n-1] = '\0';                         // 編碼結(jié)束符。
	for (i=1; i<=n; ++i)                    // 逐個字符求哈夫曼編碼
	{                  
		start = n-1;                          // 編碼結(jié)束符位置
		for (c=i, f=HT[i].parent; f!=0; c=f, f=HT[f].parent) // 從葉子到根逆向求編碼
		{
			if (HT[f].lchild==c) cd[--start] = '0';
			else cd[--start] = '1';
		}
		HC[i] = (char *)malloc((n-start)*sizeof(char));// 為第i個字符編碼分配空間
		strcpy(HC[i], &cd[start]);    // 從cd復制編碼(串)到HC
	}	
	free(cd);// 釋放工作空間	
	printf("請輸入電文：\n");
	gets(TBT);
	for(tbl=0;TBT[tbl]!=NULL;tbl++)
	{
		i=1;
		while(TBT[tbl]!=HT[i].date&&TBT[tbl]!=NULL&&HT[i].date!=NULL)i++;
		if(TBT[tbl]==HT[i].date){hc[tbl]=(char*)malloc(CL*sizeof(char));strcpy(hc[tbl],HC[i]);}
		else hc[tbl]=NULL;
	}
	printf("電文編碼如下：\n");
	for(i=0;i<tbl;i++)printf("%s ",hc[i]);
	printf("\n");
	//---建立文件codeFile并將電文編碼存入文件---
	if((fp=fopen("codeFile","wb"))==NULL)
	{printf("CANNOT OPEN FILE!\n");return;}
	for(i=0;i<tbl;i++)
		if(fwrite(hc[i],CL*sizeof(char),1,fp)!=1)printf("FILE WRITE ERROR!\n");
	fclose(fp);
	free(HT);
	free(HC);
	free(hc);	
}//EnCoding
void DeCoding()//譯碼函數(shù)
{
	FILE*fp;
	char TBT[TL];
	int tbl=0,flag=0,root=0;
	HuffmanTree HT=(HuffmanTree)malloc((2*N-1)*sizeof(HTNode));
	HuffmanCode hc=(HuffmanCode)malloc(TL*sizeof(char*));;
	unsigned i,m;
	//---從文件hfmTree讀取哈弗曼樹---
	if((fp=fopen("htmTree","rb"))==NULL)
	{printf("CANNOT OPEN FILE!\n");return;}
	flag=fread(&HT[root+1],sizeof(HTNode),1,fp);
	while(flag==1)
	{
		root++;
		flag=fread(&HT[root+1],sizeof(HTNode),1,fp);	
	}
	fclose(fp);
	//---從文件codeFile讀取電文編碼---
	if((fp=fopen("codeFile","rb"))==NULL)
	{printf("CANNOT OPEN FILE!\n");return;}	
	hc[tbl]=(char*)malloc(CL*sizeof(char));
	flag=fread(hc[tbl],CL*sizeof(char),1,fp);
	while(flag==1)
	{
		tbl++;
		hc[tbl]=(char*)malloc(CL*sizeof(char));
		flag=fread(hc[tbl],CL*sizeof(char),1,fp);
	}
	fclose(fp);
	printf("電文如下：\n");
	for(i=0;i<tbl;i++)
	{	
		m=root;
		int j=0;
		while(HT[m].lchild!=0&&HT[m].rchild!=0&&hc[i][j]!=NULL)
		{
			if(hc[i][j]=='0'){m=HT[m].lchild;j++;}
			else if(hc[i][j]=='1'){m=HT[m].rchild;j++;}
			else {printf("ERROR!\n");break;}
		}
		TBT[i]=HT[m].date;
	};
	TBT[tbl]=NULL;
	//建立文件textFile并將譯碼結(jié)果存入文件
	if((fp=fopen("textFile","wb"))==NULL)
	{printf("CANNOT OPEN FILE!\n");return;}
	for(i=0;i<tbl;i++)
		if(fwrite(&TBT[i],sizeof(char),1,fp)!=1)printf("FILE WRITE ERROR!\n");
	fclose(fp);
	printf("%s\n",TBT);
}//DeCoding
void Print()//以緊湊格式輸出
{
	FILE*fp;
	HuffmanCode hc=(HuffmanCode)malloc(TL*sizeof(char*));
	int tbl=0,flag=0;
	char str[TL*CL];
	//---從文件codeFile讀取電文編碼---
	if((fp=fopen("codeFile","rb"))==NULL)
	{printf("CANNOT OPEN FILE!\n");return;}	
	hc[tbl]=(char*)malloc(CL*sizeof(char));
	flag=fread(hc[tbl],CL*sizeof(char),1,fp);
	while(flag==1)
	{
		tbl++;
		hc[tbl]=(char*)malloc(CL*sizeof(char));
		flag=fread(hc[tbl],CL*sizeof(char),1,fp);
	}
	fclose(fp);
	strcpy(str,hc[0]);
	for(unsigned i=1;i<tbl;i++)strcpy(str,strcat(str,hc[i]));
	printf("緊湊格式的電文編碼如下：\n");
	for(i=0;str[i]!=NULL;i++)
	{
		printf("%c",str[i]);
		if((i+1)%50==0)printf("\n");
	}
	printf("\n");
	//---建立文件codePrin并將緊湊格式編碼寫入文件---
	if((fp=fopen("codePrin","wb"))==NULL)
	{printf("CANNOT OPEN FILE!\n");return;}
	if(fwrite(str,strlen(str),1,fp)!=1)printf("FILE WRITE ERROR!");
	fclose(fp);
}//Print
void PrintTree()//以凹入表示法輸出
{
	FILE*fp;
	char type,ch=2,**str;
	int flag=0,root=0,level[2*N-1][2],top,n,i,j=0,l,width=4;
	HuffmanTree stack,HT=(HuffmanTree)malloc((2*N-1)*sizeof(HTNode));
	HTNode p;
	HT[0].weight=-1;
	//---從文件hfmTree讀取哈弗曼樹---
	if((fp=fopen("htmTree","rb"))==NULL)
	{printf("CANNOT OPEN FILE!\n");return;}
	flag=fread(&HT[root+1],sizeof(HTNode),1,fp);
	while(flag==1)
	{
		root++;
		flag=fread(&HT[root+1],sizeof(HTNode),1,fp);	
	}
	fclose(fp);
	//------------------------------
	str=(char**)malloc(root*sizeof(char*));
	stack=(HuffmanTree)malloc(root*sizeof(HTNode));
	top=1;
	stack[top]=HT[root];
	level[top][0]=0;
	level[top][1]=2;
	while(top>0)
	{
		l=0;
		str[j]=(char*)malloc(100*sizeof(char));
		p=stack[top];
		n=level[top][0];
		switch(level[top][1])
		{
		case 0:type='0';break;//左節(jié)點之前輸出(0)
		case 1:type='1';break;//右節(jié)點之前輸出(1)
		case 2:type='r';break;//根節(jié)點之前輸出(r)
		}
		//把凹入表示法表示的一行存入一個字符串
		for(i=1;i<=n;i++)str[j][l++]=' ';
		str[j][l++]=p.date;str[j][l++]='(';str[j][l++]=type;str[j][l++]=')';
		for(i=n;i<=root;i++)str[j][l++]=ch;
		str[j][l++]='\0';
		top--;
		if(HT[p.rchild].weight!=-1)
		{
			top++;
			stack[top]=HT[p.rchild];
			level[top][0]=n+width;
			level[top][1]=1;
		}
		if(HT[p.lchild].weight!=-1)
		{
			top++;
			stack[top]=HT[p.lchild];
			level[top][0]=n+width;
			level[top][1]=0;
		}
		j++;
	}
	printf("凹入表示法表示的哈弗曼樹如下：\n");
	for(i=0;i<root;i++)printf("%s\n",str[i]);
	//---建立文件treePrint并將凹入表示法表示的哈弗曼樹寫入文件---
	if((fp=fopen("treePrint","wb"))==NULL)
	{printf("CANNOT OPEN FILE!\n");return;}
	for(i=0;i<root;i++)
		if(fwrite(str[i],strlen(str[i]),1,fp)!=1)printf("FILE WRITE ERROR!");
	fclose(fp);
}//PrintTree
int main()
{
	bool s=1;
	char sw,ch;
	while(s)
	{	
		printf("請選擇操作:\n1:初始化'i'\n2:編碼'e'\n3:譯碼'd'\n4:印代碼'p'\n5:凹入表輸出't'\n6:退出程序'q'\n");
		scanf("%c",&sw);
		ch=getchar(); 
		switch(sw)
		{
		case'i':InitHfmTree();printf("初始化完畢\n");break;
		case'e':EnCoding();printf("編碼完畢\n");break;
		case'd':DeCoding();printf("譯碼完畢\n");break;
		case'p':Print();printf("印代碼完畢\n");break;
		case't':PrintTree();printf("凹入表輸出完畢\n");break;
		case'q':s=0;break;
		default:printf("輸入錯誤!");break;
		}
	}
}