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

目 录

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