哈夫曼树

王小二°

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. #include<string.h>
   
4. #define N 30
   
5. #define MAX 2*N-1
   
6. 
   
7. typedef struct HMtree
   
8. {
   
9.         double weight;
   
10.         char s;
    
11.         int parent, rchild, lchild;
    
12. }HMtree,HM[MAX+1];
    
13. 
    
14. void select(HM ht, int x, int* m1, int* m2)//找出森林中全职最小的两个
    
15. {
    
16.         double min1 = 999;
    
17.         double min2 = 999;
    
18.         int j;
    
19.         for (j = 1; j <= x; j++)
    
20.         {
    
21.                 if (ht[j].weight < min1 && ht[j].parent == 0)
    
22.                 {
    
23.                         min1 = ht[j].weight;
    
24.                         *m1 = j;
    
25.                 }
    
26.         }
    
27.         int k;
    
28.         for (k = 1; k <= x; k++)
    
29.         {
    
30.                 if (ht[k].weight < min2 && k != *m1 && ht[k].parent == 0)
    
31.                 {
    
32.                         min2 = ht[k].weight;
    
33.                         *m2 = k;
    
34.                 }
    
35.         }
    
36. }
    
37. 
    
38. //构建哈夫曼树
    
39. void CreatHM(HM ht, int n)
    
40. {
    
41.         int i;
    
42.         for(i=n+1;i<=2*n-1;i++)
    
43.         {
    
44.                 int m1, m2;
    
45.                 select(ht, i - 1, &m1, &m2);
    
46.                 ht[i].weight = ht[m1].weight + ht[m2].weight;
    
47.                 ht[i].lchild = m1;
    
48.                 ht[i].rchild = m2;
    
49.                 ht[i].parent = 0;
    
50.                 ht[m1].parent = i;
    
51.                 ht[m2].parent = i;
    
52.                
    
53.         }
    
54. }
    
55. 
    
56. //哈夫曼编码
    
57. void HMcoding(HM ht, char** hc, int n)
    
58. {
    
59.         char* cd = (char*)malloc(n * sizeof(char));
    
60.         cd[n - 1] = '\0';
    
61.         int now = 1;
    
62.         int p = 0;
    
63.         int start;
    
64.         int i = 0;
    
65.         while (i < n)
    
66.         {
    
67.                 start = n - 1;
    
68.                 now = i + 1;
    
69.                 p = ht[now].parent;
    
70.                 while (p != 0)
    
71.                 {
    
72.                         start--;
    
73.                         if (ht[p].lchild == now)
    
74.                         {
    
75.                                 cd[start] = '0';
    
76.                         }
    
77.                         else {
    
78.                                 cd[start] = '1';
    
79.                         }
    
80.                         now = p;
    
81.                         p = ht[now].parent;
    
82.                        
    
83.                 }
    
84.                 hc[i + 1] = (char*)malloc((n - start) * sizeof(char));
    
85.                 strcpy(hc[i + 1], &cd[start]);
    
86.                 i++;
    
87.         }
    
88.        
    
89. }
    
90. 
    
91. //先序打印
    
92. void dayin(HM ht, char** hc, int index)
    
93. {
    
94.         if (index >= 1)
    
95.         {
    
96.                 if (ht[index].lchild == 0 && ht[index].rchild)
    
97.                 {
    
98.                         printf("%c:%s\n", ht[index].s, hc[index]);
    
99.                         return;
    
100.                        
     
101.                 }
     
102.                 dayin(ht, hc, ht[index].lchild);
     
103.                 dayin(ht, hc, ht[index].rchild);
     
104.         }
     
105. }
     
106. 
     
107. //在生成的树里查找目标
     
108. void chaHM(HM ht, int n,char* pwd)
     
109. {
     
110.         printf("original:");
     
111.         int len = strlen(pwd);
     
112.         int i = 0;
     
113.         int node = 2 * n - 1;
     
114.         while (i < len)
     
115.         {
     
116.                 if (pwd[i] == '0')
     
117.                 {
     
118.                         node = ht[node].lchild;
     
119.                         i++;
     
120.                         if (ht[node].lchild == 0 && ht[node].rchild == 0)
     
121.                         {
     
122.                                 printf("%c", ht[node].s);
     
123.                                 node = 2 * n - 1;
     
124.                         }
     
125.                 }
     
126.                 if (pwd[i] == '1')
     
127.                 {
     
128.                         node = ht[node].rchild;
     
129.                         i++;
     
130.                         if (ht[node].lchild == 0 && ht[node].rchild == 0)
     
131.                         {
     
132.                                 printf("%c", ht[node].s);
     
133.                                 node = 2 * n - 1;
     
134.                         }
     
135.                 }
     
136.         }
     
137. }
     
138. 
     
139. int main()
     
140. {
     
141.         HM ht;
     
142.         int n;//字符个数
     
143.         scanf("%d", &n);
     
144.         getchar();
     
145.         char* hc[4 + 1];
     
146.         int i;
     
147.         for (i = 1; i <= n; i++)
     
148.         {
     
149.                 scanf("%c%lf", &ht[i].s, &ht[i].weight);
     
150.                 getchar();
     
151.                 ht[i].lchild = 0;
     
152.                 ht[i].rchild = 0;
     
153.                 ht[i].parent = 0;
     
154.                
     
155.         }
     
156.         char pwd[99];
     
157.         scanf("%s", pwd);
     
158.         CreatHM(ht, n);
     
159.         HMcoding(ht,hc,n);
     
160.         dayin(ht, hc, 2 * n - 1);
     
161.         chaHM(ht, n, pwd);
     
162. }

复制代码

我的问题是为什么没有对应每个字符的编码的输出，是函数哪里出问题了吗？

小甲鱼的二师兄

主要问题出在 dayin 函数的实现中。

在判断叶子节点时存在逻辑错误，导致没有正确打印字符的编码。

修复后的完整代码如下：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <string.h>
   
4. #define N 30
   
5. #define MAX 2 * N - 1
   
6. 
   
7. typedef struct HMtree {
   
8.     double weight;
   
9.     char s;
   
10.     int parent, rchild, lchild;
    
11. } HMtree, HM[MAX + 1];
    
12. 
    
13. void selectMin(HM ht, int x, int* m1, int* m2) {
    
14.     double min1 = 999;
    
15.     double min2 = 999;
    
16.     int j;
    
17.     for (j = 1; j <= x; j++) {
    
18.         if (ht[j].weight < min1 && ht[j].parent == 0) {
    
19.             min1 = ht[j].weight;
    
20.             *m1 = j;
    
21.         }
    
22.     }
    
23.     int k;
    
24.     for (k = 1; k <= x; k++) {
    
25.         if (ht[k].weight < min2 && k != *m1 && ht[k].parent == 0) {
    
26.             min2 = ht[k].weight;
    
27.             *m2 = k;
    
28.         }
    
29.     }
    
30. }
    
31. 
    
32. // 构建哈夫曼树
    
33. void CreatHM(HM ht, int n) {
    
34.     int i;
    
35.     for (i = n + 1; i <= 2 * n - 1; i++) {
    
36.         int m1, m2;
    
37.         selectMin(ht, i - 1, &m1, &m2);
    
38.         ht[i].weight = ht[m1].weight + ht[m2].weight;
    
39.         ht[i].lchild = m1;
    
40.         ht[i].rchild = m2;
    
41.         ht[i].parent = 0;
    
42.         ht[m1].parent = i;
    
43.         ht[m2].parent = i;
    
44.     }
    
45. }
    
46. 
    
47. // 哈夫曼编码
    
48. void HMcoding(HM ht, char** hc, int n) {
    
49.     char* cd = (char*)malloc(n * sizeof(char));
    
50.     cd[n - 1] = '\0';
    
51.     int now = 1;
    
52.     int p = 0;
    
53.     int start;
    
54.     int i = 0;
    
55.     while (i < n) {
    
56.         start = n - 1;
    
57.         now = i + 1;
    
58.         p = ht[now].parent;
    
59.         while (p != 0) {
    
60.             start--;
    
61.             if (ht[p].lchild == now) {
    
62.                 cd[start] = '0';
    
63.             } else {
    
64.                 cd[start] = '1';
    
65.             }
    
66.             now = p;
    
67.             p = ht[now].parent;
    
68.         }
    
69.         hc[i] = (char*)malloc((n - start + 1) * sizeof(char)); // 改为从 0 开始
    
70.         strcpy(hc[i], &cd[start]);
    
71.         i++;
    
72.     }
    
73.     free(cd);
    
74. }
    
75. 
    
76. // 先序打印
    
77. void dayin(HM ht, char** hc, int index) {
    
78.     if (index >= 1) {
    
79.         if (ht[index].lchild == 0 && ht[index].rchild == 0) { // 叶子节点
    
80.             printf("%c:%s\n", ht[index].s, hc[index - 1]); // 索引从 0 开始
    
81.             return;
    
82.         }
    
83.         // 遍历左子树
    
84.         dayin(ht, hc, ht[index].lchild);
    
85.         // 遍历右子树
    
86.         dayin(ht, hc, ht[index].rchild);
    
87.     }
    
88. }
    
89. 
    
90. // 在生成的树里查找目标
    
91. void chaHM(HM ht, int n, char* pwd) {
    
92.     printf("original:");
    
93.     int len = strlen(pwd);
    
94.     int i = 0;
    
95.     int node = 2 * n - 1;
    
96.     while (i < len) {
    
97.         if (pwd[i] == '0') {
    
98.             node = ht[node].lchild;
    
99.             i++;
    
100.             if (ht[node].lchild == 0 && ht[node].rchild == 0) { // 到达叶子节点
     
101.                 printf("%c", ht[node].s);
     
102.                 node = 2 * n - 1;
     
103.             }
     
104.         } else if (pwd[i] == '1') {
     
105.             node = ht[node].rchild;
     
106.             i++;
     
107.             if (ht[node].lchild == 0 && ht[node].rchild == 0) { // 到达叶子节点
     
108.                 printf("%c", ht[node].s);
     
109.                 node = 2 * n - 1;
     
110.             }
     
111.         } else { // 非法输入
     
112.             printf("\nError: Invalid character in encoded string.\n");
     
113.             return;
     
114.         }
     
115.     }
     
116.     printf("\n");
     
117. }
     
118. 
     
119. int main() {
     
120.     HM ht;
     
121.     int n; // 字符个数
     
122.     printf("Enter the number of characters:\n");
     
123.     scanf("%d", &n);
     
124.     getchar();
     
125.     char* hc[N]; // 动态调整大小，索引从 0 开始
     
126.     int i;
     
127.     printf("Enter characters and their weights (format: <char> <weight>):\n");
     
128.     for (i = 1; i <= n; i++) {
     
129.         scanf("%c %lf", &ht[i].s, &ht[i].weight);
     
130.         getchar();
     
131.         ht[i].lchild = 0;
     
132.         ht[i].rchild = 0;
     
133.         ht[i].parent = 0;
     
134.     }
     
135.     char pwd[99];
     
136.     printf("Enter the encoded string:\n");
     
137.     scanf("%s", pwd);
     
138.     CreatHM(ht, n);
     
139.     HMcoding(ht, hc, n);
     
140.     printf("Huffman Codes:\n");
     
141.     dayin(ht, hc, 2 * n - 1);
     
142.     chaHM(ht, n, pwd);
     
143.     // 释放动态分配的内存
     
144.     for (i = 0; i < n; i++) {
     
145.         free(hc[i]);
     
146.     }
     
147.     return 0;
     
148. }

复制代码

很cool的阳

您的代码中存在几个问题，可能导致没有对应每个字符的编码输出。以下是我发现的一些问题和相应的解决方案：

1. **`HMcoding`函数中的内存分配问题**：
   在`HMcoding`函数中，您为`cd`分配了`n * sizeof(char)`大小的内存，但实际需要的内存应该是`n + 1`，因为字符串的结尾需要一个空字符`'\0'`。

   ```c
   char* cd = (char*)malloc((n + 1) * sizeof(char)); // 修改这里
   ```

2. **`HMcoding`函数中的字符串复制问题**：
   在复制编码到`hc[i + 1]`时，您应该使用`strncpy`来确保正确复制字符串，并且要设置目标字符串的结束符。

   ```c
   strncpy(hc[i + 1], &cd[start], n - start);
   hc[i + 1][n - start] = '\0'; // 确保字符串正确结束
   ```

3. **`HMcoding`函数中的逻辑问题**：
   您的`HMcoding`函数逻辑似乎有误。您应该从叶子节点开始构建编码，而不是从根节点开始。此外，您需要为每个字符分配一个编码，而不是只分配一个。

4. **`dayin`函数的实现问题**：
   您的`dayin`函数似乎是想实现先序遍历打印哈夫曼树，但是实现有误。您需要一个递归函数来正确地打印每个节点的值和对应的编码。

5. **`chaHM`函数中的逻辑问题**：
   在`chaHM`函数中，当找到叶子节点时，您应该继续打印字符，直到遍历完整个密码串。

6. **`main`函数中的`hc`数组初始化问题**：
   您需要为`hc`数组的每个元素分配足够的内存，以存储可能的最长编码。

7. **`main`函数中的输入问题**：
   在读取字符和权重后，您使用了`getchar()`来消耗换行符，这在某些情况下可能会导致问题。确保输入格式正确，并且`getchar()`的使用是恰当的。

8. **编码的打印**：
   您需要在构建完哈夫曼树和编码后，打印出每个字符对应的编码。