哈夫曼树c++实现（bupt信通大一下数据结构实验）_北邮c++ 哈夫曼树

数据结构做到哈夫曼，找到了以前的代码

使用时：按1回车，输入字符串，回车，然后依次2，回车，3，回车…n，回车

#include <iostream>
#include <cstring>
#include <iomanip>
// #include "Huffman.h"
using namespace std;
char s[150];            //目标字符串
char ch[150];           //出现过的字符
int  num[150];          //ch中字符对应的个数
int  position[150];     //直接下标为ASCll码存储字符在num及ch中的位置
char Encoded[1024];     //存放编码过后的字符串
char ans[1024];         //存放编码再解码的字符串
int m, n;
//样例：I love data Structure, I love Computer. I will try my best to study data Structure.
//
struct HCode {
	char data;
	char code[100];
};
struct HNode {
	int weight;
	int Lchild, Rchild;
	int parent;
};
class Huffman {
private:
	int originalLen;
	int newLen;
	HNode* huffTree;
	HCode* HCodeTable;
	int N;
public:
	void CreateHTree(int a[], int n);                      //建树
	void CreateCodeTable(char b[], int n);                 //建码表
	void Encode(char* s, char* d, int n, int a[]);         //编码
	void Decode(char* s, char* d, int n);                  //解码
	void checkLen();                                       //输出编码前后长度
	void PrintTree(char *s);                                      //凹入法打印
	void PreOrder(int root, int depth, char *s);                 //前序遍历
	~Huffman();
};
void SelectMin(HNode* hTree, int n, int& i1, int& i2);
void Reverse(char c[]);
void work() {//对字符串进行统计处理
	cout << "正在对字符串进行处理" << endl;
	m = strlen(s), n = 0;
	int pos(0);
	for (int i = 0; i < m; i++) {
		if (position[s[i]]) {
			num[position[s[i]]] += 1;
		}
		else {
			position[s[i]] = ++pos;
			ch[pos] = s[i];
			num[pos] = 1;
		}
	} n = pos;
	for (int i = 1; i <= n; i++) {
		cout << std::left << ch[i] << ":" << setw(8) << num[position[ch[i]]] << " ";
		if (i % 5 == 0) puts("");
	}
	puts("");
}
int main() {
	Huffman test;
	//*************************************
	int op(-1);
	cout << "0：停止进程" << endl;
	cout << "1：输入字串" << endl;
	cout << "2：建树" << endl;
	cout << "3：建表" << endl;
	cout << "4：编码" << endl;
	cout << "5：解码" << endl;
	cout << "6：查看长度" << endl;
	cout << "7：打印树" << endl;//凹入表示法
	cout << "I love data Structure, I love Computer. I will try my best to study data Structure." << endl;
	cout << "------------------------*" << endl;
	//*************************************
	while (cin >> op) {
		if (!op) { 
			cout << "进程停止" << endl;
			break;
		}
		if (op == 1) {//输入要进行操作的字符
			cout << "输入要进行操作的字串：" << endl; getchar();
			cin.getline(s, 150);
			cout << "------------------------*" << endl;
			work();
			cout << "------------------------*" << endl;
		}
		if (op == 2) {//建树
			cout << "---------TreeCreating" << endl;
			test.CreateHTree(num + 1, n);
			cout << "------------------------*" << endl;
		}
		if (op == 3) {//建表
			test.CreateCodeTable(ch + 1, n);
			cout << "------------------------*" << endl;
		}
		if (op == 4) {//编码
			test.Encode(s, Encoded, m, position);
			cout << "----------stringEncoded:" << endl << Encoded << endl;
			cout << "------------------------*" << endl;
		}
		if (op == 5) {//解码
			test.Decode(Encoded, ans, n);
			cout << "----------stringDecoded:" << endl << ans << endl;
			cout << "------------------------*" << endl;
		}
		if (op == 6) {//查看压缩前后字串长度
			test.checkLen();
			cout << "------------------------*" << endl;
		}
		if (op == 7) {
			test.PrintTree(ch + 1);
			cout << "------------------------*" << endl;
		}
	}
	return 0;
}
void Huffman::CreateHTree(int a[], int n) {
	N = 2 * n - 1;
	huffTree = new HNode[2 * n - 1];
	for (int i = 0; i < n; i++) {
		huffTree[i].weight = a[i];
		huffTree[i].Lchild = -1;
		huffTree[i].Rchild = -1;
		huffTree[i].parent = -1;
	}
	int li, ri;
	for (int i = n; i < 2 * n - 1; i++) {
		SelectMin(huffTree, i, li, ri);
		huffTree[li].parent = huffTree[ri].parent = i;
		huffTree[i].weight = huffTree[li].weight + huffTree[ri].weight;
		huffTree[i].Lchild = li;
		huffTree[i].Rchild = ri;
		huffTree[i].parent = -1;
	}
	cout << "---------Tree Created" << endl;
 }
//建表
void Huffman::CreateCodeTable(char b[], int n) {
	cout << "---------CodeTable Creating..." << endl;
	HCodeTable = new HCode[n];
	for (int i = 0; i < n; i++) {
		HCodeTable[i].data = b[i];
		int k = 0, ic = i;
		int ip = huffTree[i].parent;
		while (ip != -1) {
			if (ic == huffTree[ip].Lchild)
				HCodeTable[i].code[k] = '0';
			else HCodeTable[i].code[k] = '1';
			k++, ic = ip;
			ip = huffTree[ic].parent;
		}
		HCodeTable[i].code[k] = '\0';
		Reverse(HCodeTable[i].code);
	}
	cout << "---------CodeTable Created..." << endl;
	//输出码表：如下
	cout << "输出码表如下：" << endl;
	for (int i = 0; i < n; i++) {
		cout << std::left << b[i] << ":" << setw(12) << HCodeTable[i].code;
		if ((i+1) % 5 == 0) puts("");
	} puts("");
}
//编码
void Huffman::Encode(char* s, char* d, int n, int position[]) {
	originalLen = n;
	cout << "----------Encoding..." << endl;
	int pos = 0;
	for (int i = 0; i < n; i++) {
		int k = strlen(HCodeTable[position[s[i]] - 1].code);
		for (int j = 0; j < k; j++)
			d[pos++] = HCodeTable[position[s[i]] - 1].code[j];
	}
	newLen = pos;
}
//解码
void Huffman::Decode(char* s, char* d, int n) {
	cout << "----------Decoding..." << endl;
	//cout << s << endl;
	while (*s != '\0') {
		int k = 2 * n - 2;
		while (huffTree[k].Lchild != -1) {
			if (*s == '0')
				k = huffTree[k].Lchild;
			else k = huffTree[k].Rchild;
			s++;
		}
		*d = HCodeTable[k].data;
		d++;
	}
}
Huffman::~Huffman() {
	delete [] huffTree;
	delete [] HCodeTable;
}
//倒置数组
void Reverse(char *c) {
	int k = strlen(c);
	int i = 0, j = k - 1;
	while (i < j) {
		swap(c[i], c[j]);
		i++, j--;
	}
}
//寻找最小的两个作为兄弟
void SelectMin(HNode* hTree, int n, int& i1, int& i2) {
	int i;
	for (i = 0; i < n; i++)
		if (hTree[i].parent == -1) { i1 = i; break; }

	for (++i; i < n; i++)
		if (hTree[i].parent == -1) { i2 = i; break; }

	if (hTree[i1].weight > hTree[i2].weight) swap(i1, i2);
	for (++i; i < n; i++) {
		if (hTree[i].parent == -1) {
			if (hTree[i].weight < hTree[i1].weight)
				i2 = i1, i1 = i;
			else if (hTree[i].weight < hTree[i2].weight)
				i2 = i;
		}
	}
}
void Huffman::checkLen() {
	cout << "编码前长度：" << originalLen << " byte" << endl;
	cout << "编码后长度：" << newLen << " bit (如果用bit编码)" << endl;
}
void Huffman::PreOrder(int root, int depth, char *s) {
	if (huffTree[root].weight) {
		for (int i = 0; i < depth*2; i++) cout << " ";
		cout << std::left << setw(25-depth * 2) << setfill('-') << huffTree[root].weight;
		if (huffTree[root].Lchild == -1 && huffTree[root].Rchild == -1) {
			cout << s[root];
			if (s[root] == ' ') cout << "(空格)";
		}
		cout << endl;
	}
	if (huffTree[root].Lchild != -1) PreOrder(huffTree[root].Lchild, depth + 1, s);
	if (huffTree[root].Rchild != -1) PreOrder(huffTree[root].Rchild, depth + 1, s);
}
void Huffman::PrintTree(char *s) {
	cout << "----------TreePrinting..." << endl;
	PreOrder(N-1, 1, s);
}
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