哈夫曼树
#include<iostream.h>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#define INT_MAX 100000
#define N 10000
typedef struct HTNode//类型定义
{
int weight;
int parent;
int lchild;
int rchild;
char data;
char code[20];
}*HuffmanTree;
void Select(HuffmanTree HT,int end,int &s1,int &s2)
//查找权值最小的两个字符序号
{
int i,j,t;
int min1=INT_MAX;
int min2;
for (i=1;i<=end;i++)
{
if (HT[i].parent==0&&HT[i].weight<min1)
{
s1=i;
min1=HT[i].weight;
}
}
min2=INT_MAX;
for(j=1;j<=end;j++)
{
if (HT[j].parent==0&&(s1!=j)&&min2>HT[j].weight)
{
s2=j;
min2=HT[j].weight;
}
}
if(s1>s2)
{
t=s1;
s1=s2;
s2=t;
}
}
void Initialization(HuffmanTree &ht,int a,int b)
//初始化HuffmanTree,建立该树
{
int i,start,f,c,s1,s2;
char *cd;
char *str;
int *w;
str=new char[a+1];
w=new int[a+1];
cout<<"输入源字符:"<<endl;
for(i=1;i<=a;i++)
//初始化输入字符时,注意:应连续输入,再按回车键!
cin>>str[i];
cout<<"输入权值:"<<endl;
for(i=1;i<=a;i++)
cin>>w[i];
ht=new HTNode[b+1];
for(i=1;i<=a;i++)
{
ht[i].weight=w[i];
ht[i].parent=0;
ht[i].lchild=0;
ht[i].rchild=0;
ht[i].data=str[i];
}
for(;i<=b;i++)
{
ht[i].weight=0;
ht[i].parent=0;
ht[i].lchild=0;
ht[i].rchild=0;
ht[i].data='\0';
ht[i].code[0]='\0';
}
for(i=a+1;i<=b;i++){
Select(ht,i-1,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;
}
cd=new char[a];
cd[a-1]='\0';
for(i=1;i<=a;++i)
//求出各字符相应的编码
{
f=ht[i].parent;
c=i;
start=a-1;
while(f!=0)
{
if(ht[f].lchild==c)
cd[--start]='0';
else
cd[--start]='1';
c=f;
f=ht[f].parent;
}
strcpy(ht[i].code,&cd[start]);
}
}
void Encoding(HuffmanTree ht)
//要求输入报文,然后编码!
{
int i=0,j;
char str[N];
cout<<"输入要编译的字符"<<endl;
cin>>str;
cout<<endl<<"编译后的字符为:"<<endl;
while(str[i]!='\0')
{
j=1;
while(ht[j].data!=str[i])j++;
cout<<ht[j].code;
i++;
}
cout<<endl<<endl;
}
void Decoding(HuffmanTree ht,int m)
//要求输入原码,进行译码!
{
int i=0,p;
char s[N];
cout<<"输入要译回的数字(二进制):"<<endl;
cin>>s;
cout<<"其真实字符为:"<<endl;
p=m;
while(s[i]!='\0')
{
while(ht[p].lchild!=0&&s[i]!='\0')
{
if(s[i]=='0')
p=ht[p].lchild;
else
p=ht[p].rchild;
i++;
}
cout<<ht[p].data;
p=m;
} cout<<endl<<endl;
}
void print(HuffmanTree ht,int n,int m)
//打印HuffmanTree到输出端
{
int i;
cout<<"下面将列出创建哈夫曼树的结果:"<<endl<<endl;
cout<<"loc"<<'\t'<<"w"<<'\t'<<"par"<<'\t'<<"lch"<<'\t'<<"rch"<<'\t'<<"data"<<'\t'<<"code"<<endl;
for(i=1;i<=m;i++)
cout<<i<<'\t'<<ht[i].weight<<'\t'<<ht[i].parent<<'\t'<<ht[i].lchild<<'\t'<<ht[i].rchild<<'\t'<<ht[i].data<<'\t'<<ht[i].code<<'\t'<<endl;
}
void main()
{
int n,m;
char a,b;
HuffmanTree HT=NULL;
while(b!='Q')
//系统界面……
{
cout<<"请选择要进行的操作:"<<endl;
cout<<"创建哈夫曼树型结构(I)"<<'\t'<<"编码(E)"<<'\t'<<"译码(D)"<<'\t'<<"输出(P)"<<'\t'<<"退出程序(Q)"<<endl;
cin>>a;
switch(a){
case 'I':
cout<<"输入哈夫曼 源字符的个数:"<<endl;
cin>>n;
m=2*n-1;
Initialization(HT,n,m);
break;
case 'E':
Encoding(HT);
break;
case 'D':
Decoding(HT,m);
break;
case 'P':
print(HT,n,m);
break;
case 'Q':
b='Q';
break;
}
}
}