//huffman树和huffman编码
#include <stdlib.h>
#include <iostream.h>
#include <stdio.h>
#include <string.h>
#define OVERFLOW -1
typedef struct
{
char letter;
int weight;
int parent;
int lchild;
int rchild;
}HTNode,*HuffmanTree;
typedef char * *HuffmanCode;
void Select(HuffmanTree &HT,int i,int &s1,int &s2)
{
/*选择森林中，根结点的权值最小和次小的两个树，
*将其根结点的下标号记入s1和s2中
*/
int j, k;
for(k = 1; k < i; k++)
{
if(HT[k].parent != NULL)
continue;
s1 = k;/*init the number*/
break;
}
for(j = 1; j < i; j++)
{
if(HT[j].parent != NULL)
continue;
if(HT[j].weight < HT[s1].weight)
s1 = j;
}
for(k = 1; k <= i; k++)
{
if(HT[k].parent != NULL || k == s1)
continue;
s2 = k;
break;
}
for(j = 1; j < i; j++)
{
if(HT[j].parent != NULL)
continue;
if(HT[j].weight <= HT[s2].weight && j != s1)
s2 = j;
}
}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,char *zi,int *w,int n)
{
HuffmanTree p;
int m,i,s1,s2,f,c;
int Istart = 1;
char *cd;
if(n <= 1)
return;
m = 2*n-1;
if(!(HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode))))
exit(OVERFLOW);
for(p=HT+1,i=1;i<=n;++i,++zi,++p,++w)
{
/*生成独立的森林*/
p->parent = NULL;
p->letter = *zi;
p->lchild = NULL;
p->rchild = NULL;
p->weight = *w;
}
for(;i<=m;++i,++p)
{
(*p).weight=0;
(*p).parent=0;
(*p).lchild=0;
(*p).rchild=0;
}
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;
}
HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
cd=(char*)malloc(n*sizeof(char));/*临时的code存储*/
cd[n-1]='\0';
for(i=1;i<=n;++i)
{
Istart = n - 1;
/*按已生成的哈夫曼树，得到各个字符的哈夫曼编码
*/
for(c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent)
if(HT[f].lchild == c)
cd[--Istart] = '0';
else
cd[--Istart] = '1';
HC[i] = (char *)malloc((n - Istart) * sizeof(char));
strcpy(HC[i], &cd[Istart]);
}
free(cd);
}
void main()
{
HuffmanTree HT;
HuffmanCode HC;
int i,j,yu;
char zi[9]={'A','B','C','D','E','F','G','H'};
int w[100];
char z;
char c[100];
z='A';
cout<<endl;
for(i=0;i<=7;i++)
{
cout<<"please input the weight for "<<z<<":";
cin>>w[i];
z++;
}
HuffmanCoding(HT,HC,zi,w,8);
cout<<endl;
cout<<"char weight huffmancode "<<endl;
for(i=1;i<=8;i++)
cout<<HT[i].letter<<" "<<HT[i].weight<<" "<<HC[i]<<endl;
cout<<"please input the text:";
cin>>c;
cout<<"The code is:";
for(i=0; i < strlen(c); i++)
/*根据字符的哈夫曼编码，将输入的文本（变量c表示的）翻译成电码。
*/
cout<<HC[(c[i] - 'A' + 1)];
cout<<endl;
cout<<"Enter the code:";
cin>>c;
j=strlen(c);
yu=15;
i=1;
cout<<"The text is:";
while(i <= j)
{
while(HT[yu].lchild != 0)/*因为是完全二叉树*/
{
if(c[i-1] == '0')
{
/*用哈夫曼树，将输入的电码（变量c表示的）翻译成文本，
说明：变量名c在程序中
*/
yu = HT[yu].lchild;
i++;
continue;
}
if(c[i-1]== '1')
{
yu=HT[yu].rchild;
i++;
continue;
}
}
/*显示由部分电码译码得到的字符，并准备对后面的电码进行译码*/
cout<<HT[yu].letter;
yu = 15;
}
cout<<endl;
}
//没有出错处理
