哈夫曼编码问题
代码由bug求改进#include<iostream>
#include<string.h>
#include<fstream>
using namespace std;
#define Max 200 //最大结点数目
#define INT 10000
char ch[Max]; //叶子结点信息（字符）
int i,w[Max]; //w为输入的权值数组
typedef struct{
unsigned int weight; //权值
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树
typedef char * *HuffmanCode; //动态分配数组存储哈夫曼编码表
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{//w存放n个字符的权值(均>0),构造哈夫曼树HT，并求出n个字符的哈夫曼编码HC。
int s1,s2,j,min1,min2;
if(n<=1) return;
int m=2*n-1;
HT=new HTNode[m+1];//0号单元未用
for(i=1;i<=n;++i) //哈夫曼树叶子结点的初始化
{
HT[i].weight=w[i]; HT[i].parent=0;
HT[i].lchild=0; HT[i].rchild=0;
}
for(i=n+1;i<=m;++i) //非叶子结点的初始化
{
HT[i].weight=0; HT[i].parent=0;
HT[i].lchild=0; HT[i].rchild=0;
}
for(i=n+1;i<=m;++i) //建哈夫曼树
{ //在HT[1..i-1]选择parent为0且weight最小的两个结点S1和S2
min1=min2=INT;
for(j=1;j<i;j++)
if(HT[j].parent==0&&(HT[j].weight<min1))
{
min1=HT[j].weight;
s1=j;
}
for(j=1;j<i;j++)
if(HT[j].parent==0&&(HT[j].weight<min2)&&j!=s1)
{ min2=HT[j].weight;
s2=j;
}
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;
ch[i]='?';//非叶子结点的结点字符
}
//从叶子到根逆向求每个字符的哈夫曼编码
HC=new char*[n+1]; //分配n个字符编码的头指针向量
char *cd=new char[n]; //分配求编码的工作空间
HT[i].lchild=s1; HT[i].rchild=s2;
cd[n-1]='\0'; //编码结束符
for(i=1;i<=n;i++) //逐个字符求哈夫曼编码
{
int c,f,start=n-1;//编码结束符位置
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
/*cd[--start]=(HT[f].lchild==c?'0':'1';*/ //从叶子到根逆向求编码
if(HT[f].lchild==c)
cd[--start]='0';
else
cd[--start]='1';
HC[i]=new char[n-start];//为第i个字符编码分配空间
strcpy(HC[i],&cd[start]); //从cd复制编码（串）到HC
}
delete cd;
}
void Initialization(HuffmanTree &HT,HuffmanCode &HC,int &n)//初始化,注意加引用符号
{
char c;
ifstream fin("hfmTree.txt",ios::in);//读出
if(fin.fail()) //若不存在此文件，则从终端读入
{
cout<<"请输入字符个数n：";
cin>>n;
cout<<"请输入字符及相应权值："<<endl;
for(i=1;i<=n;i++)
{
//getchar()是在输入缓冲区顺序读入一个字符(包括空格、回车和tab)。
getchar(); //取消换行符
//getchar每次只能读取一个字符.如果需要取消'\n'的影响,可以用getchar();来清除,
//这里getchar();只是取得了'\n'但是并没有赋给任何字符变量,所以不会有影响,相当于清除了这个字符.
ch[i]=getchar(); //保证空格读进
cin>>w[i];
}
HuffmanCoding(HT,HC,w,n);
ofstream fout("hfmTree.txt",ios::out);//写入
cout<<n<<endl;
for(i=1;i<=2*n-1;i++)//写入字符，权值，父结点，左右孩子
fout<<ch[i]<<" "<<HT[i].weight<<" "<<HT[i].parent<<" "<<HT[i].lchild<<" "<<HT[i].rchild<<endl;
for(i=1;i<=n;i++)//写入字符及相应的编码
fout<<ch[i]<<" "<<HC[i]<<endl;
fout.close();
}
else{ //如果文件存在，即读到内存中
fin>>n;
for(i=1;i<=2*n-1;i++)
{
fin.get(ch[i]);
fin>>HT[i].weight>>HT[i].parent>>HT[i].lchild>>HT[i].rchild;
fin.get(c);
}
for(i=1;i<=n;i++)
{
fin.get(ch[i]);
fin>>HC[i];
fin.get(c);
}
}
fin.close();
}
void Encoding(HuffmanCode & HC,int n) //编码
{
int i,j;
string str,str1;
ifstream fin("ToBeTran.txt",ios::in);//打开文件
ofstream fout("CodeFile.txt",ios::out);
if(fin.fail())
cout<<"文件ToBeTran.txt打开失败！"<<endl;
getline(fin,str);//读入一行，可以读入空格
while(!fin.eof())//文件不结束
{
getline(fin,str1);
str=str+str1;
}
fin.close();
for(i=0;str[i]!='\0';i++)//编码过程，一个字符一个字符来
{
j=1;
while(ch[j]!=str[i]&&j<=n) j++;
if(j<=n) fout<<HC[j];
}
fout<<endl;
fout.close();
}
void Decoding(HuffmanTree HT,int n)//译码
{
int j,len,m;
string str;
m=2*n-1;
ifstream fin("CodeFile.txt",ios::in);
ofstream fout("TextFile.txt",ios::out);
if(fin.fail())
{
cout<<"文件CodeFile.txt打开失败！"<<endl;
return ;
}
fin>>str;
fin.close();
len=str.size();
i=0;j=m;
while(i<len)
{ //从根出发，按字符'0'或'1'确定找左孩子或右孩子，直至叶子结点
if(str[i]=='0')
j=HT[j].lchild;
else j=HT[j].rchild;
if(HT[j].lchild==0)
{ fout<<ch[j]; j=m; }
i++;
}
fout<<endl;
}
void Print(HuffmanTree HT,int n)//打印代码文件
{
int i;
char str[Max];
ifstream fin("CodeFile.txt",ios::in);
ofstream fout("CodePrin.txt",ios::out);
if(fin.fail())
cout<<"文件CodeFile.txt打开失败！"<<endl;
fin>>str;
cout<<"毎行50个代码形式的编码如下："<<endl;
for(i=0;i<strlen(str);i++)
{
if(i%50==0&&i!=0) //毎50以换行
{
cout<<endl; fout<<endl;
}
cout<<str[i];fout<<str[i];
}
cout<<endl;fout<<endl;
fin.close(); fout.close();
}
//非叶子结点用权值表示，叶子结点用字符表示
void PrintTree(HuffmanTree &HT,int &n)
{
ofstream fout("TreePrint.txt",ios::out);//写入文件
int l,j,m=0,k=1,q=0,p=0,r=1;//k 表示层数,r表示每层的结点数
for(i=1;i<=2*n-1;i++)
if(HT[i].parent==0)//找根结点的权值
m=HT[i].weight;
for(l=m;l>0;l--)
for(i=1;i<=2*n-1;i++)
if(HT[i].weight==l)
{
for(j=0;j<k;j++)
{ cout<<" "; fout<<" "; }//控制每层前面的空格
if(ch[i]!='?') //如果是叶子结点就直接输出，否则输出权重
{
if(ch[i]==' ') ch[i]='#';//标记为空的字符
{ cout<<ch[i]<<endl; fout<<ch[i]<<endl; }
}
else
{ cout<<HT[i].weight<<endl; fout<<HT[i].weight<<endl; p++; }//p 表示每层的非叶子结点数
q++;//q 记录每层的结点数目
if(q==r) { k++; r=2*p; p=0; q=0; } //如果该层的结点满了，就到下一层，即k+1
}
}
int main()
{
HuffmanTree HT;
HuffmanCode HC;
char c;
int n;
HT=new HTNode[Max];
HC=new char*[Max];
for(int i=1;i<=Max;i++)//初始化
HC[i]=new char[20];
cout<<"-----------------------欢迎进入哈夫曼的编/译码系统---------------------------"<<endl;
cout<<"| 菜单如下："<<endl;
cout<<"| 1、初始化"<<endl;
cout<<"| 2、编码"<<endl;
cout<<"| 3、译码"<<endl;
cout<<"| 4、打印代码文件"<<endl;
cout<<"| 5、打印哈夫曼树"<<endl;
cout<<"| 6、退出"<<endl;
cout<<"-----------------------------------------------------------------------------"<<endl;
while(c!='Q')
{
cout<<"请选择操作：";
cin>>c;
switch(c)
{
case '1': Initialization(HT,HC,n);
cout<<"哈夫曼树成功存入文件hfmTree中！"<<endl;
break;
case '2': Encoding(HC,n);
cout<<"对文件ToBeTran的编码结果成功存入文件CodeFile中！"<<endl;
break;
case '3': Decoding(HT,n);
cout<<"对文件CodeFile的译码结果成功存入文件TextFile中！"<<endl;
break;
case '4': Print(HT,n);
cout<<"毎行50个代码形式的编码结果成功写入文件CodePrin中！"<<endl;
break;
case '5': cout<<"哈夫曼树的凹入表示法如下："<<endl;
PrintTree(HT,n);
cout<<"哈夫曼树以凹入表形式成功写入文件TreePrint中！"<<endl;
default: break;
}
}
return 0;
}
