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

发布时间:2024年01月02日

一、 问题描述

在进行程序设计时,通常给每一个字符标记一个单独的代码来表示一组字符,即编码。在进行二进制编码时,假设所有的代码都等长,那么表示 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. 包含头文件和命名空间:代码包含了 、 和 头文件,并使用 using namespace std; 来引入标准命名空间。
  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/

文章来源:https://blog.csdn.net/qq_40179418/article/details/135349551
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。