C++实现哈夫曼编码完整代码

C++实现哈夫曼编码完整代码

C++实现哈夫曼编码完整代码 #include #include #include #include

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 &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 q) { while (!q.empty()) {

Node node = q.top(); q.pop();

cout << node.c << \ } }

1

C++实现哈夫曼编码完整代码

//构造哈夫曼树

void huffmanTree(priority_queue &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 &result) { string m_prefix = prefix; if (root->left == NULL) return; //处理左子树

prefix += \

//如果是叶子结点则输出,否则递归打印左子树 if (root->left->left == NULL) result[root->left->c] = prefix;

//cout << root->left->c << \ else

huffmanCode(root->left, prefix, result); //还原原来的路径,回溯 prefix = m_prefix; //处理右子树

prefix += \

//如果是叶子结点，则输出, 否则递归打印右子树 if (root->right->right == NULL) result[root->right->c] = prefix;

//cout << root->right->c << \ else

huffmanCode(root->right, prefix, result); }

2

C++实现哈夫曼编码完整代码

void testResult(map result) { //迭代map容器

map::const_iterator it = result.begin(); while (it != result.end()) {

cout << it->first << \ ++it; } }

int main() {

priority_queue q; int nodeNum; //初始化字符信息

cout << \请输入结点个数: \ cin >> nodeNum; initNode(q, nodeNum); //showNode(q); //构造哈夫曼树 huffmanTree(q); //构造哈夫曼编码 Node root = q.top(); string prefix = \ map result;

huffmanCode(&root, prefix, result); //检验结果是否正确 testResult(result); return 0; }

3