這篇文章主要介紹了C++如何實(shí)現(xiàn)哈夫曼樹(shù)對(duì)文件壓縮、加密功能，具有一定借鑒價(jià)值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

公司主營(yíng)業(yè)務(wù)：成都網(wǎng)站設(shè)計(jì)、成都做網(wǎng)站、移動(dòng)網(wǎng)站開(kāi)發(fā)等業(yè)務(wù)。幫助企業(yè)客戶(hù)真正實(shí)現(xiàn)互聯(lián)網(wǎng)宣傳，提高企業(yè)的競(jìng)爭(zhēng)能力。創(chuàng)新互聯(lián)是一支青春激揚(yáng)、勤奮敬業(yè)、活力青春激揚(yáng)、勤奮敬業(yè)、活力澎湃、和諧高效的團(tuán)隊(duì)。公司秉承以“開(kāi)放、自由、嚴(yán)謹(jǐn)、自律”為核心的企業(yè)文化，感謝他們對(duì)我們的高要求，感謝他們從不同領(lǐng)域給我們帶來(lái)的挑戰(zhàn)，讓我們激情的團(tuán)隊(duì)有機(jī)會(huì)用頭腦與智慧不斷的給客戶(hù)帶來(lái)驚喜。創(chuàng)新互聯(lián)推出秦都免費(fèi)做網(wǎng)站回饋大家。

在以前寫(xiě)LZW壓縮算法的時(shí)候，遇到很多難受的問(wèn)題，基本上都在哈夫曼編碼中解決了，雖然寫(xiě)這代碼很費(fèi)神，但還是把代碼完整的碼出來(lái)了，畢竟哈夫曼這個(gè)思想確實(shí)很牛逼。哈夫曼樹(shù)很巧妙的解決了當(dāng)時(shí)我在LZW序列化的時(shí)候想解決的問(wèn)題，就是壓縮后文本的分割。比如用lzw編碼abc，就是1,2,3。但這個(gè)在存為文件的時(shí)候必須用分割符把1,2,3分割開(kāi)，非常浪費(fèi)空間，否則會(huì)和12 23 123 產(chǎn)生二義性。而哈夫曼樹(shù)，將所有char分布在葉節(jié)點(diǎn)上，在還原的時(shí)候，比如1101110，假設(shè)110是葉節(jié)點(diǎn)，那么走到110的時(shí)候就可以確定，已經(jīng)走到盡頭，回到根節(jié)點(diǎn)繼續(xù)走，這樣就避免了字符的分割，全部用1010101010101這樣的路徑表示字符，可以將8位壓縮為1個(gè)char進(jìn)行存儲(chǔ)。在構(gòu)造樹(shù)的時(shí)候，將出現(xiàn)率高的char放在上面，這樣路徑就很短，自然就節(jié)省了存儲(chǔ)空間。雖然哈夫曼壓縮效率不是最高的，但還算比較樂(lè)觀(guān)的。

哈夫曼除了壓縮以外還可以用于加密，在將文本用哈夫曼編碼時(shí)，需持久化生成的char計(jì)數(shù)鏈表結(jié)構(gòu)，這樣才能還原出樹(shù)結(jié)構(gòu)，而解碼時(shí)路徑正是依賴(lài)于樹(shù)結(jié)構(gòu)的。也就是說(shuō)，這種編碼是屬于約定形式的編碼，在編碼時(shí)用原文本產(chǎn)生樹(shù)結(jié)構(gòu)，而存儲(chǔ)的是樹(shù)路徑，解碼的時(shí)候缺少樹(shù)或樹(shù)結(jié)構(gòu)與原先不相符都是無(wú)法完成解碼的，就好比，我用10代表a，你存的是10，你將10解釋為 b或c等等都是不正確的。由于轉(zhuǎn)換為了char存儲(chǔ)，所以還需持久化最后填充的數(shù)目、文本長(zhǎng)度，才能還原出原先的01表示的文本格式

這個(gè)代碼有一定缺陷，由于當(dāng)時(shí)考慮的是對(duì)文本進(jìn)行處理，當(dāng)文件中有char='\0' 時(shí)會(huì)出現(xiàn)錯(cuò)誤，這個(gè)代碼打的很費(fèi)神，就不繼續(xù)修復(fù)了，如有需要，可自行更改，解決的辦法應(yīng)該挺多的

先來(lái)個(gè)運(yùn)行圖：

源代碼

#include 
#include 
#include 
 
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->countcount){ 
      lnode->next=first; 
      first=lnode; 
    } 
    else{ 
      L_Node* iter=first; 
       
      while(iter->next!=0&&iter->next->countcount){ 
        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<<':'<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;i0){ 
      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<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<left); 
    PreOrderTraversal(node->right); 
  } 
} 
 
char* Encode(const char* content,char** table,int length){ 
   
  stringstream ss; 
 
  for(int i=0;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;i0){ 
    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;ileft; 
    } 
    else if(encode_content[i]=='1'){ 
      node=node->right; 
    } 
 
    if(node->data!=0){ 
      ss<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<
感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享的“C++如何實(shí)現(xiàn)哈夫曼樹(shù)對(duì)文件壓縮、加密功能”這篇文章對(duì)大家有幫助，同時(shí)也希望大家多多支持創(chuàng)新互聯(lián)建站，關(guān)注創(chuàng)新互聯(lián)網(wǎng)站建設(shè)公司行業(yè)資訊頻道，更多相關(guān)知識(shí)等著你來(lái)學(xué)習(xí)!
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)建站www.cdcxhl.com，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線(xiàn)，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性?xún)r(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專(zhuān)為企業(yè)上云打造定制，能夠滿(mǎn)足用戶(hù)豐富、多元化的應(yīng)用場(chǎng)景需求。
            

            網(wǎng)站名稱(chēng)：C++如何實(shí)現(xiàn)哈夫曼樹(shù)對(duì)文件壓縮、加密功能-創(chuàng)新互聯(lián)            

            文章來(lái)源：http://weahome.cn/article/diejpc.html