一、 问题描述
在进行程序设计时，通常给每一个字符标记一个单独的代码来表示一组字符，即编码。在进行二进制编码时，假设所有的代码都等长，那么表示 n 个不同的字符需要 位，称为等长编码。如果每个字符的使用频率相等，那么等长编码无疑是空间效率最高的编码函数，而如果字符出现的频率不同，则可以让频率高的字符采用尽可能短的编码，频率低的字符采用尽可能长的编码，来构造出一种不等长编码，从而获得更好的空间效率。
在设计不等长编码时，要考虑解码的唯一性，如果一组编码中任一编码都不是其他任何一个编码的前缀，那么称这组编码为前缀编码，其保证了编码被解码时的唯一性。霍夫曼树可用于构造最短的前缀编码，即哈夫曼编码（Huffman Code）。
—— OI Wiki
二、 设计思路
以下是项目目录结构图：
HuffmanTree/
├── include/
│ ├── HuffmanNode.h
│ └── HuffmanTree.h
├── src/
│ ├── HuffmanNode.cpp
│ └── HuffmanTree.cpp
├── mainwindow.h
├── mainwindow.ui
├── mainwindow.cpp
└── main.cpp
- 创建 HuffmanNode 类：
HuffmanNode 类用于表示 Huffman 树的节点。
每个节点包含字符数据、频率以及左右子节点指针。
为了便于操作，该类包括一个构造函数，用于初始化节点的数据成员。 - 创建 CompareNodes 结构体：
CompareNodes 结构体是一个自定义的比较器。
用于在优先队列中比较两个 HuffmanNode 指针的频率，以便按频率升序排序节点。 - 创建 HuffmanTree 类：
HuffmanTree 类表示 Huffman 树的结构和操作。
构造函数接受一个映射（map）参数，其中包含字符和对应的频率，然后调用 buildTree 函数构建 Huffman 树。 - 实现 buildTree 函数：
buildTree 函数用于根据字符频率构建 Huffman 树。
使用优先队列（最小堆）来维护节点，每个节点代表一个字符及其频率。
循环从优先队列中弹出两个最小频率的节点，然后创建一个新的父节点，将这两个节点作为子节点，父节点的频率为子节点频率之和。
将新创建的父节点放回优先队列，重复这个过程直到队列中只剩下一个节点，即 Huffman 树的根节点。 - 实现 generateCodes 函数：
generateCodes 函数是一个递归函数，用于遍历 Huffman 树并生成字符的 Huffman 编码。
从根节点开始，沿着左子树的路径添加 “0”，沿着右子树的路径添加 “1”。
当遇到叶子节点时，将字符和路径编码存储在一个字符到编码的映射中。
三、 数据结构设计
- 哈夫曼节点类 HuffmanNode：
HuffmanNode 类用于表示哈夫曼树的节点，包括字符数据、频率以及左右子节点指针。
构造函数初始化节点的数据、频率和子节点指针。 - 比较器结构 CompareNodes：
CompareNodes 结构用于比较两个 HuffmanNode 指针，按照频率从小到大的顺序排序，以便在优先队列中使用。 - 哈夫曼树类 HuffmanTree：
HuffmanTree 类用于构建哈夫曼树。
构造函数接受一个 map<char, int> 参数，其中包含字符和它们的频率信息，并调用 buildTree 函数构建哈夫曼树。
buildTree 使用优先队列（最小堆）来构建哈夫曼树，首先将字符频率转化为节点，然后反复合并频率最低的两个节点，直到只剩下一个根节点。
getCodes 函数生成字符到编码的映射。 - 私有函数 generateCodes：
generateCodes 用于递归地生成字符到编码的映射，遍历哈夫曼树，构建每个字符的编码。
在遇到叶子节点时将字符和编码存储在映射中。
四、 功能函数设计
- 包含头文件和命名空间：代码包含了 、 和
- 用于比较 HuffmanNode 指针的比较器 CompareNodes：定义了一个用于优先队列比较的自定义比较器，按照节点的频率从小到大进行比较。
- buildTree 构建哈夫曼树的主要逻辑，使用优先队列来合并频率最低的节点，直到只剩下一个根节点。
- getCodes 用于获取字符到哈夫曼编码的映射。
- generateCodes：递归，用于生成字符到哈夫曼编码的映射，从根节点开始遍历树。
五、 程序代码
// main.cpp#include "mainwindow.h"
#include <QApplication>int main(int argc, char *argv[]) {QApplication a(argc, argv);MainWindow w;w.setWindowTitle("DS 课程设计 zdy229074447");w.show();return a.exec();
}
// mainwindows.h#ifndef MAINWINDOW_H
#define MAINWINDOW_H#include <QMainWindow>
#include <QtWidgets>
#include <map>
#include "include/HuffmanTree.h"QT_BEGIN_NAMESPACE
namespace Ui {
class MainWindow;
}
QT_END_NAMESPACEclass MainWindow: public QMainWindow {Q_OBJECT
public:MainWindow(QWidget *parent = nullptr);~MainWindow();void onButtonConfirmClicked();void onButtonResetClicked();
private:Ui::MainWindow *ui;QTableWidget* tableWidget;QLineEdit* charInput;QLineEdit* frequencyInput;QPushButton* buttonConfirm, *buttonReset;HuffmanTree* huffmanTree;map<char, int> frequencies;void updateTable();
};#endif // MAINWINDOW_H
// mainwindow.cpp#include <QtWidgets>
#include "mainwindow.h"
#include "ui_mainwindow.h"
#include "include/HuffmanNode.h"
#include "include/HuffmanTree.h"MainWindow::MainWindow(QWidget *parent): QMainWindow(parent), ui(new Ui::MainWindow) {ui->setupUi(this);// 初始化输入框和按钮tableWidget = this->findChild<QTableWidget *>("Table_Result");charInput = this->findChild<QLineEdit *>("Char_Input");frequencyInput = this->findChild<QLineEdit *>("Frequency_Input");buttonConfirm = this->findChild<QPushButton *>("Button_Confirm");buttonReset = this->findChild<QPushButton *>("Button_Reset");// 连接按钮点击事件到槽函数Zconnect(buttonConfirm, &QPushButton::clicked, this, &MainWindow::onButtonConfirmClicked);connect(buttonReset, &QPushButton::clicked, this, &MainWindow::onButtonResetClicked);// 初始化哈夫曼树huffmanTree = nullptr; // 在这里初始化为空// 设置表格的列数和表头tableWidget->setColumnCount(3);tableWidget->setHorizontalHeaderLabels({"字符", "频次", "哈夫曼编码"});}void MainWindow::onButtonResetClicked() {for (auto pair: frequencies) {frequencies[pair.first] = 0;}delete huffmanTree;huffmanTree = new HuffmanTree(frequencies);updateTable();
}void MainWindow::onButtonConfirmClicked() {QString charText = charInput->text();QString freqText = frequencyInput->text();if (!charText.isEmpty() && !freqText.isEmpty()) {char character = charText.at(0).toLatin1(); // 获取第一个字符int frequency = freqText.toInt();// 创建哈夫曼树（如果尚未创建）if (huffmanTree == nullptr) {frequencies[character] = frequency; // 使用 [] 操作符添加键值对huffmanTree = new HuffmanTree(frequencies);} else {// 更新频率frequencies[character] += frequency;huffmanTree->buildTree(frequencies); // 重新构建哈夫曼树}// 更新表格内容updateTable();}
}void MainWindow::updateTable() {// 清空表格内容tableWidget->clearContents();tableWidget->setRowCount(0);// 获取哈夫曼树的编码映射map<char, string> codes = huffmanTree->getCodes();// 遍历编码映射并更新表格int row = 0;for (auto pair: codes) {tableWidget->insertRow(row);QTableWidgetItem* charItem = new QTableWidgetItem(QString(pair.first));QTableWidgetItem* frequencyItem = new QTableWidgetItem(QString::number(frequencies[pair.first]));QTableWidgetItem* codeItem = new QTableWidgetItem(QString::fromStdString(pair.second));tableWidget->setItem(row, 0, charItem);tableWidget->setItem(row, 1, frequencyItem);tableWidget->setItem(row, 2, codeItem);row++;}
}MainWindow::~MainWindow() {delete ui;
}
// HuffmanNode.h#ifndef HUFFMANNODE_H
#define HUFFMANNODE_Hclass HuffmanNode {
public:char data;int frequency;HuffmanNode *left, *right;HuffmanNode(char data, int frequency);
};#endif // HUFFMANNODE_H
// HuffmanTree.h#ifndef HUFFMANTREE_H
#define HUFFMANTREE_H#include "HuffmanNode.h"
#include <map>
#include <string>using namespace std;// 哈夫曼树类
class HuffmanTree {
private:
public:void generateCodes(HuffmanNode* node, string code, map<char, string>& codes);HuffmanNode* root;HuffmanTree(map<char, int> frequencies);void buildTree(map<char, int> frequencies);map<char, string> getCodes();
};#endif // HUFFMANTREE_H
// HuffmanNode.cpp#include "../include/HuffmanNode.h"HuffmanNode::HuffmanNode(char data, int frequency) {this->data = data;this->frequency = frequency;this->left = nullptr;this->right = nullptr;
}
// HuffmanTree.cpp#include "../include/HuffmanTree.h"
#include <vector>
#include <queue>// 用于比较 HuffmanNode 指针的比较器
struct CompareNodes {bool operator()(HuffmanNode* left, HuffmanNode* right) {return left->frequency > right->frequency;}
};HuffmanTree::HuffmanTree(map<char, int> frequencies) {buildTree(frequencies);
}void HuffmanTree::buildTree(map<char, int> frequencies) {priority_queue<HuffmanNode*, vector<HuffmanNode*>, CompareNodes> heap;// 将字符频率构建为节点，并将它们添加到优先队列for (auto entry: frequencies) {HuffmanNode* node = new HuffmanNode(entry.first, entry.second);heap.push(node);}// 构建哈夫曼树while (heap.size() > 1) {HuffmanNode* left = heap.top();heap.pop();HuffmanNode* right = heap.top();heap.pop();// 创建一个新节点作为父节点，其频率为左右子树的频率之和HuffmanNode* parent = new HuffmanNode('\0', left->frequency + right->frequency);parent->left = left;parent->right = right;heap.push(parent);}// 根节点就是哈夫曼树的根root = heap.top();
}map<char, string> HuffmanTree::getCodes() {map<char, string> codes;generateCodes(root, "", codes);return codes;
}void HuffmanTree::generateCodes(HuffmanNode* node, string code, map<char, string>& codes) {if (node == nullptr) return;// 叶子节点，将字符和编码存储在映射中if (node->data != '\0') codes[node->data] = code;generateCodes(node->left, code + "0", codes);generateCodes(node->right, code + "1", codes);
}
// mainwindows.ui<?xml version="1.0" encoding="UTF-8"?>
<ui version="4.0"><class>MainWindow</class><widget class="QMainWindow" name="MainWindow"><property name="geometry"><rect><x>0</x><y>0</y><width>451</width><height>582</height></rect></property><property name="windowTitle"><string>MainWindow</string></property><widget class="QWidget" name="centralwidget"><widget class="QPushButton" name="Button_Confirm"><property name="geometry"><rect><x>260</x><y>10</y><width>111</width><height>41</height></rect></property><property name="styleSheet"><string notr="true">font: 10pt "Microsoft YaHei UI";</string></property><property name="text"><string>添加</string></property></widget><widget class="QLineEdit" name="Char_Input"><property name="geometry"><rect><x>50</x><y>10</y><width>51</width><height>41</height></rect></property><property name="styleSheet"><string notr="true">font: 10pt "Microsoft YaHei UI";</string></property><property name="text"><string/></property></widget><widget class="QLineEdit" name="Frequency_Input"><property name="geometry"><rect><x>140</x><y>10</y><width>111</width><height>41</height></rect></property><property name="styleSheet"><string notr="true">font: 10pt "Microsoft YaHei UI";</string></property><property name="text"><string/></property></widget><widget class="QTableWidget" name="Table_Result"><property name="geometry"><rect><x>20</x><y>60</y><width>411</width><height>471</height></rect></property></widget><widget class="QPushButton" name="Button_Reset"><property name="geometry"><rect><x>380</x><y>10</y><width>51</width><height>41</height></rect></property><property name="styleSheet"><string notr="true">font: 10pt "Microsoft YaHei UI";</string></property><property name="text"><string>重置</string></property></widget><widget class="QLabel" name="label"><property name="geometry"><rect><x>20</x><y>20</y><width>41</width><height>19</height></rect></property><property name="text"><string><html><head/><body><p><span style=" font-size:10pt;">字符</span></p></body></html></string></property></widget><widget class="QLabel" name="label_2"><property name="geometry"><rect><x>110</x><y>20</y><width>41</width><height>19</height></rect></property><property name="text"><string><html><head/><body><p><span style=" font-size:10pt;">频次</span></p></body></html></string></property></widget></widget><widget class="QStatusBar" name="statusbar"/><widget class="QMenuBar" name="menubar"><property name="geometry"><rect><x>0</x><y>0</y><width>451</width><height>24</height></rect></property><widget class="QMenu" name="menu"><property name="title"><string>哈夫曼编码求解</string></property></widget><addaction name="menu"/></widget></widget><resources/><connections/>
</ui>
六、 运行结果及分析
多次添加后，如左图；重置操作后，如右图
所需实现的功能达成，并且可以动态更新。
七、 设计心得
使用了C++的面向对象编程来将Huffman编码的各个组成部分封装成类，这有助于代码的模块化和可维护性。合理地使用了STL容器和数据结构，如map和priority_queue，来简化实现。通过C++Qt构建图形化GUI界面，简化了用户操作，提升了交互属性。
八、 参考资料
霍夫曼树 - OI Wiki (oi-wiki.org) https://oi-wiki.org/ds/huffman-tree/
