www.pudn.com > haffman.zip > HUFF_MAN.h, change:2009-11-15,size:2830b


//**************************************************************************************** 
//日期:2009年11月14日 
//作者:040840114 柯文炜 
//题目:赫夫曼编码 
//**************************************************************************************** 
 
#include<iostream> 
using namespace std; 
#include<string.h> 
 
typedef struct{ 
	unsigned int weight; 
	unsigned int parent,lchild,rchild; 
}HTNode,*HuffmanTree;        //动态分配数组存储赫夫曼树 
 
typedef char ** HuffmanCode; //动态分配数组存储赫夫曼编码表 
 
void Select(HuffmanTree HT,int n,int &s1,int &s2)   //查找最小的两个点,最小为s1,次小为s2 
{ 
	int i=1,j; 
	for(i=1;i<=n;i++)                //两个for语句确定s1,s2的初值 
	{ 
		if((HT+i)->parent==0) 
		{ 
			s1=i; 
			break; 
		} 
			 
	} 
	for(j=i+1;j<=n;j++) 
	{ 
		if((HT+j)->parent==0) 
		{ 
			s2=j; 
			break; 
		} 
	} 
	if((HT+s1)->weight>(HT+s2)->weight)          
	{ 
		s1=i; 
		s1=s2; 
		s2=i; 
	}   
 
 
	/*for(i = 1;i <= n;i++)              //找到最小的s1 
		if(((HT+s1)->weight>(HT+i)->weight)&&((HT+i)->parent==0)&&(s2!=i)) s1=i;  
	for(j = 1;j <= n;j++)              //找到次小的s2 
		if(((HT+s2)->weight>(HT+j)->weight)&&((HT+j)->parent==0)&&(s1!=j)) s2=j; */ 
 
 
	for(i=1;i<=n;i++)   //在一趟中实现查找s1和s2   
	{ 
		if(((HT+i)->parent==0)&&((HT+s2)->weight>(HT+i)->weight)) 
		{ 
			if(((HT+s1)->weight>(HT+i)->weight)) 
			{ 
				s2=s1; 
				s1=i; 
			} 
			else if(s1!=i) 
			{ 
				s2=i; 
			} 
		}   
	} 
} 
 
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int * w,int n) //w存放n个字符的权值(均大于零),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC 
{ 
	int m,s1,s2,i,start; 
	int c,f; 
	char *cd; 
	if(n<=1) return; 
	m=2*n-1; 
	HT=new HTNode [m+1]; 
	for(i=1;i<=n;i++) 
	{ 
		(HT+i)->weight=*(w+i); 
		(HT+i)->parent=0; 
		(HT+i)->lchild=0; 
		(HT+i)->rchild=0; 
	} 
	for(;i<=m;i++) 
	{ 
		(HT+i)->weight=0; 
		(HT+i)->parent=0; 
		(HT+i)->lchild=0; 
		(HT+i)->rchild=0; 
	} 
    for(i=n+1;i<=m;i++)    //建赫夫曼树 
	{ 
		Select(HT,i-1,s1,s2);      //在HT[1...i-1]选择parent为0,且weight最小的两个结点,其序号分别为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; 
	} 
	//      从叶子到根逆向求每个字符的赫夫曼编码 
	HC=new char* [n+1];       //分配n个字符编码的头指针向量 
    cd=new char [n];          //分配求编码的工作空间 
    *(cd+n-1)='\0';           //编码结束符 
	for(i=1;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)=new char [n-start];   //为第i个字符编码分配空间 
		strcpy(*(HC+i),(cd+start));     //从cd复制编码(串)到HC 
	} 
	delete [n] cd;   //释放工作空间 
}