[已解决]该贴无效，请删除

小纸张二号

设字符集为10个字符，其出现频度如下表所示。先建哈夫曼树，输出对应字符的译码，再利用此树对报文“ADEC”进行编码和译码，输出对应
字符        A        B        C        D        E        F        G        H        I        J
频度        24     20        1        7        9        11        8        15    2        3

最佳答案

月排行榜 / 总排行榜

Croper

2019-12-20 20:19:58

1. //vs的调试功能太好用，我是在vs里写的代码，但其不支持C语言的部分功能,例如变长数组，例如直接使用strlen（即使在C环境下） \
   
2. 所以使用宏定义#ifdef __cplusplus确保程序在传统C环境下也能运行；
   
3. 
   
4. //不使用数组代替二叉树，因为霍夫曼树可能非常“不完全”，其使用数组代替时占用空间可能过大；
   
5. 
   
6. #ifdef __cplusplus
   
7. #define _CRT_SECURE_NO_WARNINGS
   
8. #include <iostream>
   
9. #include <malloc.h>
   
10. #include <memory.h>
    
11. #include <string.h>
    
12. #endif
    
13. #include <stdio.h>
    
14. 
    
15. #define _Out_
    
16. #ifndef NULL
    
17. #define NULL 0
    
18. #endif
    
19. 
    
20. typedef char string[128];  //单个字符编码长度不超过128；
    
21. 
    
22. //霍夫曼书的节点
    
23. typedef struct node_t {   
    
24.         struct node_t* left;
    
25.         struct node_t* right;
    
26.         struct node_t* parent;
    
27.         int freq;
    
28.         char code;
    
29. }node;
    
30. 
    
31. 
    
32. //删除树
    
33. void DestroyTree(node* root) {
    
34.         if (!root) return;
    
35.         DestroyTree(root->left);
    
36.         DestroyTree(root->right);
    
37.         free(root);
    
38. };
    
39. 
    
40. 
    
41. //生成编码
    
42. string* generateHuffmanCode(char ch[], int freq[], int N, string _Out_ *codelist) {
    
43.         int i, j, k;
    
44. 
    
45. #ifdef __cplusplus
    
46.         node *pool[128], *pool_backup[128];  //c++环境下不支持变长数组；
    
47. #else
    
48.         node *pool[N], *pool_backup[N];
    
49. #endif
    
50. 
    
51.         //为每个字符创建节点
    
52.         for (i = 0; i < N; ++i) {
    
53.                 pool[i] = (node*)malloc(sizeof(node));
    
54.                 pool[i]->freq = freq[i];
    
55.                 pool[i]->left = NULL;
    
56.                 pool[i]->right = NULL;
    
57.                 pool[i]->parent = NULL;
    
58.         }
    
59.         //做一个备份
    
60.         memcpy(pool_backup, pool, sizeof(pool));
    
61. 
    
62.         //每次选取两个节点组合，共需组合N-1次
    
63.         for (i = 0; i < N - 1; ++i) {
    
64.                 int min_freq[2]; //频次最低的两个节点的编号
    
65.                 memset(min_freq, -1, sizeof(min_freq));
    
66.                 for (j = 0; j < N - i; ++j) {
    
67.                         if (min_freq[0] == -1 || pool[j]->freq < pool[min_freq[0]]->freq) {
    
68.                                 min_freq[1] = min_freq[0];
    
69.                                 min_freq[0] = j;
    
70.                         }
    
71.                         else if (min_freq[1] == -1 || pool[j]->freq < pool[min_freq[1]]->freq) {
    
72.                                 min_freq[1] = j;
    
73.                         }
    
74.                 }
    
75. 
    
76.                 //组合两个节点，新节点的频次是两个子节点之和
    
77.                 node* sum = (node*)malloc(sizeof(node));
    
78.                 sum->left = pool[min_freq[0]];
    
79.                 sum->right = pool[min_freq[1]];
    
80.                 sum->parent = NULL;
    
81. 
    
82.                 sum->left->code = '0';
    
83.                 sum->right->code = '1';
    
84.                 sum->left->parent = sum;
    
85.                 sum->right->parent = sum;
    
86.                 sum->freq = sum->left->freq + sum->right->freq;
    
87. 
    
88.                 //于节点池中，用新节点代替原有子节点，并移除另一个子节点
    
89.                 pool[min_freq[0]] = sum;
    
90.                 for (j = min_freq[1]; j + 1 < N - i; ++j) {
    
91.                         pool[j] = pool[j + 1];
    
92.                 }
    
93.         }
    
94.         //霍夫曼树生成完毕
    
95. 
    
96.        
    
97.         pool[0]->code = 0;
    
98.         for (i = 0; i < 128; ++i) {
    
99.                 codelist[i][0] = 0;
    
100.         }
     
101.         //对于每一个字符对应的节点（即叶节点），向上搜寻直到根节点，路径即为颠倒的编码；
     
102.         for (i = 0; i < N; ++i) {
     
103.                 node* p = pool_backup[i];
     
104.                 char *line = codelist[ch[i]];
     
105.                 for (j = 0; p != NULL; ++j, p = p->parent) {
     
106.                         line[j] = p->code;
     
107.                 }
     
108.                 j--;
     
109. 
     
110.                 //再将颠倒的编码回正
     
111.                 for (k = 0; k < j / 2; ++k) {
     
112.                         char t = codelist[ch[i]][k];
     
113.                         line[k] = line[j - 1 - k];
     
114.                         line[j - 1 - k] = t;
     
115.                 }
     
116.         }
     
117. 
     
118.         //删除霍夫曼树，释放空间
     
119.         DestroyTree(pool[0]);
     
120. 
     
121.         return codelist;
     
122. }
     
123. 
     
124. //根据编码表编码字符串
     
125. char* encode(char* sz, string codelist[], char* _Out_ szEncoded) {
     
126.         char* p = szEncoded;
     
127.         while (*sz) {
     
128.                 int l = strlen(codelist[*sz]);
     
129.                 strcpy(p, codelist[*sz]);
     
130.                 p += l;
     
131.                 sz++;
     
132.         }
     
133.         return szEncoded;
     
134. }
     
135. 
     
136. //解码字符串
     
137. char* decode(char* szEncoded, string codelist[], char* _Out_ szDecoded) {
     
138.         int i, j;
     
139. 
     
140.         //根据编码表重新生成树
     
141.         node* root = (node*)malloc(sizeof(node));
     
142.         root->left = NULL;
     
143.         root->right = NULL;
     
144.         for (i = 0; i < 128; ++i) {
     
145.                 node* p;
     
146.                 char* pch;
     
147.                 for (p = root, pch = codelist[i]; *pch != 0; ++pch) {
     
148.                         if (*pch == '0') {
     
149.                                 if (p->left == NULL) {
     
150.                                         p->left = (node*)malloc(sizeof(node));
     
151.                                         p->left->left = NULL;
     
152.                                         p->left->right = NULL;
     
153.                                 }
     
154.                                 p = p->left;
     
155.                         }
     
156.                         else if (*pch == '1') {
     
157.                                 if (p->right == NULL) {
     
158.                                         p->right = (node*)malloc(sizeof(node));
     
159.                                         p->right->left = NULL;
     
160.                                         p->right->right = NULL;
     
161.                                 }
     
162.                                 p = p->right;
     
163.                         }
     
164.                 }
     
165.                 p->code = i;
     
166.         }
     
167. 
     
168. 
     
169.         //根据编码的0或1，进入当前节点的左子树或右子树，直到到达叶节点，并记录
     
170.         char* pch, *pret;
     
171.         node* p;
     
172.         for (p = root, pch = szEncoded, pret = szDecoded; *pch != 0; ++pch) {
     
173.                 if (*pch == '0') {
     
174.                         p = p->left;
     
175.                 }
     
176.                 else {
     
177.                         p = p->right;
     
178.                 }
     
179.                 if (p->left == NULL) {
     
180.                         *pret++ = p->code;
     
181.                         p = root;
     
182.                 }
     
183.         }
     
184. 
     
185.         //删除树，释放空间
     
186.         DestroyTree(root);
     
187.         *pret = '\0';
     
188.         return szDecoded;
     
189. }
     
190. 
     
191. int main() {
     
192.         string codelist[128];
     
193.         char sz[] = { 'A','B','C','D','E','F','G','H','I','J'};
     
194.         int freq[] = { 24,20,1,7,9,11,8,15,2,3};
     
195. 
     
196.         generateHuffmanCode(sz, freq, sizeof(sz), codelist);
     
197. 
     
198.         printf("========编码表================\n");
     
199.         unsigned char c;
     
200.         for (c = 0; c < 128; ++c) {
     
201.                 if (codelist[c][0] == 0) continue;
     
202.                 printf("%c:%s\n", c, codelist[c]);
     
203.         }
     
204. 
     
205.         char a[] = "ADEC";
     
206.         char code[1024];
     
207.         char b[10];
     
208.         encode(a, codelist, code);
     
209.         decode(code, codelist, b);
     
210.         printf("===================================\n");
     
211.         printf("%s 的编码结果为%s\n", a, code);
     
212.         printf("%s 的解码结果为%s\n", code, b);
     
213. #ifdef __cplusplus
     
214.         system("pause");
     
215. #endif
     
216. }

复制代码

跳转到最佳答案楼层

Croper

1. //vs的调试功能太好用，我是在vs里写的代码，但其不支持C语言的部分功能,例如变长数组，例如直接使用strlen（即使在C环境下） \
   
2. 所以使用宏定义#ifdef __cplusplus确保程序在传统C环境下也能运行；
   
3. 
   
4. //不使用数组代替二叉树，因为霍夫曼树可能非常“不完全”，其使用数组代替时占用空间可能过大；
   
5. 
   
6. #ifdef __cplusplus
   
7. #define _CRT_SECURE_NO_WARNINGS
   
8. #include <iostream>
   
9. #include <malloc.h>
   
10. #include <memory.h>
    
11. #include <string.h>
    
12. #endif
    
13. #include <stdio.h>
    
14. 
    
15. #define _Out_
    
16. #ifndef NULL
    
17. #define NULL 0
    
18. #endif
    
19. 
    
20. typedef char string[128];  //单个字符编码长度不超过128；
    
21. 
    
22. //霍夫曼书的节点
    
23. typedef struct node_t {   
    
24.         struct node_t* left;
    
25.         struct node_t* right;
    
26.         struct node_t* parent;
    
27.         int freq;
    
28.         char code;
    
29. }node;
    
30. 
    
31. 
    
32. //删除树
    
33. void DestroyTree(node* root) {
    
34.         if (!root) return;
    
35.         DestroyTree(root->left);
    
36.         DestroyTree(root->right);
    
37.         free(root);
    
38. };
    
39. 
    
40. 
    
41. //生成编码
    
42. string* generateHuffmanCode(char ch[], int freq[], int N, string _Out_ *codelist) {
    
43.         int i, j, k;
    
44. 
    
45. #ifdef __cplusplus
    
46.         node *pool[128], *pool_backup[128];  //c++环境下不支持变长数组；
    
47. #else
    
48.         node *pool[N], *pool_backup[N];
    
49. #endif
    
50. 
    
51.         //为每个字符创建节点
    
52.         for (i = 0; i < N; ++i) {
    
53.                 pool[i] = (node*)malloc(sizeof(node));
    
54.                 pool[i]->freq = freq[i];
    
55.                 pool[i]->left = NULL;
    
56.                 pool[i]->right = NULL;
    
57.                 pool[i]->parent = NULL;
    
58.         }
    
59.         //做一个备份
    
60.         memcpy(pool_backup, pool, sizeof(pool));
    
61. 
    
62.         //每次选取两个节点组合，共需组合N-1次
    
63.         for (i = 0; i < N - 1; ++i) {
    
64.                 int min_freq[2]; //频次最低的两个节点的编号
    
65.                 memset(min_freq, -1, sizeof(min_freq));
    
66.                 for (j = 0; j < N - i; ++j) {
    
67.                         if (min_freq[0] == -1 || pool[j]->freq < pool[min_freq[0]]->freq) {
    
68.                                 min_freq[1] = min_freq[0];
    
69.                                 min_freq[0] = j;
    
70.                         }
    
71.                         else if (min_freq[1] == -1 || pool[j]->freq < pool[min_freq[1]]->freq) {
    
72.                                 min_freq[1] = j;
    
73.                         }
    
74.                 }
    
75. 
    
76.                 //组合两个节点，新节点的频次是两个子节点之和
    
77.                 node* sum = (node*)malloc(sizeof(node));
    
78.                 sum->left = pool[min_freq[0]];
    
79.                 sum->right = pool[min_freq[1]];
    
80.                 sum->parent = NULL;
    
81. 
    
82.                 sum->left->code = '0';
    
83.                 sum->right->code = '1';
    
84.                 sum->left->parent = sum;
    
85.                 sum->right->parent = sum;
    
86.                 sum->freq = sum->left->freq + sum->right->freq;
    
87. 
    
88.                 //于节点池中，用新节点代替原有子节点，并移除另一个子节点
    
89.                 pool[min_freq[0]] = sum;
    
90.                 for (j = min_freq[1]; j + 1 < N - i; ++j) {
    
91.                         pool[j] = pool[j + 1];
    
92.                 }
    
93.         }
    
94.         //霍夫曼树生成完毕
    
95. 
    
96.        
    
97.         pool[0]->code = 0;
    
98.         for (i = 0; i < 128; ++i) {
    
99.                 codelist[i][0] = 0;
    
100.         }
     
101.         //对于每一个字符对应的节点（即叶节点），向上搜寻直到根节点，路径即为颠倒的编码；
     
102.         for (i = 0; i < N; ++i) {
     
103.                 node* p = pool_backup[i];
     
104.                 char *line = codelist[ch[i]];
     
105.                 for (j = 0; p != NULL; ++j, p = p->parent) {
     
106.                         line[j] = p->code;
     
107.                 }
     
108.                 j--;
     
109. 
     
110.                 //再将颠倒的编码回正
     
111.                 for (k = 0; k < j / 2; ++k) {
     
112.                         char t = codelist[ch[i]][k];
     
113.                         line[k] = line[j - 1 - k];
     
114.                         line[j - 1 - k] = t;
     
115.                 }
     
116.         }
     
117. 
     
118.         //删除霍夫曼树，释放空间
     
119.         DestroyTree(pool[0]);
     
120. 
     
121.         return codelist;
     
122. }
     
123. 
     
124. //根据编码表编码字符串
     
125. char* encode(char* sz, string codelist[], char* _Out_ szEncoded) {
     
126.         char* p = szEncoded;
     
127.         while (*sz) {
     
128.                 int l = strlen(codelist[*sz]);
     
129.                 strcpy(p, codelist[*sz]);
     
130.                 p += l;
     
131.                 sz++;
     
132.         }
     
133.         return szEncoded;
     
134. }
     
135. 
     
136. //解码字符串
     
137. char* decode(char* szEncoded, string codelist[], char* _Out_ szDecoded) {
     
138.         int i, j;
     
139. 
     
140.         //根据编码表重新生成树
     
141.         node* root = (node*)malloc(sizeof(node));
     
142.         root->left = NULL;
     
143.         root->right = NULL;
     
144.         for (i = 0; i < 128; ++i) {
     
145.                 node* p;
     
146.                 char* pch;
     
147.                 for (p = root, pch = codelist[i]; *pch != 0; ++pch) {
     
148.                         if (*pch == '0') {
     
149.                                 if (p->left == NULL) {
     
150.                                         p->left = (node*)malloc(sizeof(node));
     
151.                                         p->left->left = NULL;
     
152.                                         p->left->right = NULL;
     
153.                                 }
     
154.                                 p = p->left;
     
155.                         }
     
156.                         else if (*pch == '1') {
     
157.                                 if (p->right == NULL) {
     
158.                                         p->right = (node*)malloc(sizeof(node));
     
159.                                         p->right->left = NULL;
     
160.                                         p->right->right = NULL;
     
161.                                 }
     
162.                                 p = p->right;
     
163.                         }
     
164.                 }
     
165.                 p->code = i;
     
166.         }
     
167. 
     
168. 
     
169.         //根据编码的0或1，进入当前节点的左子树或右子树，直到到达叶节点，并记录
     
170.         char* pch, *pret;
     
171.         node* p;
     
172.         for (p = root, pch = szEncoded, pret = szDecoded; *pch != 0; ++pch) {
     
173.                 if (*pch == '0') {
     
174.                         p = p->left;
     
175.                 }
     
176.                 else {
     
177.                         p = p->right;
     
178.                 }
     
179.                 if (p->left == NULL) {
     
180.                         *pret++ = p->code;
     
181.                         p = root;
     
182.                 }
     
183.         }
     
184. 
     
185.         //删除树，释放空间
     
186.         DestroyTree(root);
     
187.         *pret = '\0';
     
188.         return szDecoded;
     
189. }
     
190. 
     
191. int main() {
     
192.         string codelist[128];
     
193.         char sz[] = { 'A','B','C','D','E','F','G','H','I','J'};
     
194.         int freq[] = { 24,20,1,7,9,11,8,15,2,3};
     
195. 
     
196.         generateHuffmanCode(sz, freq, sizeof(sz), codelist);
     
197. 
     
198.         printf("========编码表================\n");
     
199.         unsigned char c;
     
200.         for (c = 0; c < 128; ++c) {
     
201.                 if (codelist[c][0] == 0) continue;
     
202.                 printf("%c:%s\n", c, codelist[c]);
     
203.         }
     
204. 
     
205.         char a[] = "ADEC";
     
206.         char code[1024];
     
207.         char b[10];
     
208.         encode(a, codelist, code);
     
209.         decode(code, codelist, b);
     
210.         printf("===================================\n");
     
211.         printf("%s 的编码结果为%s\n", a, code);
     
212.         printf("%s 的解码结果为%s\n", code, b);
     
213. #ifdef __cplusplus
     
214.         system("pause");
     
215. #endif
     
216. }

复制代码