#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int s1,s2,selfnumber; //s1,s2存储最小和次小的两个结点，selfnumber存储出现字符个数
//构造HuffmanTree类型
typedef struct
{
char self; //字符存储
int weight; //权值存储
int parent ,lchild,rchild; //结点存储
int bl; //存在判断
}HuffmanTree;
//构Huffman编码临时存储类型
typedef struct
{
char cd[900]; //编码临时存储
int start; //编码起始点
}HuffmanCode;
//存储Huffman编码
typedef struct
{
char self; //字符存储
char code[900]; //编码存储
}codesaver;
//字符->编码，编码->字符的查询
void codesearch(codesaver cd[])
{
char c,ch[900],ch1; //ch1存储要查询的字符，ch[]存储要查询的编码，c作判断
int i;
while(1)
{
cout<<"/n Press 'c' to search the char/n"<<endl;
cout<<"/n Press 'd' to search the code/n"<<endl;
cout<<"/n Press other to exit/n"<<endl;
cin>>"%c">>&c;
getchar();
if(c=='c')
{
cout<<"/n Input the char :"<<endl;
cin>>"%c">>&ch1; //输入要查询的字符
getchar();
for(i=0;i<selfnumber;i++)
{
if(cd[i].self==ch1) //如遇相同则打印，否则退出
{
cout<<"/n The code is : %s/n"<<cd[i].code<<endl;
break;
}
if(i==selfnumber-1)
{
cout<<"/n Not find!/n"<<endl;
}
}
}
else if(c=='d')
{
cout<<"/n Input the code :"<<endl;
cin>>"%s">>ch; //输入要查询的编码
getchar();
for(i=0;i<selfnumber;i++)
{
if(strcmp(cd[i].code,ch)==0) //如遇相同则打印，否则退出
{
cout<<"/n The char is : %c/n"<<cd[i].self<<endl;
break;
}
if(i==selfnumber-1)
{
cout<<"/n Not find!/n"<<endl;
}
}
}
else
{
break;
}
}
return;
}
//打印Huffman编码
void PrintHuffmanCode(HuffmanTree tree[],HuffmanCode code[],codesaver cd[])
{
int i,j,k;
cout<<"/n Print Huffman Code:/n"<<endl;
for(i=0;i<selfnumber;i++)
{
cout<<" %c :"<<tree[i].self<<endl; //打印字符
cd[i].self=tree[i].self;
j=0;
for(k=code[i].start;k<=selfnumber;k++) //打印编码
{
cout<<" %c "<<code[i].cd[k]<<endl;
cd[i].code[j]=code[i].cd[k];
cd[i].code[j+1]=0;
j++;
}
cout<<"/n";
}
}
//构造Huffman编码
void CreateHuffmanCode(HuffmanTree tree[],HuffmanCode code[])
{
int i,f,c;
HuffmanCode d;
for(i=0;i<selfnumber;i++)
{
d.start=selfnumber+1;
c=i;
f=tree[i].parent;
while(f!=0)
{
if(tree[f].lchild==c) //左转为0
d.cd[--d.start]='0';
else
d.cd[--d.start]='1'; //右转为1
c=f;
f=tree[f].parent;
}
code[i]=d;
}
}
//找寻parent为0,权最小的两个节点
void select(HuffmanTree tree[],int k)
{
int i;
for (i=0;i<=k && tree[i].parent!=0 ;i++); s1=i; //判断双亲是否为0
//寻找最小和次小结点
for (i=0;i<=k;i++)
if (tree[i].parent==0 && tree[i].weight<tree[s1].weight) s1=i;
for (i=0; i<=k ; i++)
if (tree[i].parent==0 && i!=s1) break; s2=i;
for (i=0;i<=k;i++)
if ( tree[i].parent==0 && i!=s1 && tree[i].weight<tree[s2].weight) s2=i;
}
//生成HuffmanTree
void CreateHuffmanTree(HuffmanTree tree[],int *w)
{
int m,i;
m=2*selfnumber-1; //m为结点个数
for (i=0;i<selfnumber;i++) //初始化树但保留权值
{
tree[i].parent=0;
tree[i].lchild=0;
tree[i].rchild=0;
}
for (i=selfnumber+1;i<=m;i++)
{
tree[i].parent=0;
tree[i].lchild=0;
tree[i].rchild=0;
}
for (i=selfnumber+1;i<=m;i++)
{
select(tree, i-1); //寻找最小和次小结点
tree[s1].parent=i;
tree[s2].parent=i;
tree[i].lchild=s1;
tree[i].rchild=s2;
tree[i].weight =tree[s1]. weight+ tree[s2].weight; //新结点权值等于最小和次小相加
}
}
//根据字符出现次数进行权值累加
void weightadd(HuffmanTree tree[95])
{
FILE *fp;
char name[900],ch;
int i;
while(1)
{
cout<<"/n Input the file name:"<<endl;
cin>>name;
fp=fopen(name,"r");
if(fp==NULL) //判断文件是否为空
{
cout<<"/n The file can not be find!/n"<<endl;
}
else
break;
}
cout<<"/n"<<endl;
while(!feof(fp)) //读文件
{
ch=fgetc(fp);
cout<<"%c"<<ch<<endl;
for(i=0;i<95;i++)
{
if(tree[i].self==ch) //如遇相同字符则自加一次
{
tree[i].weight++;
tree[i].bl=1;
}
}
}
cout<<"/n"<<endl;
fclose(fp);
for(i=0;i<95;i++) //统计文章中字符个数存入selfnumber中
{
if(tree[i].bl==1)
selfnumber++;
}
};
int main(int argc, char* argv[])
{
while(1)
{
int i,w[95],j=0;
HuffmanTree tree[95],newtree[95]; //95为字符种类最大数
HuffmanCode code[95];
codesaver cd[95];
selfnumber=0;
for(i=32;i<=126;i++) //HuffmanTree的初始化赋值
{
tree[i-32].self=i;
tree[i-32].weight=0;
tree[i-32].parent=0;
tree[i-32].lchild=0;
tree[i-32].rchild=0;
tree[i-32].bl=0;
}
for(i=0;i<95;i++)
{
w[i]=tree[i].weight;
}
weightadd(tree); //调用函数进行权值累加
cout<<"/n";
if(selfnumber!=0&&selfnumber!=1)
{
for(i=0;i<95;i++)
{
w[i]=tree[i].weight;
}
for(i=0;i<95;i++) //将出现的字符存入新树中
{
if(tree[i].bl==1)
{
newtree[j].self=tree[i].self;
newtree[j].weight=tree[i].weight;
newtree[j].parent=0;
newtree[j].lchild=0;
newtree[j].rchild=0;
j++;
}
}
CreateHuffmanTree(newtree,w); //构造HuffmanTree
CreateHuffmanCode(newtree,code); //构造Huffman编码
PrintHuffmanCode(newtree,code,cd); //打印Huffman编码
codesearch(cd); //对字符和编码的查找
}
else
{
cout<<"/n There is on or only one words in it!/n"<<endl;
}
}
return 0;
}
