哈夫曼.cpp

信息编码的几个小的源程序。进行信息编码。

 /* 函数结果状态代码 */
 #define TRUE 1
 #define FALSE 0
 #define OK 1
 #define ERROR 0
 #define INFEASIBLE -1
 /* #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行 */
 typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
 typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */
#define max 100
typedef struct{
	int weight;
	int parent,lchild,rchild;
}htnode,*huffmantree;
typedef  char  **huffmancode; 
void huffmancoding(huffmantree &ht,huffmancode &hc,int *w,int n){
        char *cd;
		huffmantree p;
	if(n<=1) return;
	int i,m1,m2,l,r;
	int m=2*n-1;
    ht=(huffmantree)malloc((m+1)*sizeof(htnode));
	for(p=ht,i=0;i<=n;i++,p++,w++) 
{ 
p->weight=*w; 
p->parent=0; 
p->lchild=0; 
p->rchild=0; 
} 
for(;i<=m;i++,p++) 
{ 
p->weight=0; 
p->parent=0; 
p->lchild=0; 
p->rchild=0; 
} 
	for(i=1;i<2*n;i++)
		ht[i].parent=ht[i].lchild=ht[i].rchild=0;

//  cout<<"\n每次权值最小的结点及其权值为:\n";
	for(i=n+1;i<=m;++i)//---------------------------构建huffmantree，求两个最小权值结点
	{ 
		m1=m2=32767;
		l=r=0;      //------------------------------------l和r为最小权重的两个结点位置
		for(int k=1;k<i;k++)   
			if(ht[k].parent==0)
				if(ht[k].weight<m1)
				{ m2=m1;   r=l;
				  m1=ht[k].weight;  l=k;
				}
				else if(ht[k].weight<m2)
				{m2=ht[k].weight;   r=k;}
		ht[l].parent=i; ht[r].parent=i;
		ht[i].lchild=l; ht[i].rchild=r;
		ht[i].weight=ht[l].weight+ht[r].weight;
	//	cout<<"第"<<l<<"个结点权值为"<<ht[l].weight<<"，第"<<r<<"个结点权值为"<<ht[r].weight<<endl;
	}
//----------------------------------------------------------------分配n个字符编码的头指针向量	
	hc=(huffmancode)malloc((n+1)*sizeof(char * ));
//----------------------------------------------------------------分配求编码的工作空间    
	cd=(char * )malloc(n * sizeof(char *));
//----------------------------------------------------------------编码结束符     
	cd[n-1]='\0'; 
      for(i=1;i<=n;++i){    //------------------------------------逐个字符求赫夫曼编码
           int start=n-1;            //---------------------------编码结束符位置
           for(int c=i,f=ht[i].parent;f!=0;c=f,f=ht[f].parent)  
//----------------------------------------------------------------从叶子到根逆向求编码
                if(ht[f].lchild==c)  cd[--start]='1';
                else                 cd[--start]='0'; 
		hc[i]= (char * )malloc((n-start) * sizeof(char *));
//----------------------------------------------------------------为第i个字符编码分配空间
		  strcpy(hc[i],&cd[start]);  //---------------------------从cd复制编码(串)到hc
      }
      free(cd);
}
void hafuman()
{
	huffmantree ht;
	huffmancode hc;
    int n,i;
	int *w;
	cout<<"元素个数：";
	cin>>n;
	w=(int *)malloc((n+1)*sizeof(int *));
	for(i=1;i<=n;i++){
		cout<<"第"<<i<<"个元素的权重为";
		cin>>w[i];
	}
	huffmancoding(ht,hc,w,n);
	cout<<endl<<"输出哈夫曼编码："<<endl;   //-------------------------------输出哈夫曼编码
	for(i=1;i<=n;i++)
			cout<<"第"<<i<<"个元素的编码为:"<<hc[i]<<endl;
}