C++Qt6 哈夫曼编码求解 数据结构课程设计 | JorbanS

一、 问题描述

在进行程序设计时，通常给每一个字符标记一个单独的代码来表示一组字符，即编码。在进行二进制编码时，假设所有的代码都等长，那么表示 n 个不同的字符需要 位，称为等长编码。如果每个字符的使用频率相等，那么等长编码无疑是空间效率最高的编码函数，而如果字符出现的频率不同，则可以让频率高的字符采用尽可能短的编码，频率低的字符采用尽可能长的编码，来构造出一种不等长编码，从而获得更好的空间效率。
在设计不等长编码时，要考虑解码的唯一性，如果一组编码中任一编码都不是其他任何一个编码的前缀，那么称这组编码为前缀编码，其保证了编码被解码时的唯一性。霍夫曼树可用于构造最短的前缀编码，即哈夫曼编码（Huffman Code）。
—— OI Wiki

二、 设计思路

以下是项目目录结构图：

HuffmanTree/
├── include/
│   ├── HuffmanNode.h
│   └── HuffmanTree.h
├── src/
│   ├── HuffmanNode.cpp
│   └── HuffmanTree.cpp
├── mainwindow.h
├── mainwindow.ui
├── mainwindow.cpp
└── main.cpp

1. 创建 HuffmanNode 类：
   HuffmanNode 类用于表示 Huffman 树的节点。
   每个节点包含字符数据、频率以及左右子节点指针。
   为了便于操作，该类包括一个构造函数，用于初始化节点的数据成员。
2. 创建 CompareNodes 结构体：
   CompareNodes 结构体是一个自定义的比较器。
   用于在优先队列中比较两个 HuffmanNode 指针的频率，以便按频率升序排序节点。
3. 创建 HuffmanTree 类：
   HuffmanTree 类表示 Huffman 树的结构和操作。
   构造函数接受一个映射（map）参数，其中包含字符和对应的频率，然后调用 buildTree 函数构建 Huffman 树。
4. 实现 buildTree 函数：
   buildTree 函数用于根据字符频率构建 Huffman 树。
   使用优先队列（最小堆）来维护节点，每个节点代表一个字符及其频率。
   循环从优先队列中弹出两个最小频率的节点，然后创建一个新的父节点，将这两个节点作为子节点，父节点的频率为子节点频率之和。
   将新创建的父节点放回优先队列，重复这个过程直到队列中只剩下一个节点，即 Huffman 树的根节点。
5. 实现 generateCodes 函数：
   generateCodes 函数是一个递归函数，用于遍历 Huffman 树并生成字符的 Huffman 编码。
   从根节点开始，沿着左子树的路径添加 “0”，沿着右子树的路径添加 “1”。
   当遇到叶子节点时，将字符和路径编码存储在一个字符到编码的映射中。

三、 数据结构设计

1. 哈夫曼节点类 HuffmanNode：
   HuffmanNode 类用于表示哈夫曼树的节点，包括字符数据、频率以及左右子节点指针。
   构造函数初始化节点的数据、频率和子节点指针。
2. 比较器结构 CompareNodes：
   CompareNodes 结构用于比较两个 HuffmanNode 指针，按照频率从小到大的顺序排序，以便在优先队列中使用。
3. 哈夫曼树类 HuffmanTree：
   HuffmanTree 类用于构建哈夫曼树。
   构造函数接受一个 map<char, int> 参数，其中包含字符和它们的频率信息，并调用 buildTree 函数构建哈夫曼树。
   buildTree 使用优先队列（最小堆）来构建哈夫曼树，首先将字符频率转化为节点，然后反复合并频率最低的两个节点，直到只剩下一个根节点。
   getCodes 函数生成字符到编码的映射。
4. 私有函数 generateCodes：
   generateCodes 用于递归地生成字符到编码的映射，遍历哈夫曼树，构建每个字符的编码。
   在遇到叶子节点时将字符和编码存储在映射中。

四、 功能函数设计

1. 包含头文件和命名空间：代码包含了 、 和
2. 用于比较 HuffmanNode 指针的比较器 CompareNodes：定义了一个用于优先队列比较的自定义比较器，按照节点的频率从小到大进行比较。
3. buildTree 构建哈夫曼树的主要逻辑，使用优先队列来合并频率最低的节点，直到只剩下一个根节点。
4. getCodes 用于获取字符到哈夫曼编码的映射。
5. 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_NAMESPACE

class 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");

    // 连接按钮点击事件到槽函数Z
    connect(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_H

class 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 &quot;Microsoft YaHei UI&quot;;</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 &quot;Microsoft YaHei UI&quot;;</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 &quot;Microsoft YaHei UI&quot;;</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 &quot;Microsoft YaHei UI&quot;;</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>&lt;html&gt;&lt;head/&gt;&lt;body&gt;&lt;p&gt;&lt;span style=&quot; font-size:10pt;&quot;&gt;字符&lt;/span&gt;&lt;/p&gt;&lt;/body&gt;&lt;/html&gt;</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>&lt;html&gt;&lt;head/&gt;&lt;body&gt;&lt;p&gt;&lt;span style=&quot; font-size:10pt;&quot;&gt;频次&lt;/span&gt;&lt;/p&gt;&lt;/body&gt;&lt;/html&gt;</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/