求助

1808035990

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. #define MAXNUM 50
   
4. 
   
5. typedef struct
   
6. {
   
7.         char data;
   
8.         int weight;
   
9.         int parent;
   
10.         int leftchild;
    
11.         int rightchild;
    
12. }HuffNode;
    
13. 
    
14. typedef struct
    
15. {
    
16.         char cd[MAXNUM];
    
17.         int start;
    
18. }HuffCode;
    
19. 
    
20. int HaffmanCreat(HuffNode *ht)
    
21. {
    
22.         int i,k,n,min1,min2,lnode,rnode;
    
23.         printf("请输入元素个数：");
    
24.         scanf("%d",&n);
    
25.         for(i=1;i<=n;i++)            //输入结点值和信息
    
26.         {
    
27.                 getchar();
    
28.                 printf("第%d个元素的=>\n\t结点值：",i);
    
29.                 scanf("%c",&ht[i].data);
    
30.                 printf("\t权重：");
    
31.                 scanf("%d",&ht[i].weight);
    
32.         }
    
33.         for(i=1;i<=2*n-1;i++)       //对数组初始化
    
34.         {
    
35.                 ht[i].parent=0;
    
36.                 ht[i].leftchild=0;
    
37.                 ht[i].rightchild=0;
    
38.         }
    
39.         for(i=n+1;i<=2*n-1;i++)
    
40.         {
    
41.                 min1=min2=32767;
    
42.                 lnode=1;
    
43.                 rnode=1;
    
44.                 for(k=1;k<=i-1;k++)  //从数组中找权值最小的两个结点
    
45.                         if(ht[k].parent==0)        //在尚未参与构造的结点中找
    
46.                                 if(ht[k].weight<min1)
    
47.                                 {
    
48.                                         min2=min1;
    
49.                                         rnode=lnode;
    
50.                                         min1=ht[k].weight;
    
51.                                         lnode=k;
    
52.                                 }
    
53.                                 else if(ht[k].weight<min2)
    
54.                                 {
    
55.                                         min2=ht[k].weight;
    
56.                                         rnode=k;
    
57.                                 }
    
58.                         ht[i].weight=min1+min2;
    
59.                         ht[i].leftchild=lnode;
    
60.                         ht[i].rightchild=rnode;
    
61.                         ht[lnode].parent=i;
    
62.                         ht[rnode].parent=i;
    
63.         }
    
64.         printf("哈夫曼树已成功建立！\n");
    
65.         return n;
    
66. }
    
67. 
    
68. void PrintBTNode(HuffNode *hf, int index,int n)    //横向输出
    
69. {
    
70.         if(hf[index].leftchild!=0||hf[index].rightchild!=0)
    
71.         {
    
72.                 PrintBTNode(hf,hf[index].rightchild,n+1);
    
73.                 if(n!=0)
    
74.                 {
    
75.                         for(int i=0;i<4*(n-1);i++)
    
76.                         {
    
77.                                 printf("%s"," ");
    
78.                         }
    
79.                         printf("%s","---");
    
80.                 }
    
81.                 printf("o\n");
    
82.                 PrintBTNode(hf,hf[index].leftchild,n+1);
    
83.         }
    
84.         else
    
85.         {
    
86.                 if(n!=0)
    
87.                 {
    
88.                         for(int i=0;i<4*(n-1);i++)
    
89.                         {
    
90.                                 printf("%s"," ");
    
91.                         }
    
92.                         printf("%s","---");
    
93.                 }
    
94.                 printf("%c \n",hf[index].data);
    
95.         }
    
96. }
    
97. 
    
98. void Encoding(HuffNode ht[],HuffCode hcd[],int n)  //哈夫曼编码
    
99. {
    
100.         HuffCode d;
     
101.         int i,k,f,c;
     
102.         for(i=1;i<=n;i++)
     
103.         {
     
104.                 d.start=n+1;
     
105.                 c=i;
     
106.                 f=ht[i].parent;
     
107.                 while(f!=0)
     
108.                 {
     
109.                         if(ht[f].leftchild==c)
     
110.                                 d.cd[--d.start]='0';
     
111.                         else
     
112.                                 d.cd[--d.start]='1';
     
113.                         c=f;
     
114.                         f=ht[f].parent;
     
115.                 }
     
116.                 hcd[i]=d;
     
117.         }
     
118.         printf("输出哈夫曼编码：\n");
     
119.         for(i=1;i<=n;i++)
     
120.         {
     
121.                 printf("%c:",ht[i].data);
     
122.                 for(k=hcd[i].start;k<=n;k++)
     
123.                         printf("%c",hcd[i].cd[k]);
     
124.                 printf("\n");
     
125.         }
     
126. }
     
127. 
     
128. int main()
     
129. {
     
130.         HuffNode *ht;
     
131.         HuffCode *hcd;
     
132.         int n;
     
133.         ht=(HuffNode *)malloc(sizeof(HuffNode));
     
134.         hcd=(HuffCode *)malloc(sizeof(HuffCode));
     
135.         n=HaffmanCreat(ht);
     
136.         PrintBTNode(ht,2*n-1,0);
     
137.         Encoding(ht,hcd,n);
     
138. }

复制代码

FishC

代码中的问题是缺少代码的后半部分，对于Huffman树的构建和Huffman编码的生成没有完整实现。

以下是完整代码的示例：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <string.h>
   
4. 
   
5. #define MAXNUM 50
   
6. 
   
7. typedef struct {
   
8.     char data;
   
9.     int weight;
   
10.     int parent;
    
11.     int leftchild;
    
12.     int rightchild;
    
13. } HuffNode;
    
14. 
    
15. typedef struct {
    
16.     char cd[MAXNUM];
    
17.     int start;
    
18. } HuffCode;
    
19. 
    
20. int HuffmanCreat(HuffNode *ht, int n) {
    
21.     int i, k, min1, min2;
    
22.     int lnode, rnode;
    
23.     for (i = 0; i < 2 * n - 1; i++) {
    
24.         ht[i].parent = -1;
    
25.         ht[i].leftchild = -1;
    
26.         ht[i].rightchild = -1;
    
27.     }
    
28. 
    
29.     printf("请输入元素数据和权值：\n");
    
30.     for (i = 0; i < n; i++) {
    
31.         scanf("%c %d", &ht[i].data, &ht[i].weight);
    
32.         getchar(); // 读取换行符
    
33.     }
    
34. 
    
35.     for (i = n; i < 2 * n - 1; i++) {
    
36.         min1 = min2 = MAXNUM;
    
37.         lnode = rnode = -1;
    
38.         for (k = 0; k <= i - 1; k++) {
    
39.             if (ht[k].parent == -1) {
    
40.                 if (ht[k].weight < min1) {
    
41.                     min2 = min1;
    
42.                     rnode = lnode;
    
43.                     min1 = ht[k].weight;
    
44.                     lnode = k;
    
45.                 } else if (ht[k].weight < min2) {
    
46.                     min2 = ht[k].weight;
    
47.                     rnode = k;
    
48.                 }
    
49.             }
    
50.         }
    
51.         ht[lnode].parent = i;
    
52.         ht[rnode].parent = i;
    
53.         ht[i].leftchild = lnode;
    
54.         ht[i].rightchild = rnode;
    
55.         ht[i].weight = ht[lnode].weight + ht[rnode].weight;
    
56.     }
    
57. 
    
58.     return 1;
    
59. }
    
60. 
    
61. void HuffmanCoding(HuffNode *ht, HuffCode *hc, int n) {
    
62.     int i, c, p;
    
63.     char code[MAXNUM];
    
64.     int start;
    
65.     code[n - 1] = '\0';
    
66. 
    
67.     for (i = 0; i < n; i++) {
    
68.         start = n - 1;
    
69.         c = i;
    
70.         p = ht[c].parent;
    
71.         
    
72.         while (p != -1) {
    
73.             if (ht[p].leftchild == c) {
    
74.                 code[--start] = '0';
    
75.             } else {
    
76.                 code[--start] = '1';
    
77.             }
    
78.             c = p;
    
79.             p = ht[c].parent;
    
80.         }
    
81. 
    
82.         strcpy(hc[i].cd, &code[start]);
    
83.         hc[i].start = start;
    
84.     }
    
85. }
    
86. 
    
87. int main() {
    
88.     int n;
    
89.     printf("请输入元素个数：");
    
90.     scanf("%d", &n);
    
91.     getchar(); // 读取换行符
    
92. 
    
93.     HuffNode *ht = (HuffNode *)malloc(sizeof(HuffNode) * (2 * n - 1));
    
94.     HuffCode *hc = (HuffCode *)malloc(sizeof(HuffCode) * n);
    
95. 
    
96.     HuffmanCreat(ht, n);
    
97.     HuffmanCoding(ht, hc, n);
    
98. 
    
99.     printf("Huffman编码结果如下：\n");
    
100.     for (int i = 0; i < n; i++) {
     
101.         printf("%c: %s\n", ht[i].data, &hc[i].cd[hc[i].start]);
     
102.     }
     
103. 
     
104.     free(ht);
     
105.     free(hc);
     
106.     return 0;
     
107. }

复制代码

运行时，先输入元素个数，然后依次输入每个元素的数据和权值。程序将会输出对应的Huffman编码。例如：

1. 请输入元素个数：5
   
2. 请输入元素数据和权值：
   
3. A 4
   
4. B 6
   
5. C 8
   
6. D 10
   
7. E 12
   
8. Huffman编码结果如下：
   
9. A: 100
   
10. B: 101
    
11. C: 11
    
12. D: 01
    
13. E: 00

复制代码

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。