哈夫曼编码
以下是哈夫曼编码的简陋实现方式,使用了STL库中的Vector和优先队列。只能对单字符进行编码,无法对中文进行编码,且算法有待改进。
1 #include <iostream> 2 #include <string> 3 #include <vector> 4 #include <queue> 5 using namespace std; 6 //哈夫曼树节点类 7 class HuffmanNode 8 { 9 public: 10 int weight=0; //权值 11 char ch; //节点值 12 HuffmanNode* left; //左孩子 13 HuffmanNode* right; //右孩子 14 HuffmanNode* parent;// 父结点 15 string code = ""; 16 HuffmanNode(double w, char c=NULL, HuffmanNode* l=NULL, HuffmanNode* r=NULL, HuffmanNode* p=NULL) : 17 weight(w), ch(c), left(l), right(r), parent(p) {} 18 }; 19 //STL库优先队列小顶堆比较类 20 class cmp 21 { 22 public: 23 bool operator () (HuffmanNode*& a, HuffmanNode*& b) const 24 { 25 return a->weight > b->weight; 26 } 27 }; 28 //前序遍历编码 29 void postOrderCoding(HuffmanNode* root,string code="") 30 { 31 if (root != NULL) 32 { 33 postOrderCoding(root->left,code+'0'); 34 postOrderCoding(root->right,code+'1'); 35 root->code = code; 36 } 37 } 38 //释放内存 39 void destroyTree(HuffmanNode* root) 40 { 41 if (root != NULL) 42 { 43 destroyTree(root->left); 44 destroyTree(root->right); 45 delete root; 46 } 47 } 48 //构建哈夫曼树 49 vector<HuffmanNode*> createHuffmanTree(string str) 50 { 51 //处理字符串,得到叶节点以及叶节点对应的权重 52 vector<HuffmanNode*> nodes;//(vector)nodes存放叶节点 53 for (int i = 0; i < str.size(); i++) 54 { 55 bool flag = false; 56 for (int j = 0; j < nodes.size(); j++) 57 { 58 if (str[i] == nodes[j]->ch) 59 { 60 flag = true; 61 nodes[j]->weight++; 62 break; 63 } 64 } 65 if (!flag) 66 nodes.push_back(new HuffmanNode(1, str[i])); 67 } 68 //简单地使用STL库中的优先队列 69 priority_queue<HuffmanNode* ,vector<HuffmanNode*>,cmp> q; 70 for (int i = 0; i < nodes.size(); i++) 71 q.push(nodes[i]); 72 //选择队列中权重最小的两棵树合并,将合并后的树放入优先队列中 73 while (q.size() != 1) 74 { 75 HuffmanNode* temp1 = q.top(); 76 q.pop(); 77 HuffmanNode* temp2 = q.top(); 78 q.pop(); 79 if (temp1->weight > temp2->weight) 80 swap(temp1, temp2); 81 HuffmanNode* father = new HuffmanNode(temp1->weight + temp2->weight, NULL, temp1, temp2); 82 q.push(father); 83 } 84 //nodes首位存放哈夫曼树根节点 85 nodes.insert(nodes.begin(), q.top()); 86 //进行编码 87 postOrderCoding(q.top()); 88 return nodes; 89 } 90 int main() 91 { 92 string str; 93 for (;;) 94 { 95 getline(cin, str); 96 vector<HuffmanNode*> nodes; 97 nodes = createHuffmanTree(str); 98 for (int i = 1; i < nodes.size(); i++) 99 { 100 cout << nodes[i]->ch << ":" << nodes[i]->code << endl; 101 } 102 destroyTree(nodes[0]); 103 } 104 }