基于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  
#include  
#include  
#include  
#include  
#include  
#include  
 
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); 
 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297