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;   //释放工作空间
}```