生成哈夫曼编码的代码实现

  1 #include <iostream>
  2 #include <vector>
  3 #include <stack>
  4 #include <string>
  5 #include <algorithm>
  6 
  7 using std::cin;
  8 using std::cout;
  9 using std::endl;
 10 using std::vector;
 11 using std::sort;
 12 using std::string;
 13 
 14 struct _WEIGHTNODE {
 15     float weight;
 16     char value;
 17     struct _WEIGHTNODE *ptrLeft, *ptrRight, *ptrParent;
 18 
 19     _WEIGHTNODE(char _input, float _W) {
 20         weight = _W;
 21         value = _input;
 22         ptrLeft = ptrRight = ptrParent = nullptr;
 23     }
 24 
 25     _WEIGHTNODE() {
 26         weight = 0.0f;
 27         value = ‘?‘;
 28         ptrLeft = ptrRight = ptrParent = nullptr;
 29     }
 30 
 31     _WEIGHTNODE(const struct _WEIGHTNODE &n) {
 32         weight = n.weight;
 33         value = n.value;
 34         ptrLeft = n.ptrLeft;
 35         ptrRight = n.ptrRight;
 36         ptrParent = n.ptrParent;
 37     }
 38 
 39     friend std::ostream &operator<<(std::ostream &output, struct _WEIGHTNODE const *NODE) {
 40         return output << "Value : " << NODE->value << " --- Weight : " << NODE->weight;
 41     }
 42 };
 43 
 44 typedef struct _WEIGHTNODE NODE;
 45 
 46 void GetLeaf(NODE *root, vector<NODE *> &leaf) {
 47     if (root) {
 48         if (root->value != ‘#‘) {
 49             leaf.push_back(root);
 50         }
 51         GetLeaf(root->ptrLeft, leaf);
 52         GetLeaf(root->ptrRight, leaf);
 53     }
 54 }
 55 
 56 bool compareWeight(const NODE *n1, const NODE *n2) {
 57     return n1->weight < n2->weight;
 58 }
 59 
 60 int main() {
 61     vector<NODE *> TotalValues;
 62     float inputWeight;
 63     char inputValue;
 64     while (cin >> inputValue >> inputWeight) {
 65         if (inputWeight < 0 || inputValue == ‘?‘) {
 66             break;
 67         }
 68         TotalValues.push_back(new NODE(inputValue, inputWeight));
 69     }
 70 
 71     for (auto EachMember : TotalValues) {
 72         cout << EachMember << endl;
 73     }
 74     cout << endl << "=== Huffman Code ===" << endl;
 75 
 76     //根据已有节点创建Huffman Tree
 77     while (TotalValues.size() > 1) {
 78         //从小到大排序
 79         sort(TotalValues.begin(), TotalValues.end(), compareWeight);
 80 
 81         NODE *tmp1 = *TotalValues.begin();
 82         TotalValues.erase(TotalValues.begin());
 83 
 84         NODE *tmp2 = *TotalValues.begin();
 85         TotalValues.erase(TotalValues.begin());
 86 
 87         NODE *CombinedNode = new NODE(‘#‘, tmp1->weight + tmp2->weight);
 88         CombinedNode->ptrLeft = tmp1;
 89         CombinedNode->ptrRight = tmp2;
 90         tmp1->ptrParent = tmp2->ptrParent = CombinedNode;
 91 
 92         TotalValues.push_back(CombinedNode);
 93     }
 94 
 95     NODE *ptrRoot = *TotalValues.begin();
 96 
 97     //根据生成的Huffman Tree求各节点的编码
 98     if (ptrRoot == nullptr) {
 99         cout << "Empty BinaryTree" << endl;
100         return 0;
101     }
102 
103     //存放所有叶子节点
104     //从下往上逆向寻找
105     vector<NODE *> leaves;
106     GetLeaf(ptrRoot, leaves);
107 
108     float WPL = 0.0f;
109 
110     for (auto leaf:leaves) {
111 
112         char alphe = leaf->value;
113         float tmpWPL = leaf->weight;
114 
115         string code;
116         while (leaf->ptrParent != nullptr) {
117             if (leaf == leaf->ptrParent->ptrLeft) {
118                 code = ‘0‘ + code;
119             } else {
120                 code = ‘1‘ + code;
121             }
122             leaf = leaf->ptrParent;
123         }
124         WPL += tmpWPL * code.length();
125         cout << alphe << " : " << code << endl;
126     }
127 
128     cout<<endl<<"WPL : "<<WPL<<endl;
129     //缺少delete相关功能
130 
131     return 0;
132 }