本文实例讲述了C++数据结构与算法之哈夫曼树的实现方法。分享给大家供大家参考，具体如下：
哈夫曼树又称最优二叉树，是一类带权路径长度最短的树。
对于最优二叉树，权值越大的结点越接近树的根结点，权值越小的结点越远离树的根结点。
前面一篇图文详解JAVA实现哈夫曼树对哈夫曼树的原理与java实现方法做了较为详尽的描述，这里再来看看C++实现方法。
具体代码如下：
|
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
|
#include <iostream>using namespace std;#if !defined(_HUFFMANTREE_H_)#define _HUFFMANTREE_H_/* * 哈夫曼树结构 */class HuffmanTree{public: unsigned int Weight; unsigned int Parent; unsigned int lChild; unsigned int rChild;};typedef char **HuffmanCode;/* * 从结点集合中选出权值最小的两个结点 * 将值分别赋给s1和s2 */void Select(HuffmanTree* HT,int Count,int *s1,int *s2){ unsigned int temp1=0; unsigned int temp2=0; unsigned int temp3; for(int i=1;i<=Count;i++) { if(HT[i].Parent==0) { if(temp1==0) { temp1=HT[i].Weight; (*s1)=i; } else { if(temp2==0) { temp2=HT[i].Weight; (*s2)=i; if(temp2<temp1) { temp3=temp2; temp2=temp1; temp1=temp3; temp3=(*s2); (*s2)=(*s1); (*s1)=temp3; } } else { if(HT[i].Weight<temp1) { temp2=temp1; temp1=HT[i].Weight; (*s2)=(*s1); (*s1)=i; } if(HT[i].Weight>temp1&&HT[i].Weight<temp2) { temp2=HT[i].Weight; (*s2)=i; } } } } }}/* * 霍夫曼编码函数 */void HuffmanCoding(HuffmanTree * HT, HuffmanCode * HC, int *Weight, int Count){ int i; int s1,s2; int TotalLength; char* cd; unsigned int c; unsigned int f; int start; if(Count<=1) return; TotalLength=Count*2-1; HT = new HuffmanTree[(TotalLength+1)*sizeof(HuffmanTree)]; for(i=1;i<=Count;i++) { HT[i].Parent=0; HT[i].rChild=0; HT[i].lChild=0; HT[i].Weight=(*Weight); Weight++; } for(i=Count+1;i<=TotalLength;i++) { HT[i].Weight=0; HT[i].Parent=0; HT[i].lChild=0; HT[i].rChild=0; } //建造哈夫曼树 for(i=Count+1;i<=TotalLength;++i) { Select(HT, i-1, &s1, &s2); HT[s1].Parent = i; HT[s2].Parent = i; HT[i].lChild = s1; HT[i].rChild = s2; HT[i].Weight = HT[s1].Weight + HT[s2].Weight; } //输出霍夫曼编码 (*HC)=(HuffmanCode)malloc((Count+1)*sizeof(char*)); cd = new char[Count*sizeof(char)]; cd[Count-1]='\0'; for(i=1;i<=Count;++i) { start=Count-1; for(c = i,f = HT[i].Parent; f != 0; c = f, f = HT[f].Parent) { if(HT[f].lChild == c) cd[--start]='0'; else cd[--start]='1'; (*HC)[i] = new char [(Count-start)*sizeof(char)]; strcpy((*HC)[i], &cd[start]); } } delete [] HT; delete [] cd;}/* * 在字符串中查找某个字符 * 如果找到，则返回其位置 */int LookFor(char *str, char letter, int count){ int i; for(i=0;i<count;i++) { if(str[i]==letter) return i; } return -1;}void OutputWeight(char *Data,int Length, char **WhatLetter, int **Weight,int *Count){ int i; char* Letter = new char[Length]; int* LetterCount = new int[Length]; int AllCount=0; int Index; int Sum=0; float Persent=0; for(i=0;i<Length;i++) { if(i==0) { Letter[0]=Data[i]; LetterCount[0]=1; AllCount++; } else { Index=LookFor(Letter,Data[i],AllCount); if(Index==-1) { Letter[AllCount]=Data[i]; LetterCount[AllCount]=1; AllCount++; } else { LetterCount[Index]++; } } } for(i=0;i<AllCount;i++) { Sum=Sum+LetterCount[i]; } (*Weight) = new int[AllCount]; (*WhatLetter) = new char[AllCount]; for(i=0;i<AllCount;i++) { Persent=(float)LetterCount[i]/(float)Sum; (*Weight)[i]=(int)(1000*Persent); (*WhatLetter)[i]=Letter[i]; } (*Count)=AllCount; delete [] Letter; delete [] LetterCount;}#endifvoid main(){ HuffmanTree * HT = NULL; HuffmanCode HC; char Data[100]; char *WhatLetter; int *Weight; int Count; cout<<"请输入一行文本数据:"<<endl; cin>>Data; cout<<endl; OutputWeight(Data,strlen(Data), &WhatLetter, &Weight, &Count); HuffmanCoding(HT, &HC, Weight, Count); cout<<"字符 出现频率 编码结果"<<endl; for(int i = 0; i<Count; i++) { cout<<WhatLetter[i]<<" "; cout<<Weight[i]/1000.0<<"%\t"; cout<<HC[i+1]<<endl; } cout<<endl;} |
希望本文所述对大家C++程序设计有所帮助。
原文链接：http://blog.csdn.net/earbao/article/details/8134913
