main.cpp

霍夫曼编码算法

#include <cstdlib>
#include <iostream>
#include <string.h>

using namespace std;

typedef struct HTNode{
	unsigned int weight;
	unsigned int parent,lchild,rchild;
} *HuffmanTree;

typedef char **HuffmanCode;
typedef char *ss;

ss s;

void Select(HuffmanTree HT,int mark,int & s1,int & s2)
{
	HuffmanTree p;
	p=HT;
	if(!p)
	{
		cout<<"链表为空."<<endl; 
	   return ;
		}
		
	int min1,min2,i,j;
	i=0;
	while((p->parent)&&(i<mark)) //找到第一个parent为0的节点
  {
	  p++; 
		i++;
	}
//	cout<<"到达第"<<i<<"个节点"<<endl;
//	cout<<"HT["<<i<<"]  weight="<<HT[i].weight<<endl;
	 
	if(i==mark)  return;
	
	min1=min2=(p)->weight;
//	cout<<"min1="<<min1<<"  min2="<<min2<<endl;
	s1=s2=i;
	i++;
	p++;
	
//	cout<<"进入比较循环前i="<<i<<endl;
	 
	for(;i<mark;i++)
	{
		  if(p->parent)		  
		    p++;
		  else       //找到parent为0的节点 
		  {
	//			 cout<<"HT["<<i<<"].weight="<<p->weight<<endl;
				 
				 if(p->weight<min2)
				 {
						if(p->weight<min1)
						{
							min2=min1;
							s2=s1;
							min1=p->weight;
							s1=i;							
						}
						else if(p->weight>min1)
						{
							  min2=p->weight;
							  s2=i;
						}
				 }
				 else
				 {
						if(min1==min2)
						{
						   min2=p->weight;
						   s2=i;
							}
						   
					}
	//			 cout<<"比较后s1.s2分别为"<<s1<<"  "<<s2<<endl; 
				 p++;
			}		
	}
}

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{   //w存放n个字符的权值（都大于0），构造哈弗曼树HT，并求出n个字符的哈弗曼编码HC 
	if(n<=1)
	   return ;
	int m=2*n-1;
	int i,c,start,f;
	int s1;
	int s2;
	HT=(HuffmanTree)malloc(m*sizeof(struct HTNode));  //存放2n-1个节点 
	HuffmanTree p=(HuffmanTree)malloc(sizeof(struct HTNode));  //链表动态指针 
	for(p=HT,i=0;i<n;++i,++p,++w)    //对实值节点进行初始化 
	{
	  (*p).weight=(*w);
	  (*p).parent=(*p).lchild=(*p).rchild=0;
	}
	for(;i<m;++i,++p)                //对除n个字符节点之外的n-1个节点进行初始化 
	{
		(*p).weight=0;
	  (*p).parent=(*p).lchild=(*p).rchild=0;
	}
	
//	for(i=0;i<m;i++)
///	{
//		cout<<"HT["<<i<<"]   weight="<<HT[i].weight<<"  parent="<<HT[i].parent<<endl;
//	}
	
	for(i=n;i<m;++i)                 //建立Haffman树关系 
	{
		Select(HT,i,s1,s2);           //从HT[1，i-1]中选择parent为0且weight最小的两个节点，序号分别为s1,s2 
//	  cout<<"s1="<<s1<<"s2="<<s2<<endl;
		HT[s1].parent=HT[s2].parent=i;
	  HT[i].lchild=s1;                  //规定左孩子是最小的元素，右孩子是次小的元素 
	  HT[i].rchild=s2;
	  HT[i].weight=HT[s1].weight+HT[s2].weight;	//权值相加	 
	}	
	HC=(HuffmanCode)malloc(n*sizeof(char *));   //分配器n个字符编码的头指针 
	char * cd=(char *)malloc(n*sizeof(char));              //分配球编码的工作空间 
	cd[n-1]='\0';                                   //编码的结束符 
	for(i=0;i<n;++i)                               //逐个字符求哈弗曼编码 
	{
		start=n-1;                                    //编码的结束位置 
		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));
		strcpy(HC[i],&cd[start]);	
    cout<<"字符"<<s[i]<<"的编码为："<<HC[i]<<endl;	
	}
	free(cd);	
}


int main(int argc, char *argv[])
{
	  HuffmanTree HT;
		int *w;
		int len,i;
		HuffmanCode hfc;	
		
    cout<<"输入字符总数：TN=";
		cin>>len;
		w=new int[len];
		s=new char[len+1];
		for(i=0;i<len;i++)
		{
			cout<<"输入字符:";
			cin>>s[i];
			cout<<"输入该字符的权值:";
			cin>>w[i];			
		}
		s[i]='\0';		
		HuffmanCoding(HT,hfc,w,len);	
		cout<<"原报文序列为:"<<s<<endl;
		cout<<"编码报文为  :";
		for(i=0;i<len;i++)
		  cout<<hfc[i]<<" ";
		cout<<endl;	
    system("PAUSE");
    return EXIT_SUCCESS;
}