哈夫曼编码问题

看清之后才看轻

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. #define n 7
   
5. #define m 2 * n - 1
   
6. #define maxval 100.0 //令maxval为最大值
   
7. typedef struct
   
8. {
   
9.     float weight;
   
10.     int parent, lchild, rchild;
    
11. } hufmtree;
    
12. typedef struct
    
13. {
    
14.     char bits[n];
    
15.     int start;
    
16.     char ch;
    
17. } Codetype;
    
18. Codetype code[n];
    
19. hufmtree tree[2 * n - 1];
    
20. void Huffman(hufmtree tree[])
    
21. {
    
22.     int i, j, p1, p2;
    
23.     float small1, small2, f;
    
24.     for (i = 0; i < m; i++)
    
25.     {
    
26.         tree[i].parent = 0; //初始化数组
    
27.         tree[i].lchild = 0;
    
28.         tree[i].rchild = 0;
    
29.         tree[i].weight = 0.0;
    
30.     }
    
31.     printf("Input every character's weight!\n");
    
32.     for (i = 0; i < n; i++)
    
33.     {
    
34.         scanf("%f", &f);
    
35.         tree[i].weight = f;
    
36.     }
    
37.     for (i = n; i < m; i++)
    
38.     {
    
39.         p1 = p2 = 0;
    
40.         small1 = small2 = maxval;
    
41.         for (j = 0; j <= i - 1; j++)
    
42.         {
    
43.             if (tree[j].parent == 0)
    
44.                 if (tree[j].weight < small1)
    
45.                 {
    
46.                     small2 = small1;
    
47.                     small1 = tree[j].weight;
    
48.                     p2 = p1;
    
49.                     p1 = j;
    
50.                     // printf("%d#",p1);
    
51.                 }
    
52.                 else if (tree[j].weight < small2)
    
53.                 { //查找次小权，并用p2记录下标
    
54.                     small2 = tree[j].weight;
    
55.                     p2 = j;
    
56.                     // printf("%d#",p2);
    
57.                 }
    
58.             tree[p1].parent = tree[p2].parent = i;
    
59.             tree[i].weight = tree[p1].weight + tree[p2].weight;
    
60.             tree[i].lchild = p1;
    
61.             tree[i].rchild = p2;
    
62.         }
    
63.     }
    
64. }
    
65. void HuffmanCode(hufmtree tree[])
    
66. {
    
67.     int i, j, p;
    
68.     for (i = 0; i < n; i++)
    
69.     {
    
70.         code[i].start = n - 1;
    
71.         j = i;
    
72.         p = tree[i].parent;
    
73.         while (p != 0)
    
74.         {
    
75.             // printf("%d %d#\n",i,j);
    
76.             if (tree[p].lchild == j)
    
77.                 code[i].bits[code[i].start] = '0';
    
78.             else
    
79.                 code[i].bits[code[i].start] = '1';
    
80.             code[i].start--;
    
81.             j = p;
    
82.             p = tree[p].parent;
    
83.         }
    
84.     }
    
85. }
    
86. void print_prefix_code(Codetype code[])
    
87. {
    
88.     for (int i = 0; i < n ; i++)
    
89.     {
    
90.         printf("%c's prefix code is ", code[i].ch);
    
91.         for (int j = 0; j < n; j++)
    
92.         {
    
93.             printf("%c", code[i].bits[j]);
    
94.         }
    
95.         printf("\n");
    
96.     }
    
97. }
    
98. int main()
    
99. {
    
100.     printf("Input code character!Maxsize is 7.\n");
     
101.     for (int i = 0; i < n; i++)
     
102.     {
     
103.         scanf("%c", &code[i].ch);
     
104.     }
     
105.     Huffman(tree);
     
106.     HuffmanCode(tree);
     
107.     // for (int i = 0; i < n; i++)
     
108.     // {
     
109.     //     printf("%f ",tree[i].weight);
     
110.     // }
     
111.     print_prefix_code(code);
     
112. 
     
113.     return 0;
     
114. }

复制代码

请问这个代码为什么输入ABCDEFG和0.40 0.30 0.15 0.05 0.04 0.03 0.03输出的编码不是唯一的？

Gacy

数据结构 上学期的 学得人麻了

阿萨德按时

伽羅~

心驰神往

顶

100gram

顶

新手入场

1