哈夫曼编码/译码 一、【实验内容】【问题描述】      利用哈夫曼编码进行住处通讯可以大大提高信道利用率,缩短住处传输时间,降低成本,但是,这要求在发送端通过一个编码系统将传输的数据预先编码,在接收端通过一个译码系统对传来的数据进行译码(复原),对于双向传输信息的信道,每端都一个完整的编码译码系统,试为这样的住处收发站写一个哈夫曼友的编码译码系统. 【基本要求】：一个完整的系统应以下功能:(1) I. 初始化(Initialization)。从终端读入字符集大小n，以及n个字符和n个权值,建立哈夫曼树,并将它存放在文件hfmTree中.(2) E. 编码(Encoding)。利用已建立好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码,然后将结果代码存(传输)到文件CodeFile中.(3) D. 译码(Decoding)。利用已建好的哈夫曼树,对传输到达的CodeFile中的数据代码进行译码,将译码结果存入文件TextFile中. (4) P. 印文件代码(Print)。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。 (5) T. 印哈夫曼树(TreePrinting)。将已在内存中的哈夫曼树以直观的方式(树或凹入表的形式)显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。　　　　　　测试数据：(1) 利用教科书例6-2中的数据调试程序。(2) 用下表给出的字符集和频度的计数据建立哈曼树,并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”.。字符       A   B    C    D    E    F    G    H    I    J    K    L    M频数 186  64   13   22   32   103  21   15   47   57   1    5    32   20字符 N    O    P    Q    R    S    T    U    V    W    X    Y    Z频数 57   63   15   1    48   51   80   23   8    18   1    16   1 二、实验目的树型结构是一种应用极为广泛的非线性数据结构,也是本课程的重点内容,哈夫曼树(最优二叉树)是树型结构的典型应用,本次实验突出了数据结构加操作的程序设计观点,希望能根据树型结构的非线性特点,熟悉各种存储结构的特性,达到如何应用树型结构的非线性特点,熟悉各种存储结构的特性,达到如何应用树型结构解决具体问题的目的.     三、实验文档：                  哈夫曼编码/译码一、 需求分析1、 利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（既可以双向传输信息的信道），每端都需要一个完整的编/译码系统。本次设计就是为这样的信息收发站写的一个哈夫曼的编/译码器。本实验要求：2、本演示程序中，用户可以输入键盘中的任意字符，长度为任意长，字符输入顺序不限，且允许出现重码3、演示程序以用户与计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令，相应的输入数据（可虑去输入中的非法字符）和运算结果显示在其后。4、本演示程序中，当用户选择的功能错误时，系统会输出相应的提示。5、在本系统中，用户可以对任意长的字符串可进行编码/译码。6、程序执行的命令包括：　1) 初始化(I)　　　2) 编码(E)　　　　3) 译码(D) 4) 印代码文件(P)　5) 印哈夫曼树(T)　6) 退出(Q)７、测试数据：　　（１）利用教科书例6-2中的数据调试程序。（２）用下表给出的字符集和频度的计数据建立哈曼树,并实现以下报文的　　　编码和译码：“THIS PROGRAM IS MY FAVORITE”.。字符     A   B   C   D   E   F   G   H   I   J   K   L   M频数 186  64    13    22    32   103    21   15   47    57    1    5     32    20字符 N  O   P   Q   R    S    T   U    V   W   X    Y   Z频数 57   63    15    1    48     51     80    23     8      18    1      16    1 二、概要设计为实现上述程序功能，应以指针存储结点。为此，需要定义一个抽象数据类型。1. 抽象数据类型定义为：ADT HuffmanTree{数据对象：D={ai| ai∈CharSet,i=1,2,……,n,  n≥0}数据关系：R={< ai-1, ai > ai-1, ai∈D, ai-1<ai ,i=2，3，……，n}基本操作P：HuffmanTree();       构造函数~ HuffmanTree();     析构函数Initialization(int WeightNum);操作结果：构造哈夫曼树。Encoder()初始条件：哈夫曼树已存在或者哈夫曼树已存到文件中。操作结果：对字符串进行编码Decoder();初始条件：哈夫曼树已存在且已编码。操作结果：对二进制串进行译码Print()初始条件：编码文件已存在。操作结果：把已保存好的编码文件显示在屏幕TreePrinting()初始条件：哈夫曼树已存在。操作结果：将已在内存中的哈夫曼树以直观的方式显示在终端上2.本程序包含三个模块：1)主程序模块：void main(){    初始化；do{   接受命令；   处理命令；}while(“命令”=”退出”)}2)、建树模块——实现定义的抽象数据类型3)、编/译码模块——实现字符串的编/译码各模块之间的调用关系如下：                    主程序模块                                                                建树模块                                                            编/译码模块三、详细设计程序代码如下//        程序名：HuffmanTree.h//      程序功能：哈夫曼树类的头文件(并用其来实现编/译码)//          作者：刘伟高//          日期：2006.11.27//          版本：1.0 //对应类实现文件: HuffmanTree.cpp//对应主程序文件: main.cpp   #include<iostream>#include<fstream>#include<string>using namespace std;struct HuffmanNode        //定义哈夫曼树各结点{ int weight;        //存放结点的权值，假设只考虑处理权值为整数的情况 int parent;        //记录结点父亲位置，-1表示为根结点，否则表示为非根结点 int lchild,rchild;   //分别存放该结点的左、右孩子的所在单元的编号};class HuffmanTree     //建立哈夫曼树类{private: HuffmanNode *Node;      //哈夫曼树中结点的存储结构 char *Info;           //用来保存各字符信息 int LeafNum;          //树中的叶子结点总数public: HuffmanTree();     //构造函数 ~HuffmanTree();    //析构函数 void Initialization(int WeightNum);   //初始化函数：根据WeightNum个权值建立一棵哈夫曼树 void Encoder();           //编码函数：利用构造好的哈夫曼树对字符进行编码 void Decoder();          //译码函数：对二进制串进行译码 void Print();            //印文件函数：把已保存好的编码文件显示在屏幕 void TreePrinting();     //印哈夫曼树函数：将已在内存中的哈夫曼树以直观的方式显示在终端上}; //        程序名：HuffmanTree.cpp//      程序功能：实现哈夫曼树类的源文件(并用其来实现编/译码)//          作者：刘伟高//          日期：2006.11.27//          版本：1.0 #include"HuffmanTree.h"#include<string>using namespace std; ////////////////////////////////////////////////////////////////////////////////  构造函数//  函数功能：将结点指针初始化为NULL//  函数参数：无//  参数返回值：无HuffmanTree::HuffmanTree(){ Node=NULL;          //将树结点初始化为空  Info=NULL;          //将字符数组初始化为空 LeafNum=0;          //将叶子数初始化为0}//////////////////////////////////////////////////////////////////////////////// 析构函数// 函数功能：将所有结点的空间释放// 函数参数：无// 参数返回值：无HuffmanTree::~HuffmanTree(){ delete[] Node;         //释放结点空间 delete[] Info;         //释放字符存储空间}////////////////////////////////////////////////////////////////////////////////  初始化函数//  函数功能：从终端读入字符集大小n，以及n个字符和n个权值,//            建立哈夫曼树,并将它存放在文件hfmTree中.//  函数参数：int WeightNum表示代码个数//  参数返回值：无 void HuffmanTree::Initialization(int WeightNum)        //初始化{ int i,j,pos1,pos2,max1,max2;     //  Node=new HuffmanNode[2*WeightNum-1];  //WeightNum权值对应的哈夫曼树中的结点总数为2*WeightNum-1个 Info=new char[2*WeightNum-1]; for(i=0;i<WeightNum;i++) {  cout<<"请输入第"<<i+1<<"个字符值";  getchar();           //丢弃字符'\t'与'\n'  Info[i]=getchar();   //输入一个字符,主要是考虑输入空格而采用这种形式的  getchar();  cout<<"请输入该字符的权值或频度";  cin>>Node[i].weight;       //输入权值  Node[i].parent=-1;      //为根结点  Node[i].lchild=-1;      //无左孩子  Node[i].rchild=-1;      //无右孩子 }  for(i=WeightNum;i<2*WeightNum-1;i++) //表示需做WeightNum-1次合并 {  pos1=-1;  pos2=-1;          //分别用来存放当前最小值和次小值的所在单元编号   max1=32767;      //32767为整型数的最大值   max2=32767;      //分别用来存放当前找到的最小值和次小值    for(j=0;j<i;j++)      //在跟节点中选出权值最小的两个   if(Node[j].parent==-1)         //是否为根结点    if(Node[j].weight<max1)     //是否比最小值要小    {      max2=max1;            //原最小值变为次小值     max1=Node[j].weight;      //存放最小值     pos2=pos1;            //修改次小值所在单元编号     pos1=j;               //修改最小值所在单元编号    }    else     if(Node[j].weight<max2)     //比原最小值大但比原次小值要小     {      max2=Node[j].weight;     //存放次小值      pos2=j;                  //修改次小值所在的单元编号     }    //for  Node[pos1].parent=i;       //修改父亲位置  Node[pos2].parent=i;  Node[i].lchild=pos1;       //修改儿子位置  Node[i].rchild=pos2;  Node[i].parent=-1;             //表示新结点应该是根结点  Node[i].weight=Node[pos1].weight+Node[pos2].weight; } //for LeafNum=WeightNum;   char ch; cout<<"是否要替换原来文件(Y/N):"; cin>>ch; if(ch=='y'||ch=='Y') { ofstream fop;   //以二进制方式打开hfmTree.dat文件，并当重新运行时覆盖原文件 fop.open("hfmTree.dat",ios::out|ios::binary|ios::trunc); if(fop.fail())                     //文件打开失败  cout<<"文件打开失败！\n"; fop.write((char*)&WeightNum,sizeof(WeightNum));  //写入WeightNum for(i=0;i<WeightNum;i++)         //把各字符信息写入文件 {  fop.write((char*)&Info[i],sizeof(Info[i]));  flush(cout); } for(i=0;i<2*WeightNum-1;i++)        //把个节点内容写入文件 {  fop.write((char*)&Node[i],sizeof(Node[i]));  flush(cout); } fop.close();            //关闭文件 } cout<<"哈夫曼树已构造完成。\n";}//Initialization ////////////////////////////////////////////////////////////////////////////////  编码函数//  函数功能：利用已建立好的哈夫曼树（如不在内存，则从文件hfmTree中读入），//            对文件ToBeTran中的正文进行编码,然后将结果代码存(传输)到文件CodeFile中.//  函数参数：无//  参数返回值：无void HuffmanTree::Encoder(){ if(Node==NULL)       //哈夫曼树不在内存，从文件hfmTree中读入 {  ifstream fip;        //以二进制方式打开hfmTree.dat文件  fip.open("hfmTree.dat",ios::binary|ios::in);  if(fip.fail())       //文件打开失败  {   cout<<"文件打开失败！\n";   return;          //结束本函数  }  fip.read((char*)&LeafNum,sizeof(LeafNum));  //读取叶子数  Info=new char[LeafNum];   Node=new HuffmanNode[2*LeafNum-1];  for(int i=0;i<LeafNum;i++)              //读取字符信息   fip.read((char*)&Info[i],sizeof(Info[i]));  for(i=0;i<2*LeafNum-1;i++)              //读取结点信息   fip.read((char*)&Node[i],sizeof(Node[i])); }  char *Tree;          //用于存储需编码内容 int i=0,num; char Choose;         //让用户选择读取文件或重新输入需编码内容 cout<<"你要从文件中读取内容(1)，还是重新输入(2):"; cin>>Choose; if(Choose=='1')          //读取文件ToBeTran.txt {  ifstream fip1("ToBeTran.txt");  if(fip1.fail())      //文件不存在  {   cout<<"文件打开失败!\n";   return;          //结束本函数  }  char ch;  int k=0;  while(fip1.get(ch))              {   k++;                     //计算CodeFile中代码长度  }   fip1.close();     Tree=new char[k+1];  ifstream fip2("ToBeTran.txt");   k=0;   while(fip2.get(ch))  {   Tree[k]=ch;           //读取文件内容，并存到Tree中   k++;  }  fip2.close();  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

评论