哈夫曼1编码.txt

哈夫曼编码译码

  Tree[k]='\0';          //结束标志
  cout<<"需编码内容为:";
  cout<<Tree<<endl;
 }//if(Choose=='1')

 else           //Choose!='1',重新输入
 {
  string tree;         //用于输入需编码内容，由于string类对象可以输入任意长度，
                     //所以先利用这个对象输入，再转存在Tree中
  
  cin.ignore();
  cout<<"请输入需要编码的内容(可输入任意长，结束时请按2下回车):\n";
  getline(cin,tree,'\n');         //输入任意长字符串，
         //getline以回车('\n')作为结束符，第一次按回车表示字符串结束，第二次按回车才开始输出。
  while(tree[i]!='\0')
   i++;
  num=i;             //计算tree长度
  i=0;
  Tree=new char[num+1];
  while(tree[i]!='\0')       //将tree中的字符转存到Tree中
  {
   Tree[i]=tree[i];
   i++;
  }
     Tree[i]='\0';          //结束标志符
 }
 
 ofstream fop("CodeFile.dat",ios::trunc);      //存储编码后的代码,并覆盖原文件
 i=0;
 int k=0;
 char *code;
 code=new char[LeafNum];        //为所产生编码分配容量为LeafNum的存储空间
                               //因为不等长编码中最长的编码一定不会超过要求编码的字符个数
 while(Tree[k]!='\0')              //对每一个字符编码
 {
  int j,start=0;
  for(i=0;i<LeafNum;i++)
   if(Info[i]==Tree[k])            //求出该文字所在单元的编号
    break; 
   j=i;
  while(Node[j].parent!=-1)        //结点j非树根
  {
   j=Node[j].parent;             //非结点j的双亲结点
   if(Node[j].lchild==i)           //是左子树，则生成代码0
    code[start++]='0';
   else                       //是右子树，则生成代码1
    code[start++]='1';\
   i=j;
  }
  code[start]='\0';             //置串结束符


  for(i=0;i<start/2;i++)           //对二进制序列进行逆置
  {
   j=code[i];
   code[i]=code[start-i-1];
   code[start-i-1]=j;
  }
        i=0;
  while(code[i]!='\0')        //存储代码
  {
   fop<<code[i];
   i++;
  }
  k++;
 }
 fop.close();
 cout<<"已编码！且存到文件CodeFile.dat中！\n\n";
}  //Encode

//////////////////////////////////////////////////////////////////////////////
//  译码函数
//  函数功能：利用已建好的哈夫曼树,对传输到达的CodeFile中的数据代码进行译码,
//            将译码结果存入文件TextFile中.
//  函数参数：无
//  参数返回值：无
void HuffmanTree::Decoder()
{
 int i=0,k=0;
 int j=LeafNum*2-1-1;      //表示从根结点开始往下搜索
 char* BitStr;
 
 ifstream fip1("CodeFile.dat");          //利用已建好的哈夫曼树将文件CodeFile中的代码进行译码
 if(fip1.fail())         //文件打开失败，还未编码
 {
  cout<<        "请先编码！\n";
  return;
 }
 cout<<"经译码,原内容为:";
 char ch;
 while(fip1.get(ch))            
 {
  k++;                     //计算CodeFile中代码长度
 }
 fip1.close();  
 
 BitStr=new char[k+1];
 ifstream fip2("CodeFile.dat");
 k=0;
 while(fip2.get(ch))
 {
  BitStr[k]=ch;          //读取文件内容
  k++;
 }
 fip2.close();                
 BitStr[k]='\0';         //结束标志符
 if(Node==NULL)         //还未建哈夫曼树
 {
  cout<<"请先编码!\n";
  return;
 }
 ofstream fop("TextFile.dat");         //将字符形式的编码文件写入文件CodePrin中
 while(BitStr[i]!='\0')
 {
  if(BitStr[i]=='0')
   j=Node[j].lchild;          //往左走
  else
   j=Node[j].rchild;         //往右走
  if(Node[j].rchild==-1)   //到达叶子结点
  {
   cout<<Info[j];         //输出叶子结点对应的字符
   j=LeafNum*2-1-1;             //表示重新从根结点开始往下搜索
   fop<<Info[j];               //存入文件
  }//if、
  i++;
 }//while
 fop.close();
 
 cout<<"\n译码成功且已存到文件TextFile.dat中！\n\n";
}//Decoder
//////////////////////////////////////////////////////////////////////////////
//  印文件代码函数
//  函数功能：将文件CodeFile以紧凑格式显示在终端上，
//            每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。
//  函数参数：无
//  参数返回值：无
void HuffmanTree::Print()
{
 char ch;
 int i=1;
 ifstream fip("CodeFile.dat");           //读取文件
 ofstream fop("CodePrin.dat");           //存储文件
 if(fip.fail())
 {
  cout<<"没有文件，请先编码！\n";

  return;
 }
 while(fip.get(ch))
 {
  cout<<ch;            //读取文件内容
  fop<<ch;              //存到文件中
  if(i==50)        //每行输出50个字符
  {
   cout<<endl;
   i=0;
  }
  i++;
 }
 cout<<endl;
 fip.close();          //关闭CodeFile.dat文件
 fop.close();            //关闭CodePrin.dat文件
}
//////////////////////////////////////////////////////////////////////////////
//  印哈夫曼树函数
//  函数功能：将已在内存中的哈夫曼树以直观的方式(树或凹入表的形式)显示在终端上，
//            同时将此字符形式的哈夫曼树写入文件TreePrint中。
//  函数参数：无
//  参数返回值：无
void HuffmanTree::TreePrinting()
{
 if(Node==NULL)         //未建立哈夫曼树
 {
  cout<<"请先建立哈夫曼树！\n";
  return;
 }
 ofstream fop("TreePrint.dat");
 cout<<"结点位置(权值)  "<<"编码  "<<"左孩子  "<<"编码"<<"右孩子('^'表示叶子)\n";
 fop<<"结点位置(权值)  "<<"编码  "<<"左孩子  "<<"编码"<<"右孩子('^'表示叶子)\n";
 int i;
 for(i=(2*LeafNum-2);i>LeafNum-1;i--)        //输出哈夫曼树
 {
  cout<<i<<"("<<Node[i].weight<<")"<<"--1--"
  <<Node[i].lchild<<"("<<Node[Node[i].lchild].weight<<")"<<"--0--"
  <<Node[i].rchild<<"("<<Node[Node[i].rchild].weight<<")"<<endl;
  fop<<i<<"("<<Node[i].weight<<")"<<"--1--"
  <<Node[i].lchild<<"("<<Node[Node[i].lchild].weight<<")"<<"--0--"
  <<Node[i].rchild<<"("<<Node[Node[i].rchild].weight<<")"<<endl;
 }
 for(;i>=0;i--)
 {
  cout<<i<<":"<<Node[i].weight<<"("<<Info[i]<<")---^\n";
  fop<<i<<":"<<Node[i].weight<<"("<<Info[i]<<")---^\n";
 }
}

//        程序名：main.cpp
//      程序功能：主函数源文件
//          作者：刘伟高
//          日期：2006.11.27
//          版本：1.0


#include"HuffmanTree.h"
#include<string.h>
#include<stdlib.h>

//////////////////////////////////////////////////////////////////////////////
//  主函数
//参数返回值：无

int main()
{
 cout<<"         欢迎使用哈夫曼码的编/译码系统!\n";
 cout<<"                         刘伟高\n";
 cout<<"              版权所有,盗版必究\n"; 
 cout<<"在此系统中可以进行以下操作:\n";
 cout<<"(1) 初始化(I);\n";
 cout<<"(2) 编码(E);\n";
 cout<<"(3) 译码(D);\n";
 cout<<"(4) 印代码文件(P);\n";
 cout<<"(5) 印哈夫曼树(T)\n";
 cout<<"(6) 退出(Q)\n\n";
 HuffmanTree huftree;         //定义哈夫曼树对象
 int weight;
 char Choose;
 while(1)
 {
  cout<<"请从清单中选择一个操作(不区分大小写):";
  cin>>Choose;
  switch(Choose)
  {
  case 'I':
  case 'i':
   cout<<"请输入编码长度：";
   cin>>weight;
   huftree.Initialization(weight);      //初始化哈夫曼树
   break;
  case 'E':
  case 'e':
   huftree.Encoder();
   break;
  case 'D':
  case 'd':
   huftree.Decoder();
   break;
  case 'P':
  case 'p':
   huftree.Print();
   break;
  case 'T':
  case 't':
   huftree.TreePrinting();
   break;
  case 'Q':
  case 'q':
   cout<<"\n        ***********感谢使用本系统!***********\n\n";
           system(“pause”);    //暂停运行
   return 0;
  }
  cout<<"(1) 初始化(I)      (2) 编码(E)         (3) 译码(D)\n";
  cout<<"(4) 印代码文件(P)  (5) 印哈夫曼树(T)   (6) 退出(Q)\n";
 }
}
四、调试分析
1、由于二维指针和string类，还有文件操作的推敲不足，使程序调试时费时不少。还有对单个空格字符的输入，也花了一些时间，不过最终能实现单个空格的输入，还是值得的。
2、本程序有些代码重复出现，从而减少了空间的利用率和增加了程序代码的杂乱性，特别是文件操作方面，如果可能的话，可以把文件读入、读出分别写成一个函数（就是把文件名作为参数），然后就可以直接调用了。
3、本程序模块划分比较合理，且利用指针和string类对象实现字符串的操作，操作方便。
4、算法的时空分析
在此程序中，存储字符串都用了指针，先动态申请空间，然后再存，这样就有效的利用了空间，不过为了实现任意长字符串的输入，引入了string类，先定义string对象，再输入。最后转存到字符指针里，这样就浪费了一些空间。
而对于哈夫曼树算法本身，由于这里只是一个静态的，所以当进行网络传输时，可能会显得效率比较低。
5、本实验采用数据抽象的程序设计方法，将程序分为3个模块，使得设计时思路清晰，实现时调试可以顺利完成，各模块具有较好的可重用性，确实得到了一次良好的程序设计训练。
五、用户手册
1、本程序的运行环境为DOS操作系统
2、进入演示程序后即显示文本方式的用户界面
  
 
 

3、进入界面后，就会提示输入字符串的输入形式，结束符为“回车符”。
六、测试结果
    如上图所示。
七、附录
源程序文件名清单：
HuffmanTree.h                    //元素结点定义单元
HuffmanTree.cpp                  //链表实现单元
main.cpp                          //主程序

 

四、实验总结（心得体会）
１、通过实验更好的掌握了哈夫曼树，并对哈夫曼树有了深一步的了解
２、掌握了用getchar可以输入单个空格
４、更进一步掌握有关类的操作
5、由于算法推敲不足，使程序调试时费时不少
6、本程序有些代码重复出现，从而减少了空间的利用率和增加了程序代码的杂乱性
７、更熟悉了文件的操作
８、更好的掌握了对程序的调试，并从中感受到调试的巨大的力量，特别是当程序不能实现预想结果时

 

五、参考文献：
1、《数据结构与算法》    黄定  黄煜廉  刘贤兴  编著  
广东科技出版社  2000年1月第1版
2、《〈数据结构与算法〉学习与实验指导》  黄煜廉 编著   2005. 8