最近完成了数据结构课程设计,被分到的题目是《哈夫曼编码和解码》,现在在这篇博文里分享一下自己的成果。
我在设计时,在网上参考了很多老师和前辈的算法和代码,向他们表示感谢!他们的成果给了我很多启示和帮助。另外,自己的成品中也还有很多不完善的地方,欢迎批评指正。
课题:哈夫曼编码与解码 C++代码实现
(1)统计某电文中字符出现的频率(假设电文中只含有大小写英文字母,以及逗号和点号);
(2)把字符出现的频率作为权值建立哈夫曼树,进行哈夫曼编码,并输出每个字符的编码结果;
(3)对电文进行哈夫曼编码;
(4)把电文的哈夫曼编码进行译码,输出对应电文的内容。
1 #include <stdlib.h>
2 #include <stdio.h>
3 #include <malloc.h>
4 #include <string.h>
5 #include <ctype.h>
6 #define MAX 999999 //一个极大值
7 #define NUM 10
8
9 //存储哈夫曼树每个结点
10 typedef struct Node {
11 char ch;
12 int weight; //权值
13 int parent;
14 int lchild,rchild;
15 }HFNode;
16 //存储每个字符及其哈夫曼编码
17 typedef struct {
18 char ch;
19 char code[NUM];
20 }HFCharCode;
21
22 HFNode HT[28*2-1]; //哈夫曼树结构体
23 HFCharCode HCD[28]; //哈夫曼编码结构体
24 int LeafNum; //叶子结点数
25 int NodeNum; //所有结点数
26 char EnterStr[MAX]; //输入的待编码电文
27 char EnterCode[MAX]; //输入的待解码密文
28 char RealStr[MAX]; //密文解码后的电文
29 int AllWeight[28]; //存储所有28个字符的权值
30
31 void Statistics();
32 void CreateHFTree();
33 void SelectMin(int &min1, int &min2);
34 void CreateHFCode();
35 void ReverseStr(char *str);
36 void EncodeStr();
37 void DecodeHFCode();
38
39 int main() {
40 printf("****** 哈夫曼编码与解码 ******\n\n");
41 printf("*** 输入一串字符串 ***\n");
42 scanf("%s", EnterStr);
43 getchar();
44 Statistics();
45 CreateHFTree();
46 CreateHFCode();
47 EncodeStr();
48 printf("\n*** 输入想解码的内容 ***\n");
49 scanf("%s", EnterCode);
50 getchar();
51 DecodeHFCode();
52 return 0;
53 }
54
55 //统计每个字符权值
56 void Statistics() {
57 int len = strlen(EnterStr);
58 for(int i = 0; i <= 27; i++)
59 AllWeight[i] = 0;
60 for(int j = 0; j <= len - 1; j++) {
61 if(isalpha(EnterStr[j])) {
62 EnterStr[j] = tolower(EnterStr[j]);
63 AllWeight[EnterStr[j]-'a']++;
64 }
65 else if((int)EnterStr[j] == 44)
66 AllWeight[26]++;
67 else if((int)EnterStr[j] == 46)
68 AllWeight[27]++;
69 else {
70 printf("\n输入不符合要求!\n\n");
71 exit(-1);
72 }
73 }
74 int i = 0, j = 0;
75 for( ; i <= 25; i++) {
76 if(AllWeight[i] != 0) {
77 HT[j].weight = AllWeight[i];
78 HT[j].ch = i+'a';
79 j++;
80 }
81 }
82 if(AllWeight[i] != 0) {
83 HT[j].weight = AllWeight[i];
84 HT[j].ch = ',';
85 j++;
86 i++;
87 }
88 if(AllWeight[i] != 0) {
89 HT[j].weight = AllWeight[i];
90 HT[j].ch = '.';
91 }
92 printf("\n*** 打印每个字符的权值 ***\n");
93 int n = 0;
94 for(int i = 0; i <= 27; i++) {
95 if(AllWeight[i] != 0) {
96 n++;
97 if(i <= 25)
98 putchar('a'+i);
99 else if(i == 26)
100 printf(",");
101 else
102 printf(".");
103 printf(": %d\n", AllWeight[i]);
104 }
105 }
106 LeafNum = n;
107 NodeNum = 2*LeafNum-1;
108 }
109
110 //构造哈夫曼树
111 void CreateHFTree() {
112 int i;
113 for(i = 0; i <= LeafNum-1; i++) {
114 HT[i].parent = -1;
115 HT[i].lchild = -1;
116 HT[i].rchild = -1;
117 HT[i].weight = HT[i].weight;
118 }
119 for(; i <= NodeNum-1; i++) {
120 HT[i].parent = -1;
121 HT[i].lchild = -1;
122 HT[i].rchild = -1;
123 HT[i].weight = MAX;
124 }
125 int min1, min2;
126 for(i = LeafNum; i <= NodeNum-1; i++) {
127 SelectMin(min1, min2);
128 HT[min1].parent = i;
129 HT[min2].parent = i;
130 HT[i].lchild = min1;
131 HT[i].rchild = min2;
132 HT[i].weight = HT[min1].weight + HT[min2].weight;
133 }
134 // printf("\n*** 打印哈夫曼树 ***\n");
135 // for(int i = 0; i <= NodeNum-1; i++) {
136 // printf("序号:%d 字符:%c 权值:%d 双亲:%d 左孩:%d 右孩:%d\n", i, HT[i].ch, HT[i].weight, HT[i].parent, HT[i].lchild, HT[i].rchild);
137 // }
138 }
139 //找到两个权值最小的二叉树的序号
140 void SelectMin(int &min1, int &min2) {
141 int i = 0;
142 int temp;
143 int wetmin1, wetmin2;
144 while(HT[i].parent != -1)
145 i++;
146 wetmin1 = HT[i].weight;
147 min1 = i;
148 i++;
149 while(HT[i].parent != -1)
150 i++;
151 wetmin2 = HT[i].weight;
152 min2 = i;
153 i++;
154 if(wetmin1 > wetmin2) {
155 temp = wetmin2;
156 wetmin2 = wetmin1;
157 wetmin1 = temp;
158 temp = min2;
159 min2 = min1;
160 min1 = temp;
161 }
162 for(; i <= NodeNum-1; i++) {
163 if(HT[i].weight < wetmin1 && HT[i].parent == -1) {
164 wetmin2 = wetmin1;
165 wetmin1 = HT[i].weight;
166 min2 = min1;
167 min1 = i;
168 } else if(HT[i].weight < wetmin2 && HT[i].parent == -1) {
169 wetmin2 = HT[i].weight;
170 min2 = i;
171 }
172 }
173 }
174
175 //进行哈夫曼编码
176 void CreateHFCode() {
177 int i, j, len;
178 for(i = 0; i <= LeafNum-1; i++) {
179 len = 0;
180 j = i;
181 HCD[i].ch = HT[j].ch;
182 while(HT[j].parent != -1) { //不是根节点
183 if(HT[HT[j].parent].lchild == j) { //是双亲结点的左孩子
184 HCD[i].code[len++] = '0'+0; //加上字符0
185 }else //是右孩子
186 HCD[i].code[len++] = '0'+1; //加上字符1
187 j = HT[j].parent; //往上遍历
188 }
189 HCD[i].code[len] = '\0'; //字符串末尾
190 ReverseStr(HCD[i].code);
191 }
192 printf("\n*** 打印每个字符的编码 ***\n");
193 for(int i = 0; i <= LeafNum-1; i++)
194 printf("%c: %s\n", HT[i].ch, HCD[i].code);
195 }
196 //将一个字符串反转
197 void ReverseStr(char *str) {
198 int i, j;
199 char c;
200 for(i = 0, j = strlen(str)-1; i < j; i++, j--) {
201 c = str[i];
202 str[i] = str[j];
203 str[j] = c;
204 }
205 }
206
207 //哈夫曼编码
208 void EncodeStr() {
209 int len = strlen(EnterStr);
210 printf("\n*** 编码结果 ***\n");
211 for(int i = 0; i <= len-1; i++) {
212 for(int j = 0; j <= LeafNum-1; j++) {
213 if(EnterStr[i] == HCD[j].ch)
214 printf("%s", HCD[j].code);
215 }
216 }
217 printf("\n");
218 }
219
220 //哈夫曼解码
221 void DecodeHFCode() {
222 int k = NodeNum-1; //根结点序号, 开始时一定在最后一个
223 int len = 0, i = 0;
224 while(EnterCode[i]) {
225 if(EnterCode[i] == '0'+0)
226 k = HT[k].lchild;
227 else if(EnterCode[i] == '0'+1)
228 k = HT[k].rchild;
229 else {
230 printf("\n错误! 密文中仅能含有1和0!\n\n");
231 exit(-1);
232 }
233 if(HT[k].lchild == -1 && HT[k].rchild == -1) {
234 RealStr[len++] = HT[k].ch;
235 k = NodeNum-1;
236 }
237 i++;
238 }
239 RealStr[len] = '\0';
240 if(k == NodeNum-1) {
241 printf("\n*** 解码结果 ***\n%s\n\n", RealStr);
242 exit(0);
243 }
244 printf("\n错误! 部分密文无法解密!\n\n");
245 exit(-1);
246 }
原文链接: https://www.cnblogs.com/deepcho/p/huffman-tree-node-code-decode-encode-cpp.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/266214
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!