前些日子，我的一个同学（包包）的朋友给了他一个有点烦的任务。她叫包包做个赫夫曼编码、译码器给她，可是我同学呢。算是有点懒吧，不太愿意做啊。说实在的，应该说是我们没学过数据结构的东西，根本就是无从下手。就这样，包包就找上我了，让我帮他完成这个任务。
可是不巧的是，我那几天身体不舒服，没什么心思做这些东西，而且是我们根本就是不懂的东西，虽然我们学过C++，但是没学数据结构啊。唉……真不知道怎么办，那天我就告诉他，我做不好这个赫夫曼编码、译码器，还是让他朋友自己去解决吧。
放假回家后感觉很空虚，我就拿这个东西出来玩玩。没想到最后我弄出来了。O（∩_∩）O哈哈哈~
现在我就来说明一下这个实现方法吧。整个项目我就用win32控制台程序写的。这样可以方便测试，排除其他麻烦。
首先，我们来看看main函数：
void main()
{
char choice=' ';
while(choice!='q')
{ cout<<"\n******************************"<<endl;
cout<<" 欢迎使用赫夫曼编码译码系统"<<endl;
cout<<"******************************"<<endl;
cout<<"(1)要初始化赫夫曼链表请输入'i'"<<endl;
cout<<"(2)输入要编码的字符'w'"<<endl;
cout<<"(3)要编码请输入'e'"<<endl;
cout<<"(4)要译码请输入'd'"<<endl;
cout<<"(5)要打印编码请输入'p'"<<endl;
cout<<"(6)要打印赫夫曼树请输入't'"<<endl;
cout<<"(7)要离开请输入'q'"<<endl;
if(flag==0)cout<<"\n请先初始化赫夫曼链表,输入'i'"<<endl;
cin>>choice;
switch(choice)
{
case 'i':
Initialization();
break;
case 'w':
InputCode();
break;
case 'e':
Encoding();
break;
case 'd':
Decoding();
break;
case 'p':
Code_printing();
break;
case 't':
Tree_printing(HT,2*n-1);
break;
case 'q':
break;
default:
cout<<"input error"<<endl;
}
}
free(z);
free(w);
free(HT);
}
void Initialization()
{
flag=1;
int num;
int num2;
cout<<"下面初始化赫夫曼链表"<<endl<<"请输入结点的个数n：";
cin>>num;
n=num;
w=(int*)malloc(n*sizeof(int));
z=(char*)malloc(n*sizeof(char));
cout<<"\n请依次输入"<<n<<"个字符(字符型)\n注意:必须以回车结束："<<endl;
char base[2];
for(i=0;i<n;i++)
{
cout<<"第"<<i+1<<"个字符:"<<endl;
gets(base);//这个地方有点小小的问题
*(z+i)=*base;
}
for(i=0;i<=n-1;i++)
{
cout<<setw(6)<<*(z+i);
}
cout<<"\n请依次输入"<<n<<"个权值(\n注意:必须以回车结束)："<<endl;
for(i=0;i<=n-1;i++)
{
cout<<endl<<"第"<<i+1<<"个字符的权值:";
cin>>num2;
*(w+i)=num2;
}
HuffmanCoding(HT,HC,w,n);
//------------------------打印编码-------------------------------------------
cout<<"字符对应的编码为:"<<endl;
for(i=1;i<=n;i++)
{
//cout<<"字符"<<*(z+i-1)<<"的编码";
puts(HC[i]);
}
//--------------------------将赫夫曼编码写入文件------------------------
cout<<"下面将赫夫曼编码写入文件"<<endl<<"...................."<<endl;
FILE *hfmTree;
char r[]={' ','\0'};
if((hfmTree=fopen("hfmTree.txt","w"))==NULL)
{
cout<<"can not open file"<<endl;
return;
}
fputs(z,hfmTree);
for(i=0;i<n+1;i++)
{
fprintf(hfmTree,"%6d",*(w+i));
fputs(r,hfmTree);
}
for(i=1;i<=n;i++)
{
fputs(HC[i],hfmTree);
fputs(r,hfmTree);
}
fclose(hfmTree);
cout<<"已将字符与对应编码写入根目录下文件hfmTree.txt中"<<endl<<endl;
}
上述代码中有个小问题，已经用红色标示，这个地方获取数据的时候有一次是没有输入就直接执行的。这个疑问我一直都没想通。初始化的结果放入hfmTree.txt的文件中。
下面来看看输入要编码的字符的函数InputCode（）
void InputCode()
{
//cout<<"请输入你想要编码的字符"<<endl;
FILE *tobetran;
char str[100];
if((tobetran=fopen("tobetran.txt","w"))==NULL)
{
cout<<"不能打开文件"<<endl;
return;
}
cout<<"请输入你想要编码的字符"<<endl;
cin>>str;
fputs(str,tobetran);
cout<<"获取报文成功"<<endl;
fclose(tobetran);
}
这个函数里我也碰到了一个问题，cin>>str；部分一开始的时候，我是用gets代替的，不过问题就是用gets我不用输入就能直接执行完函数。这个郁闷啊。
下面来看看编码和译码函数
//---------------------编码函数---------------------------------
void Encoding()
{
cout<<"下面对目录下文件tobetran.txt中的字符进行编码"<<endl;
FILE *tobetran,*codefile;
if((tobetran=fopen("tobetran.txt","rb"))==NULL)
{
cout<<"不能打开文件"<<endl;
}
if((codefile=fopen("codefile.txt","wb"))==NULL)
{
cout<<"不能打开文件"<<endl;
}
char *tran;
i=99;
tran=(char*)malloc(100*sizeof(char));
while(i==99)
{
if(fgets(tran,100,tobetran)==NULL)
{
cout<<"不能打开文件"<<endl;
break;
}
for(i=0;*(tran+i)!='\0';i++)
{
for(j=0;j<=n;j++)
{
if(*(z+j-1)==*(tran+i))
{
fputs(HC[j],codefile);
if(j>n)
{
cout<<"字符错误，无法编码!"<<endl;
break;
}
}
}
}
}
cout<<"编码工作完成"<<endl<<"编码写入目录下的codefile.txt中"<<endl<<endl;
fclose(tobetran);
fclose(codefile);
free(tran);
}
//-----------------译码函数---------------------------------
void Decoding()
{
cout<<"下面对根目录下文件codefile.txt中的字符进行译码"<<endl;
FILE *codef,*txtfile;
if((txtfile=fopen("\\Textfile.txt","w"))==NULL)
{
cout<<"不能打开文件"<<endl;
}
//txtfile=fopen("Textfile.txt","w");
if ((codef=fopen("codefile.txt","r"))==NULL)
{
cout<<"不能打开文件"<<endl;
}
//codef=fopen("codefile.txt","r");
char *work,*work2,i2;
int i4=0,i,i3;
unsigned long length=10000;
work=(char*)malloc(length*sizeof(char));
fgets(work,length,codef);
work2=(char*)malloc(length*sizeof(char));
i3=2*n-1;
for(i=0;*(work+i)!='\0';i++)
{
i2=*(work+i);
if(HT[i3].lchild==0)
{
*(work2+i4)=*(z+i3-1);
i4++;
i3=2*n-1;
i--;
}
else if(i2=='0') i3=HT[i3].lchild;
else if(i2=='1') i3=HT[i3].rchild;
}
*(work2+i4)='\0';
fputs(work2,txtfile);
cout<<"译码完成"<<endl<<"内容写入根目录下的文件txtfile.txt中"<<endl<<endl;
free(work);
free(work2);
fclose(txtfile);
fclose(codef);
}
整个编码译码过程也就这样了。
我没有学过数据结构，我只是看过一些资料，这里可能会有不好的地方，高手可以指点一下。