哈夫曼编解码C++实现

 C++ Code 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228

#include <iostream> #include <vector> #include <string> #include <map> using namespace std; // 哈夫曼编码 template<typename Type> class CHaffumanCode { public:     //哈夫曼树的结点结构     typedef struct _HaffNode {         typename Type symbol;       // 符号         int weight;         //权值         int flag;           //标记，是否存在父节点         int parent;         //双亲结点下标         int leftChild;      //左孩子下标         int rightChild;     //右孩子下标     }HaffNode;     // 设置符号列表及权重列表     void Set(const std::vector<Type> &symbolVec, const std::vector<int> &weightVec){         m_symbolVec = symbolVec;         m_weightVec = weightVec;     }     // 添加符号及相应的权重     void Push(const Type &d, int weight){         m_symbolVec.push_back(d);         m_weightVec.push_back(weight);     }     // 由符号及权重建立基于数组的哈夫曼树     void BuildHaffmanTree(){         int iSymbolNum = m_weightVec.size();         m_haffTree.clear(); //哈夫曼树haffTree初始化。n个叶结点的哈夫曼树共有2n-1个结点         m_haffTree.reserve(2*iSymbolNum-1);         for(int i = 0; i < 2 * iSymbolNum - 1 ; i++){             HaffNode hNode;             if(i < iSymbolNum) {                 hNode.weight = m_weightVec[i];                 hNode.symbol = m_symbolVec[i];             }             else                     hNode.weight = 0;             hNode.parent = 0;             hNode.flag   = 0;             hNode.leftChild = -1;             hNode.rightChild = -1;             m_haffTree.push_back(hNode);         }         //构造哈夫曼树haffTree的n-1个非叶结点         for(int i = 0; i < iSymbolNum-1; i++)   {             int iMin_1 = INT_MAX, iMin_2 = INT_MAX; // iMin_1 存放最小值，iMin_2存放次小值             int iMin_1_pos = 0, iMin_2_pos = 0;    // iMin_1_pos指示最小值的位置，iMin_2_pos指示次小值的位置             for(int j = 0; j < iSymbolNum+i; j++)   {                 if (m_haffTree[j].weight < iMin_1 && m_haffTree[j].flag == 0){                     iMin_2 = iMin_1;                     iMin_2_pos = iMin_1_pos;                     iMin_1 = m_haffTree[j].weight;                     iMin_1_pos = j;                 }                 else if(m_haffTree[j].weight < iMin_2 && m_haffTree[j].flag == 0){                     iMin_2 = m_haffTree[j].weight;                     iMin_2_pos = j;                 }             }             //将找出的两棵权值最小的子树合并为一棵子树             m_haffTree[iMin_1_pos].parent  = iSymbolNum+i;                m_haffTree[iMin_2_pos].parent  = iSymbolNum+i;             m_haffTree[iMin_1_pos].flag    = 1;             m_haffTree[iMin_2_pos].flag    = 1;             m_haffTree[iSymbolNum+i].weight = m_haffTree[iMin_1_pos].weight+m_haffTree[iMin_2_pos].weight;             m_haffTree[iSymbolNum+i].leftChild = iMin_1_pos;             m_haffTree[iSymbolNum+i].rightChild = iMin_2_pos;         }     }     // 由哈夫曼树构建(符号,码)对     void BuildHaffmanCode(){         int n = m_haffTree.size()/2+1;         for(int i = 0; i < n; i++)  { //求n个叶结点的哈夫曼编码             typename Type symbol = m_haffTree[i].symbol;             string szKey;             int child = i;             int parent = m_haffTree[child].parent;             //由叶结点向上直到根结点             while(parent != 0)             {                 if(m_haffTree[parent].leftChild == child)                     szKey.push_back('0');                 else                                         szKey.push_back('1');                 child = parent;                 parent = m_haffTree[child].parent;             }             m_codeMap[symbol] = string(szKey.rbegin(), szKey.rend());         }     }     // 哈夫曼编码     /*      * @Parm begin [in]: 符号流的起始迭代位置      * @Parm end [in]: 符号流的结束迭代位置      * @Parm szCode [in/out]: 输出码流      */     template<typename IterateType>     void Encode(IterateType begin, IterateType end, std::string &szCode){         for (; begin != end; ++begin){             if (m_codeMap.lower_bound(*begin) == m_codeMap.end()){                 std::cout << "Encode : 未知符号..." << endl;                 return;             }             szCode += m_codeMap[*begin];         }     }     /*      * @Parm begin [in]: 符号流的起始迭代位置      * @Parm end [in]: 符号流的结束迭代位置      * @Parm szCode [in/out]: 输出码流      */     template<typename IterateType>     std::string Encode(IterateType begin, IterateType end){         std::string szCode;         for (; begin != end; ++begin){             if (m_codeMap.lower_bound(*begin) == m_codeMap.end()){                 std::cout << "Encode : 未知符号..." << endl;                 return szCode;             }             szCode += m_codeMap[*begin];         }         return szCode;     }     // 哈夫曼解码     void Decode(const std::string &szCode, std::vector<Type> &symbolVec){         int iPos = m_haffTree.size() - 1; // 解码前至于根节点处         for (auto it = szCode.begin(); it != szCode.end(); ++it){             if (*it == '0')                 iPos = m_haffTree[iPos].leftChild;             else if (*it == '1')                 iPos = m_haffTree[iPos].rightChild;             // 该节点为叶子节点             if ((m_haffTree[iPos].leftChild == -1) && (m_haffTree[iPos].rightChild == -1)){                  symbolVec.push_back(m_haffTree[iPos].symbol);                 iPos =  m_haffTree.size() - 1;             }         }     }     std::vector<Type> Decode(const std::string &szCode){         std::vector<Type> &symbolVec;         int iPos = m_haffTree.size() - 1; // 解码前至于根节点处         for (auto it = szCode.begin(); it != szCode.end(); ++it){             if (*it == '0')                 iPos = m_haffTree[iPos].leftChild;             else if (*it == '1')                 iPos = m_haffTree[iPos].rightChild;             // 该节点为叶子节点             if ((m_haffTree[iPos].leftChild == -1) && (m_haffTree[iPos].rightChild == -1)){                  symbolVec.push_back(m_haffTree[iPos].symbol);                 iPos =  m_haffTree.size() - 1;             }         }     }     // 打印编码信息     void PrintCodeInfo(){         for (auto it = m_codeMap.begin(); it != m_codeMap.end(); ++it){             std::cout << it->first << ", ";         }         std::cout << endl;         for (auto it = m_codeMap.begin(); it != m_codeMap.end(); ++it){             std::cout << it->second.length() << ", ";         }         cout << endl;         for (auto it = m_codeMap.begin(); it != m_codeMap.end(); ++it){             std::cout << "<" << it->first << ", 长度为 " << it->second.length() << ", " << it->second << ">" << endl;         }     } private:     std::vector<Type> m_symbolVec; // 符号列表     std::vector<int> m_weightVec;  // 符号对应的权重列表     std::vector<HaffNode> m_haffTree; // 哈夫曼树     std::map<Type, std::string> m_codeMap; }; void main(void){     int symbol[] =  {100, 1, 1, 1, 2, 3, 5, 7, 59,100, 1, 2, 3, 5, 7, 59,16, 20, 30, 99, 40,100, 1, 2, 3, 5, 7, 59, 8, 10, 12, 78, 14, 16, 20, 30, 99, 40, 50, 97, 120};     int weight[] = {100, 1, 2, 3, 5, 7, 59, 8, 10, 12, 78, 14, 16, 20, 30, 99, 40, 50, 97, 120};     CHaffumanCode<int> haff;     haff.Set(vector<int>(weight, weight+sizeof(weight)/sizeof(int)), vector<int>(weight, weight+sizeof(weight)/sizeof(int)));     haff.BuildHaffmanTree();     haff.BuildHaffmanCode();     haff.PrintCodeInfo();     string szCode;     haff.Encode(symbol, symbol+sizeof(symbol)/sizeof(int), szCode);     cout << "码流：\n\n" << szCode << endl;     cout << "编码前的符号：" << endl;     ostream_iterator<int> out(cout, ", ");     copy(symbol, symbol+sizeof(symbol)/sizeof(int), out);     cout << "\n解码后的符号：" << endl;     vector<int> symVec;     haff.Decode(szCode, symVec);     copy(symVec.begin(), symVec.end(), out);     cout << endl; }