赫夫曼树2.txt

自己做的赫夫曼树

程序代码如下  
//        程序名：HuffmanTree.h  
//      程序功能：哈夫曼树类的头文件(并用其来实现编/译码)  
//          作者：刘伟高  
//          日期：2006.11.27  
//          版本：1.0  

//对应类实现文件: HuffmanTree.cpp  
//对应主程序文件: main.cpp  
#include  
#include  
#include  
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  
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 {  
  cout<<"请输入第"<  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   if(Node[j].parent==-1)         //是否为根结点  
    if(Node[j].weight    {   
     max2=max1;            //原最小值变为次小值  
     max1=Node[j].weight;      //存放最小值  
     pos2=pos1;            //修改次小值所在单元编号  
     pos1=j;               //修改最小值所在单元编号  
    }  
    else  
     if(Node[j].weight     {  
      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 {  
  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   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< }//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’;          //结束标志符