在以前写LZW压缩算法的时候，遇到很多难受的问题，基本上都在哈夫曼编码中解决了，虽然写这代码很费神，但还是把代码完整的码出来了，毕竟哈夫曼这个思想确实很牛逼。哈夫曼树很巧妙的解决了当时我在LZW序列化的时候想解决的问题，就是压缩后文本的分割。比如用lzw编码abc，就是1,2,3。但这个在存为文件的时候必须用分割符把1,2,3分割开，非常浪费空间，否则会和12 23 123 产生二义性。而哈夫曼树，将所有char分布在叶节点上，在还原的时候，比如1101110，假设110是叶节点，那么走到110的时候就可以确定，已经走到尽头，回到根节点继续走，这样就避免了字符的分割，全部用1010101010101这样的路径表示字符，可以将8位压缩为1个char进行存储。在构造树的时候，将出现率高的char放在上面，这样路径就很短，自然就节省了存储空间。虽然哈夫曼压缩效率不是最高的，但还算比较乐观的。

哈夫曼除了压缩以外还可以用于加密，在将文本用哈夫曼编码时，需持久化生成的char计数链表结构，这样才能还原出树结构，而解码时路径正是依赖于树结构的。也就是说，这种编码是属于约定形式的编码，在编码时用原文本产生树结构，而存储的是树路径，解码的时候缺少树或树结构与原先不相符都是无法完成解码的，就好比，我用10代表a，你存的是10，你将10解释为 b或c等等都是不正确的。由于转换为了char存储，所以还需持久化最后填充的数目、文本长度，才能还原出原先的01表示的文本格式

这个代码有一定缺陷，由于当时考虑的是对文本进行处理，当文件中有char='\0' 时会出现错误，这个代码打的很费神，就不继续修复了，如有需要，可自行更改，解决的办法应该挺多的

先来个运行图：

源代码

#include<iostream> 
#include<sstream> 
#include<fstream> 
 
void WriteFile(char* path,const char* content,int length,bool append=false); 
using namespace std; 
struct Node{  
  char data; 
  Node* left; 
  Node* right;  
}; 
 
struct L_Node{ 
  int count; 
  Node* node; 
  L_Node* next; 
}; 
 
Node* AddNode(int count,char data,L_Node*& first){ 
  L_Node* lnode=new L_Node(); 
  lnode->count=count; 
  Node* node=new Node(); 
  node->data=data; 
  node->left=0; 
  node->right=0; 
  lnode->node=node; 
  if(first==0){ 
    first=lnode; 
  } 
  else{ 
    if(lnode->count<first->count){ 
      lnode->next=first; 
      first=lnode; 
    } 
    else{ 
      L_Node* iter=first; 
       
      while(iter->next!=0&&iter->next->count<lnode->count){ 
        iter=iter->next; 
      } 
       
      if(iter->next==0){ 
        iter->next=lnode; 
        lnode->next=0; 
      } 
      else{ 
        lnode->next=iter->next; 
        iter->next=lnode; 
      } 
    } 
  } 
  return node; 
} 
 
void SaveLNodes(L_Node* first){ 
  stringstream ss; 
  while(first!=0){ 
    ss<<(int)(unsigned char)first->node->data<<':'<<first->count<<' '; 
    first=first->next; 
  } 
  WriteFile("nodes.txt",ss.str().c_str(),ss.str().length()); 
} 
 
void GetLNodes(L_Node*& first){ 
  char temp[32]; 
  ifstream in; 
  in.open("nodes.txt",ios::in|ios::binary); 
  while(!in.eof()){ 
    temp[0]=0; 
    in>>temp; 
    if(strlen(temp)>0){ 
      char* data=strtok(temp,":"); 
      char* count=strtok(0,":"); 
      AddNode(atoi(count),atoi(data),first); 
    } 
     
  } 
} 
 
void BuildSortedList(char* content,L_Node*& first,int length){ 
  int array[256]={ 
    0 
  }; 
 
  for(int i=0;i<length;i++){ 
    array[(unsigned char)content[i]]++; 
  } 
 
  for(int i=0;i<256;i++){ 
    if(array[i]>0){ 
      AddNode(array[i],(char)i,first); 
    } 
  } 
  SaveLNodes(first); 
} 
 
void BuildTree(L_Node*& first,Node*& root){//get l1->node,l2->node,remove l1,l2,then put l3 into list,then set l3->left and l3->right 
  if(first->next==0){ 
    Node* node=new Node(); 
    root=node; 
    root->right=0; 
    node=new Node(); 
    node->data=first->node->data; 
    node->left=0; 
    node->right=0; 
    root->left=node; 
    delete first; 
    return; 
  } 
      
  while(first->next!=0){ 
    int count=first->count+first->next->count; 
    Node* node1=first->node; 
    L_Node* temp=first; 
    first=first->next; 
    delete temp; 
    Node* node2=first->node; 
    temp=first; 
    delete temp; 
    first=first->next; 
    root=AddNode(count,0,first); 
    root->left=node1; 
    root->right=node2; 
    //cout<<(int)node1->data<<':'<<(int)node2->data<<endl; 
  } 
  delete first; 
} 
 
void PreOrderTraversal(Node* node,char* track,int branch,char** table){ 
  if(node!=0){ 
     
    char* track2=0; 
     
    if(branch==0){ 
      track2=new char[strlen(track)+2]; 
      sprintf(track2,"%s0\0",track); 
    } 
    else if(branch==1){ 
      track2=new char[strlen(track)+2]; 
      sprintf(track2,"%s1\0",track); 
    } 
    else{ 
      track2=new char[strlen(track)+1]; 
      sprintf(track2,"%s\0",track); 
    } 
   
    if(node->data!=0){ 
      table[(unsigned char)node->data]=track2; 
    } 
     
    PreOrderTraversal(node->left,track2,0,table); 
    PreOrderTraversal(node->right,track2,1,table); 
     
   
    if(node->data==0){ 
      delete track2; 
    } 
  } 
} 
 
void PreOrderTraversal(Node* node){ 
  if(node!=0){ 
    cout<<(int)(unsigned char)node->data<<endl; 
    PreOrderTraversal(node->left); 
    PreOrderTraversal(node->right); 
  } 
} 
 
char* Encode(const char* content,char** table,int length){ 
   
  stringstream ss; 
 
  for(int i=0;i<length;i++){ 
    if((unsigned char)content[i]==0){ 
 
    } 
    else{ 
      ss<<table[(unsigned char)content[i]];  
    } 
  } 
   
   
  char* encoded_content=new char[ss.str().length()+1]; 
  memcpy(encoded_content,ss.str().c_str(),ss.str().length()); 
  encoded_content[ss.str().length()]=0; 
  return encoded_content; 
} 
 
int BinToDec(char* bin_content){ 
  int number=0; 
  int cur=1;  
  for(int i=7;i>=0;i--){ 
    number+=(bin_content[i]-'0')*cur; 
    cur*=2; 
  } 
  return number; 
}  
 
char* BinToCharText(const char* bin_content,int& fill_count,int& save_length){ 
  int length=strlen(bin_content); 
   
  fill_count=8-length%8; 
 
  if(fill_count>0){ 
    char* temp=new char[length+fill_count+1]; 
     
    char temp1[fill_count]; 
    for(int i=0;i<fill_count;i++){ 
      temp1[i]='0'; 
    } 
     
    sprintf(temp,"%s%s",bin_content,temp1); 
    temp[length+fill_count]=0; 
    bin_content=temp; 
  } 
   
  length+=fill_count; 
   
  save_length=length/8; 
 
  char* text=new char[length/8+1]; 
  for(int i=0;i<length;i+=8){ 
    char temp[8]; 
    memcpy(temp,bin_content+i,8); 
    text[i/8]=(char)BinToDec(temp); 
    
  } 
  text[length/8]=0; 
   
  if(fill_count>0){ 
    delete bin_content; 
  } 
   
  return text; 
} 
 
char* DecToBin(int num){ 
  char* bin=new char[8]; 
  if(num<0){ 
    num=256+num; 
  } 
   
  for(int i=7;i>=0;i--){ 
    bin[i]=num%2+'0'; 
    num/=2; 
  } 
  return bin; 
} 
 
char* CharTextToBin(char* text,int fill_count,int save_length){ 
  int length=save_length; 
 
  char* content=new char[8*length+1]; 
   
  int pos=0; 
  for(int i=0;i<length;i++){ 
    int number=text[i]; 
    char* bin=DecToBin(number); 
    memcpy(content+pos,bin,8); 
    pos+=8; 
    delete bin; 
  } 
   
  content[8*length-fill_count]=0; 
 
  return content; 
} 
 
char* Decode(const char* encode_content,Node* tree){ 
  stringstream ss; 
  Node* node=tree; 
 
  for(int i=0;i<strlen(encode_content);i++){ 
    if(encode_content[i]=='0'){ 
      node=node->left; 
    } 
    else if(encode_content[i]=='1'){ 
      node=node->right; 
    } 
 
    if(node->data!=0){ 
      ss<<node->data; 
      node=tree; 
    } 
  } 
  char* decode_content=new char[ss.str().length()+1]; 
  memcpy(decode_content,ss.str().c_str(),ss.str().length()); 
  decode_content[ss.str().length()]=0; 
  return decode_content; 
} 
 
 
void ReleaseTable(char** table){ 
  for(int i=0;i<256;i++){ 
    if(table[i]!=0){ 
      delete table[i]; 
    } 
  } 
} 
 
void PostOrderTraversal(Node* node){ 
  if(node!=0){ 
    PostOrderTraversal(node->left); 
    PostOrderTraversal(node->right); 
    delete node; 
  } 
}  
 
char* ReadFile(char* path,long& length){ 
  char* content=0; 
  ifstream in; 
  in.open(path,ios::in|ios::binary); 
  in.seekg(0,ios::end); 
  length=in.tellg(); 
  content=new char[length+1]; 
  in.seekg(0,ios::beg); 
  int i=0; 
  while(!in.eof()){ 
    content[i++]=in.get(); 
  } 
  content[length]=0; 
  in.close(); 
  return content; 
} 
 
char* ReadFile(char* path,int& fill_count,int& save_length){ 
  char* content=0; 
  ifstream in; 
  in.open(path,ios::in|ios::binary); 
  in>>fill_count>>save_length; 
  long cur=in.tellg()+(long)1; 
  in.seekg(0,ios::end); 
  long length=in.tellg()-cur; 
  content=new char[length+1]; 
  in.seekg(cur,ios::beg); 
  int i=0; 
  while(!in.eof()){ 
    content[i++]=in.get(); 
  } 
  content[length]=0; 
  in.close(); 
  return content; 
} 
 
void WriteFile(char* path,const char* content,int length,bool append){ 
  ofstream out; 
  if(append){ 
    out.open(path,ios::out|ios::binary|ios::app); 
  } 
  else{ 
    out.open(path,ios::out|ios::binary); 
  } 
   
  out.write(content,length); 
  out.close(); 
} 
 
int main(){ 
  long length; 
  char* content=ReadFile("content.txt",length); 
 
  L_Node* first=0; 
   
  BuildSortedList(content,first,length); //create nodes list and save to nodes file 
  //GetLNodes(first);//get and recreate nodes from file 
 
  Node* root=0;//used for buildtable and decode 
  BuildTree(first,root);//build tree by nodes list and release sorted list 
   
  char* table[256]={//build table,used for encode 
    0 
  }; 
 
  PreOrderTraversal(root,"",-1,table);//create table 
   
 
  char* encode_content=Encode(content,table,length);//convert content to encoded bin text 
  cout<<encode_content<<endl; 
  delete content; 
   
  ReleaseTable(table);//release table when encode finished 
   
   
  int fill_count; 
  int save_length; 
  char* save_text=BinToCharText(encode_content,fill_count,save_length);//convert encoded bin text to char text and save these text to file 
  delete encode_content; 
  char head_info[32]; 
  sprintf(head_info,"%d %d ",fill_count,save_length); 
  WriteFile("encoded_content.txt",head_info,strlen(head_info)); 
  WriteFile("encoded_content.txt",save_text,save_length,true); 
  delete save_text; 
  save_text=ReadFile("encoded_content.txt",fill_count,save_length);//read fill_count、save_length、encoded char text from file 
   
  char* bin_text= CharTextToBin(save_text,fill_count,save_length);//convert char text to bin text 
  delete save_text; 
   
  char* decode_content=Decode(bin_text,root);//decode by bin_text and tree 
  cout<<decode_content<<endl; 
  delete bin_text; 
  delete decode_content; 
   
   
  PostOrderTraversal(root);//release tree 
   
  return 0; 
} 

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。

# C++  # 哈夫曼树  # 哈夫曼树文件压缩  # 哈夫曼树压缩文件  # C++深入讲解哈夫曼树  # C++详解哈夫曼树的概念与实现步骤  # C++实现哈夫曼树的方法  # C++实现哈夫曼树编码解码  # C++实现哈夫曼树算法  # C++数据结构与算法之哈夫曼树的实现方法  # C++数据结构之文件压缩（哈夫曼树）实例详解  # 解析C++哈夫曼树编码和译码的实现  # C++实现哈夫曼树简单创建与遍历的方法  # C++使用数组来实现哈夫曼树  # 的是  # 都是  # 化生  # 解决了  # 我在  # 放在  # 还可以  # 都在  # 走到  # 就不  # 如有  # 中有  # 有一定  # 我用  # 还算  # 你将  # 来个  # 则会  # 不正确  # 还需 

相关栏目： 【 网站优化151355 】 【 网络推广146373 】 【 网络技术251813 】 【 AI营销90571 】

相关推荐： ,网页ppt怎么弄成自己的ppt？  百度浏览器ai对话怎么关 百度浏览器ai聊天窗口隐藏  如何在宝塔面板中创建新站点？  什么是javascript作用域_全局和局部作用域有什么区别？  Laravel如何编写单元测试和功能测试？（PHPUnit示例）  Laravel如何使用Laravel Vite编译前端_Laravel10以上版本前端静态资源管理【教程】  美食网站链接制作教程视频,哪个教做美食的网站比较专业点？  html文件怎么打开证书错误_https协议的html打开提示不安全【指南】  网站制作免费,什么网站能看正片电影？  Laravel如何为API生成Swagger或OpenAPI文档  如何挑选最适合建站的高性能VPS主机？  如何在万网利用已有域名快速建站？  ChatGPT常用指令模板大全 新手快速上手的万能Prompt合集  如何用JavaScript实现文本编辑器_光标和选区怎么处理  如何在服务器上配置二级域名建站？  北京企业网站设计制作公司,北京铁路集团官方网站？  如何快速搭建安全的FTP站点？  如何快速搭建高效可靠的建站解决方案？  Laravel软删除怎么实现_Laravel Eloquent SoftDeletes功能使用教程  Python文件操作最佳实践_稳定性说明【指导】  详解Huffman编码算法之Java实现  简单实现Android文件上传  百度浏览器网页无法复制文字怎么办 百度浏览器复制修复  如何在建站之星绑定自定义域名？  Laravel如何与Pusher实现实时通信？（WebSocket示例）  Win11关机界面怎么改_Win11自定义关机画面设置【工具】  惠州网站建设制作推广,惠州市华视达文化传媒有限公司怎么样？  如何在阿里云域名上完成建站全流程？  Laravel怎么实现前端Toast弹窗提示_Laravel Session闪存数据Flash传递给前端【方法】  如何快速搭建高效简练网站？  Java垃圾回收器的方法和原理总结  高防服务器租用首荐平台，企业级优惠套餐快速部署  七夕网站制作视频,七夕大促活动怎么报名？  logo在线制作免费网站在线制作好吗,DW网页制作时，如何在网页标题前加上logo？  Laravel的辅助函数有哪些_Laravel常用Helpers函数提高开发效率  如何在建站之星网店版论坛获取技术支持？  如何快速生成橙子建站落地页链接？  绝密ChatGPT指令：手把手教你生成HR无法拒绝的求职信  Laravel如何实现API版本控制_Laravel API版本化路由设计策略  详解jQuery中基本的动画方法  html5的keygen标签为什么废弃_替代方案说明【解答】  php中::能调用final静态方法吗_final修饰静态方法调用规则【解答】  Bootstrap CSS布局之列表  如何用ChatGPT准备面试 模拟面试问答与职场话术练习教程  矢量图网站制作软件,用千图网的一张矢量图做公司app首页，该网站并未说明版权等问题，这样做算不算侵权？应该如何解决？  如何自定义建站之星网站的导航菜单样式？  高端建站如何打造兼具美学与转化的品牌官网？  Win11怎么修改DNS服务器 Win11设置DNS加速网络【指南】  今日头条微视频如何找选题 今日头条微视频找选题技巧【指南】  如何快速搭建高效香港服务器网站？