#include
using namespace std;
template
class hfTree {
private:
struct Node
{
Type data;
int weight;
int parent, left, right;
};
Node * elem;
int length;
public:
struct hfCode {
Type data;
string code;
};
hfTree(const Type *x, const int * w, int size);
void getCode(hfCode result[]);
~hfTree() { delete [] elem; }
};
template
hfTree::hfTree(const Type * v, const int * w, int size)
{
const int max = 32767;
int min1, min2;//最小树，次最小树的权值
int x, y;//最小树，次最小树的下标
length = 2 * size;
elem = new Node[length];
//将数表初始化
for (int i = size; i < length; ++i)
{
elem[i].weight = w[i - size];
elem[i].data = v[i - size];
elem[i].parent = elem[i].left = elem[i].right = 0;
}
//归并森林中的树
for (int i = size - 1; i > 0; --i)
{
min1 = min2 = max; x = y = 0;
for (int j = i + 1; j<length; ++j)
if (elem[j].parent == 0)
if (elem[j].weight<min1)
{
min2 = min1; min1 = elem[j].weight; x = y; y = j;
}
else if (elem[j].weight<min2)
{
min2 = elem[j].weight; x = j;
}//第52-61:找出待归并的两棵树
elem[i].weight = min1 + min2;
elem[i].left = x; elem[i].right = y; elem[i].parent = 0;
elem[x].parent = i; elem[y].parent = i;
}
}
template
void hfTree::getCode(hfCode result[])
{
int size = length / 2;
int p, s;//p是s的父节点
for (int i = size; i<length; ++i)
{
result[i - size].data = elem[i].data;
result[i - size].code = " ";
p = elem[i].parent; s = i;
while (p) {
if (elem[p].left == s)
result[i - size].code = "0" + result[i - size].code;
else result[i - size].code = "1" + result[i - size].code;
s = p; p = elem[p].parent;
}
}
}
#include"hfTree.h"
#include
#include
using namespace std;
/*
输入一篇英文文章，统计每个字符出现的次数，
并以此构造哈夫曼树和输出每个字符的哈夫曼编码，
最后输出这篇文章的编码。
*/
int main()
{
struct Wen
{
char abc;
int weight;
}; Wen *elems;
//结点指针保存文章的字符和权重
cout << "请输入一段英文，按回车键结束。" << endl;
string str;
getline(cin, str);
int str_lenth = str.length();
elems=new Wen [str_lenth];
int _length = 0;
for (int j = 0; j < str_lenth; j++)
for (int i = 0; i <= j; i++)
{
if (elems[i].abc== str[j])
{
elems[i].weight++; break;
}
else if(elems[i].abc==0)
elems[i].abc = str[j];
elems[i].weight = 1;
_length++;
}//两次for循环统计文章相同的字符和权重
char *xx = new char[_length];
int *ww = new int[_length];
for (int i = 0; i < _length; i++) {
xx[i] = elems[i].abc;
ww[i] = elems[i].weight;
}//将文章出现的字符和权重保存在两个数组中
hfTree<char>tree(xx, ww, _length);
hfTree<char>::hfCode result [200];
tree.getCode(result);
for (int i = 0; i < _length; ++i)
cout << result[i].data << " " << result[i].code <<endl;
system("pause");
return 0;
}
VS2015和dev都可以编译，但是vs2015再输入文章后程序就无法运行了
dev则是输出不正确。
其实我不是很懂C++,我是实现pascal的
1 /***************************************
2 目的：1.根据输入的字符代码集及其权值集，
3 构造赫夫曼树，输出各字符的赫夫曼编码
4 2.输入赫夫曼码序列，输出原始字符代码
5 作者：Dmego 时间：2016-11-11
6 ****************************************/
7 #include
8 #define MAX_MA 1000
9 #define MAX_ZF 100
10 using namespace std;
11
12 //哈夫曼树的储存表示
13 typedef struct
14 {
15 int weight; //结点的权值
16 int parent, lchild, rchild;//双亲，左孩子，右孩子的下标
17 }HTNode,*HuffmanTree; //动态分配数组来储存哈夫曼树的结点
18
19 //哈夫曼编码表的储存表示
20 typedef char **HuffmanCode;//动态分配数组存储哈夫曼编码
21
22 //返回两个双亲域为0且权值最小的点的下标
23 void Select(HuffmanTree HT, int n, int &s1, int &s2)
24 {
25 /*n代表HT数组的长度
26 /
27
28 //前两个for循环找所有结点中权值最小的点（字符）
29 for (int i = 1; i <= n; i++)
30 {//利用for循环找出一个双亲为0的结点
31 if (HT[i].parent == 0)
32 {
33 s1 = i;//s1初始化为i
34 break;//找到一个后立即退出循环
35 }
36 }
37 for (int i = 1; i <= n; i++)
38 {/利用for循环找到所有结点（字符）权值最小的一个
39 并且保证该结点的双亲为0*/
40 if (HT[i].weight < HT[s1].weight && HT[i].parent == 0)
41 s1 = i;
42 }
43 //后两个for循环所有结点中权值第二小的点（字符）
44 for (int i = 1; i <= n; i++)
45 {//利用for循环找出一个双亲为0的结点，并且不能是s1
46 if (HT[i].parent == 0 && i != s1)
47 {
48 s2 = i;//s2初始化为i
49 break;//找到一个后立即退出循环
50 }
51 }
52
53 for (int i = 1; i <= n; i++)
54 {/*利用for循环找到所有结点（字符）权值第二小的一个，
55 该结点满足不能是s1且双亲是0*/
56 if (HT[i].weight < HT[s2].weight && HT[i].parent == 0 && i!= s1)
57 s2 = i;
58 }
59
60 }
61
62 //构造哈夫曼树
63 void CreateHuffmanTree(HuffmanTree &HT, int n)
64 {
65 /*-----------初始化工作-------------------------*/
66 if (n <= 1)
67 return;
68 int m = 2 * n - 1;
69 HT = new HTNode[m + 1];
70 for (int i = 1; i <= m; ++i)
71 {//将1~m号单元中的双亲，左孩子，右孩子的下标都初始化为0
72 HT[i].parent = 0; HT[i].lchild = 0; HT[i].rchild = 0;
73 }
74 for (int i = 1; i <= n; ++i)
75 {
76 cin >> HT[i].weight;//输入前n个单元中叶子结点的权值
77 }
78 /*-----------创建工作---------------------------*/
79 int s1,s2;
80 for (int i = n + 1; i <= m; ++i)
81 {//通过n-1次的选择，删除，合并来构造哈夫曼树
82 Select(HT, i - 1, s1, s2);
83 /*cout << HT[s1].weight << " , " << HT[s2].weight << endl;*/
84 /*将s1,s2的双亲域由0改为i
85 (相当于把这两个结点删除了，这两个结点不再参与Select()函数)*/
86 HT[s1].parent = i;
87 HT[s2].parent = i;
88 //s1,与s2分别作为i的左右孩子
89 HT[i].lchild = s1;
90 HT[i].rchild = s2;
91 //结点i的权值为s1,s2权值之和
92 HT[i].weight = HT[s1].weight + HT[s2].weight;
93 }
94 }
95
96 //从叶子到根逆向求每个字符的哈夫曼编码，储存在编码表HC中
97 void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n)
98 {
99 HC = new char*[n + 1];//分配储存n个字符编码的编码表空间
100 char cd = new char[n];//分配临时存储字符编码的动态空间
101 cd[n - 1] = '\0';//编码结束符
102 for (int i = 1; i <= n; i++)//逐个求字符编码
103 {
104 int start = n - 1;//start 开始指向最后，即编码结束符位置
105 int c = i;
106 int f = HT[c].parent;//f指向结点c的双亲
107 while (f != 0)//从叶子结点开始回溯，直到根结点
108 {
109 --start;//回溯一次，start向前指向一个位置
110 if (HT[f].lchild == c) cd[start] = '0';//结点c是f的左孩子，则cd[start] = 0;
111 else cd[start] = '1';//否则c是f的右孩子，cd[start] = 1
112 c = f;
113 f = HT[f].parent;//继续向上回溯
114 }
115 HC[i] = new char[n - start];//为第i个字符编码分配空间
116 strcpy(HC[i], &cd[start]);//把求得编码的首地址从cd[start]复制到HC的当前行中
117 }
118 delete cd;
119 }
120
121 //哈夫曼译码
122 void TranCode(HuffmanTree HT,char a[],char zf[],char b[],int n)
123 {
124 /
125 HT是已经创建好的哈夫曼树
126 a[]用来传入二进制编码
127 b[]用来记录译出的字符
128 zf[]是与哈夫曼树的叶子对应的字符（叶子下标与字符下标对应）
129 n是字符个数，相当于zf[]数组得长度
130 /
131
132 int q = 2*n-1;//q初始化为根结点的下标
133 int k = 0;//记录存储译出字符数组的下标
134 int i = 0;
135 for (i = 0; a[i] != '\0';i++)
136 {//for循环结束条件是读入的字符是结束符（二进制编码）
137 //此代码块用来判断读入的二进制字符是0还是1
138 if (a[i] == '0')
139 {/读入0，把根结点(HT[q])的左孩子的下标值赋给q
140 下次循环的时候把HT[q]的左孩子作为新的根结点*/
141 q = HT[q].lchild;
142 }
143 else if (a[i] == '1')
144 {
145 q = HT[q].rchild;
146 }
147 //此代码块用来判断HT[q]是否为叶子结点
148 if (HT[q].lchild == 0 && HT[q].rchild == 0)
149 {/*是叶子结点，说明已经译出一个字符
150 该字符的下标就是找到的叶子结点的下标*/
151 b[k++] = zf[q];//把下标为q的字符赋给字符数组b[]
152 q = 2 * n - 1;//初始化q为根结点的下标
153 //继续译下一个字符的时候从哈夫曼树的根结点开始
154 }
155 }
156 /*译码完成之后，用来记录译出字符的数组由于没有结束符输出的
157 时候回报错，故紧接着把一个结束符加到数组最后*/
158 b[k] = '\0';
159 }
160 //菜单函数
161 void menu()
162 {
163 cout << endl;
164 cout << " ┏〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓┓" << endl;
165 cout << " ┃ ★★★★★★★哈夫曼编码与译码★★★★★★★ ┃" << endl;
166 cout << " ┃ 1. 创建哈夫曼树 ┃" << endl;
167 cout << " ┃ 2. 进行哈夫曼编码 ┃" << endl;
168 cout << " ┃ 3. 进行哈夫曼译码 ┃" << endl;
169 cout << " ┃ 4. 退出程序 ┃" << endl;
170 cout << " ┗〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓┛" << endl;
171 cout << " <><注意：空格字符用'- '代替><>" << endl;
172 cout << endl;
173 }
174 void main()
175 {
176 int falg;//记录要编码的字符个数
177 char a[MAX_MA];//储存输入的二进制字符
178 char b[MAX_ZF];//存储译出的字符
179 char zf[MAX_ZF];//储存要编码的字符
180 HuffmanTree HT = NULL;//初始化树为空数
181 HuffmanCode HC = NULL;//初始化编码表为空表
182 menu();
183 while (true)
184 {
185 int num;
186 cout << "<><请选择功能(1-创建 2-编码 3-译码 4-退出)><>: ";
187 cin >> num;
188 switch (num)
189 {
190 case 1 :
191 cout << "<><请输入字符个数><>:";
192 cin >> falg;
193 //动态申请falg个长度的字符数组，用来存储要编码的字符
194 /*char zf = new char[falg];/
195 cout << "<><请依次输入" << falg << "个字符:><>: ";
196 for (int i = 1; i <= falg; i++)
197 cin >> zf[i];
198 cout << "<><请依次输入" << falg << "个字符的权值><>: ";
199 CreateHuffmanTree(HT, falg);//调用创建哈夫曼树的函数
200 cout << endl;
201 cout << "<><创建哈夫曼成功！,下面是该哈夫曼树的参数输出><>：" << endl;
202 cout << endl;
203 cout << "结点i"<<"\t"<<"字符" << "\t" << "权值" << "\t" << "双亲" << "\t" << "左孩子" << "\t" << "右孩子" << endl;
204 for (int i = 1; i <= falg * 2 - 1; i++)
205 {
206 cout << i << "\t"< 207 }
208 cout 209 break;
210 case 2:
211 CreatHuffmanCode(HT, HC, falg);//调用创建哈夫曼编码表的函数
212 cout 213 cout <生成哈夫曼编码表成功！,下面是该编码表的输出><>：" << endl;
214 cout << endl;
215 cout << "结点i"<<"\t"<<"字符" << "\t" << "权值" << "\t" << "编码" << endl;
216 for (int i = 1; i <= falg; i++)
217 {
218 cout << i << "\t"< 219 }
220 cout 221 break;
222 case 3:
223 cout <请输入想要翻译的一串二进制编码><>：";
224 /*这样可以动态的直接输入一串二进制编码，
225 因为这样输入时最后系统会自动加一个结束符*/
226 cin >> a;
227 TranCode(HT, a, zf, b, falg);//调用译码的函数，
228 /*这样可以直接把数组b输出，因为最后有
229 在数组b添加输出时遇到结束符会结束输出*/
230 cout << endl;
231 cout << "<><译码成功！翻译结果为><>：" << b << endl;
232 cout << endl;
233 break;
234 case 4:
235 cout << endl;
236 cout << "<><退出成功！><>" << endl;
237 exit(0);
238 default:
239 break;
240 }
241 }
242
243 //-abcdefghijklmnopqrstuvwxyz
244 //186 64 13 22 32 103 21 15 47 57 1 5 32 20 57 63 15 1 48 51 80 23 8 18 1 16 1
245 //000101010111101111001111110001100100101011110110
246
247 }