基于C++的通讯发报应用课程设计

向右看齐 2024-04-07 13:13 74阅读 0赞

目 录

1 题目介绍 … 1

1.1 问题描述 … 1  
1.1.1 问题背景 … 1  
1.1.2 主要任务 … 1  
1.2 问题分析 … 1

2 系统总体设计 … 2

2.1 系统总体功能 … 2  
2.2 系统总体流程 … 3

3 数据结构设计 … 4

3.1 HUFFMAN 类 … 4  
3.2 HUFFMAN NODE 结构体 … 5

4 功能模块设计 … 6

4.1 输入字符以及对应的频度模块 … 6  
4.2 解码模块 … 7

5 系统测试与运行结果 … 8

5.1 调试及调试分析 … 8  
5.2 测试用例 … 8

6 总 结 … 13

参考文献 … 14

附 录 （程序清单） … 15  
1 题目介绍

1.1问题描述

在通讯发报应用中，需要让应用对输入的字符集以及字符频度进行处理，构造哈夫曼树，并进行哈夫曼编码。比如输入以下内容：  
字符集：A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z  
字符频度：186，64，13，22，32，103，21，15，47，571，5，32，20，57，  
63，15，1，48，51，80，23，7，18，2，16，38

1.1.1问题背景  
在通讯发报中，需要对发出的字符串进行缩短，进行最大化的无损压缩，由此想到构造哈夫曼树，并进行哈夫曼编码，频度最高的字母使用较短的编码，频度低的字母使用较长的编码。  
1.1.2主要任务  
(1)由用户来输入初始字符集、相应字符及字符频度。  
(2)输入一个要发报的字符串，将其编码后发报。  
(3)接收一组发报信息，将其还原为字符序列。  
1.2问题分析  
需要解决的问题： (1)如何使用户输入数据并进行有效的存储？  
(2)如何构造一棵哈夫曼树并对结点进行哈夫曼编码？  
(3)如何对输入的错误数据进行容错性处理？  
求解方法：  
(1)使用基本的 cin，getchar()获取输入并存储于 vector 中。  
(2)使用递归来构造哈夫曼树，使用层次遍历的方法来对结点进行哈夫曼编码。  
(3)对待错误的信息进行直接解码，然后对解码信息进行判断。  
本文转载自http://www.biyezuopin.vip/onews.asp?id=15357  
2系统总体设计  
2.1系统总体功能  
通过问题分析后，设计通讯发报应用分为 5 个模块，分别为输入字符和字符频度，展示字符和字符频度，编码，解码，退出程序。  
输入字符和字符频度模块中包含输入数据，哈希表存储，构造哈夫曼树。构造哈夫曼树中包含入队，出队，获取元素个数操作。  
展示字符和字符频度包含哈希表遍历。  
编码中包含输入编码值，树的先序遍历，输出解码值。  
解码中包含输入编码值，树的遍历，输出解码值，其中树的遍历依据二进制编码，从而选择向左还是向右对哈夫曼树进行遍历。

Main.cpp 
     
    #include "Huffman.h" 
     
    int main() 
    {
         
        int choose; 
        Huffman huffman; 
     
        while(true) 
        {
         
            cout << "[1] Input Huffman hash map" << endl; 
            cout << "[2] Show out Huffman hash map" << endl; 
            cout << "[3] Encode element" << endl; 
            cout << "[4] Decode element" << endl; 
            cout << "[5] Exit" << endl << endl; 
     
            cout << "Plz choose:"; 
            cin >> choose; 
     
            switch(choose) 
            {
         
                case 1: 
                    huffman.getMap(); 
                    break; 
                case 2: 
                    huffman.showMap(); 
                    break; 
                case 3: 
                    huffman.encodeElement(); 
                    break; 
                case 4: 
                    huffman.decodeElement(); 
                    break; 
                case 5: 
                    exit(0); 
                    break; 
    
                default: 
                    cout << "Plz consider another choose!" << endl; 
                    break; 
            } 
     
            cout << endl; 
            huffman.clearData(); // 清除特定数据 
        } 
        return 0; 
    } 
     
     
      Huffman.h 
     
    #ifndef MAIN_HUFFMAN_H 
    #define MAIN_HUFFMAN_H 
     
    #include <iostream> 
    #include <cstdio> 
    #include <vector> 
    #include <queue> 
    #include <map> 
    #include <string> 
    #include <algorithm> 
     
    using namespace std; 
     
    struct HuffNode 
    {
         
        char data; // 信 息 
        int weight; // 权值 
        string huff_code; // Huffman 编码值 
        HuffNode * left;  // 左 节 点 
        HuffNode * right; // 右 节 点 
    }; 
     
    class Huffman 
    {
         public: 
        Huffman();  // 构造函数 
        ~Huffman(); // 析构函数 
     
    
        void getMap();  // 输入 Huffman 映射表 
        void showMap(); // 显示 Huffman 映射表 
     
        void encodeElement(); // 编 码 
        void decodeElement(); // 解 码 
     
        void setEncode(HuffNode * head, char data);     // 输出编码后的信息 
        void setDecode(HuffNode * head, string encode); // 输出解码后的信息 
     
        void createTree(); // 创 建 Huffman 
     
        void preOrder(HuffNode * head); // 先 序 遍 历 
     
        void clearData(); // 清除特定数据 
      private: 
        map<char, int> huffman_map; // Huffman 映 射 表 
        map<char, int>::iterator iter; // Huffman 映射表遍历 
     
        vector<char> huffdata; // 输入的元素 
        vector<HuffNode *> huffnodes; // 输入的元素 
     
        string encode;  // 编码后的信息 
        string decode;  // 解码后的信息 
     
        HuffNode * huffHeadPtr; // Huffman 头 节 点 
    }; 
     
    #endif //MAIN_HUFFMAN_H 
      Huffman.cpp 
     
    #include "Huffman.h" 
     
    // @brief 排序函数 
    bool sortByWeight(HuffNode * first, HuffNode * second) 
    {
         
        return first->weight < second->weight; 
    } 
     
    // @brief 构造函数Huffman::Huffman() 
    {
         
    
        huffHeadPtr = nullptr; // 头节点指向空 
    } 
     
    // @brief 析构函数Huffman::~Huffman() 
    {
         
        // TODO:递归删除哈弗曼树 
        delete huffHeadPtr; // 删除头节点 
        encode = ""; 
    } 
     
    // @brief 输入 Huffman 映射表void Huffman::getMap() 
    {
         
        char flag; // 判断回车标志 
        char input_char; // 输入的字符 
        int input_weight; // 输入的权重 
     
        while(true) 
        {
         
            cin >> input_char; 
            huffman_map.insert(pair<char, int>(input_char, -1)); // 插入字符 
     
            if((flag = getchar()) == '\n') 
                break; 
        } 
     
        for(iter = huffman_map.begin(); iter != huffman_map.end(); iter++) 
        {
         
            cin >> input_weight; 
            iter->second = input_weight; 
     
            flag = getchar(); // 吸收逗号 
        } 
     
        // 创建初始化容器 
        for(iter = huffman_map.begin(); iter != huffman_map.end(); iter++) 
        {
         
            HuffNode * temp = new HuffNode; 
     
            temp->data = iter->first; 
            temp->weight = iter->second; 
            temp->left = nullptr; 
    
            temp->right = nullptr; 
     
            huffnodes.push_back(temp); 
        } 
     
        createTree(); // 构 造 huffman 树 
     
        // 使用层次遍历 构造每一个节点 Huffman 编码 
        if(huffHeadPtr == nullptr) 
            return; 
     
        HuffNode * headTemp = huffHeadPtr; 
        queue<HuffNode *> huffnodes_qe; 
        huffnodes_qe.push(headTemp); 
     
        while(huffnodes_qe.size() > 0) 
        {
         
            headTemp = huffnodes_qe.front(); 
            huffnodes_qe.pop(); 
     
            if(headTemp->left) 
            {
         
                huffnodes_qe.push(headTemp->left); 
                headTemp->left->huff_code = headTemp->huff_code + "0"; 
            } 
            if(headTemp->right) 
            {
         
                huffnodes_qe.push(headTemp->right); 
                headTemp->right->huff_code = headTemp->huff_code + "1"; 
            } 
        } 
     
        preOrder(huffHeadPtr); // 使用遍历来验证 Huffman 
    } 
     
    // @brief 打印 Huffman 映射表void Huffman::showMap() 
    {
         
    // cout << huffman_map.size() << endl; 
        for(iter = huffman_map.begin(); iter != huffman_map.end(); iter++) 
        {
         
            cout << iter->first << " " << iter->second << endl; 
        } 
    
        cout << endl; 
    } 
     
    // @brief 编码 
    void Huffman::encodeElement() 
    {
         
        char flag; 
        char input; 
     
        // input elements 
        while(true) 
        {
         
            cin >> input; 
            huffdata.push_back(input); 
     
            if((flag = getchar()) == '\n') 
                break; 
        } 
     
        for(auto data : huffdata) 
            setEncode(huffHeadPtr, data); 
     
        cout << "编码后的信息:" << encode << endl; 
    } 
     
    // @brief 解码 
    void Huffman::decodeElement() 
    {
         
        cin >> encode; 
     
        setDecode(huffHeadPtr, encode); 
     
        cout << "解码后的信息:" << decode << endl; 
    } 
     
    // @brief 设置编码 
    void Huffman::setEncode(HuffNode * head, char data) 
    {
         
        if(head) 
        {
         
            if(head->data == data) 
                encode += head->huff_code; 
            setEncode(head->left, data); 
    
            setEncode(head->right, data); 
        } 
    } 
     
    // @brief 设置解码 
    void Huffman::setDecode(HuffNode * head, string encode) 
    {
         
        int index = 0; 
        HuffNode * temp = huffHeadPtr; 
        while(index < encode.size()) 
        {
         
            if(encode.at(index) == '0') 
            {
         
                temp = temp->left; 
                index++; 
            } 
            else if(encode.at(index) == '1') 
            {
         
                temp = temp->right; 
                index++; 
            } 
    
     
     	 
     	else 
    {
         
     	 	 	cout << “非法数据输入，程序退出” << endl; 
     	 	 	exit(0); 
    		} 
     
            if(temp->left == nullptr && temp->right == nullptr) 
            {
         
                decode += temp->data; 
                temp = huffHeadPtr; 
            } 
        } 
    } 
     
    // @brief 创建 Huffman 树void Huffman::createTree() 
    {
         
        while(huffnodes.size() > 0) 
        {
         
            // 按照 weight 从小到大进行排序 
            sort(huffnodes.begin(), huffnodes.end(), sortByWeight);

![在这里插入图片描述][f3f84a76b0a145a5a9f3a22f949eb114.png_pic_center]  
![在这里插入图片描述][950280afb0d848eda02841e10d994d4d.png_pic_center]  
![在这里插入图片描述][70813ffceb8c4a7099f9f1986f392594.png_pic_center]  
![在这里插入图片描述][f4db06f834fd456c8239f45d7c22645d.png_pic_center]  
![在这里插入图片描述][f58fa7eb4ff3418999e64336d18403e3.png_pic_center]  
![在这里插入图片描述][27379a65f4e549df9b38f4e91e208637.png_pic_center]  
![在这里插入图片描述][774b358fe2be4659ab1a01eb9a5118e7.png_pic_center]  
![在这里插入图片描述][f5e216d031344c6285657ce3e7ff9cce.png_pic_center]  
![在这里插入图片描述][7f1124c626f347a583db5b90a9fad002.png_pic_center]  
![在这里插入图片描述][0717f2d7375149c9b934cc1faf0681a3.png_pic_center]  
![在这里插入图片描述][a05fbd50164e4852bfb41d1e820e07fe.png_pic_center]  
![在这里插入图片描述][e0f8b2d6fe9e47f2a7ed62a30777396e.png_pic_center]  
![在这里插入图片描述][3ca9b146b92443feaae97d4931d15247.png_pic_center]  
![在这里插入图片描述][ca09e434859746f3a81bb59a90b43644.png_pic_center]

[f3f84a76b0a145a5a9f3a22f949eb114.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/d61beea1f72040afb553302d2d661794.png
[950280afb0d848eda02841e10d994d4d.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/1ba3fd27ec9f48548c948f6f384ea424.png
[70813ffceb8c4a7099f9f1986f392594.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/81aad5f94a62451db51cdb9753d4f89c.png
[f4db06f834fd456c8239f45d7c22645d.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/a494491494ed4dc6b919de28abe2e6c9.png
[f58fa7eb4ff3418999e64336d18403e3.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/40495b1677024dc0a0d06fe084b9e846.png
[27379a65f4e549df9b38f4e91e208637.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/10446ff0075844a2951d715ae8a8a1a9.png
[774b358fe2be4659ab1a01eb9a5118e7.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/1ee6294aa9c5418a9656be3404e8798a.png
[f5e216d031344c6285657ce3e7ff9cce.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/7e4afaee14ae45e2a3a4bd0629d210fc.png
[7f1124c626f347a583db5b90a9fad002.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/95c697a0762a43f19f9740f94f8b5892.png
[0717f2d7375149c9b934cc1faf0681a3.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/a5d860f7722e44aaac752c63eb425b88.png
[a05fbd50164e4852bfb41d1e820e07fe.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/114ee19480f04dc094d58a0bcf00b91b.png
[e0f8b2d6fe9e47f2a7ed62a30777396e.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/71e5211584e54cf290472d6d08613d7c.png
[3ca9b146b92443feaae97d4931d15247.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/5b98780ee0bf45bab42758fa715fa74d.png
[ca09e434859746f3a81bb59a90b43644.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/dc2e2e9bcf8a4c27b105ed75d4fa47da.png