*/ --------------------------------------------------------------------------------------
*/ 出自： 编程中国 http://www.bc-cn.net
*/ 作者： 风动 E-mail：xidiankeda492@yahoo.com.cn QQ：３０５６８７９１０
*/ 时间： 2007-7-21 编程论坛首发
*/ 声明： 尊重作者劳动，转载请保留本段文字
*/ --------------------------------------------------------------------------------------


#include "iostream.h"
#include "math.h"
#include "stdlib.h"
#include <string.h>
#define MAXSIZE 100 //最多子叶数
#define MAXCODE 10000 //编码最大长度

typedef struct
{
char info; //关联字符信息
unsigned int weight; //每个节点的权职
unsigned int parent, lchild, rchild;
}HTNode,*HuffmanTree;

typedef char **HuffmanCode; //存储哈弗曼编码

void Select(HuffmanTree HT, int j,int &s1,int &s2)
{//选择双亲节点为0，并且最小的两个子叶节点
int i=1,m;
while(HT[i].parent!=0)
i++; //找第一个双亲节点为0的子叶结点
for(s2=s1=i;i<j;i++)
{//保证s1中的权值最小，s2次小
if(HT[i].parent==0 && HT[i].weight<HT[s1].weight)
{
s2=s1;
s1=i;
}
else if(HT[i].parent==0 && HT[i].weight>=HT[s1].weight && HT[i].weight<=HT[s2].weight)
s2=i;
while(HT[i].parent==0 && s1==s2)
{
m=i;
m++;
while(HT[m].parent!=0)
m++;
s2=m;
}
}
}
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n, char *info)
{//哈弗曼编码
int i,m;
HuffmanTree p;
if(n<1) return;
m = 2*n-1;
HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(p=HT+1,i=1;i<=n;++i,++p,++w,++info)
{//初始化所有已存在的子叶信息
p->info = *info;
p->weight = *w;
p->parent = 0;
p->lchild = 0;
p->rchild = 0;
}//for
for(; i<=m;++i,++p)
{//构造所需要的过度根节点
p->weight = 0;
p->parent = 0;
p->lchild = 0;
p->rchild = 0;
}//for
for(i=n+1;i<=m;++i)
{//建立哈弗曼树
int s1,s2;
Select(HT,i-1,s1,s2);
HT[s1].parent =i;
HT[s2].parent =i;
HT[i].lchild = s2;
HT[i].rchild = s1;
HT[i].weight = HT[s1].weight+HT[s2].weight;
}//for
//哈弗曼编码
HC = (HuffmanCode)malloc((n+1)*sizeof(char *));
char* cd = (char*)malloc(n*sizeof(char));
cd[n-1] = '\0';
for(i=1;i<=n;++i)
{
int f;
unsigned int c;
int 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]);
}//for
free(cd);
}//HuffmanCoding

void CheckCoding(HuffmanTree HT, HuffmanCode HC, char *strcheck, int m)
{//查询哈弗曼编码信息
// char *strcopy=new char[MAXCODE];
for(int i=0; i<m; i++)
{
for(int j=1; HT[j].info != strcheck[i]; j++);
cout<<HC[j];
}
cout<<endl;
}//CheckCoding

void HuffmanTranslateCoding(HuffmanTree HT, int n,char*c)
{//译码过程
int m=2*n-1;
int i,j=0;
while(c[j]!='\0')
{
i=m;
while(HT[i].lchild && HT[i].rchild)
{
if(c[j]=='0')
i=HT[i].lchild;
else if(c[j]=='1')
i=HT[i].rchild;
j++;
}
cout<<HT[i].info;
}
cout<<endl;
}
void main()
{
int n,*w,m;
w=new int[MAXSIZE];
char *info;
char *strcheck=new char[MAXSIZE];
info=new char[MAXSIZE];
char *ch=new char[MAXSIZE];
HuffmanTree HT=new HTNode[MAXSIZE];
HuffmanCode HC=NULL;
cout<<"***********************************************************"<<endl;
cout<<"****** HuffmanCode and HUffmanTranslate ********"<<endl;
cout<<"****** 西安电子科技大学 计算机学院 030514班 ********"<<endl;
cout<<"****** 学号： 03051433 制作人：王甲楼 ********"<<endl;
cout<<"***********************************************************"<<endl;
cout<<"读入叶子节点数 n= ";
cin>>n;
for(int i=0; i<n;i++)
{
cout<<"读入第"<<i+1<<"个叶子结点的权值：";
cin>>w[i];
cout<<"读入编码字符: ";
cin>>info[i];
}
HuffmanCoding( HT, HC, w, n,info);
cout<<"读入要查询的字符串中字符个数: ";
cin>>m;
cout<<"读入要编码的字符串: ";
cin>>strcheck;
CheckCoding(HT,HC,strcheck,m);
cout<<"读入编码: "<<endl;
cin>>ch;
HuffmanTranslateCoding(HT,n,ch);
}