#include
#include
using namespace std
int Count(int cou[]) //计算输入的字母的个数
{
char word;
char letter[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'};
fstream SourceFile;
SourceFile.open("SourceFile.txt",ios::in);
if (!SourceFile)
{
cout<<"Can't open this file"<<endl;
}
while (!SourceFile.eof())
{
SourceFile.get(word);
if (word>='A'&&word<='Z')
{
word=word+32;
}
int i=word-96;
cou[i]++;
}
SourceFile.close();
cout<<"letter"<<'\t'<<'\t'<<"频率为"<<endl;
for (int j=1;j<=26;j++)
{
if (cou[j]!=0)
{
cout<<letter[j]<<'\t'<<'\t'<<cou[j]<<endl;
}
}
cout<<"读入完事儿！"<<endl;
return 0;
}
/*-----------选择HT中双亲域为0的权值最小的两个结点--------------*/
void Select(HuffmanTree HT,int i,int &s1,int &s2)
{
//选择两个最小值，将他们的位序输出到s1,s2
int m=0,k=0;
for(k=1;k<=n;++k) //得到第一个父节点为零的节点
{
if(0==HT[k].parent)
{
m=HT[k].weight;
s1=k;
break;
}
}
for(;k<=n;++k) //得到最小值
{
if(0==HT[k].parent && HT[k].weight<m)
{
m=HT[k].weight;
s1=k;
}
}
for(k=1;k<=n;++k) //得到第二个父节点为零的节点
{
if(k!=s1 && 0==HT[k].parent)
{
m=HT[k].weight;
s2=k;
break;
}
}
for(;k<=n;++k) //求得次小元
{
if(0==HT[k].parent && k!=s1 && HT[k].weight<m)
{
m=HT[k].weight;
s2=k;
}
}
}//Select
/*---------算法5.10 根据统计结果建立Huffman树-----------*/
void CreatHuffmanTree(HuffmanTree &HT,int cou[])
{ if(n<=1) return;
int m=2*n-1;
HT=new HTNode[m+1]; //0 号单元未用，所以需要动态分配m+1个单元，HT[m]表示根节点
int s1=0,s2=0; //
for(int i=1;i<=m;i++) //初始化HuffmanTree 将1~m单元中的双亲，左右孩子的下标初始化为0
{
HT[i].lchild=0;
HT[i].rchild=0;
HT[i].parent=0;
}
for(i=1;i<=n;i++) //输入叶节点的权值
HT[i].weight=cou[i-1];
for(i=n+1;i<=m;i++)
{
Select(HT,i,s1,s2); //选择HT中两个双亲域为0且权值最小的两个节点的序号s1和s2
HT[s1].parent=i; HT[s2].parent=i; //标记其双亲结点为HT[i]
HT[i].lchild=s1; HT[i].rchild=s2; //HT[s1]和HT[s2]作为HT[i]的左右孩子
HT[i].weight=HT[s1].weight+HT[s2].weight; //HT[i]的权值为左右孩子权值之和
}
cout<<"huffmantree构造完成"<<endl;
}
/*--------------------算法5.11 根据统计结果对各字符进行编码，并保存在Code.txt中------------------*/
void CreatHuffmanCode(HuffmanTree HT,HuffmanCode &HC)
{ int start;
char cd;
HC=new char[n+1];
cd=new char[n];
cd[n-1]='\0';
int i,c,f;
for (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]);
}
delete cd;
cout<<"HuffmanCode创建完毕"<<endl;
}
/*----------对SourceFile.txt进行编码，并保存在ResultFile.txt中-----------*/
void Code(HuffmanTree &HT,HuffmanCode &HC)
{
string alph;
ifstream infile("SourceFile.txt");
if(!infile){
cout<<"Cannot open this file!"<
exit(1);
}
infile>>alph;
infile.close();
ofstream outfile;
outfile.open("ResultFile.txt");
if(!outfile)
cout<<"cannot open the file!"<<endl;
else{
for(int i=0;i<alph.length();i++){
int j=alph[i]-97;
for(int k=1;k<=n;k++){
if(HT[k].weight==cou[j])
outfile<<HC[k];
}
}
}
cout<<"huffman编码完成"<<endl;
outfile.close();
}
