利用优先队列(堆排序)优化的哈夫曼编码/解码简易程序(c/c++)
showMenu 函数用于在命令行中显示用户操作菜单，提供了编码、解码、查看密码本和退出等选项。
·
前言
哈夫曼编码是一个经典的贪心问题，面对贪心问题，思路是将一个题目分成若干个互不影响的子问题，分别求每个子问题的最优解，最后即为整个问题的最优解。
构建哈夫曼树时，我们可以采用递归或循环的方式，将字符串中出现频次最多的字符放到哈夫曼树更靠近根节点的位置。换句话说，出现频次越多的字符，所需要的编码就越短，以达到总体性能最优的效果。
代码实现中，使用了c++STL库提供的string、unordered_map、priority_queue容器，文章最后会提供无痛转为c语言的思路方法。
函数/结构体/变量说明
函数：
1.showMenu()
showMenu 函数用于在命令行中显示用户操作菜单，提供了编码、解码、查看密码本和退出等选项。
2.buildHFM(string str)
buildHFM 函数用于构建哈夫曼树，接受一个输入字符串 str 作为参数，统计字符频率并构建哈夫曼树。返回哈夫曼树的根节点。
3.calculate(Node* root, string str)
calculate 函数是一个递归函数，用于计算哈夫曼树节点的编码。接受当前节点 root、当前编码字符串 str 和存储编码的 codes 映射表引用作为参数。
4.encode()
encode 函数实现了对用户输入字符串的编码过程。首先调用 buildHFM 构建哈夫曼树，然后调用 calculate 计算编码，最后输出字符对应的编码以及整个字符串的编码结果。
5.decode()
decode 函数实现了对用户输入编码的解码过程。通过用户输入的编码和之前生成的哈夫曼树，逐步解码得到原始字符串，并输出解码结果。
6.showCodes()
showCodes 函数用于显示已生成的密码本，即字符和对应的哈夫曼编码的映射。
结构体：
struct Node 哈夫曼树的节点。
struct Node {
char data;//字符数据
int fre;//出现频次
Node* left;//左子树
Node* right;//右子树
};
变量/容器：
1.bool isEncode
用于记录是否进行过编码，以便在解码时进行判断。初始值为0（flase）。
2.unordered_map<char, string> codes
用于存储字符和对应哈夫曼编码的映射关系。未出现过的key对应的value为0。
其中，<char,string> char为key值，代表字符。string为value，代表哈夫曼编码。
3.Node* root
哈夫曼树的根节点，在不同函数中共享，用于实现编码和解码功能。
函数调用关系：
其中，在buildHFM()函数中，使用优先队列（小根堆）,按照出现频次递减的顺序，对Node进行排序。在使用优先队列对结构体进行排序时，需要提供比较规则。
比较规则：
struct cmp {
bool operator()(Node* const& a, Node* const& b) {
return a->fre > b->fre;
}
};
函数实现
头文件/ 全局变量
#include<iostream>
#include<unordered_map>
#include<queue>
using namespace std;
bool isEncode;//记录是否有编码，用于解码过程判断是否已有编码
unordered_map<char, string> codes;//密码本
Node* root;//哈夫曼树根节点
buildHFM()
//在encode()中调用buildHFM()
Node* buildHFM(string str) {
//统计字符串频率，并储存在times中
unordered_map<char, int> times;
for (char x : str) {
times[x]++;
}
//打印字符出现频次
cout << "频次： ";
for (auto pair : times) {
cout << pair.first << ":" << pair.second << " ";
}
cout << endl;
//将所有字符按照放进小根堆中
priority_queue<Node*, vector<Node*>, cmp> minHeap;
for (auto pair : times) {
Node* tmp=new struct Node();
tmp->data = pair.first;
tmp->fre = pair.second;
tmp->left = NULL;
tmp->right = NULL;
minHeap.push(tmp);
}
//用小根堆创建哈夫曼树
while (minHeap.size() > 1) {
//每次将小根堆中出现频次最小的两个节点取出，合成一个节点
//新节点的权重（频次）等于两个节点的权重（频次）和
//并将这个节点作为原来两个节点的父节点
Node* left = minHeap.top();
minHeap.pop();
Node* right = minHeap.top();
minHeap.pop();
Node* tmp=new struct Node();
tmp->left = left;
tmp->right = right;
//在哈夫曼树中，仅叶节点的data有效
//我们将所有非叶节点的data赋值为‘ \ ’
tmp->data = '\\';
tmp->fre = left->fre + right->fre;
minHeap.push(tmp);
}
//此时小根堆中只剩一个元素，即为哈夫曼树的根节点
return minHeap.top();
}
calculate()
//在encode()中调用calculate()
void calculate(Node* root,string str) {
//递归计算编码,并储存在codes中
if (root) {
if (root->data != '\\') {
//有效节点,叶节点，编码已完成
codes[root->data] = str;
}
//左0右1
calculate(root->left, str + "0");
calculate(root->right, str + "1");
}
}
encode()
void encode() {
string str;
cin >> str;
//root定义在全局，方便使用
root = buildHFM(str);
calculate(root,"");
//将是否存在编码的标识改为1
isEncode = 1;
//打印字符对应的编码
cout << "编码："<<endl;
for (auto pair : codes) {
cout << pair.first << ":" << pair.second << endl;
}
//打印字符串对应的编码
cout << "电文： " << str << endl;
cout << "电文的编码： ";
for (char x : str) {
cout << codes[x]<<" ";
}
cout << endl;
cout << endl << "编码完毕!" << endl;
system("pause");
system("cls");
}
decode()
void decode() {
if (!isEncode) {
//编码不存在
cout << "no code exist" << endl;
system("pause");
system("cls");
}
Node* tmp = root;
string str;
//在这里输入要解码的编码
cout << "输入编码："<<endl;
cin >> str;
string ans="";
for (char x : str) {
if (x == '0') {
if (tmp->left == NULL) {
//提示解码错误，容错
//如果该节点的任一左右子树为空，却没有在上一步循环中处理掉，证明编码出现错误
cout << "输入的编码有误，无法解码" << endl;
system("pause");
system("cls");
return;
}
tmp = tmp->left;
}
else {
if (tmp->right == NULL) {
//提示解码错误，容错
//如果该节点的任一左右子树为空，却没有在上一步循环中处理掉，证明编码出现错误
cout << "输入的编码有误，无法解码" << endl;
system("pause");
system("cls");
return;
}
tmp = tmp->right;
}
if (tmp->left==NULL&&tmp->right==NULL) {
if(tmp->data=='\\'){
//提示解码错误，容错
//此时左右字数为空，说明遍历到叶节点。
//如果叶节点的值为' \ ',说明编码错误
cout << "输入的编码有误，无法解码" << endl;
system("pause");
system("cls");
return;
}
ans += tmp->data;
tmp = root;
}
}
if(tmp->data=='\\'&&tmp!=root){
//提示解码错误，容错
//判断最后一个编码的位置，如果最后一个编码的值是' \ '且tmp!=root,证明编码没有被用完，出现错误
cout << "输入的编码有误，无法解码" << endl;
system("pause");
system("cls");
return;
}
cout << "解码成功，结果为： " << endl;
cout << ans << endl;
system("pause");
system("cls");
}
优缺点/代码局限性/可改进的地方
使用map储存编码，理论上可以储存‘ \ ’（判断非叶节点字符）以外所有的字符，而不只是26个小写英文字母。
编/解码过程中，仅能处理字符数量大于1且字符种类大于1的情况。
转c语言
1.使用数组代替unordered_map，实现密码本功能。
2.手写小根堆，代替priority_queue，或者利用数组进行排序。
3.使用char[ ]代替string。
完整代码
#include<iostream>
#include<unordered_map>
#include<queue>
using namespace std;
bool isEncode;//记录是否有编码，用于解码过程判断是否已有编码
unordered_map<char, string> codes;//密码本
struct Node {
char data;
int fre;
Node* left;
Node* right;
};
Node* root;//哈夫曼树根节点
//优先队列的比较规则
struct cmp {
bool operator()(Node* const& a, Node* const& b) {
return a->fre > b->fre;
}
};
void showMenu() {
cout << "1.编码(仅第一次编码有效)" << endl;
cout << "2.解码" << endl;
cout << "3.密码本" << endl;
cout << "0.退出" << endl;
}
Node* buildHFM(string str) {
//统计字符串频率，并储存在times中
unordered_map<char, int> times;
for (char x : str) {
times[x]++;
}
//打印字符出现频次
cout << "频次： ";
for (auto pair : times) {
cout << pair.first << ":" << pair.second << " ";
}
cout << endl;
//将所有字符按照放进小根堆中
priority_queue<Node*, vector<Node*>, cmp> minHeap;
for (auto pair : times) {
Node* tmp=new struct Node();
tmp->data = pair.first;
tmp->fre = pair.second;
tmp->left = NULL;
tmp->right = NULL;
minHeap.push(tmp);
}
//用小根堆创建哈夫曼树
while (minHeap.size() > 1) {
Node* left = minHeap.top();
minHeap.pop();
Node* right = minHeap.top();
minHeap.pop();
Node* tmp=new struct Node();
tmp->left = left;
tmp->right = right;
tmp->data = '\\';
tmp->fre = left->fre + right->fre;
minHeap.push(tmp);
}
//此时小根堆中只剩一个元素，即为哈夫曼树的根节点
return minHeap.top();
}
void calculate(Node* root,string str) {
//递归计算编码
if (root) {
if (root->data != '\\') {
//有效节点,叶节点，编码已完成
codes[root->data] = str;
}
//左0右1
calculate(root->left, str + "0");
calculate(root->right, str + "1");
}
}
void encode() {
string str;
cin >> str;
//root定义在全局，方便使用
root = buildHFM(str);
//unordered_map<char, string> codes;
//全程用到，为了方便使用，将codes改为全局变量
calculate(root,"");
//将是否存在编码的标识改为1
isEncode = 1;
//打印字符对应的编码
cout << "编码："<<endl;
for (auto pair : codes) {
cout << pair.first << ":" << pair.second << endl;
}
//打印字符串对应的编码
cout << "电文： " << str << endl;
cout << "电文的编码： ";
for (char x : str) {
cout << codes[x]<<" ";
}
cout << endl;
cout << endl << "编码完毕!" << endl;
system("pause");
system("cls");
}
void decode() {
if (!isEncode) {
//编码不存在
cout << "no code exist" << endl;
system("pause");
system("cls");
}
Node* tmp = root;
string str;
cout << "输入编码："<<endl;
cin >> str;
string ans="";
for (char x : str) {
if (x == '0') {
if (tmp->left == NULL) {
//提示解码错误，容错
cout << "输入的编码有误，无法解码" << endl;
system("pause");
system("cls");
return;
}
tmp = tmp->left;
}
else {
if (tmp->right == NULL) {
//提示解码错误，容错
cout << "输入的编码有误，无法解码" << endl;
system("pause");
system("cls");
return;
}
tmp = tmp->right;
}
if (tmp->left==NULL&&tmp->right==NULL) {
if(tmp->data=='\\'){
//提示解码错误，容错
cout << "输入的编码有误，无法解码" << endl;
system("pause");
system("cls");
return;
}
ans += tmp->data;
tmp = root;
}
}
if(tmp->data=='\\'&&tmp!=root){
//提示解码错误，容错
//判断最后一个编码的位置，如果最后一个编码的值是\\且tmp!=root,证明编码没有被用完，出现错误
cout << "输入的编码有误，无法解码" << endl;
system("pause");
system("cls");
return;
}
cout << "解码成功，结果为： " << endl;
cout << ans << endl;
system("pause");
system("cls");
}
void showCodes() {
if (!isEncode) {
cout << "密码本不存在" << endl;
system("pause");
system("cls");
return;
}
for (auto pair : codes) {
cout << "字符: " << pair.first << " 编码: " << pair.second << endl;
}
system("pause");
system("cls");
return;
}
int main() {
while (1) {
showMenu();
int choice;
cin >> choice;
switch (choice) {
case 1:encode();
break;
case 2:decode();
break;
case 3:showCodes();
break;
case 0:return 0;
}
}
}
腾讯云面向开发者汇聚海量精品云计算使用和开发经验，营造开放的云计算技术生态圈。
更多推荐
18
0- 0
已为社区贡献2条内容
所有评论(0)