C++實現哈夫曼編碼完整代碼

C++實現哈夫曼編碼完整代碼

#include <iostream>
#include <queue>
#include <vector>
#include <map>
#include <string>

using namespace std;

class Node {
public:
char c; //表示字符
int frequency; //表示該字符出現的次數或頻率
Node *left;
Node *right;

Node(char _c, int f, Node *l = NULL, Node *r = NULL)
:c(_c), frequency(f), left(l), right(r) { }

bool operator<(const Node &node) const { //重載<運算法以至於在加入優先隊列的時候決定如何處理結點位置
return frequency > node.frequency;
}
};

void initNode(priority_queue<Node> &q, int nodeNum) {
char c;
int frequency;
for (int i = 0; i < nodeNum; i++) {
cout << "輸入字符和結點出現的次數: ";
cin >> c >> frequency;
Node node(c, frequency);
q.push(node);
}
}

void showNode(priority_queue<Node> q) {
while (!q.empty()) {
Node node = q.top(); q.pop();
cout << node.c << ", " << node.frequency << endl;
}
}

//構造哈夫曼樹
void huffmanTree(priority_queue<Node> &q) {
while (q.size() != 1) {
Node *left = new Node(q.top()); q.pop();
Node *right = new Node(q.top()); q.pop();

Node node('R', left->frequency + right->frequency, left, right);
q.push(node);
}
}

// 打印哈夫曼編碼
void huffmanCode(Node *root, string &prefix, map<char, string> &result) {
string m_prefix = prefix;

if (root->left == NULL)
return;

//處理左子樹
prefix += "0";
//如果是葉子結點則輸出,否則遞歸打印左子樹
if (root->left->left == NULL)
result[root->left->c] = prefix;
//cout << root->left->c << ": " << prefix << endl;
else
huffmanCode(root->left, prefix, result);

//還原原來的路徑,回溯
prefix = m_prefix;

//處理右子樹
prefix += "1";
//如果是葉子結點，則輸出, 否則遞歸打印右子樹
if (root->right->right == NULL)
result[root->right->c] = prefix;
//cout << root->right->c << ": " << prefix << endl;
else
huffmanCode(root->right, prefix, result);

}

void testResult(map<char, string> result) {
//迭代map容器
map<char, string>::const_iterator it = result.begin();
while (it != result.end()) {
cout << it->first << ": " << it->second << endl;
++it;
}
}
int main() {
priority_queue<Node> q;
int nodeNum;

//初始化字符信息
cout << "請輸入結點個數: ";
cin >> nodeNum;
initNode(q, nodeNum);
//showNode(q);

//構造哈夫曼樹
huffmanTree(q);

//構造哈夫曼編碼
Node root = q.top();
string prefix = "";
map<char, string> result;
huffmanCode(&root, prefix, result);

//檢驗結果是否正確
testResult(result);
return 0;
}