huffmanalgo.h

本代码是基于VC++用C语言编写的哈弗曼编码 调试已通过 可使用 程序有待改善之处是译码程序没有

//哈弗曼算法
//作者：kenneth
//时间：12.1


//------初始化结点--------------
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;                     //标记未构造的结点
		T[i].lchild=0;
		T[i].rchild=0;
	}
}//InitHT


void Select(HTNode HT[],int n,int *a1,int *a2)
{
/*选择森林中，根结点的权值最小和次小的两个树，
*将其根结点的下标号记入s1和s2中
	*/
	int i,j, k;
	float min;
	int index[2]={0,0};   //存最小和次小下标
	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];
}


//函数名：    HuffmanCoding(HTNode HT[],unsigned in t n)
//函数功能：构造哈弗曼树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)                     //构造哈弗曼树
	{
	    
		Select(HT, i, &s1, &s2);              //在HT中选择parent为0，且权值最小的两个结点，其序号分别为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)   //判断当前字符是否已记录过， 是则跳过
						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);
}
	

//函数名：GetNodeCode(HTNode HT[],int n) 
//函数功能：求每个结点编码
//------从叶子结点到根结点逆向求每个字符的哈弗曼编码-----
void GetNodeCode(HTNode HT[],int n)
{
	int start,i,f,c,j;
	char cd[10];   //存临时编码变量
                                     //结束编码符
	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中复制编码串到HC
		  HT[i].code[start]='\0';
		}
	}
//	free(cd);
}


//函数名：*Get_Telegram_Code(char *Telegram,int n) 
//函数功能：得到电文编码
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)    //若电文当前字母为字符串结束字符则退出循环
	{
		k=0;        //每次找前对k赋0
		for(i=0;i<52;i++)
		{
			if(*str0==M_Souce[i])    //在码源中找到该码	
				k++;
		}
		if(k == 0) return (1);       //电文中有非法字符
		str0++;
	}

     return (0);                    //电文中没有非法字符  
}