//哈弗曼算法
//作者：kenneth
//時間：12.1


//------初始化結(jié)點(diǎn)--------------
void InitT(unsigned int n)
{
	int i,m;
	m=2*n-1;
	for(i=0;i<m;i++)
	{
		
	    T[i].data=0;
		T[i].weight=0;
		T[i].selected=0;
		T[i].parent=-1;                     //標(biāo)記未構(gòu)造的結(jié)點(diǎn)
		T[i].lchild=0;
		T[i].rchild=0;
	}
}//InitHT


void Select(HTNode HT[],int n,int *a1,int *a2)
{
/*選擇森林中，根結(jié)點(diǎn)的權(quán)值最小和次小的兩個樹，
*將其根結(jié)點(diǎn)的下標(biāo)號記入s1和s2中
	*/
	int i,j, k;
	float min;
	int index[2]={0,0};   //存最小和次小下標(biāo)
	for(i = 0; i < 2; i++)
	{
		j=0;
		while(HT[j].selected!=0) j++;
		min=HT[j].weight;         
	    for(k = j, index[i] =k;k<n; k++)
		{

		  if(min > HT[k].weight && HT[k].selected == 0)
		  {
			  min=HT[k].weight;
			  index[i]=k;
		  }	
		}
	   HT[index[i]].selected=1;
	 }
	*a1=index[0];
	*a2=index[1];
}


//函數(shù)名：    HuffmanCoding(HTNode HT[],unsigned in t n)
//函數(shù)功能：構(gòu)造哈弗曼樹HT，
//          
void HuffmanCoding(HTNode HT[],unsigned int n)
{
	unsigned int m,i;
	int s1,s2;
	if(n <= 1)
	 return;
	m = 2*n -1;
	                    
	for(i=n; i<m; ++i)                     //構(gòu)造哈弗曼樹
	{
	    
		Select(HT, i, &s1, &s2);              //在HT中選擇parent為0，且權(quán)值最小的兩個結(jié)點(diǎn)，其序號分別為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;
	}
	
	
}//HuffmanCoding


//手動獲得字符概率
void Get_P(char *Telegram,FILE *fp,int n)
{
	int i,j,t=0,k=0;
	char p,*str0;
	str0=Telegram;
	while(*str0)    
	{
		p=*str0;
		fputc(p,fp);
		for(i=0;i<53;i++)
		{
			if(p==M_Souce[i])    //在碼源中找到改碼
			{	
				
				for(j=0;j <= k;j++)
				{
					if(T[j].data==p)   //判斷當(dāng)前字符是否已記錄過， 是則跳過
						t++;   
				}
				if(t==0)
				{ 
					T[k].data=p;
		            printf("請輸入字符 %c 的概率值:",T[k].data);
					scanf("  %f",&T[k].weight);
					k++;
				}  //獲得字符和概率
				if(t!=0) t=0;
				
			}
		
				
		}
		str0++;
	}
	fclose(fp);
}
	

//函數(shù)名：GetNodeCode(HTNode HT[],int n) 
//函數(shù)功能：求每個結(jié)點(diǎn)編碼
//------從葉子結(jié)點(diǎn)到根結(jié)點(diǎn)逆向求每個字符的哈弗曼編碼-----
void GetNodeCode(HTNode HT[],int n)
{
	int start,i,f,c,j;
	char cd[10];   //存臨時編碼變量
                                     //結(jié)束編碼符
	for(i=0; i < n; i++)
	{
		start = 0;
		for(c=i, f=HT[i].parent; f != -1; c=f, f=HT[f].parent)  
		{
			
			if(HT[f].lchild == c) 
				cd[start++]='0';
			else if(HT[f].rchild == c)
				cd[start++]='1';
		}
		for(j=0;j<start;j++)
		{HT[i].code[j]=cd[start-j-1];                             //從cd中復(fù)制編碼串到HC
		  HT[i].code[start]='\0';
		}
	}
//	free(cd);
}


//函數(shù)名：*Get_Telegram_Code(char *Telegram,int n) 
//函數(shù)功能：得到電文編碼
void Get_Telegram_Code(char *Telegram,FILE *fp,int n)
{
	
	int i,j;
	printf("該電文的編碼:\n");
	while(*Telegram)
	{
		for(i=0;i < n;i++)
		{
			if( *Telegram == T[i].data)    //查到則打印出碼字
			{
                for(j=0;T[i].code[j] != '\0'; j++)
				fputc(T[i].code[j],fp);
                printf("%s",T[i].code);
				break;   //找到該字符編碼 跳下一個字符搜索
			}
		}
		Telegram++;
	}
	printf("\n");
	fclose(fp);

}


//檢測非法字符
int Check_Character(char *Telegram)
{

	int i,k=0;
	char *str0;
	str0=Telegram;    //將電文首地址賦給指針str0
	while(*str0)    //若電文當(dāng)前字母為字符串結(jié)束字符則退出循環(huán)
	{
		k=0;        //每次找前對k賦0
		for(i=0;i<52;i++)
		{
			if(*str0==M_Souce[i])    //在碼源中找到該碼	
				k++;
		}
		if(k == 0) return (1);       //電文中有非法字符
		str0++;
	}

     return (0);                    //電文中沒有非法字符  
}