【数据结构与算法】为通讯电文设计哈夫曼编码 C++实现（映射+优先队列+哈夫曼树）

哈夫曼编码

题目描述

设用于通讯的电文由$n$个字母组成，给出字母在电文中出现的频率。试为这$n$个字母设计哈夫曼编码。

输入格式

输入的第一行包含一个整数$n$，表示字母的数量。

第二行包含$n$个大写字母，由空格分隔，表示电文中的字母。

第三行包含$n$个整数，由空格分隔，表示对应字母在电文中出现的频率。

输出格式

输出$n$行，每行包含一个字母和其对应的哈夫曼编码，用冒号隔开。

样例 #1

样例输入 #1

8
A B C D E F G H
8 10 5 19 30 15 11 28

样例输出 #1

A: 0001
B: 1110
C: 0000
D: 110
E: 10
F: 001
G: 1111
H: 01

---

思路

首先，定义了一些常量和类型别名。TreeNode 结构体定义了哈夫曼树节点，包含字符数据、左子节点和右子节点。Node 结构体包含频率和哈夫曼树节点，并重载了 < 运算符，用于构建小顶堆。

接着，定义了全局变量 n、f、a 和 code。n 用于存放字符数量，f 和 a 分别用于存放字符和对应的频率，code 用于存放每个字符的哈夫曼编码。

createTreeNode 函数用于创建一个新的哈夫曼树节点。createHuffmanTree 函数用于根据输入的字符和频率创建哈夫曼树。在这个函数中，先将所有字符和对应的频率构造成节点放入优先队列（小顶堆）中，然后每次从堆中取出两个频率最小的节点，创建一个新的节点作为这两个节点的父节点，频率为这两个节点的频率之和，然后将新节点放入堆中。重复这个过程，直到堆中只剩下一个节点，这个节点就是哈夫曼树的根节点。

preorder 函数用于先序遍历哈夫曼树并生成哈夫曼编码。对于非叶子节点，向左遍历时编码添加 “0”，向右遍历时编码添加 “1”。当遇到叶子节点（即字符节点）时，将字符和对应的编码存入 code 中。

printHuffmanCode 函数用于打印所有字符的哈夫曼编码。先调用 preorder 函数生成哈夫曼编码，然后遍历 code 并打印出每个字符和对应的编码。

main 函数先从输入中读取字符数量和每个字符及其频率，然后调用 createHuffmanTree 函数创建哈夫曼树，最后调用 printHuffmanCode 函数打印哈夫曼编码。

算法分析

时间复杂度为 $O(n\log n)$，其中 $n$ 是字符数量。这是因为创建哈夫曼树需要 $n-1$ 次插入和删除操作，每次操作的时间复杂度为 $O(\log n)$。生成哈夫曼编码的时间复杂度为 $O(n)$，因为需要遍历所有节点。所以总的时间复杂度为 $O(n\log n)$。

空间复杂度为 $O(n)$，其中 $n$ 是字符数量。这是因为需要存放所有的字符、频率、哈夫曼树节点和哈夫曼编码。

---

代码

#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#define AUTHOR "HEX9CF"
using namespace std;
using Status = int;
using ElemType = char;const int N = 1e6 + 7;
const int M = 1e3 + 7;
const int TRUE = 1;
const int FALSE = 0;
const int OK = 1;
const int ERROR = 0;
const int INFEASIBLE = -1;
// const int OVERFLOW = -2;struct TreeNode {ElemType data;TreeNode *left, *right;
};
using HuffmanTree = TreeNode *;struct Node {int f;TreeNode *node;bool operator<(const Node &b) const { return f > b.f; }
};int n;
int f[N];
ElemType a[N];
map<char, string> code;TreeNode *createTreeNode(ElemType e, TreeNode *l, TreeNode *r) {TreeNode *t = (TreeNode *)malloc(sizeof(TreeNode));if (!t) {return NULL;}t->data = e;t->left = l;t->right = r;return t;
}HuffmanTree createHuffmanTree(int n, ElemType *a, int *f) {priority_queue<Node> hmin;for (int i = 0; i < n; i++) {TreeNode *t = createTreeNode(a[i], nullptr, nullptr);hmin.push({f[i], t});}while (hmin.size() > 1) {Node a = hmin.top();hmin.pop();Node b = hmin.top();hmin.pop();if (a.f > b.f) {swap(a, b);}TreeNode *t = createTreeNode(' ', a.node, b.node);// cout << a.f << " " << b.f << endl;hmin.push({a.f + b.f, t});}return hmin.top().node;
}void preorder(HuffmanTree T, string c) {if (T) {if (T->data != ' ') {// cout << T->data << ": " << c << endl;code[T->data] = c;return;}preorder(T->left, c + "0");preorder(T->right, c + "1");}
}Status printHuffmanCode(HuffmanTree root) {preorder(root, "");for (const auto i : code) {cout << i.first << ": " << i.second << endl;}return OK;
}int main() {cin >> n;for (int i = 0; i < n; i++) {cin >> a[i];}for (int i = 0; i < n; i++) {cin >> f[i];}HuffmanTree root = createHuffmanTree(n, a, f);printHuffmanCode(root);return 0;
}