本帖最后由 反光镜 于 2018-5-27 15:29 编辑
#include <iostream> #include <list> #include <vector> #include <iomanip> using namespace std; struct Huff_node { int bit; float prob; // Huff_node*next_node1; // Huff_node*next_node2; // Huff_node*next_node3; Huff_node*pre_node; }; bool compareProb(Huff_node*, Huff_node*); void ClearHuffNodeIndex(list<Huff_node*> *); void print_Huff_Code(list<Huff_node*> *); int main() { //vector里依次输入N个概率，N未定 list<Huff_node*> Huff_node_index_B; list<Huff_node*> Huff_node_encode_B; list<Huff_node*> Huff_node_index_T; list<Huff_node*> Huff_node_encode_T; int num; Huff_node*tmpHuff_node; Huff_node*tmpHuff_node1; Huff_node*tmpHuff_node2; Huff_node*tmpHuff_node3; while(1) { //每输入一个概率，new一个node，存入概率 cout<< "请输入大于3的概率数量n=" ; cin>> num; if(num<=3) { cout<< "请检查输入概率数量n是否大于3!!"<< endl << endl; continue; } cout<< endl << "请输入概率:" << endl; while(num>0) { tmpHuff_node1 = new Huff_node; tmpHuff_node2 = new Huff_node; cin >> tmpHuff_node1->prob; tmpHuff_node1->pre_node= nullptr; tmpHuff_node1->bit = -1; *tmpHuff_node2 = *tmpHuff_node1; //二进制和三进制分别存储一份数据 Huff_node_index_B.push_back(tmpHuff_node1); Huff_node_index_T.push_back(tmpHuff_node2); --num; } // if(sumProb>1) // { // cout << "ERROR！概率输入有误，请重新输入全部概率" << endl << endl; // ClearHuffNodeIndex(&Huff_node_index_B); //清空所有霍夫曼节点和索引 // ClearHuffNodeIndex(&Huff_node_index_T); // continue; // } //输入完毕，vector进行sort，从大到小排序，并建立编码vector组 Huff_node_index_B.sort(compareProb); Huff_node_index_T.sort(compareProb); Huff_node_encode_B = Huff_node_index_B; Huff_node_encode_T = Huff_node_index_T; //霍夫曼二进制编码 while(Huff_node_encode_B.size()!=1)//当vector的元素不等于1 { tmpHuff_node1 = Huff_node_encode_B.back(); Huff_node_encode_B.pop_back(); tmpHuff_node2 = Huff_node_encode_B.back(); Huff_node_encode_B.pop_back(); tmpHuff_node1->bit = 0; tmpHuff_node2->bit = 1; //建立前向链接 tmpHuff_node = new Huff_node; tmpHuff_node->bit=-1; tmpHuff_node->pre_node = nullptr; tmpHuff_node->prob=tmpHuff_node1->prob+ tmpHuff_node2->prob; //取出最前面的两个node，挂接到新new的node后面 tmpHuff_node1->pre_node = tmpHuff_node; tmpHuff_node2->pre_node = tmpHuff_node; //将new node放入vector尾部 Huff_node_encode_B.push_back(tmpHuff_node); //重新sort Huff_node_encode_B.sort(compareProb); } //执行霍夫曼二进制的输出 cout<< endl << endl << "霍夫曼二进制编码为:"<< endl; print_Huff_Code(&Huff_node_index_B); //霍夫曼三进制编码 while(Huff_node_encode_T.size()>2)//当vector的元素不等于1 { tmpHuff_node1 = Huff_node_encode_T.back(); Huff_node_encode_T.pop_back(); tmpHuff_node2= Huff_node_encode_T.back(); Huff_node_encode_T.pop_back(); tmpHuff_node3 = Huff_node_encode_T.back(); Huff_node_encode_T.pop_back(); tmpHuff_node1->bit = 0; tmpHuff_node2->bit = 1; tmpHuff_node3->bit = 2; //建立前向链接 tmpHuff_node = new Huff_node; tmpHuff_node->pre_node =nullptr; tmpHuff_node->prob=tmpHuff_node1->prob+tmpHuff_node2->prob+tmpHuff_node3->prob; //取出最前面的两个node，挂接到新new的node后面 tmpHuff_node1->pre_node = tmpHuff_node; tmpHuff_node2->pre_node = tmpHuff_node; tmpHuff_node3->pre_node = tmpHuff_node; //将new node放入vector尾部 Huff_node_encode_T.push_back(tmpHuff_node); //重新sort Huff_node_encode_T.sort(compareProb); } if(Huff_node_encode_T.size()==2) { tmpHuff_node1 = Huff_node_encode_T.back(); tmpHuff_node1->bit = 0; Huff_node_encode_T.pop_back(); tmpHuff_node2 = Huff_node_encode_T.back(); tmpHuff_node2->bit = 1; } //执行霍夫曼三进制的输出 cout<< endl << endl << "霍夫曼三进制编码为:"<< endl; print_Huff_Code(&Huff_node_index_T); ClearHuffNodeIndex(&Huff_node_index_B); ClearHuffNodeIndex(&Huff_node_index_T); cout<< endl << endl << endl; }//Processingcompleted, go to next circle } bool compareProb(Huff_node* node1, Huff_node* node2) { if(node1->prob > node2->prob ) returntrue; else returnfalse; } void ClearHuffNodeIndex(list<Huff_node*> *index) { for(list<Huff_node*>::iterator i = (*index).begin();i!= (*index).end();i++) { delete(*i); } (*index).clear(); } void print_Huff_Code(list<Huff_node*> *to_print) { Huff_node*curHuff_node; vector<int> curCode; for(list<Huff_node*>::iterator i =(*to_print).begin();i != (*to_print).end();i++) { curHuff_node = (*i); cout<< setw(8) << curHuff_node->prob << " 的编码: " ; while(curHuff_node->pre_node!=nullptr) { curCode.push_back(curHuff_node->bit); curHuff_node = curHuff_node->pre_node; } if(curHuff_node->bit!=-1) curCode.push_back(curHuff_node->bit); for(intj=curCode.size();j>0;j--) { cout<< curCode[j-1]; } curCode.clear(); cout<< endl; } }
| 
