huffmantree.cpp

华南师范大学计机实验3,哈夫曼树,不含实验报告

#include"HuffmanTree.h"
#include<string>
using namespace std;


HuffmanTree::HuffmanTree()
{
 Node=NULL;          
 Info=NULL;         
 LeafNum=0;         
}

HuffmanTree::~HuffmanTree()
{
 delete[] Node;        
 delete[] Info;         
}

void HuffmanTree::Initialization(int WeightNum)       
{
 int i,j,pos1,pos2,max1,max2;   
 
 Node=new HuffmanNode[2*WeightNum-1];  
 Info=new char[2*WeightNum-1];
 for(i=0;i<WeightNum;i++)
 {
  cout<<"请输入第"<<i+1<<"个字符值";
  getchar();           
  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++) 
 {
  pos1=-1;
  pos2=-1;         
  max1=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;                
     }
 
  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;   
 fop.open("hfmTree.dat",ios::out|ios::binary|ios::trunc);
 if(fop.fail())                    
  cout<<"文件打开失败！\n";
 fop.write((char*)&WeightNum,sizeof(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";
}

void HuffmanTree::Encoder()
{
 if(Node==NULL)       
 {
  ifstream fip;       
  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')       
 {
  ifstream fip1("ToBeTran.txt");
  if(fip1.fail())    
  {
   cout<<"文件打开失败!\n";
   return;       
  }
  char ch;
  int k=0;
  while(fip1.get(ch))            
  {
   k++;                    
  } 
  fip1.close();  
 
  Tree=new char[k+1];
  ifstream fip2("ToBeTran.txt");

  k=0; 
  while(fip2.get(ch))
  {
   Tree[k]=ch;         
   k++;
  }
  fip2.close();
  Tree[k]='\0';        
  cout<<"需编码内容为:";
  cout<<Tree<<endl;
 }

 else           
 {
  string tree;        
                   
  
  cin.ignore();
  cout<<"请输入需要编码的内容(可输入任意长，结束时请按2下回车):\n";
  getline(cin,tree,'\n');       
  while(tree[i]!='\0')
   i++;
  num=i;          
  i=0;
  Tree=new char[num+1];
  while(tree[i]!='\0')      
  {
   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];      
                               
 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=Node[j].parent;             
   if(Node[j].lchild==i)         
    code[start++]='0';
   else                      
    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";
} 
void HuffmanTree::Decoder()
{
 int i=0,k=0;
 int j=LeafNum*2-1-1;      
 char* BitStr;
 
 ifstream fip1("CodeFile.dat");         
 if(fip1.fail())        
 {
  cout<<        "请先编码！\n";
  return;
 }
 cout<<"经译码,原内容为:";
 char ch;
 while(fip1.get(ch))            
 {
  k++;                     
 }
 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");        
 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];               
  }
  i++;
 }
 fop.close();
 
 cout<<"\n译码成功且已存到文件TextFile.dat中！\n\n";
}
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)       
  {
   cout<<endl;
   i=0;
  }
  i++;
 }
 cout<<endl;
 fip.close();         
 fop.close();          
}

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";
 }
}