C++用哈弗曼编码实现压缩,编码文件比原文件大是怎么回事,怎么能实现压缩,代码如下,求修改 10C
#include<iostream>
#include<fstream>
#include<string>
using namespace std;
struct HuffmanNode    //树结点类定义                
{
 int weight;   //权值                       
 int parent;    //双亲                
 int lchild,rchild; //左右孩子                 
};
class HuffmanTree     //哈夫曼树类定义
{
private:
 struct  HuffmanNode *Node;              //哈夫曼树中结点的存储结构
 char *Info;                             //用来保存各字符信息的字符数组
 int LeafNum;                            //树中的叶子结点总数
public:
 HuffmanTree();                          //构造函数
 ~HuffmanTree();                         //析构函数
 void Initialization(int WeightNum);     //初始化函数    
void Encoder();                           //编码函数,生成哈夫曼编码                        
void Decoder();                         //译码函数,对二进制串进行译码
 void Print();                          //输出编码                       
void TreePrinting();                   //输出哈夫曼树                   
};
HuffmanTree::HuffmanTree()                             //初始化空树
{
 Node=NULL;                                           //将树结点初始化为空 
 Info=NULL;                                           //将字符数组初始化为空
 LeafNum=0;                                           //将叶子数初始化为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++)                   //先构造weightnum个点
 {
  cout<<"请输入第"<<i+1<<"个字符值";
  cin>>Info[i];
  cout<<"请输入该字符的权值或频度";
  cin>>Node[i].weight;                                 //输入权值
  Node[i].parent=-1;                                   //为根结点
  Node[i].lchild=-1;                                   //无左孩子
  Node[i].rchild=-1;                                   //无右孩子
 }
//这里构造出weightnum个带权结点
for(i=WeightNum;i<2*WeightNum-1;i++)                  
{
  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;                                        //修改次小值所在的单元编号
     }
  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;
 } 
 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";
}
//编码函数
void HuffmanTree::Encoder()
{
 if(Node==NULL)                                       
{
  ifstream fip;                                        
  fip.open("hfmTree.dat",ios::binary|ios::in);         //以二进制方式打开hfmTree.dat文件
  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(int 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++;                                                 
  } 
  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<<"需编码内容为:"<<Tree<<endl;
 }                                                        //if(Choose=='2')
 else                                                   
 {
  string tree;                        

  cin.ignore();
  cout<<"请输入需要编码的内容(可输入任意长,结束时请按2下回车):\n";
  getline(cin,tree,'\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                       
    code[start++]='1';                                  //是右子树,则生成代码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");                       //利用已建好的哈夫曼树将文件CodeFile中的代码进行译码
 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");                          //将字符形式的编码文件写入文件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];                                        //存入文件
  }                                                        
  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();                                               //关闭CodeFile.dat文件
 fop.close();                                               //关闭CodePrin.dat文件                                            
}
//输出哈夫曼树
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";
 }
}
int main()
{
 cout<<"~~~~~~~~~~~~~welcome to Huffman encodrding&decoding system ~~~~~~~~~~~~~~~~~~~~\n\n";
 cout<<"You can choose 1--6 options:\n";
 cout<<"(1)初始化 \n";
 cout<<"(2) 编码\n";
 cout<<"(3) 译码\n";
 cout<<"(4) 输出编码\n";
 cout<<"(5) 输出哈弗曼树\n";
 cout<<"(6) Byebye~!\n\n";
 HuffmanTree HT;        
 int weight;
 int choice;
 int OK=0;
while ( !OK )
 {
  cout<<"Please input your option (1--6):";
  cin>> choice;
  switch( choice)
  {

  case 1:
   cout<<"Please input your code lenth"<<endl;
   cin>>weight;
   HT.Initialization(weight);      
   break;

  case 2:
   HT.Encoder();
   break;

  case 3:
   HT.Decoder();
   break;

  case 4:
   HT.Print();break;

  case 5:
   HT.TreePrinting();break;

  case 6:
   cout<<"\n***********Thanks for Using!***********\n";

               OK=1;   
               break;
   return 0;
  }
  cout<<"(1)初始化\n";
  cout<<"(2)编码\n";
  cout<<"(3)译码\n";
  cout<<"(4)打印哈弗曼编码\n";
  cout<<"(5)打印哈弗曼树\n";
  cout<<"(6) Byebye~!\n\n";
 }
return 0;
}
c++

1个回答

如果你试图压缩的是高熵数据(比如已经被压缩的数据,jpg图片、zip文件等),就会出现编码以后更大的情况。
在商业压缩软件上,避免这个问题的办法就是对高熵数据不压缩处理。

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问