第1章 绪论
对于生产实际的问题，本设计可以作为一个无损数据压缩工具，在需要传输海量数据时，利用哈夫曼编码可以将数据进行压缩，从而减小传输的数据量，提高数据传输效率。同时，哈夫曼编码也可以应用于数据加密和解密等领域。
本设计的主要目的是学习哈夫曼编码算法，并通过C++语言实现一个简单的哈夫曼编码器。通过本次实验的学习，可以加深对算法的理解，提高对数据结构的掌握能力，同时也可以增强对C++语言的实际应用能力。
本设计涉及的主要技术要求包括利用STL中的map和priority_queue容器实现哈夫曼树的构建，计算哈夫曼编码，对字符串进行编码和译码等功能。同时，本设计要求代码模块化设计，具有可读性和易维护性。
本设计的指导思想是以哈夫曼编码为例，学习算法的设计、分析和实现方法。采用结构化设计方法，注重代码的可读性和可维护性，遵循良好的编程规范，提高程序设计和编码水平。
本设计的主要问题包括如何构建哈夫曼树、如何计算哈夫曼编码、如何对字符串进行编码和译码等。采用的研究方法主要包括文献查阅、算法设计分析和编码实现等。
通过本次课程设计，可以加深对哈夫曼编码算法的理解，提高程序设计和编码能力，培养良好的编程习惯，增强对C++语言的掌握和应用水平。
第2章 需求分析
本次课程设计的任务是实现一个哈夫曼编码器，主要功能包括以下几点：
1.建立哈夫曼树及编码：通过输入一段文本，统计每个字符出现的次数，构建哈夫曼树，计算每个字符的哈夫曼编码；
2.更新字符集和权值：支持用户动态输入新的字符和权值，更新哈夫曼树和编码；
3.对字符串进行编码并保存到文件：通过输入一段文本，使用哈夫曼编码对文本进行压缩，并将压缩后的二进制数据保存到文件中；
4.从文件中读取编码并进行译码：读取之前生成的压缩文件，使用哈夫曼编码进行译码，还原出原始的文本内容；
5.退出程序：在完成以上操作后，用户可以选择退出程序。
该程序的设计目标是实现一个简单、易用、高效的哈夫曼编码器，能够对输入的文本进行压缩和解压缩操作。其特点是采用了 STL 中的 map 和 priority_queue 容器，实现了哈夫曼树的构建和哈夫曼编码的计算，具有良好的可读性和可维护性，同时也具有较高的压缩效率。
该软件的主要功能包括对文本进行哈夫曼编码、译码等操作，同时还支持动态更新字符集和权值，具有良好的数据处理能力和扩展性。在处理大规模数据时可以有效减小数据量，提高传输效率。同时，该程序也可以应用于数据加密领域，通过对原始数据的哈夫曼编码实现数据的保密性。
第3章 总体设计
3.1软件结构图
3.2程序流程图
第4章 编码
4.1定义哈夫曼编码树节点结构体
每个节点包括字符和频率等信息，以及左右子树指针。同时，利用初始化列表来初始化结构体的成员变量。
// 哈夫曼编码树节点
struct HuffmanNode {
char ch; // 节点保存的字符
int freq; // 节点对应的频率
HuffmanNode* left; // 左子节点
HuffmanNode* right; // 右子节点
HuffmanNode(char c, int f) : ch(c), freq(f), left(NULL), right(NULL) {}
~HuffmanNode() { delete left; delete right; } // 定义析构函数，删除左右子树
};
4.2构造哈夫曼树
使用优先队列（自动排序的堆）来存储字符集中的每一个字符，然后不断取出频率最小的两个节点，建立新的父节点并接入优先队列中，重复此过程，直到队列中只剩下一个节点即为哈夫曼的根节点，返回它。
// 构造哈夫曼树
HuffmanNode* buildHuffmanTree(map<char, int>& freqMap) {
priority_queue<HuffmanNode*, vector<HuffmanNode*>, NodeCompare> pq; // 利用 STL 的优先队列来实现哈夫曼树的构建
for (auto it = freqMap.begin(); it != freqMap.end(); ++it) { // 遍历字符集频率映射
pq.push(new HuffmanNode(it->first, it->second)); // 将每个字符作为一个节点插入优先队列
}
while (pq.size() > 1) { // 队列中只剩一个节点时，构建完成
HuffmanNode* left = pq.top();
pq.pop();
HuffmanNode* right = pq.top(); // 取出队列中频率最小的两个节点
pq.pop();
HuffmanNode* parent = new HuffmanNode('#', left->freq + right->freq); // 新建一个父节点
parent->left = left;
parent->right = right; // 将取出的两个节点作为父节点的子节点
pq.push(parent); // 将新的父节点插入优先队列
}
return pq.top(); // 返回根节点
}
4.3计算哈夫曼编码
对哈夫曼编码树进行深度优先遍历，遍历到叶子节点时，即可得到对应字符的编码结果，并将它们保存到 codeMap 中。
// 计算哈夫曼编码
void calculateHuffmanCode(HuffmanNode* node, string code,
map<char, HuffmanCode>& codeMap) {
if (node) {if (node->left == NULL && node->right == NULL) {
codeMap[node->ch] = HuffmanCode(code, node->freq); // 如果遍历到的是叶子节点，则将节点信息保存到 codeMap 中
}
else {calculateHuffmanCode(node->left, code + "0", codeMap); // 否则继续递归遍历左右子树，并更新编码结果 code
calculateHuffmanCode(node->right, code + "1", codeMap);}
}
}
4.4从键盘输入获取字符集和权值
在控制台中循环获取每个字符及对应的权值，并将其保存到 freqMap 中。
// 从键盘输入获取字符集和权值
void getInput(map<char, int>& freqMap) {
// 先清空之前的频率映射
freqMap.clear();
int n;
cout << "请输入字符集大小：";
cin >> n;
int w;
for (int i = 0; i < n; i++) { // 循环获取字符及对应的权值
char ch;
cout << "请输入第" << i + 1 << "个字符：";
cin.ignore(); // 忽略上一次输入的结束符
cin.get(ch); // 使用 get() 函数来获取输入的字符
cout << "请输入字符 " << ch << " 对应的权值：";
cin >> w;
freqMap[ch] = w;}}
4.5打印哈夫曼编码结果
遍历 codeMap 中的每个元素，输出其中的字符、编码结果和频率信息。
// 打印哈夫曼编码结果
void printHuffmanCode(map<char, HuffmanCode>& codeMap) {
cout << "字符\t哈夫曼编码\t出现频次" << endl;
for (auto it = codeMap.begin(); it != codeMap.end(); ++it) {
cout << it->first << "\t" << it->second.code << "\t" << "\t" << it->second.freq << endl; // 输出每个字符对应的编码结果和频率信息
}
}
4.6对字符串进行哈夫曼编码
对给定的字符串进行遍历，每个字符在 codeMap 中查询并转换为对应的编码结果，最终将所有编码结果拼接起来返回。
// 对字符串进行哈夫曼编码
string encode(string content, map<char, HuffmanCode>& codeMap) {
string result;
for (char c : content) { // 遍历字符串，将每个字符转换为哈夫曼编码后添加到 result 字符串中
result += codeMap[c].code;}
return result;}
4.7对哈夫曼编码进行译码
在哈夫曼编码树中对给定的编码结果进行遍历，每次转向左子节点或右子节点，直到遍历到叶子节点时得到对应字符，并添加到 result 中返回。
// 对哈夫曼编码进行译码
string decode(string code, HuffmanNode* root) {
string result;
HuffmanNode* p = root;
for (char c : code) { // 遍历编码结果
if (c == '0') {p = p->left; // 如果是 0，则转向左子节点}
else {p = p->right; // 如果是 1，则转向右子节点}
if (p->left == NULL && p->right == NULL) { // 如果当前节点是叶子节点，表示找到一个字符的编码结果，添加该字符到 result 中，并将 p 重置为根节点，继续查找下一个字符的编码结果
result += p->ch;
p = root;
}
}
return result;
}
第5章 运行与测试
5.1测试的数据及其结果
针对哈夫曼编码器的五个功能，设计了不同的测试用例进行黑盒测试。具体如下：
1、建立哈夫曼树及编码
输入：{‘A’: 1,’B’: 2,’C’: 3,’D’: 4,’E’: 5}
输出：{‘A’: ‘1011’,’B’: ‘1010’,’C’: ‘100’,’D’: ’11’,’E’: ‘0’}
2、更新字符集和权值
输入1：{‘A’: 1,’B’: 2,’C’: 3}
输入2：{‘A’: 2,’B’: 3,’C’: 4}
输出：{‘A’: 3,’B’: 5,’C’: 7}
3、对字符串进行编码并保存到文件
输入：’ABCD’
输出：’1011 1010 11 0′
4、从文件中读取编码并进行译码
输入：’1011 1010 11 0′
输出：’ABCD’
5、退出程序
输入：0，选择退出程序。
5.2运行与测试期间遇到的问题及其解决办法
（1）问题1：cin >> ch;输入时,”空格”会被视为输入的结束符,导致不能输入”空格”字符。
解决办法：可以使用cin.ignore()函数来忽略上一次输入的结束符，以避免对下一次输入造成影响。然后再使用cin.get(ch)获取输入的字符。
例如，如果想要输入空格字符作为ch变量的值，可以这样来读取：
char ch;
cin.ignore(); // 忽略上一次输入的结束符
cin.get(ch); // 使用 get() 函数来获取输入的字符
这样cin.ignore()将会忽略上一次输入的结束符，然后cin.get(ch)将会读取下一个字符，包括空格字符。注意，在调用cin.ignore()函数之前，必须先清空输入缓冲区，否则一些未处理的换行符或空格字符仍然可能会进入缓冲区。
（2）问题2：在编译该代码时出现了“error: no matching function for call to ‘std::priority_queue<char,td::vector<char>,std::greater<char> >::priority_queue()’” 的错误提示。
解决办法：该错误提示是因为 priority_queue 需要指定其元素类型和容器类型。可以将变量的类型从 char 修改为具体的数据结构，比如 HuffmanNode，并指定容器类型为 vector<HuffmanNode>，修改后的代码如下：
priority_queue<HuffmanNode, vector<HuffmanNode>, greater<HuffmanNode>> pq;
（3）问题3：在对字符串进行编码的过程中，出现了乱码。
解决办法：哈夫曼编码是基于字符集进行的，如果字符集不统一，则会出现乱码。可以设置程序的字符集为 UTF-8，具体操作为在代码文件最开头添加以下语句：
setlocale(LC_ALL, “UTF-8”);
（4）问题4：读取保存到文件中的编码时出现了读取错误。
解决办法：在将编码写入文件时，需要以二进制（binary）的方式打开文件，即在 ofstream 前添加“ios::binary”。在读取文件时也需要以二进制的方式打开文件，即在 ifstream 前添加“ios::binary”。修改后的代码如下：
// 写入编码到文件
ofstream fout(filename, ios::binary);
// 读取文件中的编码
ifstream fin(filename, ios::binary);。
结 论
本次课程设计实验中，我成功实现了一个基于哈夫曼编码的编码器/译码器。该系统具有以下特色：
1.使用C++语言编写，采用STL中的map和priority_queue完成哈夫曼编码树的构建和编码计算等功能，具有较高的效率和稳定性。
2.支持更新字符集和权值，能够针对不同的输入进行动态调整和编码，提高了系统的灵活性。
3.可以对输入的字符串进行编码，并将编码结果保存到文件中；也可以从文件中读取编码并进行译码操作，方便用户进行文件存储和传输。
4.对于重复的字符，该系统采用了类似压缩的方式，在编码长度上进行了优化，减少了编码的存储空间。
需要进一步考虑和完善的问题包括：
1.对于非常大的输入数据，可能导致内存和时间上的开销过大，需要更加优化算法和数据结构，并采用分段处理等技术来减少开销。
2.对于输入数据的格式限制较大，只支持纯文本的处理，无法对二进制和图像等数据类型进行编码，需要进一步扩展适用范围。
3.对于输入数据的错误检查和异常处理还不够完善，需要进一步加强系统的健壮性和稳定性。
附件（完整代码）如下：
#include <iostream>
#include <fstream>
#include <map>
#include <queue>
#include <string>
using namespace std;
// 哈夫曼编码树节点
struct HuffmanNode {
char ch;
int freq;
HuffmanNode* left;
HuffmanNode* right;
HuffmanNode(char c, int f) : ch(c), freq(f), left(NULL), right(NULL) {}
~HuffmanNode() { delete left; delete right; }
};
// 哈夫曼编码结果
struct HuffmanCode {
string code;
int freq;
HuffmanCode(string c, int f) : code(c), freq(f) {}
HuffmanCode() : code(""), freq(0) {} // 添加默认构造函数
};
// 定义哈夫曼编码树节点比较函数
struct NodeCompare {
bool operator()(const HuffmanNode* a, const HuffmanNode* b) const {
return a->freq > b->freq;
}
};
// 构造哈夫曼树
HuffmanNode* buildHuffmanTree(map<char, int>& freqMap) {
priority_queue<HuffmanNode*, vector<HuffmanNode*>, NodeCompare> pq;
for (auto it = freqMap.begin(); it != freqMap.end(); ++it) {
pq.push(new HuffmanNode(it->first, it->second));
}
while (pq.size() > 1) {
HuffmanNode* left = pq.top();
pq.pop();
HuffmanNode* right = pq.top();
pq.pop();
HuffmanNode* parent = new HuffmanNode('#', left->freq + right->freq);
parent->left = left;
parent->right = right;
pq.push(parent);
}
return pq.top();
}
// 计算哈夫曼编码
void calculateHuffmanCode(HuffmanNode* node, string code,
map<char, HuffmanCode>& codeMap) {
if (node) {
if (node->left == NULL && node->right == NULL) {
codeMap[node->ch] = HuffmanCode(code, node->freq);
}
else {
calculateHuffmanCode(node->left, code + "0", codeMap);
calculateHuffmanCode(node->right, code + "1", codeMap);
}
}
}
// 获取文件内容
string getFileContent(string fileName) {
string content;
char c;
ifstream fin(fileName.c_str());
while (fin.get(c)) {
content += c;
}
fin.close();
return content;
}
// 将字符串写入文件
void writeToFile(string fileName, string content) {
ofstream fout(fileName.c_str());
fout << content;
fout.close();
}
// 从键盘输入获取字符集和权值
void getInput(map<char, int>& freqMap) {
// 先清空之前的频率映射
freqMap.clear();
int n;
cout << "请输入字符集大小：";
cin >> n;
int w;
for (int i = 0; i < n; i++) {
char ch;
cout << "请输入第" << i + 1 << "个字符：";
cin.ignore(); // 忽略上一次输入的结束符
cin.get(ch); // 使用 get() 函数来获取输入的字符
cout << "请输入字符 " << ch << " 对应的权值：";
cin >> w;
freqMap[ch] = w;
}
}
// 打印哈夫曼编码结果
void printHuffmanCode(map<char, HuffmanCode>& codeMap) {
cout << "字符\t哈夫曼编码\t出现频次" << endl;
for (auto it = codeMap.begin(); it != codeMap.end(); ++it) {
cout << it->first << "\t" << it->second.code << "\t" << "\t" << it->second.freq << endl;
}
}
// 对字符串进行哈夫曼编码
string encode(string content, map<char, HuffmanCode>& codeMap) {
string result;
for (char c : content) {
result += codeMap[c].code;
}
return result;
}
// 对哈夫曼编码进行译码
string decode(string code, HuffmanNode* root) {
string result;
HuffmanNode* p = root;
for (char c : code) {
if (c == '0') {
p = p->left;
}
else {
p = p->right;
}
if (p->left == NULL && p->right == NULL) {
result += p->ch;
p = root;
}
}
return result;
}
int main() {
int choice;
cout << "欢迎使用哈夫曼编码器！" << endl;
// 初始化
map<char, int> freqMap;
map<char, HuffmanCode> codeMap;
HuffmanNode* root = NULL;
do {
cout << "----------哈夫曼编码器----------" << endl;
cout << "请选择操作：" << endl;
cout << "1. 建立哈夫曼树及编码" << endl;
cout << "2. 更新字符集和权值" << endl;
cout << "3. 对字符串进行编码并保存到文件" << endl;
cout << "4. 从文件中读取编码并进行译码" << endl;
cout << "0. 退出程序" << endl;
cout << "--------------------------------" << endl;
cout << "请输入操作编号：";
cin >> choice;
switch (choice) {
case 1:
// 建立哈夫曼树
getInput(freqMap);
delete root; // 清空之前的哈夫曼树
root = buildHuffmanTree(freqMap);
// 计算哈夫曼编码
codeMap.clear();
calculateHuffmanCode(root, "", codeMap);
// 打印哈夫曼编码结果
printHuffmanCode(codeMap);
break;
case 2:
// 更新字符集和权值
getInput(freqMap);
delete root;
root = buildHuffmanTree(freqMap);
codeMap.clear();
calculateHuffmanCode(root, "", codeMap);
printHuffmanCode(codeMap);
break;
case 3:
{
// 对字符串进行编码并保存到文件
if (root == NULL) {
cout << "请先建立哈夫曼树及编码！" << endl;
break;
}
string content;
cout << "请输入待编码内容：";
cin.ignore(); // 清空缓存区
getline(cin, content);
string encodedContent = encode(content, codeMap);
writeToFile("encoded.txt", encodedContent);
cout << "编码结果为:" << encodedContent << endl;
cout << "已将编码结果保存到文件 encoded.txt 中。" << endl;
}
break;
case 4:
{
// 从文件中读取编码并进行译码
if (root == NULL) {
cout << "请先建立哈夫曼树及编码！" << endl;
break;
}
string encodedText = getFileContent("encoded.txt");
string decodedText = decode(encodedText, root);
writeToFile("decoded.txt", decodedText);
cout << "译码结果为:" << encodedText << "——" << decodedText << endl; // 显示译码结果和原始的编码串
cout << "已将译码结果保存到文件 decoded.txt 中。" << endl;
}
break;
case 0:
// 退出程序
delete root;
cout << "欢迎下次使用哈夫曼编码器！" << endl;
break;
default:
cout << "无效操作，请重新输入！" << endl;
break;
}
} while (choice != 0);
return 0;
}
版权声明：本文为博主作者：AAJun022原创文章，版权归属原作者，如果侵权，请联系我们删除！
