一、功能
1、根据输入的字符、字符出现频率构建哈夫曼树
2、翻译
①、字符->编码
②、编码->字符
③、报文->密码
④、破译密码
二、碰到的一些问题
1、如何读取空格？
①、读取含空格的字符串
1 while (1)
2 {
3 getline(cin, message);
4 if (message != "")
5 {
6 break;
7 }
8 }
执行死循环，然后读取字符串，当字符串不为空时跳出死循环
②、读取单个空格字符
1 while (1)
2 {
3 string pankong = "";
4 getline(cin, pankong);
5 zf = pankong[0];
6 if (zf != '\0')
7 {
8 break;
9 }
10 }
2、好像其他并没有什么值得一提的问题
三、代码
1、主函数
1 #include<iostream>
2 #include"Huffman_Tree.h"
3 #include<string>
4 using namespace std;
5 int main()
6 {
7 bool flag = true;
8 char zf;
9 string message;
10 Huffman huffman;
11 while (flag)
12 {
13 cout << "1、输出哈夫曼树的基本结构" << endl;//ok
14 cout << "2、输出字符所对应的哈夫曼编码" << endl;//ok
15 cout << "3、将报文翻译成密码" << endl;//ok
16 cout << "4、解译密码" << endl;//ok
17 cout << "5、退出" << endl;
18 cout << "请选择你想要进行的操作：";
19 int select;
20 cin >> select;
21 switch (select)
22 {
23 case 1:
24 cout << "哈夫曼树为: " << endl;
25 huffman.Print();
26 break;
27 case 2:
28 cout << "请输入字符: ";
29 while (1)
30 {
31 string pankong = "";
32 getline(cin, pankong);
33 zf = pankong[0];
34 if (zf != '\0')
35 {
36 break;
37 }
38 }
39 cout << endl << "该字符所对应的哈夫曼编码为: " << huffman.Print_cypher(zf) << endl;
40 break;
41 case 3:
42 cout << "请输入需要翻译的报文: ";
43 while (1)
44 {
45 getline(cin, message);
46 if (message != "")
47 {
48 break;
49 }
50 }
51 cout << endl << "翻译后的密码为: " << huffman.inverse_translate(message) << endl;
52 break;
53 case 4:
54 cout << "请输入你需要翻译的密码: ";
55 cin >> message;
56 cout<< "解码后的报文为: " << huffman.translate(message) << endl;
57 break;
58 case 5:
59 flag = false;
60 break;
61 default:
62 cout << "error!" << endl;
63 }
64 cout << "====================================" << endl;
65 }
66 }
2、头文件
1 #pragma once
2 #include<iostream>
3 #include<string>
4 using namespace std;
5
6 #define N 27//字符个数
7
8 bool zt[N*2-1];
9
10 struct ElemType
11 {
12 int weight;//权值
13 int parent = -1, lchild = -1, rchild = -1;//游标
14 char character;//字符
15 string cypher = "";
16 };
17
18 class Huffman
19 {
20 private:
21 ElemType huffmanTree[N * 2 - 1];
22 int number=N;//密码字符的个数
23 void supArr();//完成表格
24 int select();//选出最小权值并用状态数组标记
25 int lookup(char a);//找字符在数组中的位置
26 void code(char a);//制作a的密码
27 void Make_cypher();//调用code制作N个字符的密码
28 public:
29 Huffman();//完成一系列初始化
30 void Print();//打印表格
31 string Print_cypher(char a);//打印a的密码
32 string translate(string a);//翻译密码串a
33 string inverse_translate(string a);//逆翻译密码串
34 };
35 string Huffman::inverse_translate(string a)
36 {
37 string tra;
38 for (int i = 0; i < a.length(); i++)
39 {
40 int xb = lookup(a[i]);
41 tra = tra + huffmanTree[xb].cypher;
42 }
43 return tra;
44 }
45 string Huffman::translate(string a)
46 {
47 string tra;//译文
48 int xb = 2 * N - 2;
49 for (int i = 0; i < a.length(); i++)
50 {
51 if (huffmanTree[xb].lchild != -1 && huffmanTree[xb].rchild != -1)
52 {
53 if (a[i] == '0')
54 {
55 xb = huffmanTree[xb].lchild;
56 }
57 else
58 {
59 xb = huffmanTree[xb].rchild;
60 }
61 if (huffmanTree[xb].lchild == -1)
62 {
63 tra = tra + huffmanTree[xb].character;
64 xb = 2 * N - 2;
65 }
66 }
67 }
68 return tra;
69 }
70 string Huffman::Print_cypher(char a)
71 {
72 int xb=lookup(a);
73 return huffmanTree[xb].cypher;
74 }
75 void Huffman::code(char a)
76 {
77 int xb = lookup(a);
78 while(huffmanTree[xb].parent != -1)
79 {
80 if (huffmanTree[huffmanTree[xb].parent].lchild == xb)
81 {
82 huffmanTree[lookup(a)].cypher = "0" + huffmanTree[lookup(a)].cypher;
83 }
84 if (huffmanTree[huffmanTree[xb].parent].rchild == xb)
85 {
86 huffmanTree[lookup(a)].cypher = "1" + huffmanTree[lookup(a)].cypher;
87 }
88 xb = huffmanTree[xb].parent;
89 }
90 }
91 void Huffman::Make_cypher()
92 {
93 for (int i = 0; i < N; i++)
94 {
95 code(huffmanTree[i].character);
96 }
97 }
98 int Huffman::lookup(char a)
99 {
100 for (int i = 0; i < N; i++)
101 {
102 if (huffmanTree[i].character == a)
103 return i;
104 }
105 }
106 void Huffman::Print()
107 {
108 cout << " " << "\t" << "weight" << "\t" << "parent" << "\t" << "lchild" << "\t" << "rchild" << "\t" << endl;
109 for (int i = 0; i < 2 * N - 1; i++)
110 {
111 cout << i << "\t" << huffmanTree[i].weight << "\t" << huffmanTree[i].parent << "\t" << huffmanTree[i].lchild << "\t" << huffmanTree[i].rchild << "\t" << endl;
112 }
113 }
114 void Huffman::supArr()//完成数组表
115 {
116 for (int i = N; i < 2 * N - 1; i++)
117 {
118 int xb1 = select();
119 int xb2 = select();
120 huffmanTree[i].weight = huffmanTree[xb1].weight + huffmanTree[xb2].weight;
121 huffmanTree[i].lchild = xb1; huffmanTree[i].rchild = xb2;
122 huffmanTree[xb1].parent = i; huffmanTree[xb2].parent = i;
123 }
124 }
125 int Huffman::select()//选出两个最小的权值
126 {
127 int min = 999;
128 int xb=6;
129 for (int i = 0; i < 2 * N - 1; i++)
130 {
131 if (huffmanTree[i].weight < min && zt[i] == false)
132 {
133 min = huffmanTree[i].weight;
134 xb = i;
135 }
136 }
137 zt[xb] = true;
138 return xb;
139 }
140 Huffman::Huffman()
141 {
142 for (int i = 0; i < 2 * N - 1; i++)
143 {
144 if (i < N)
145 {
146 cout << "请输入第" << i + 1 << "个字符：";
147 while (1)
148 {
149 string pankong="";
150 getline(cin, pankong);
151 huffmanTree[i].character = pankong[0];
152 if (huffmanTree[i].character!='\0')
153 {
154 break;
155 }
156 }
157 /*if (i == 0)
158 {
159 huffmanTree[i].character = ' ';
160 }
161 else
162 {
163 cout << "请输入第" << i + 1 << "个字符：";
164 cin >> huffmanTree[i].character;
165 }*/
166 cout << "请输入第" << i + 1 << "个字符的权值：";
167 cin >> huffmanTree[i].weight;
168 }
169 else
170 {
171 huffmanTree[i].weight = 999;//方便选出两个最小权值
172 }
173 zt[i] = false;//初始化
174 }
175 supArr();
176 Make_cypher();
177 }