實現一個Huffman編碼類

//霍夫曼編碼 #include <iostream> #include <vector> #include <string> using namespace std;struct node{int freq;char c;node * left;node * right; };class HuffmanCode{//調用Insert插入字符與相應頻率，完了以后調用HuffmanCoding返回結果。private:vector<node*> input;vector<pair<char,string>> result;public:node * ExtractMinFreq(vector<node*> &arg);//找到freq最小的指針vector<pair<char,string>> HuffmanCoding();//執行霍夫曼編碼，返回編碼結果的vector，pair里char對應字符，string對應編碼 void Coding(node* arg,string str_tmp); //HuffmanCode里面調用的編碼過程 void InsertNode(const char c, const int freq);//類插入數據的方法 void Delete(node *p);//執行完編碼以后，清理掉樹 void ShowTree(node *p); };int main(){HuffmanCode code;vector<node*> input;code.InsertNode('e',9);code.InsertNode('c',12);code.InsertNode('b',13);code.InsertNode('d',16);code.InsertNode('a',45);code.InsertNode('f',5);vector<pair<char,string>> result;result = code.HuffmanCoding();cout<<"result size="<<result.size()<<endl;pair<char,string> tmp_pair;vector<pair<char,string>>::iterator it;for(it=result.begin();it!=result.end();it++){tmp_pair = *it;cout<<"char="<<tmp_pair.first<<" code="<<tmp_pair.second<<endl;}}void HuffmanCode::InsertNode(const char c, const int freq){node *p=new node;p->c = c;p->freq = freq;p->left = NULL;p->right = NULL;input.push_back(p);return; }node * HuffmanCode::ExtractMinFreq(vector<node*> &arg){vector<node*>::iterator it,it_min=arg.begin();node * min=arg[0];for(it=arg.begin();it!=arg.end();it++){if((*it)->freq<min->freq){min = *it;it_min = it;} }arg.erase(it_min);cout<<"extract ok"<<endl;cout<<"min char="<<min->c<<endl;return min;} void HuffmanCode::Coding(node* arg,string str_tmp){if(arg->left==NULL){result.push_back(make_pair(arg->c,str_tmp));return;} string str_out;str_out = str_tmp+'0';cout<<"left str_out="<<str_out<<endl;Coding(arg->left,str_out);str_out = str_tmp+'1';cout<<"right str_out="<<str_out<<endl;Coding(arg->right,str_out); }void HuffmanCode::ShowTree(node *p){if(p==NULL) return;ShowTree(p->left);cout<<"char="<<p->c<<" code="<<p->freq<<endl;ShowTree(p->right); }void HuffmanCode::Delete(node *p){if(p->left==NULL){delete p;return;}Delete(p->left);Delete(p->right);delete p;return; }vector<pair<char,string>> HuffmanCode::HuffmanCoding(){vector<node*> tmp_vector=input;int n=tmp_vector.size();cout<<"n="<<n<<endl;node * tmp_node,*x,*y;for(int i=0;i<n-1;i++){x = ExtractMinFreq(tmp_vector);cout<<"x char="<<x->c<<" x freq="<<x->freq<<endl;y = ExtractMinFreq(tmp_vector);cout<<"y char="<<y->c<<" y freq="<<y->freq<<endl;tmp_node = new node;tmp_node->c = '$';tmp_node->freq = x->freq+y->freq;tmp_node->left = x;tmp_node->right = y;cout<<"tmp char="<<tmp_node->c<<" tmp freq="<<tmp_node->freq<<endl;tmp_vector.push_back(tmp_node); }cout<<"tree ok"<<endl;cout<<"size="<<tmp_vector.size()<<endl;tmp_node = tmp_vector[0];ShowTree(tmp_node);cout<<"tree root"<<endl;if(tmp_node->left==NULL)cout<<"NULL"<<endl;string str;Coding(tmp_node,str);Delete(tmp_node);return vector<pair<char,string>>(result);}

?

總結

以上是生活随笔為你收集整理的Huffman编码实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。