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. 包含头文件和命名空间:代码包含了 、 和 头文件,并使用 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/

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/287821.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【算法系列 | 11】深入解析查找算法之—插值查找

序言 心若有阳光&#xff0c;你便会看见这个世界有那么多美好值得期待和向往。 决定开一个算法专栏&#xff0c;希望能帮助大家很好的了解算法。主要深入解析每个算法&#xff0c;从概念到示例。 我们一起努力&#xff0c;成为更好的自己&#xff01; 今天第11讲&#xff0c;讲…

阿里云服务器端口PPTP 1723放行教程

阿里云服务器安装PPTP VPN需要先开通1723端口&#xff0c;阿里云服务器端口是在安全组中操作的&#xff0c;阿里云服务器网aliyunfuwuqi.com来详细说明阿里云服务器安全组开放PPTP VPN专用1723端口教程&#xff1a; 阿里云服务器放行1723端口教程 PPTP是点对点隧道协议&#…

八大算法排序@选择排序(C语言版本)

目录 选择排序概念算法思想示例步骤1步骤2步骤...n最后一步 代码实现时间复杂度空间复杂度特性总结 选择排序 概念 选择排序&#xff08;Selection Sort&#xff09;是一种简单直观的排序算法。基本思想是在未排序的序列中找到最小&#xff08;或最大&#xff09;元素&#xf…

数据库之索引

1. 索引的定义 索引是一个排序的列表&#xff0c;包含索引字段的值和其对应的行记录的数据所在的物理地址。 索引的作用&#xff1a; 加快表的查询速度&#xff0c;还可以对字段排序。 2. 索引的工作方式 有了索引后&#xff0c;要根据条件查询某行数据时&#xff0c;需要先…

IPA打包过程中的Invalid Bundle Structure错误如果解决

在iOS应用程序开发中&#xff0c;打包和发布应用程序是一个必要的步骤。有的时候在打包的过程中可能会遇到一些错误&#xff0c;其中一个比较常见的错误是"Invalid Bundle Structure"。这个错误通常意味着应用程序的文件结构不正确&#xff0c;而导致的无法成功打包应…

自动循环采集全站文章

如果文章页面中&#xff0c;有上一篇、下一篇文章&#xff0c;推荐文章等链接&#xff0c;我们可以利用这个特点&#xff0c;仅配置采集一个文章页面&#xff0c;即可采集整个网站或某个分类下的所有文章&#xff0c;实现自动循环采集全站数据&#xff0c;非常方便简单。 使用…

天然药物,到2028年市场规模将达到 3082亿美元

天然药物&#xff0c;也称为草药或传统药物&#xff0c;是指将植物、矿物和动物产品等天然物质用于药用目的。近年来&#xff0c;人们对天然药物作为传统药物的替代品越来越感兴趣&#xff0c;这导致了天然药物市场的增长。全球天然药物市场&#xff1a; 全球天然药物市场预计从…

2024腾讯云服务器租用价格表_优惠活动大全_最新报价

腾讯云服务器租用价格表&#xff1a;轻量应用服务器2核2G3M价格62元一年、2核2G4M价格118元一年&#xff0c;540元三年、2核4G5M带宽218元一年&#xff0c;2核4G5M带宽756元三年、轻量4核8G12M服务器446元一年、646元15个月&#xff0c;云服务器CVM S5实例2核2G配置280.8元一年…

安科瑞余压监控系统在住宅小区的应用方案——安科瑞 顾烊宇

【摘要】&#xff1a;本文分析了火灾发生时人员伤亡的主要原因——烟雾&#xff0c;并针对该原因提供切实可靠的系统应用解决方案&#xff0c;并通过具体案例&#xff0c;从设计依据、产品选型、系统组网、现场安装等方式介绍余压监控系统&#xff0c;希望可以在火灾发生时较大…

BMS均衡技术

一、电池的不一致性&#xff1f; 每个电池都有自己的“个性”&#xff0c;要说均衡&#xff0c;得先从电池谈起。即使是同一厂家同一批次生产的电池&#xff0c;也都有自己的生命周期、自己的“个性”——每个电池的容量不可能完全一致。例如以下的两个原因都会造成电池不一致…

树与二叉树笔记整理

摘自小红书 ## 树与二叉树 ## 排序总结

【数据库】MySQL数据库存储引擎、数据库管理和数据库账号管理

【数据库】MySQL数据库存储引擎、数据库管理和数据库账号管理 一 常用的数据引擎1.1 InnoDB存储引擎1.2 MyISAM存储引擎1.3 Memory存储引擎1.4 ARCHIVE存储引擎 二 数据库管理2.1 元数据库概念与分类2.2 相关操作命令 三 数据表的管理四 数据库账户管理 一 常用的数据引擎 数据…

清风数学建模笔记-多分类-fisher线性判别分析

内容&#xff1a;Fisher线性判别分析 一.介绍&#xff1a; 1.给定的训练姐&#xff0c;设法投影到一维的直线上&#xff0c;使得同类样例的投影点尽可能接近和密集&#xff0c;异类投影点尽可能远离。 2.如何同类尽可能接近&#xff1a;方差越小 3.如何异类尽可能远离&#…

阿里云2核2G3M服务器能放几个网站?有限制吗?

阿里云2核2g3m服务器可以放几个网站&#xff1f;12个网站&#xff0c;阿里云服务器网的2核2G服务器上安装了12个网站&#xff0c;甚至还可以更多&#xff0c;具体放几个网站取决于网站的访客数量&#xff0c;像阿里云服务器网aliyunfuwuqi.com小编的网站日访问量都很少&#xf…

获取网页信息

每次copy & paste总是很麻烦&#xff0c;现在有点问题&#xff0c;先记录下来。 需求&#xff1a;获取url 里Feature list&#xff0c;并输出表格形式 可以用Convert curl commands to code&#xff1a;得到get请求的header&#xff0c;cookie等 import requests import…

Jmeter二次开发实操问题汇总(JDK问题,jar包问题)

前提 之前写过一篇文章&#xff1a;https://qa-lsq.blog.csdn.net/article/details/119782694 只是简单尝试了一下生成一个随机手机号码。 但是如果在工作中一个实际场景要用的二次开发&#xff0c;可能会遇到一些问题。 比如这样一个场景&#xff1a; Mobile或者前端调用部分…

【动态规划】LeetCode-10. 正则表达式匹配

10. 正则表达式匹配。 给你一个字符串 s 和一个字符规律 p&#xff0c;请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。 ‘.’ 匹配任意单个字符‘*’ 匹配零个或多个前面的那一个元素 所谓匹配&#xff0c;是要涵盖 整个 字符串 s的&#xff0c;而不是部分字符串。 …

conda: error: argument COMMAND: invalid choice: ‘activate‘

1.问题 2.解决方法 1.寻找基本路径 conda info | grep -i base environment2.更新资源 source /Users/suhang/miniconda3/etc/profile.d/conda.sh3.重新运行命令 conda activate chatglm参考图&#xff1a;

UI5与后端的文件交互(一)

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、RAP的开发1. 创建表格2. 创建CDS Entity3. 创建BDEF4. 创建implementation class5. 创建Service Definition和Binding6. 测试API 二、创建UI5 Project1. 使…

jsp+ssm+mysql实现的酒店预定管理系统项目----计算机毕业设计

项目介绍 jspssm框架&#xff08;spring、springMVC、mybaits&#xff09;实现的酒店预定管理系统的源码和视频开发教程。本系统分前台和后台管理两部分&#xff0c;前台实现了用户登录注册、查看房型信息、预定房间、提交订单、查看个人订单、修改个人资料等&#xff0c;后台…