哈夫曼编码是一个通过哈夫曼树进行的一种编码,一般情况下,以字符:‘0’与‘1’表示。编码的实现过程很简单,只要实现哈夫曼树,通过遍历哈夫曼树,这里我们从每一个叶子结点开始向上遍历,如果该结点为父节点的左孩子,则在字符串后面追加“0”,如果为其右孩子,则在字符串后追加“1”。结束条件为没有父节点。然后将字符串倒过来存入结点中。
C++实现代码如下:
1 #include<iostream>
2 #include<string>
3 using namespace std;
4
5 struct Node
6 {
7 double weight;
8 string ch;
9 string code;
10 int lchild, rchild, parent;
11 };
12
13 void Select(Node huffTree[], int *a, int *b, int n)//找权值最小的两个a和b
14 {
15 int i;
16 double weight = 0; //找最小的数
17 for (i = 0; i <n; i++)
18 {
19 if (huffTree[i].parent != -1) //判断节点是否已经选过
20 continue;
21 else
22 {
23 if (weight == 0)
24 {
25 weight = huffTree[i].weight;
26 *a = i;
27 }
28 else
29 {
30 if (huffTree[i].weight < weight)
31 {
32 weight = huffTree[i].weight;
33 *a = i;
34 }
35 }
36 }
37 }
38 weight = 0; //找第二小的数
39 for (i = 0; i < n; i++)
40 {
41 if (huffTree[i].parent != -1 || (i == *a))//排除已选过的数
42 continue;
43 else
44 {
45 if (weight == 0)
46 {
47 weight = huffTree[i].weight;
48 *b = i;
49 }
50 else
51 {
52 if (huffTree[i].weight < weight)
53 {
54 weight = huffTree[i].weight;
55 *b = i;
56 }
57 }
58 }
59 }
60 int temp;
61 if (huffTree[*a].lchild < huffTree[*b].lchild) //小的数放左边
62 {
63 temp = *a;
64 *a = *b;
65 *b = temp;
66 }
67 }
68
69 void Huff_Tree(Node huffTree[], int w[], string ch[], int n)
70 {
71 for (int i = 0; i < 2 * n - 1; i++) //初始过程
72 {
73 huffTree[i].parent = -1;
74 huffTree[i].lchild = -1;
75 huffTree[i].rchild = -1;
76 huffTree[i].code = "";
77 }
78 for (int i = 0; i < n; i++)
79 {
80 huffTree[i].weight = w[i];
81 huffTree[i].ch = ch[i];
82 }
83 for (int k = n; k < 2 * n - 1; k++)
84 {
85 int i1 = 0;
86 int i2 = 0;
87 Select(huffTree, &i1, &i2, k); //将i1,i2节点合成节点k
88 huffTree[i1].parent = k;
89 huffTree[i2].parent = k;
90 huffTree[k].weight = huffTree[i1].weight + huffTree[i2].weight;
91 huffTree[k].lchild = i1;
92 huffTree[k].rchild = i2;
93 }
94 }
95
96 void Huff_Code(Node huffTree[], int n)
97 {
98 int i, j, k;
99 string s = "";
100 for (i = 0; i < n; i++)
101 {
102 s = "";
103 j = i;
104 while (huffTree[j].parent != -1) //从叶子往上找到根节点
105 {
106 k = huffTree[j].parent;
107 if (j == huffTree[k].lchild) //如果是根的左孩子,则记为0
108 {
109 s = s + "0";
110 }
111 else
112 {
113 s = s + "1";
114 }
115 j = huffTree[j].parent;
116 }
117 cout << "字符 " << huffTree[i].ch << " 的编码:";
118 for (int l = s.size() - 1; l >= 0; l--)
119 {
120 cout << s[l];
121 huffTree[i].code += s[l]; //保存编码
122 }
123 cout << endl;
124 }
125 }
126
127 string Huff_Decode(Node huffTree[], int n,string s)
128 {
129 cout << "解码后为:";
130 string temp = "",str="";//保存解码后的字符串
131 for (int i = 0; i < s.size(); i++)
132 {
133 temp = temp + s[i];
134 for (int j = 0; j < n; j++)
135 {
136 if (temp == huffTree[j].code)
137 {
138 str=str+ huffTree[j].ch;
139 temp = "";
140 break;
141 }
142 else if (i == s.size()-1&&j==n-1&&temp!="")//全部遍历后没有
143 {
144 str= "解码错误!";
145 }
146 }
147 }
148 return str;
149 }
150
151 int main()
152 {
153 //编码过程
154 const int n=5;
155 Node huffTree[2 * n];
156 string str[] = { "A", "B", "C", "D", "E"};
157 int w[] = { 30, 30, 5, 20, 15 };
158 Huff_Tree(huffTree, w, str, n);
159 Huff_Code(huffTree, n);
160 //解码过程
161 string s;
162 cout << "输入编码:";
163 cin >> s;
164 cout << Huff_Decode(huffTree, n, s)<< endl;;
165 system("pause");
166 return 0;
167 }
运行结果如下:
更新:更新之后可以任意输入字符,自动算各各字符的权和其编码,加入了mfc界面,文件打包地址:http://pwpan.com/fs/215975716241b65924a5/
原文链接: https://www.cnblogs.com/gyk666/p/6851821.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/253924
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!