#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
//哈夫曼树存储结构
typedef struct{
char data;
int weight;
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;
void Select(HuffmanTree &HT, int i,int &s1,int &s2)
{
HuffmanTree p=HT;
int tmp;
int tag1,tag2;
tag1=tag2=32767;
//找到两个父节点为0，且权值最小的两个结点
for(int x=1;x<=i;x++)
{ if(p[x].parent==0&&p[x].weight<tag1)
{ tag1=p[x].weight;s1=x;}
}
for(int y=1;y<=i;y++)
{ if(p[y].parent==0&&y!=s1&&p[y].weight<tag2)
{ tag2=p[y].weight;s2=y;}
}
if(s1>s2) //将选出的两个节点中的序号较小的始终赋给s1
{ tmp=s1; s1=s2; s2=tmp;}
}
void creatHuffmanTree(HuffmanTree &HT,int n)
{
int qZ[27]={186,64,13,22,32,103,21,
15,47,57,1,5,32,20,57,
63,15,1,48,51,80,23,8,18,
1,16,1};
char qD[27]={' ','a','b','c','d','e','f',
'g','h','i','j','k','l','m',
'n','o','p','q','r','s','t',
'u','v','w','x','y','z'};
int i;
if(n<=1)
return;
int m = 2*n - 1; //共需生成的结点数
HT = new HTNode[m+1];
for(i = 1; i <= m; ++i)//将1~m号单元双亲，左右孩子初始化为零
{
HT[i].parent = 0;
HT[i].lchild = 0;
HT[i].rchild = 0;
}
for( i=1;i<=n;++i)//对前n个单元中的叶子节点权值及数据赋值
{
HT[i].data = qD[i-1];
HT[i].weight = qZ[i-1];
}
int s1,s2;
for( i=n +1 ;i<=m;++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;
}
}
//建立哈夫曼编码表
void creatHuffmanCode(HuffmanTree HT,HuffmanCode &HC, int n)
{
HC = new char*[n+1];
char *cd;
cd = new char[n];
cd[n-1] = ' ';
int start,c,f;
for (int i= 1;i<=n;++i)
{
start = n-1;
c = i;
f = HT[i].parent;
while(f!=0)
{
--start;
if(HT[f].lchild == c)//左子树为零，右子树为一
cd[start] = '0';
else cd[start] = '1';
c = f;
f = HT[f].parent;
}
HC[i] = new char[n - start];
strcpy(HC[i],&cd[start]);
cout<<HC[i]<<" "<<HT[i].data<<"
";
}
delete cd;
}
//编码
void EnCoding(HuffmanCode &HC,HuffmanTree &HT, int n)
{
cout<<"INput your scentece_
";
char input;
input=getchar();
while(input != '#')
{
int i;
for(i=1;i<=n;i++)
{
if(input == HT[i].data)
cout<<HC[i];
}
input=getchar();
}
}
//译码
void DeCoding(HuffmanTree &HT,HuffmanCode &HC,int n)
{
cout<<"input Binray__"<<endl;
char input[10000],scen[10000]={' '};
cin>>input;
int f,i,j,k;
i=j=k=0;
while (input[i])
{
f=2*n-1;
while(HT[f].lchild!=0)//以f对应的节点的左孩子的值==0作为结束
{
if (input[j] =='0')
f=HT[f].lchild;
else if(input[j] == '1')
f=HT[f].rchild;
j++;
}
i=j;
scen[k]=HT[f].data;
k++;
}
if(i == strlen(input))
cout<<scen;
else
cout<<"Input error";
}
int main()
{
HuffmanTree HT;
HuffmanCode HC;
creatHuffmanTree(HT,27);
creatHuffmanCode(HT,HC,27);
char input;
LOOP:
cout << "E:EnCoding"<<endl;
cout<<"D:DeCoding"<<endl;
cin>>input;
switch(input)
{
case 'E': EnCoding(HC,HT,27); break;
case 'D': DeCoding(HT,HC,27); break;
default: goto LOOP;
}
return 0;
}